ルール(？)
- AtCoder ProblemsでRecommendされた問題のうち、Moderate以上の難易度*1のものを1問以上解く
- 日曜日スタート、土曜日はABCがあるので基本お休み(3ACできるよね、という自分への圧)
- 眠さに負けてStreakが切れてもめげない。また次の日やればいいじゃないの精神
- 虚無埋め*2を考えるくらい疲れてるなら寝る
今週のおすすめレート: 753
要するに日曜に問題を解こうとしたらリストの一番上にあった問題のレート(自分のレートに依存するのでABCにRatedで参加する度に変わるはず)
先週末のABC (AtCoder Beginner Contest 271)
C問題まではいいペースで片付けられたものの、D問題のテストケース1個が最後までWAを剥がせずにそのまま終了。解説を読んでも微妙に解き方が違うので原因が分からず、配るスタイルで根本的に書き直すか？と悩んでいた矢先にふと思い立ってj軸側の配列サイズを想定値の最大まで広げたらすんなりACして「うそでしょ！？」ってマジで声が出た。
てことで二次元DPで解法は合ってたのに変なミスで落とすシリーズのバリエーション更新。
- minを取っていく問題で初期値が小さすぎてそのまま解答として出てしまいWA
- 負数が入ってくるDPで初期値に0を与えてしまいやっぱり結果がおかしくなる
- 配列のサイズ指定が小さすぎておそらく添字が意図しない値になって参照が狂う←New!
何気にコンテスト本番では初めて緑diffの問題を取れ、意外にも緑パフォーマンスを維持できたので気持ち的には差し引きで若干のプラス。でもあそこまで出来たならD問題取りたかった…！
やった問題
2022/10/02
競プロ典型 90 問: 034 - There are few types of elements(★4)
- 自力AC？ 🙅
- 所要時間: 35分
尺取り法。名前を認識しつつ解いたのはもしかしたら初かもしれない。
とりあえず端から順にカウントしていってTLEを起こし、まぁそうよねーと思って解説を読むが雰囲気しか掴めなかったのでRubyのACコードを参考にする、というか現時点では参考元のほぼ写経なのでもう少し類題やらないとダメそう。
別に根本的な考え方は悪くなかったんだけど(負け惜しみ)、データ構造もうちょい考えないとそりゃTLE起こしますよねっていう感じ。
2022/10/03
平日の立て込み最終日でした😇
2022/10/04
気が抜けてドッと疲れが…
2022/10/05
気温差で微妙に体調やられました
2022/10/06
競プロ典型 90 問: 038 - Large LCM(★3)
- 自力AC？ 🙆
- 所要時間: 5分
言語仕様のリッチさ(？)で難易度がそれなりに変わるタイプの問題。
これ多分オーバーフローの回避が焦点なんだろうなぁって思いながら、Rubyだと素朴に書いても行けるんじゃないかって雑に考えて提出してみたらそのまま通ってしまった感じ。ユークリッドの互除法は前にも出てきたので頭に置いておくとよさそう。
2022/10/07
競プロ典型 90 問: 042 - Multiple of 9(★4)
- 自力AC？ 🙅
- 所要時間: 33分
前半は完全にNの倍数の特徴に関する知識があるかどうかの問題。各桁の和を数字和っていうらしいんだけど、9の倍数はその数字和が必ず9の倍数になるというのがあるので、1つ目の条件を満たす数ならあとは該当する値の個数を出せばOKではある。
解説を読むと特定の数の倍数の性質の方がポイントだったようにも見えるんだけど、正直この後の方にほぼ時間を費やしてた。 k < 10であれば若干変則的な組み合わせ計算をすれば良さそうではあるんだけどこのケースはややこしくて、DPで解かないといけない。正直まだ本番で類題を見抜ける気がしないし、同じ問題が出たとして知識として引っ張ってくることは出来るけど、感覚的に納得して解ける気はしない。ぐぬぬ……
