kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

AtCoder Beginner’s Contest 138

昨日受けました

ところでAtCoderのコンテストって、終わったら中身書いてもいいんだよね?
解説も出るくらいだしいいよな

準備
終わったら早めに寝られるようにお風呂はすませておいた
晩ごはんの飲み物はオールフリーに
ヨメとムスメにはパパコンテスト受けるからねと宣言

ローカルで動かしてから提出するのでAからFまでファイルを作っておく
EとかFとかまで進む気はあんまりしないし何秒も変わらないとは思うけど
Python 3.4をわざわざ入れたりはしていない
f-stringくらいだよねたぶん

あとはAtCoder Beginner Contest 138のページを開いておくくらい
開始時刻になったらダイアログが出た

A - Red or Not
問題なし

B - Resistors in Parallel
問題なし

C - Alchemist
問題なし
ここまで13分

D - Ki
普通に木をたどるだけ?と思ったけどTLEが取れなかった

どうも再帰が深くなるようでREも出る
これはrecursionlimitを1000000にしたら解消(おおざっぱ

input()じゃなくてstdin.readline()にしてみたり
毎回木をたどるのはやめて、先に木をたどって子孫を全部リストアップして
みたりしたけどあまり効果なし
あと何したら速くなるかなあ、と思ったけどいいアイデアは思いつかず

解説を読む
そうか、毎回木をたどってたからTLEになったのか
全部読んでからまとめて木をたどればいいんだな
そうやってオーダを減らすわけか
ただし、正しいやり方でも遅い言語では間に合わないこともあるとか

E - Strings of Impurity
Dで行きづまった後見てみたけどできそうにないのでスルー
絶対できないとは思わなかったけどDで何か高速化を思いつくほうが
ありそうな気がした

F
ほぼ同上
こっちは考えてもできそうな気がしなかった

結果は600点
レーティングは何回か受けるまでは低い値しか出ないらしい
パフォーマンスってやつが目安にはなるらしくて783

次もなんとか参加してDまで解いてみたい
実力相応な気もするので、何度か受けて慣れたら急成長、ってことはなさそうだなあ

教訓としてはオーダを減らすことの重要さと
行きづまったらひっくり返してみるといいことがあるかもしれないということ
(ただし今回はそれではうまくいかない)