解いた問題

5/21/2012

SRM404 Div2 Hard

1000

同じ高さで到達可能なモノを1つにまとめる。
まとめると、よくあるDPになる。

SRM404 Div2 Medium

500

やるだけ。

SRM404 Div2 Easy

250

やるだけ。問題を理解するまで時間がかかった。

SRM403 Div2 Hard

1000

DPするだけ。

SRM403 Div2 Medium

500

やるだけ

SRM403 Div2 Easy

250

やるだけ

SRM402 Div2 Hand

1000

数字は多くても 8 個しかないので、とりあえずメモしながら全部試す。
+1.0 する必要があることに全然気がつかなかった。


SRM402 Div2 Medium

500

やるだけ

SRM402 Div2 Easy

250

やるだけ

5/20/2012

SRM401 Div2 Hard

1000

お手上げ。解説を読む。

KMP の接頭語関数の最後の要素と文字長の差を見るらしい
接頭辞関数って、最長の接頭辞の長さだよね・・・。


スパソから KMP を拝借してサブミット

SRM401 Div2 Medium

500

図がいまいち理解できなかった。


SRM401 Div2 Easy

250

GCDで解けるらしい。

SRM400 Div2 Hard

1000

上1行と左1列を全通り試す。
個人的にはMidより簡単な気がする。

SRM400 Div2 Medium

500

pow 関数で計算すると誤差で死ぬ。

これを1発で通せる人は凄いと思う。

SRM400 Div2 Easy

250

やるだけ

SRM543 Div1 Easy

250

mod 4 とかいうスマートな解法があるらしい。

unsigned int ならループを回しても間に合うとか間に合わないとか。

5/15/2012

SRM501 Div1 Easy

250

DPして最大値を最小値を探す。
dp[足した回数][掛けた回数]

SRM502 Div1 Easy

250

サフィックスになってるものを削除すればいい。

SRM503 Div1 Easy

250

答えは2, 1, -1の3つしかない。
最後のサンプルを見ると何となく察しがつく。

あとはそれぞれの最小値と最大値を見てそれっぽい解を返せばいい。

SRM504.5 Div1 Easy

250

下1桁だけに注目すればいい。
与えられた数と同じ下1桁を持つ数を4と7から作る。

SRM504 Div1 Easy

250

やるだけ。

AOJ1251

AOJ1231

やるだけ。気合。

5/14/2012

SRM505 Div1 Easy

300

こういう感じの問題って凄く苦戦するんだけど、何かコツとかないのかな。

AOJ1263

AOJ1263

入力として与えられる隣接行列の対角成分以外は2以上なので、必ずスイッチを経由する。
まず頂点のどれかから辺を伸ばして、スイッチを1つ設置して木のルートと見る。
そうすると、ある頂点からある頂点へ移動するときにそのルートを経由する必要があるかどうかが判定できる。
経由しなくても行ける頂点同士には、ルートから新たに辺を伸ばしてスイッチを設置して同様の処理を繰り返す。

5/13/2012

TCO2012 2B

参加記録

華麗に0完

300:
0〜N-1と1〜Nを間違えた。

550:
開いてない

900:
開いてない

5/11/2012

AOJ2033

AOJ2033

まず強連結成分分解する。
その後、連結成分を圧縮した森でルートとなっている頂点を探す。
その頂点に含まれる本来の頂点のどれかをそれ単体で作成する。

強連結成分分解のコードを描いたのがだいぶ昔なので、描き直したい衝動に駈られている。

5/09/2012

SRM542 Div1 Easy

250

まず、Tを決める。
高さ H 幅 W の四角形を考える。端から端まで使うような経路では T = 2 * (H + W)
中継地点の座標の選び方は (H - 1) * (W - 1) 通り。
その四角形の中から3点を選ぶパターンは、X座標Y座標を3つずつ選んで、
それを組み合わせてできる座標の数。つまり、3!
ex.) X = {0, a, W}, Y = {0, b, H} から作れる座標を組みは3!通り。

それを掛けて足しあわせていけばいい。

分かりやすく説明できないー。

5/07/2012

SRM506 Div1 Easy

250

やるだけ。

SRM507 Div1 Easy

250

やるだけ。

SRM509 Div1 Easy

250

9で割った余りなのが重要。10^nをかけたとしても、あまりに変化がない。
そして、各数字は 2^(文字列の長さ) 回だけ登場する。

小さいケースを手で試していたら気がついた。
簡単だとも思わないけど、Editorials を見る限りでは正答率が低いわけではない。
こういう類を苦手に思わない人たちってのはどういう過程を経て答えに行き着くのか・・・。

SRM510 Div1 Easy

250

全通り試して間に合う。

SRM511 Div1 Easy

250

条件に合うように2つのグループに分ける。
あとは、割り当て方が何通りあるかを計算する。