AtCoder Beginner Contest 030

 知ってた。難しい。

結果

 94:22(3) 48位相当


 開始時刻 2017/08/15 14:49:00 提出履歴

A: 勝率計算 - AtCoder Beginner Contest 030 | AtCoder

 2:04(AC)
 B/AとD/Cを比較するだけ。

B: 時計盤 - AtCoder Beginner Contest 030 | AtCoder

 8:20(AC)
 長針は360\times\frac{m}{60}度、短針は360\times\frac{n}{12}+30\times\frac{m}{60}度になる。小数点に気をつけながら気合いで出力。

C: 飛行機乗り - AtCoder Beginner Contest 030 | AtCoder

 17:04(AC)
 貪欲に早い飛行機に乗っていくのが最適解。飛行機の本数はせいぜい105オーダーだし、昇順であることは保障されているので、左右交互に登っていくような線形探索でもいいと思う。二分探索は地味に面倒くさい。

D: へんてこ辞書 - AtCoder Beginner Contest 030 | AtCoder

 54:49(WA)60:47(WA)68:07(WA)79:22(AC)
 とりあえず、ループに行くまでの移動距離とループの長さがわからないと話にならないので、ウサギとカメのアルゴリズム(フロイドの循環検出法)なんかを使って頑張る。ウサギとカメのアルゴリズムここが参考になる。
 kの大きさ的にループに届かない時は、順当にシミュレーションすればいい。せいぜいO(N)で済む。
 ループに届く時は、ループの長さを法としたkの値さえ分かればどうにかなる。ただし、確実にループに届くよう、ループまでの距離以上のループの長さの倍数を足す。その後に愚直にシミュレーション。こっちもO(N)程度。

感想

 028、029が簡単すぎた分、ひどく難しく感じた。多分いつも通りくらいなんだけど。