るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

AOJ 1016 Fibonacci Sets

AOJ

[問題文] AIZU ONLINE JUDGE [解法] dp + UF木 数列を作っておいて、UF木で集合を作る。 int par[2000]; int rank[2000]; void init(int n){ rep(i,n) par[i] = i; memset(rank,0,sizeof(rank)); } int find(int x){ if(par[x] == x) return x; return par[x…

Googleに行ってきました

先日部で、2泊3日の東京遠征に行ってきました。 1日目は秋葉原、2日目は発表練習、そして3日目はGoogle社に訪問させていただきました。Google社では社内食堂で、かの有名な『Binary Hacks』の著者の方とお食事、お話させていただいた後、エンジニアの方々の…

SRM 554 Div2

250 TheBrickTowerEasyDivTwo並べるだけ class TheBrickTowerEasyDivTwo { public: int find(int redCount, int redHeight, int blueCount, int blueHeight) { int now_h = 0; int C[2] = {blueCount,redCount}; int H[2] = {blueHeight,redHeight}; memset(…

PKU 1651 Multiplication Puzzle

PKU

1651 -- Multiplication Puzzle [問題] N枚のカードが与えられる。これらの中から任意の1枚を取り除く。この際、選んだカード * 左のカード * 右のカードのスコアが加算される。ただし両端のカードは選べない。 可能な限りこれらの操作を繰り返した時の合計…

PKU 1611 The Suspects

PKU

1611 -- The Suspects [問題] いくつかのグループとそこに所属する生徒のメンバーの情報が与えられる。0番の生徒が強力な風邪菌(意訳)を持っていて、同じグループに所属している生徒に感染してしまう。感染は推移的であり、例えば aグループ と bグループ両…

PKU 1564 Sum It Up

PKU

1564 -- Sum It Up [問題] N個の要素からなる集合が与えられます。合計がtとなる任意の部分集合をdecreasing orderで出力してください。(例) Input: t = 400 N = 12 [50 50 50 50 50 50 25 25 25 25 25 25]Output: Sums of 400: 50+50+50+50+50+50+25+25+25+…

PKU 3671 Dining Cows

PKU

3671 -- Dining Cows [問題] 1または2がランダムにN個並んでいる。任意の箇所を1 -> 2 もしくは 2 -> 1と書き換えることで、全ての1が2より前に来るようにしたい。 書き換える回数の最小値を求めよ。 [解法]1グループと2グループをどこで分けるかで全探索。…

PKU 2186 Popular Cows

PKU

2186 -- Popular Cows [問題] M個のペア(A,B): 牛Aが牛Bを人気者だと思っている が与えられる。ただし (A,B) ,(B,C) => (A,C) とする。(関係は推移的) 自分以外の全ての牛から人気者だと思われている牛の数を求めよ ずっと放置していた蟻本の問題。 すべての…

PKU 2140 Herd Sums

PKU

問題文→ 2140 -- Herd Sums[問題] 自然数Nが与えられる。 Nを連続した自然数の和で表すと何通りできるか。(例) N = 15 [7+8 , 4+5+6 , 1+2+3+4+5 , 15] 4通り Sum(b) - Sum(a-1) = Sum([a,b]) みたいなことすると O(n^2)とかになって間に合わない。なので S(…

AOJ 0233 Book Arrangement

AOJ

問題文→AIZU ONLINE JUDGE 10進数を-10進数に直す問題。 x mod (-10)^nをやっていく (負になった時は正にしてやる) string Trans(int n){ string ans=""; while(n != 0){ int mod=n%(-10); int nxt=n/(-10); if(mod < 0){ mod+=10; nxt++; } char c='0'+mod;…

AOJ 0531 Paint Color

AOJ

問題文→AIZU ONLINE JUDGEテープが貼ってあるので、囲まれる領域の数を答える問題。 座標圧縮+幅優先でいける。座標圧縮の解説が少なすぎて萎え...一応この問題、第7回JOIの本選5番なのでそこの解説を見れば座標圧縮の大まかな説明が載っている→ 書く量多す…

AOJ 0530 Pyon-Pyon River Crossing

AOJ

問題文→AIZU ONLINE JUDGE正解者数少なかったので、怖くて手をつけていなかった問題。やっと解けたのですごく嬉しいです。メモ化探索しました(ほとんどの方がdpしていたのでそっちの方が良かったかも...) #include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<string> #inc</string></vector></algorithm></cstdio></iostream>…

PKU 3041 Asteroids

PKU

問題文→ 3041 -- AsteroidsN*Nの格子上にK個の小惑星があります。小惑星iの位置は(R[i],C[i])にあります。縦または横一直線上の小惑星をすべて一発のビームで破壊できる強力な武器があり、これを用いてすべての小惑星を破壊するために必要な最小の発射回数を…

PKUの問題をテキストに

ネット復旧したので休憩がてらPythonでスクリプト書いてみました。 PKUの各問題を.txt形式に変換するスクリプトです。 変換する問題の範囲を指定できますが、あまり多くしすぎるとDOS攻撃に近い動きをするので、変換は間を置いて少しずつするようにします。(…

PKU 2104 K-th Number

PKU

問題文→2104 -- K-th Numbersort()とか使うと間に合わないので 区間ごとのx以下の個数を二分探索で数えます。しかし二分探索にはソートが必要なのでマージソートの要領でセグメント木を作っておき、必要な区間に対してのみ二分探索を行えば間に合うみたいで…

AOJ 0131 Doctor's Strange Particles

AOJ

問題文→ AIZU ONLINE JUDGE「あるマスを選んでそこの数字を反転(1 0)させる。 この時そのマスの上下左右も反転する。 すべてを0にするために必要な反転箇所を求めよ」 という問題。普通に考えたら O(2^100)とかで無理。 そこで一番上の行の反転の仕方を一意…

PKU 2385 Apple Catching

問題文→2385 -- Apple Catchingりんごが1分ごとに2本の木のいずれかから落ちてくる。2本の木を決められた回数内行き来して落ちてくるりんごをキャッチする。 キャッチできるりんごの合計の最大値を求めよ。とりあえずメモ化再帰を書いてみる。しかしこれでは…

AOJ 0078 Magic Square

AOJ

問題文→AIZU ONLINE JUDGEマスの数を指定して魔法陣を出力する問題 #include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<string> #include<cmath> #include<map> using namespace std; int context[15][15]; void init(){ for(int i=0;i<15;i++){ for(int j=0;j<15;j++){ context[i][j</map></cmath></string></vector></algorithm></cstdio></iostream>…

フォーマット文字列による攻撃

printf()関数の脆弱性を利用した攻撃手法です。とりあえず以下のコードを見てください。 #include <stdio.h> #include <stdlib.h> #include <string.h> int main(int argc, char *argv[]) { //お客様の名前を表示---- char text[1000]; strcpy(text,argv[1]); printf(text); printf("\n");</string.h></stdlib.h></stdio.h>…

バッファオーバーフロー

競技やったりセキュリティ勉強したりといろいろな分野に手を出しすぎている感は否めませんが、とりあえず今回はセキュリティのことについて書きます。脆弱性としてもっとも基本的なものとして「バッファオーバーフロー」が挙げられます。自分の書いたプログ…

Div2Easy 5連戦

今日は時間があまり無かったので5問だけ解きましたSRM488(Score):231.03そんなに難しくない class TheBoredomDivTwo { public: int find(int n, int m, int j, int b) { int result=n; if(j==b && n

Div2Easy 10連戦

最近TopCoderの成績がひどいので、とりあえずDiv2Easyを確実にとれるようにしようと思ってプラクティスしました。 てことでDiv2Easy 10連戦のソース(プリプロセッサ部分とかもろもろは省略してます)SRM416 map使って解いた class MostCommonLetters { public…

デバッガ実装

デバッガのゆるいやつ書いてみた。「my_debugger_defines.py」 (コピペ) from ctypes import * # Let's map the Microsoft types to ctypes for clarity BYTE = c_ubyte WORD = c_ushort DWORD = c_ulong LPBYTE = POINTER(c_ubyte) LPTSTR = POINTER(c_char…

レジスタ状態の捕捉

初めてのセキュリティ臭あふれるソースコード セキュリティのお勉強の中ではだいたい「Hello World!」にあたるぐらいの最初のコード。やってることはとりあえずWindows上で動いてるプロセスにアタッチしてスレッド列挙して、レジスタ値捕捉してるだけ「my_de…