htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Regular Contest 078 参戦記

oo-- 1337 -> 1358 (+21)

C - Splitting Pile

結果:AC
Submission #1422177 - AtCoder Regular Contest 078 | AtCoder

すぬけくんが先頭から連続した数列を取り、アライさんが残りを取ることになるので、snuke = 0,arai = sum(a)から始めて、数列から数字を1つずつ取ってすぬけくんに足してアライさんから引いて、そのつどabs(snuke - arai)を取ればいい。両者とも最低1枚は必要なことに注意。でもそれを忘れてループを最後まで回すと2つ目のサンプルケースで答えが合わず気付かせてくれるあたり、AtCoderは優しい。

D - Fennec VS. Snuke

結果:AC(3WA)
Submission #1427667 - AtCoder Regular Contest 078 | AtCoder

最初はただ単にそれぞれの初期位置から相手の初期位置をまたがずに取れるマスを数えてWA、進み方によって相手の取れるマスを減らせることにやっと気付いたあとに凡ミスでWA、最後に数が同じだった場合先行の勝ちにしててWAの3WA。

相手の方向に一直線に進んでいくと相手の進行可能なマスを減らせるので、最適な動きはお互いの初期位置への最短経路をお互いがたどることになる。んで自分はその経路を取るためにダイクストラをかまし、v[0]からv[N-1]への経路を復元して先頭から半分(切り上げ)をフェネックのもの、それ以降をすぬけくんのものと割り振り、相手のマスには進行不可能との条件を付けて幅優先探索を2回行ってお互いが取れるマスを数えた。

あんまりにもあんまりな解法だったので、解説にあるとおり初期位置からの距離を取って比較するやり方で書きなおしてみた。

Submission #1433142 - AtCoder Regular Contest 078 | AtCoder

時間的にはあんま変わんないけど。こっちは相手の初期位置で探索を止める処理を入れてないので。

おまけ

pythonで大量に入力を受け付けるとき、input()よりsys.stdin.readline()のがかなり速い。

readline = sys.stdin.readline

とキャッシュして(pythonはオブジェクトの属性探すのが遅いので)readline()で入力を受けると、入力回数5*105回の問題でinput()と比べて0.7〜0.8秒くらい速くなった。念のためinputの方も

_input = input

とローカルにキャッシュして試したが変わらなかった(それはそう)。仮に106回入力を取るような問題があるとinputでは全然ダメそうなのでreadlineを使っていきたい。