White scenery @showyou, hatena

If you have any comments, you may also send twitter @shsub or @showyou.

AtCoder Beginner Contest 123(ABC123)に参加しました

Bが普段より少し難しく、CがBよりも楽でした。

 

A

e-a < k

https://atcoder.jp/contests/abc123/submissions/4844897

B

全探索しても5!=120通りなので、深さ優先で全探索しました。深さ優先探索に書きなれてなくて時間かかりました。

https://atcoder.jp/contests/abc123/submissions/4850115

C

各点から次の点に行くまでのコストが全部1で、効率化も図れなさそうでした。

なので、一番ボトルネックになってる所が、そのまま時間に影響すると踏みました。

よって、math.ceil( n/ a~eの最小 ) - 1 + 5を答えとしました。

https://atcoder.jp/contests/abc123/submissions/4852114

D

解説見ずに解けませんでした。

純粋に全ての組み合わせで計算していくとどう考えてもTLEなので、途中でA+BにCの最大値を足しても和のリストのK番目以降だったら、それ以降除外(A, B, Cは降順にソート)したらどうかと思いましたがダメでした。

解説見ると、A+Bの和の上位K件とCの和を足したらなんとか行ける的なことが書いてますが、Pythonだと時間が厳しいです。

自分の書いたコードだと最後のテストがTLEになる一方(https://atcoder.jp/contests/abc123/submissions/4864733)、他の人のはギリギリ2000msecになったりします(https://atcoder.jp/contests/abc123/submissions/4865171)。

 

それよりかは、a*b*c <= K の条件を使ったほうがいいでしょうね(https://atcoder.jp/contests/abc123/submissions/4866932)。ただなんとなくaとかが団子状態になってたら、a*b*d > Kでもa+b+cの順位がK番目以内に入ってきそうな気もするんですが・・

 

今回運良くCが素早く解けたので、レートが上がりました。Cをコンスタントに解いて緑に上がれるといいです。

 

あと全然関係ないですが、今日の昼はGoogle Code JamのQualification Roundに参加してました。こっちはまだ続いてるので回答書きませんが、1日に2つのコンテストはハードですね。

 

4/7 1:25 追記

D問題の自前で書いてTLEになる方(https://atcoder.jp/contests/abc123/submissions/4864733)、処理系をPython3(CPython)からPyPyにしたところ、余裕で通るようになりました。それでも自分で元々考えてたコードは遅すぎてTLEなのですが・・。Pythonで時間が気になる場合はPyPy選んだほうがいいのかもしれませんね。