まさかの全完早解き回だったw
A - November 30
わりとすぐ解けたんだけど、問題をちゃんと把握できているかの確認に時間とられた。まあいい感じ。
B - Tax Rate
これも全探索はすぐ見えるが消費税という怖い(間違えやすそうな)問題。落ち着いて、整数演算で完結させたのがよかった。
("Yay!"は出ないと思ってたけど、":("が出るんかい!)
C - 100 to 105
ド典型DPなんだけど、100から105と値段が似てるので工夫したくなる。結局普通にやったが。10000以上(実際はもっと少なくていいだろうけど)だったら必ず作れるというのは思いついてて、Xが小さいときは100で割ることで何個買うか特定できて端数は105円のやつで到達できるとこなら1円単位で調節できるし。まああまり突っ込んでは考えなかったが、こうしてみるとO(1)も行けそうな。
D - Lucky PIN
全探索。3万だからさすがに間に合うだろう。しかし、10^4*10^3=10^9っていう勘違いをまたやった。色々考えたが、さすがに間に合うので全探索。難易度からすると早解きするべき問題なのに、楽しそうでつい考えこんでしまう(笑)。まあ楽しいのはいいことだ。(計算量落とせるかな)
E - Colorful Hats 2
いきなり難しくなる。前から考えていく方針は最初のころにやったが、頭がこんがらがってN=2くらいまでしかできなかった。適当なA_iを選んで、同じ色がちょうど何個あって、次の要素から見ると個数が合えばそれと同じ色にしてもいいし、個数が範囲内ならそれ以外の色にしてもいいとか。これは難しすぎる。こういう経験値を積んでから最初の方針に戻ってみると、前から見ていけば色が何個ずつあるかは決定できてしまう。あとは、どの色にするかの選択を掛け算していけばいい。
F - Interval Running
無限回出会うのは、平均スピードみたいなのが同じとき。同じなら定期的に出会うし、違うなら引き離されて会えなくなる。それ以外で1回でも出会うのは、最初のT_1分で先行した側が次のT_2分で追い越されるときのみ。T_1+T_2分時点での距離をdとすると、T_1分時点でのアドバンテージ(Xとする)はdずつ削られていく。つまり、追い越し追い越されというのを大体X/d回くらい繰り返す。あとは、ちょうど追いついたと思ったら追い越すことなく引き離されてもう出会わないというピッタリのケースを処理するだけ。
こういうの好きだし、好きなわりに今回そこまで早解きできなかったという点で苦手でもあるので、出題されてほしい系統の問題だ。やはり双子回は面白い。