■
お酒おいしい
SRM489 Div1
ここには書いていなかったのだけれど、前回のSRM488でDiv1に上がっていたので、今回からDiv1です。
とりあえず、Div2に戻らないように頑張りたい。
結果
○×× 176.84 pt
1230 -> 1300
でした。
以下、断片的なメモ
1163 Cards
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1163
方針
明らかに2部グラフのマッチングに見える。
ソース
1296 Repeated Substitution with Sed
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1296
方針
置換えを実行すると必ず文字数が増えるという条件と、
targetとなる文字列の長さが10以下という条件から、置き換えは最大9回しか起こらないということが分かるので、BFSする。
ソース
1304 Infected Land
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1304
方針
広さが5*5しかないので、BFSした。
ソース
2229 Sumsets
http://poj.org/problem?id=2229
方針
nが偶数の時
f(n) = f(n/2) + f(n-2)
nが奇数の時
f(n) = f(n-1)
となるため、小さい方から順に求めてやる
ソース
2211 迷い猫、走った
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2211&lang=jp
方針
最大値を最小化する問題なので、2分探索すればいいのはすぐにわかる。
けれども、ある猫の数以下で条件を満たすことができるかどうかの判定が難しい。
解説のスライドを見ても、なかなか分からなかった。