ルール(？)
- AtCoder ProblemsでRecommendされた問題のうち、Moderate以上の難易度*1のものを1問以上解く
- 日曜日スタート、土曜日はABCがあるので基本お休み(3ACできるよね、という自分への圧)
- 眠さに負けてStreakが切れてもめげない。また次の日やればいいじゃないの精神
- 虚無埋め*2を考えるくらい疲れてるなら寝る
今週のおすすめレート: 778
要するに日曜に問題を解こうとしたらリストの一番上にあった問題のレート(自分のレートに依存するのでABCにRatedで参加する度に変わるはず)
先週末のABC (AtCoder Beginner Contest 272)
何とか4完。最近緑パフォーマンスが続くので欲が出てしまい、茶色に戻ったときのショック具合が今からちょっと怖い。 D問題でパニックになりすぎて三平方の定理が吹っ飛び「距離が√5になる位置関係って何！？」ってなってたあたりがハイライト。コンテスト中に解けてよかった…… 最近E問題も眺めているとなんか半分くらいは時間かけたら出来そうな気がしてくる不思議*3。典型問題の★3★4を埋め終わった頃にはもうちょっと戦えるようになるかなぁ。
ということで今週も元気に競プロ典型 90 問をやっていきます。
やった問題
2022/10/09
競プロ典型 90 問: 043 - Maze Challenge with Lack of Sleep(★4)
- 自力AC？ 🙅
- 所要時間: 2時間15分(未完)
これABC272のD問題の類題っぽい*4と思って40分くらい悩んだ後に解説読みながらやったけどWAが剥がれず、解説のコードをRubyに翻訳しつつ写経したらTLEになり、今日は一旦諦め。このパターン久しぶり😇 読んだRubyのACコードがことごとく解説と違うコードなので、多分こっちのスタイルでは無理なのかもしれない。
2022/10/10
続・競プロ典型 90 問: 043 - Maze Challenge with Lack of Sleep(★4)
- 自力AC？ 🙅
- 所要時間: 40分 (+2時間15分+睡眠)
昨日の続き。他の人のRubyのACコードを参考に何とかAC。これはきつかったー
どうもRubyだと計算量的に厳しめの問題ぽく、解説みたいに4方向のコストを全部計算する時間的余裕は無いみたいで、進行中のコストのみ計算して直進できるだけ進めてしまうスタイル、かつわりとシビアなチューニングをしないとダメっぽい。とは言え、実行時間1秒切ってる人4人*5いるんだよなぁ、今度写経させてもらおうかな…
2022/10/11
競プロ典型 90 問: 044 - Shift and Swapping(★3)
- 自力AC？ 🙆
- 所要時間: 15分
時々よくある配列をぐるぐる回す問題。素朴に配列をコピーしていくとTLE不可避なのでオフセットの値を管理していきましょうねというやつ。 swapするのにもうちょいコストかかるかなぁと思ってたんだけど、意外と素直にACが取れた。
……で終わらせようとしてたんだけど、他の人のACコード読んだらArray#rotate!してて普通に早いコードがあるので驚いた。今度類題見たら検討しても良さそう。
2022/10/12
競プロ典型 90 問: 046 - I Love 46(★3)
- 自力AC？ 🙆
- 所要時間: 8分
データをちゃんと整えさえすれば計算量の心配は無用なタイプの問題。
和が46の倍数になるには剰余の合計が46の倍数になればOKなので、剰余が同じ値は同一視することが出来る。ということで配列の値に対して全部剰余を取ってしまえば後はArray#tallyすれば最大46個まで圧縮できる。そこまで小さくできればあとは全探索で十分間に合う。
考えた通りの実装ですんなりACしたので安心したー
2022/10/13
体調が微妙でスキップ。
2022/10/14
用事があったのでスキップ。
