Codeforces #60

仮眠してからスタート。

A Harry Potter and Three Spells

方針

まさかの Harry Potter ネタ。個人的にはナルニア派だけど、ハリー・ポッターも原著で全巻読む程度には好きでした。

本質的には、ace < bdf。サンプルを見ると、0 の場合がやっかいそう。いくつか検討してみると、bdf / ace を、∞も含めて1と大小比較すればよさそう……って、ダメじゃん。1, 0, 0, 1, 0, 1 とか 100, 1, 100, 1, 0, 1 とかあるし……

この手の条件分けがややこしい問題は、本番で通った試しがない。撤収して寝たくなるが、訓練だと思って考える。まず、0 が全くない場合は、ace < bdf でいい。

d が 0 の時は、全く作れないからハーたんの勝ち。d が正で、c が 0 のときは黄金が無限生成(いい響きだ)できる。

c, d が 0 じゃないときは、原料(鉛) が無限供給(いい響きだ)できればよい。b が 0 の時は、全く作れないからハーたんの勝ち。b が正で、a が 0 のときは鉛が無限生成できるので、黄金も無限生成できる。

a, b, c, d が 0 じゃないとき。この時は、砂が無限供給できればいいので、e, f について以下同文。

あ、なんか解けてしまった感。

実装

Ruby で書くだけ。

まだ見落としがある気がするが、これ以上考えたくないので次へ行く。

B Harry Potter and the History of Magic

方針

あー、なんかいたなぁ、こんな先生。

dp[何項目め][今の年] ? n = 1000 だから大丈夫。

実装

年号の一桁だけ書き換えるってのが、Cだと面倒。これもRubyでやろう。

ん? 答えを1つ出せばいいんだから、これ dp 必要ないんじゃね?

えっと、各項目ごとに作れる年号を列挙しておいて、最初の項目から、可能な限り小さい年号を取っていけば……

書けた。

C Harry Potter and the Golden Snitch

方針

あー、幾何だ。幾何だ。幾何の問題は、今まで(練習も含めて)一問も解いたことないぞ。

各線分ごとにそこにスニッチがいる時間帯を求める。Harry のスタート地点から、線分までの距離を求め、時間に変換して、スニッチがいる時間帯までに到着できるか調べる。

これで行けるはずだけど、点と線分までの距離とか、浮動小数点の誤差を含んだ評価とか、うまく書ける自信がない。パス。

D Harry Potter and the Sorting Hat

方針

DP[どこまで決まった?][G の生徒数][H の生徒数][R の生徒数][S の生徒数] だと、状態数が多すぎて無理。

ん? 逆から考えたらどうだ? G に入れるか調べる, H に入れるか調べる……ってのは? 例えば、G に入れたいときは、G以外の部屋になるべく詰め込めばいいんだから……

実装

? を入れたい部屋以外に分配して、入れたい部屋の人数を最小にできるか書く。

1つ目が合わない。って、過程でも「最小の部屋」にしか入れられないじゃん。なんでこういう勘違いをするかなぁ? それでも、入れられる部屋に複数の選択肢がある場合、目標の部屋以外を選べばどれでも同じだよね。←間違い!

pretest passed.

結果

1611→1752! でも、D は落ちてた。単純な greedy ではダメだった様子。

考察・感想

A は苦手なタイプの問題だったが、通せたので嬉しい。他の人のバグをつつきまくって点を取るという手段もあっただろうが、自分の解答にも自信なかったので lock しなかった。

D は結果としては落ちてしまったが、前からシミュレートするのではなく、逆から考える、すなわち、"ある解が存在するか調べる"という発想ができたのは一歩前進だと思う。この発想法は、二分探索を使った最適解探しなどにも使える(らしい)ので、大切にしたい。

C は、あとで書いてみないとなぁ。