文字列がいくつか与えられるので全ての文字列に現れる部分文字列の中で最長のものの長さを求めよ。 suffix arrayを使えば良い。共通部分文字列は蟻本に詳しく書いてる。嘘解法だった。隣同士の最長共通部分文字列しか計算してないのに通っていた。 #define I…

問題文 https://icpcarchive.ecs.baylor.edu/external/58/5874.pdf 二部グラフのマッチング。嘘解法だった。本当は一般グラフのマッチングで解くらしい。 #include<iostream> #include<vector> #include<algorithm> #include<set> #define INF 1LL<<62 #define MAX_V 1000 using namespace std;</set></algorithm></vector></iostream>…

問題文 https://icpcarchive.ecs.baylor.edu/external/58/5872.pdf二つの四則演算のみの式a,bが与えられる。a=bであるかどうか判定せよ。 変数の値を乱数で適当に決めて、1000回判定をした。 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cctype> #include<map> using n</map></cctype></string></algorithm></vector></iostream>…

問題文 https://icpcarchive.ecs.baylor.edu/external/41/4130.pdf人の名前と要らないものと欲しいもののリストが与えられる。 物々交換により欲しいものを手に入れたい。 自分が持っているいらないものが相手の欲しいものであり、かつ 自分の欲しいものが相…

問題文 https://icpcarchive.ecs.baylor.edu/external/57/5790.pdf図のようにコストがついた玉がいくつか与えられる。ある玉を取り除くとそのコスト分だけ得点がもらえる。その玉の上に玉が無ければ取り除くことができる。得点を最大化せよ。 与えられる玉を…

問題文 https://icpcarchive.ecs.baylor.edu/external/42/4201.pdfバルブを光らせるパターンが与えられるので、クエリで与えられるとおりにバルブを光らせるまでの最短手数を求めよ。 ビットDP。 dp[パターンのid][バルブの状態]:=最短手数 とすると、DAGの…

問題文 http://livearchive.onlinejudge.org/external/40/4058.pdf縦3横nの長方形が、与えられた回転できないブロックで作る方法がいくつあるか求めよ。 f[ n ]:=横nの長方形の場合の数 とする。 g1[n],g2[n],g3[n],g4[n]についてはそれぞれ以下のような図形…

問題文 https://icpcarchive.ecs.baylor.edu/external/36/3673.pdfn×nの黒と白のグリッドが与えられる。任意の行と行、列と列をスワップすることができる。この操作を繰り返すことで、縦と横の番号が同じようなマスを全て白にできるか判定せよ。 斜めに並べ…

問題文 https://icpcarchive.ecs.baylor.edu/external/61/6133.pdf補完機能を使って文字を打つとき、ひとつの文字を打つのに必要な最小の打たなければいけない文字数の平均を求めよ。 トライ木を使った。そのノードの子が2つ以上なら、そこまでで補完機能一…

問題文 https://icpcarchive.ecs.baylor.edu/external/42/4210.pdfグラフが与えられる。最短経路に含まれる辺をひとつも使わない経路の中で最短のものを求めよ。ただし最短経路は複数ある場合もある。 ダイクストラを2回やる。一回目で最短経路に含まれる辺…

問題文 https://icpcarchive.ecs.baylor.edu/external/42/4212.pdfn*mのグリッドが与えられる。マスの数字はそのマスにあるキャンディーの個数だ。このグリッドのあるマスからそのマスにあるキャンディーを全てとるとき、図のようにそのマスの左右のマスと上…

問題文 https://icpcarchive.ecs.baylor.edu/external/56/5689.pdf色のついた円が与えられる。各データセットには色が400.0の円と789.0の円がひとつずつ含まれる。この円の上を通って、400.0の円から789.0の円に行って戻ってくることができるかどうか判定せ…

問題文 https://icpcarchive.ecs.baylor.edu/external/61/6139.pdf数列とクエリが与えられる。クエリは以下の2種類である。C a b 数列のa番目をbに更新する。 P a b 数列の区間[a,b]の積が負であれば-、0であれば0、正であれば+を出力する。 セグメント木を…

問題文 https://icpcarchive.ecs.baylor.edu/external/61/6138.pdf与えられた数字が、時計の短針と長針が作る角度に含まれるかどうかを判定せよ。短針は長針が12進んだときに1進む。 短針と長針が作る角度を全て生成しておく。工夫は必要ない。 #include<iostream> #in</iostream>…