ルール(？)
- AtCoder ProblemsでRecommendされた問題のうち、Moderate以上の難易度*1のものを1問以上解く
- 日曜日スタート、土曜日はABCがあるので基本お休み(3ACできるよね、という自分への圧)
- 眠さに負けてStreakが切れてもめげない。また次の日やればいいじゃないの精神
- 虚無埋め*2を考えるくらい疲れてるなら寝る
今週のおすすめレート: 665
要するに日曜に問題を解こうとしたらリストの一番上にあった問題のレート(自分のレートに依存するのでABCにRatedで参加する度に変わるはず)
直近のABC269は4完でした。久々の緑パフォーマンス。
ひゃっほいと喜んだものの、diffを見てみると612なのでそんなに難しくはなかったらしい。この間解いたばっかりのUnionFindの典型問題とほぼ同じだったのもそうなんだけど、どうやら計算量的にDFSでも行けたらしく、そういう側面もあるとかないとか。
そこそこ時間が余ったんだけどE問題に手も足も出せず、F問題が出来そうで出来ない気持ちでいたら時間切れ。E問題が二分探索で、解法に気付いてみれば自分の持っている道具で解けたということに気付く、が、インタラクティブな問題の場合は$stdout.sync = trueの設定を入れることを知らないと標準出力がいつまでもフラッシュされず延々とオールTLEな提出結果を眺めることになるので、やっぱり今回は5完以上を目指すのは厳しかった模様。コンテスト出るようになったころから相変わらず二分探索が鬼門。にぶたんに泣かされるたびに強くなる……と思いたい。
ということで今週も競プロ典型 90 問の続き。
やった問題
2022/09/18
- 自力AC？ 🙅
- 所要時間: 28分
まずは前日のABCでAC出来なかったE問題を解説AC。縦横がそれぞれ被らない位置にn-1個のルークが置いてあって残り1か所を置く場所を見つけるので、二分探索をしていってルークが置いてない場所を見つけていく。
当日は眠すぎて訳分からんと思っていたが、翌日洗濯物を回している間に急に解法を理解する。二分探索だけにそれはもうモーセの海割りのごとく。
行に対して以下のような検証を行い、ルークのない行を特定する。行と列を入れ替えて、列に対しても同じ検証を行う。今回の問題の制約であれば、合わせて20回以内で検証を終えることができる(らしい)。
- 行の範囲を
start=1, center = n / 2, end = n、列は全体を検索範囲として指定する(行を絞っている間、列はずっと全体指定) startからcenterまでの範囲にルークがいくつあるかクエリを投げる- 検索した行数とルークの個数が一致するかどうかで次の探索範囲を決める
- 1行を指定していて0が返されたらそこが置くべき行なので探索を終了する
- 検索した行数とルークの個数が一致していたらそこには置くべき行がないので、
start=center + 1としてcenterを再計算して2に戻る - 検索した行数とルークの個数が一致していなければ置くべき行が含まれているので、
end=centerとしてcenterを再計算して2に戻る
競プロ典型 90 問: 026 - Independent Set on a Tree(★4)
- 自力AC？ 🙅
- 所要時間: 32分
筋は良かった、筋は。 時々よくあるツリー全体を2色に塗り分けていくパターン。BFSして階層を1つ飛びに見ていったら絶対に隣り合わないし大体半分になるよね、的なところまではたどり着いたものの、たまたま見ていった方が少ない方だったらどうするのよ、的な考慮が足りずWAを重ねる羽目になる。ついでに最初の走査で塗り分けまでやらないとTLE。
2022/09/19
色々立て込んでたのでお休み(1日目)
2022/09/20
色々立て込んでたのでお休み(2日目)
2022/09/21
色々立て込んでたのでお休み(3日目)
2022/09/22
競プロ典型 90 問: 028 - Cluttered Paper(★4)
- 自力AC？ 🙅
- 所要時間: 42分
いもす法初体験。10分と経たず「これは泥臭い手段以外知らん」となり解説を読む。
入力を受けている間は目印だけ置いて行って最後にガッと集計していくイメージなんだけど、なんか2回目の集計で横着して最終結果を計算しようとしたら何故かおかしなことになったらしく、サンプル問題以外が全部WAになる。逆になんでサンプル問題は無事だったんだ。
大人しく計算が終わった後にtallyで数え上げるようにしたらあっさりAC。正直何がダメだったのかよくわからず……
2022/09/23
体調が思わしくなくお休み
