htkb-proconの日記

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

AtCoder Regular Contest 079 参戦記

o-o- 1355 -> 1395 (+40)

C - Cat Snuke and a Voyage

結果:AC
Submission #1463078 - AtCoder Regular Contest 079 | AtCoder

用意してあったダイクストラをそのままベタッと貼りました。完。

pythonheapqは二分ヒープのようなのでこれを使ったダイクストラ(E+V)*log2Vで大体6.6*10^6くらいで、こんなもんでもpythonだと時間が結構やばめなので怖い。

D - Decrease (Contestant ver.)

結果:わかんなかった

1 0 0 ← k = 0
2 0 0 ← k = 0
3 0 0 ← k = 1
6 0 0 ← k = 2
9 0 0 ← k = 5 ???

みたいに基本は数字を1個だけ動かしてなんとかしようとしたのでめちゃくちゃこんがらがった。逆順でシミュレートするなら足す数以外は全部引けばいいという発想が全く出てこなかった。

N=50決め打ちで、数列の初期状態を[0, 1, 2, ... 49]にして、K // 50(切り捨て)の数だけ数列の全ての数に加算して、K % 50回だけ「数列の最小値に50を足し他の数字を-1する」をシミュレートすればいい。←このシミュレートを50回繰り返すと結果的に数列の全ての数が1加算された状態になる。

Submission #1471485 - AtCoder Regular Contest 079 | AtCoder

E - Decrease (Judge ver.)

結果:AC
Submission #1466238 - AtCoder Regular Contest 079 | AtCoder

「数列の数aiNを超えていたらai // Nを他の数に加算しai = ai % Nにする」という二重ループをmax(a) < Nになるまで繰り返すシミュレーションで通ってしまった。計算量がよくわからなかったのでダメ元だったんだけど(そして解説読んでもよくわからん)。N=50で数列が全て10^16の場合、whileブロックは838回しかループしないみたい。Youtubeの解説では二分探索やってたけどそっちは絶対思いつかない……。