毎日格上の問題を倒すやつの67日目です。
嘘です、はるくさんのやらかし回です。本番のコンテストだと許されないことをしてるので、懺悔としてまとめておきます。
コンテストリンク
結果
0完🌞(笑)
解法と反省
A
二次元累積和まではパッと思い付き、まあ三乗なんだろうなというところもわかりました。が、
やらかし①
問題文を盛大に誤読し、左上の座標が であると誤認していました。
そのため、「二乗じゃん、簡単じゃね?」と思いつつ実装します。そんなわけないんですが。
幸い、サンプル2がそれだと合わないので、比較的早く気付くことにはできました。これだけなら十分取り返しのつく範囲ですが、
やらかし②
もう少し考えればわかりそうだと思いつつ、先にBCを30分ほど考えてしまいました。解けるわけないのに。
この間Aの考察していれば、Aは通せたと思います。しかし、
やらかし③
コンテスト終了30分前まで、YouTubeを鑑賞しながら考察していました。馬鹿なの?
当然考察がはかどるわけもなく、何もなくただ徒に時間が過ぎていきました。
しかし、YouTubeを見終わったとたん、なぜかAの解法を思いつきます。絶対ずっと考えるべきだったのに。
上下を全探索し、右端を全探索すればあとは、こうなんかいい感じに累積和の要領で最適な左を計算できるのです。
そのため、この体たらくでもこれを実装すれば0完は免れるというところまではきました。
ただ、「やらかし①」の段階からもっと大きなやらかしをしていたのです。
やらかし④
盛大にバグらせ、コンテスト終了に間に合いませんでした。
いや、もはやこれはどうでもいいんです。次が大問題。
やらかし⑤
終始Pythonで実装していました。
「何が問題なの?」と思われそうですが、こどふぉは余裕でpy虐殺問題が出ます。今回のもそうでした。
コンテスト後、何とか実装を終わらせるも無事TLE。終わりすぎです。
この前、Pythonの速度に関して「遅いが言い訳できるほどではない」と言いました*1が、それは大抵AtCoderだけの話です。ほかのコンテストでは普通にcppじゃないと解けないものも存在します。*2
cppを普段から使っていないのが一番の問題ですが、TLとその割に大きい制約を見て一目で気づくべきでした。目利き力✖。
それにしても黄色になってからpyとcppの差が顕著になってきた気がします。JOIもあるし、今度しっかり持ち換えようかな…
...え、cppでは実装しなかったのかって?私は力尽きました。
問題の提出
A
まとめ
空いた日にやってたこと
66日目
【今日の精進】
— はるく@競プロ (@halc_kyopro) 2023年11月25日
Codeforces Round 684 (Div. 1)
A...とりあえず左上から合わせていく感じで、あとは下二列をいい感じに
B...もうなんかわからん、N^1.5くらいでできそうな気はするが