ルール(？)
- AtCoder ProblemsでRecommendされた問題のうち、Moderate以上の難易度*1のものを1問以上解く
- 日曜日スタート、土曜日はABCがあるので基本お休み(3ACできるよね、という自分への圧)
- 眠さに負けてStreakが切れてもめげない。また次の日やればいいじゃないの精神
- 虚無埋め*2を考えるくらい疲れてるなら寝る
今週のおすすめレート: 808
要するに日曜に問題を解こうとしたらリストの一番上にあった問題のレート(自分のレートに依存するのでABCにRatedで参加する度に変わるはず)
直近参加のABCをunratedにしてたので値は変わらず。そして今週も元気に競プロ典型 90 問の★3～4の問題をやっていきます。
先週末のABC (AtCoder Beginner Contest 281)
C問題まではわりとスムーズに進み、D問題に十分な時間を割くことが出来たのにそのまま撃沈。残念ながらunratedでよかったと言わざるを得ない結果となりました。
配列の範囲・選んだ数・modで三次元DPを作るという基本方針までは合っていたんだけど、実装がなんだか間違っていたらしい。貰うDPでどうしてもうまく行かず13ケースくらいWAが残り、諦めて解説の配るDPでとりあえずのupsolve。なんか考慮が足りてないんだなというふんわりとした理解レベルでモヤモヤが収まらず、後述しますが元の貰うDPでもう一度解いてみました。
やった問題
2022/12/11
競プロ典型 90 問: 072 - Loop Railway Plan(★4)をやろうとしたのですが、15分くらい経過したところで集中力ブッツブツだったので寝ることにしました。あともしかしたらちょっとDFSに苦手意識があるかもしれない。
2022/12/12
眠かったので寝ようとしたのですが結局寝られなかった…
2022/12/13
ABC281: D - Max Multiple 貰うDPスタイル
- 自力AC？ 🙆 (当日のupsolve以降、新しくコードや解説を読んでいないという意味では)
- 所要時間: 1時間20分
@kyopro_friendsさんちのサーバルさんが「(配るDPと貰うDPの)両方書いてみるといいと思うよ」と仰っていたのでちょっとこちらを先にやってみることにしました。
サーバル「今回の問題だと、配るDPでも貰うDPでも、考えることは「Aiを選ぶか選ばないか」だから、そんなに難しさは変わらないはずだし、両方書いてみるといいと思うよ」
— 競技プログラミングをするフレンズ (@kyopro_friends) 2022年12月11日
……あーでもないこーでもないと1時間超コードをこねくり回した結果、修正点が「Aiを選べるかどうかの判定が> 0ではなく> -1で比較しないといけなかった(制約条件の読み違い)」と「target_modの算出方法が間違っていた」の2か所だったときの顔をしながらACジャッジを眺めることになりました*3。
配るDPと貰うDPの違いとかそういう次元でもなく、やるべきことはほぼ出来ていたのにケアレスミスという話。
今回に関しては確かに難易度的にはほぼ同じ、配る方がコード量が多少減るので見通しがいいかな、程度の違いとなりました。これを…当日…22:30頃には…気付きたかった……！
2022/12/14
アドカレ三部作の最終話を書いてたのでスキップ。
2022/12/15
競プロ典型 90 問: 072 - Loop Railway Plan(★4) の続き
- 自力AC？ 🙅
- 所要時間: 1時間40分 + 15分
二次元空間のDFS。多分類題っぽいのをコンテストでやったことがあるはず。
何となく総当たり的な解法が浮かんだものの、苦手意識が先行して早々に解説を見て写経までしたのにxとyの見間違いのケアレスミスに気付かずネストが深すぎるって言われ続けて頭を抱えてしまった。
家族にも寝不足の兆候を指摘されたのでちょっとゆっくり寝た方がいいかもしれない。
2022/12/16
競プロ典型 90 問: 075 - Magic For Balls(★3)
- 自力AC？ 🙆
- 所要時間: 15分
素因数分解を使う問題。なんかようやく自信を持って問題が解けてホッとした。
問題でやっている操作はまんま素因数分解。最終的に出来るボールの数は素因数の数と一致する。今回は多くても40個まで行かない*4はずなので、primeライブラリのInteger#prime_divisionでガッと求めてしまう。
分割に一番効率がいいのはなるべく素因数の数が半々になるように割っていって倍々にボールを増やしていくことなので、2nと順番に比較していって、素因数の個数以上になる一番小さい整数が正解になる。私はそっちの発想が出なくて対数取って切り上げちゃったけど、これだとfloatの誤差が怖いかも。40回程度だし解説通りにループ回しちゃうのが良さそう。
この辺はコードを書く前に紙の上で210あたりを試してみると理解しやすいと思う。
ちなみに、1回に1個しか分割できない場合は素因数の数 - 1が答えになるはず。
