ルール(？)
- AtCoder ProblemsでRecommendされた問題のうち、Moderate以上の難易度*1のものを1問以上解く
- 日曜日スタート、土曜日はABCがあるので基本お休み(3ACできるよね、という自分への圧)
- 眠さに負けてStreakが切れてもめげない。また次の日やればいいじゃないの精神
- 虚無埋め*2を考えるくらい疲れてるなら寝る
今週のおすすめレート: 808
要するに日曜に問題を解こうとしたらリストの一番上にあった問題のレート(自分のレートに依存するのでABCにRatedで参加する度に変わるはず)
いわゆる内部レートが800を超え(て)たようです。うぇーい。
直近はリソースを諸々別のところに割いていたので、競プロ問題触るのは2ヶ月ぶりくらい。安易にコンテストに参加してレート下がって無駄にショック受けるのが嫌すぎるため今週はリハビリのつもりで、週末のコンテストはよっぽど調子良くない限りunratedで参加しようと思います。
と、散々レートの話をしておいてアレなんだけど、引き続き競プロ典型 90 問の★3～4の問題を解いていきます。今週スタート時点であと11問。
やった問題
2022/12/04
競プロ典型 90 問: 063 - Monochromatic Subgrid(★4)
- 自力AC？ 🙅
- 所要時間: 1時間13分(+α)
途中計測忘れてたりなんだりあるので多分実際は1時間半くらいだと思う。
開始後早々に解説を読んだけど内容を理解するのに結構かかった。
解説のとおり、行数の制約が異様に少なく8行なので、行をどう選ぶかは全探索で行ける、というのがポイント。選んだ行の中で全部値が一致している数をHashに取っていって、一番一致した回数の多い数に対して一致した回数 * 選んでいる行数を出していく。その最大値が答え。
Hash#maxの仕様を完全に勘違いして逆にこれで何でほとんどのケースが通ったんだろうっていう感じのWAを取り、悩んだ末正しいロジックに直したら余計に手をつけたところでTLEを起こし、そこだけ元に戻してようやくAC。ついでに実行時間が長いと思ったら制限時間が4secだった。
2022/12/05
別件作業があったのでお休み。
2022/12/06
- 自力AC？ 🙅
- 所要時間: 53分
★3なのに自力で解けずぐぬぬってなった。
変化が起こる位置の開始と終了だけ差が求められたらいいよねってところまではすぐ分かったものの、それをどうやって管理しようと迷走して40分、その後解説を読んでどうにかクリア。累積和ぽみもあり。
2022/12/07
アドカレ書いてたのでお休み🥰
2022/12/08
競プロ典型 90 問: 069 - Colorful Blocks 2(★3)
- 自力AC？ 🙅
- 所要時間: 40分
血迷ってまたDP使おうとしたところから制約のN <= 10 ^ 18を見て正気に戻り図をゴリゴリ書き、基本的には k * (k - 1) * (k - 2) ** (n - 2) で行けるところまでは理解。
まずn == 1 とその他で分ければ、どうやっても無理なパターンはうまいこと0乗算で消えてくれることに気付かず一波乱。ここまでで22分くらい。
その後解説を読んでも基本方針は合っていて意味不明だったのでRubyのACコードを読むと、べき乗を使って解いている人はみんな2引数のInteger#powを使っていることに気付く。ここまでで追加11分。
競プロ典型 90 問は幸いテストケースが公開されているので、2引数でACするのを確認した後に1引数のInteger#powでダメだったケースを手元で動かしてみる。
$ ruby typical90_bq.rb 1000000000000000000 937318945 typical90_bq.rb:10: warning: in a**b, b may be too big NaN
Rubyは結構大きな値でもだいたいうまいことやってくれるので最後にmodを取れば済むケースが多いんだけど、今回は扱っている数が巨大すぎていくら上限なしって言ってもねぇみたいな感じで最初からmodを取らないと計算できないパターンだったらしい。これは本番のC問題として遭遇してたら撃沈してたかも。
2022/12/09
競プロ典型 90 問: 070 - Plant Planning(★4)
- 自力AC？ 🙅
- 所要時間: 30分
グラフ系の問題で「全体からの最小」が必要になったら中央値を求める。
「全体からの最短距離ってことは何かしらの真ん中ってことだよね、平均ではなさそう」「xとyは別に考えて良さそうだよね」は自力で導けたんだけど、中央値を使うことにたどり着かなかったのがちょっとくやしい。
ついでに問題を読んでいて微妙に引っかかっていた「この問題の制約下で答えは整数となることが証明できます。」に関してメモっておく。
中央値はその性質上、今回の制約では整数値にならないこともある。が、そのケースはNが偶数の時にしか発生しないので、結果的に距離の合計は整数になるということらしい。
そのほか、Sendai.rbのイベントで2問ほどモブプロしました。楽しかった～
ABC089-C MarchはRubyで書くとびっくりするほどノーストレスで話が進められるのが大変気持ちよかったです。
