ルール(？)
- AtCoder ProblemsでRecommendされた問題のうち、Moderate以上の難易度*1のものを1問以上解く
- 日曜日スタート、土曜日はABCがあるので基本お休み(3ACできるよね、という自分への圧)
- 眠さに負けてStreakが切れてもめげない。また次の日やればいいじゃないの精神
- 虚無埋め*2を考えるくらい疲れてるなら寝る
今週のおすすめレート: 816
要するに日曜に問題を解こうとしたらリストの一番上にあった問題のレート(自分のレートに依存するのでABCにRatedで参加する度に変わるはず)
と言いつつ今週も競プロ典型 90 問の★3～4の問題をやっていきます。あとちょっと！
先週末のABC (AtCoder Beginner Contest 282)
久々のRated参加でだいぶ緊張してました。
よく寝たし、コーヒーたっぷり淹れたし、あとはやるだけ
— あのぶる+@1日1ACしたい🦥㌠ (@thatblue_plus) 2022年12月17日
ABCの3問までは何気に過去最速で通し*3、なんか怖いと思っていたらD問題(とE問題)の前に崩れ去りました。コンテスト終了後に解説を読んだところ、どちらも完全に初見のタイプの問題だったのでもう仕方ないです。
D問題がやたら難しかったのは私にとってだけではなく実際全体的な傾向としてそうだったみたいで、diffも1154でほぼ水色だし(？)、直近10回分のD問題としては一番難しかったみたい。何なら今回のD問題よりdiffが低いE問題もあるし……
やった問題
2022/12/18
- 自力AC？ 🙅
- 所要時間: 1時間24分
まずは当日めげた直近のコンテストのupsolve。
制約を確認すると、辺の数がでループも孤立点も全然ありうることが分かる。木のつもりのDFSでやるとダメっぽいなー、というところまではコンテスト中に理解。
……したんだけどここまでで完全にお手上げ。最初にイメージしたのが完全に木構造で、「even階層目の点とodd階層目のノードの末端をくっつけちゃえばいいんじゃないかな」みたいな発想になってしまったのがわりとアウトだったかもしれない。何なら別にsampleがたまたまそうだったってだけで末端である必要もないし。
ということで黙々と解説コードの写経。珍しくコメントも超丁寧に書いたので、あとで読む人が参考にしてくれたらとてもうれしい。
多分、まずこの辺の用語を理解する必要がある。(解説を読みながら調べた…)
- 連結グラフ : グラフのすべての2頂点を辺を通ることで移動ができるグラフのこと。この場合2頂点が直接接続している必要はなく、通る辺は複数でも可。
- 連結成分 : すごい雑な説明をすると、(特にグラフ全体が連結ではないときの)連結であるひと塊のこと。数学的に正確に説明すると「極大で連結な部分グラフ」。
- 2部グラフ : グラフの頂点を2色に塗り分けたとき、どのように辺を移動しても必ず2色の点を交互に通るように塗ることが出来るグラフのこと。
- 木は連結グラフかつ2部グラフの一種で、この性質を使った問題がちょくちょく登場する*4。
- 2部グラフ全体としては必ずしも連結グラフであるとは限らないというのが多分今回のポイントの一つ。
- 単純グラフ : 自己ループ・多重辺がないグラフ
- 自己ループ : 辺の両端が同じ点に接続されていること、
みたいなのとは別
- 多重辺: 辺uvのuとvの値が同じ組み合わせが複数存在すること
- 自己ループ : 辺の両端が同じ点に接続されていること、
やることは3つ。
- 全ての連結部分を走査する
- 先頭の点から順番に走査し、塗り分けがされていない点を見つけ次第DFSしていく
- すべての連結成分が2部グラフであることを確認する
- 一つでも2部グラフじゃないものがあれば何をしても全体も2部グラフにならないので、発見次第解を0として処理終了
- 各連結成分内の塗り分け結果を確認して、増やせる辺の数を計算する。全体の数から選べない選択肢を引いていく方向で考えるらしい
- 単純グラフで引ける辺の最大数は
なので、まずはそこから実在している辺の数
mを引く。= (1) - 連結成分をまたいでつなぐ場合は必ず二分グラフになるので気にする必要がない
- 「最大何本引けますか」みたいな問題で複数引くなら別だが、今回は1本だけ引くケースを考えればよい
- 連結成分内は同じ色の点どうしをつなぐことができないので、A色とB色のそれぞれで組み合わせの総数を計算して(1)から都度引いていく = (2)
- 単純グラフで引ける辺の最大数は
全ての点の走査が終わり、2部グラフであることが確認できたときの(2)の値が解となる。 しっかり咀嚼してみると確かにまぁEじゃないねDだよねってなるし、全く同じ問題ならさすがに次は解けると思うけど、まだ2部グラフへの自信はない。ただ、とりあえず解説コードを読み下せたことに安堵した日。
2022/12/19
競プロ典型 90 問: 076 - Cake Cut(★3)
- 自力AC？ 🙆
- 所要時間: 15分
これは累積和と尺取り法のコンビネーションですね！？とドヤ顔で解いたら解説を読む限りあんまり関係なかった。尺取り法はオプション扱いで、よく考えたら尺取りするなら都度最後尾を引くなり先頭を足すなりしたらいいので組み合わせることないなって思いました。まぁでも尺取り法も前のときはちゃんと使えてなかったので思い出して使えてよかったとポジティブに考えてみる。
解説を読んだ後で、むしろこれ二分探索でどうやって範囲絞るん…？と思ってもうちょっとちゃんと読んでみた。開始位置を端から決め打ちしていって範囲を絞っていくらしい、なるほど。
ポイント的にはループする構造の場合にどう終端を乗り越えるかで、配列をまるっとコピーして長さを倍にする方法が紹介されていた。データサイズさえ許せば確かにそれはシンプルかつ確実…！
2022/12/20
競プロ典型 90 問: 079 - Two by Two(★3)
- 自力AC？ 🙆
- 所要時間: 12分
結局関係なかったけど何となくいもす法を連想しつつ、まずはどうやって探索しようかなって悩む。
例えば四隅は操作手段が一択なので、端から詰めていくようなイメージで値の調整とチェックを繰り返していって、そこを起点に操作することができない右端と下端のどこかで矛盾が出たらダメっぽいし、最後まで矛盾が出なかったらカウントしておいた操作回数が答えだね、という感じでよいらしい。
提出コード、何なら事前にdiffを取る必要がなくて1回分全走査を無駄にしてるまである。
自信がなくて怖々提出したらだばだばWAが出て一瞬焦った。手元で正しい結果が出たはずののサンプルもWAだったのでおかしいなと思ってよく見たら操作に成功したときの"Yes"を出し忘れてただけだった。
ちょっと前まで「いやこれ通るの？」って怯んで解きもせずに解説読んで悔しい気持ちになることが多かったので、とりあえず思いついた方法でやってみて通ったっていうのはよい体験かもしれない。コンテストじゃないからペナルティとか気にしなくていいもんね、当日は当日で通せば勝ち精神でペナルティ積み上げても思いつく手があればめげないけど……
2022/12/21
競プロ典型 90 問: 082 - Counting Numbers(★3)
- 自力AC？ 🙆
- 所要時間: 15分
ちょっと工夫して三角数でガッと計算していく感じ。
nをn個書いたときの値の個数は三角数の組み合わせで出すことが出来るので、あとは桁数ごとに順番に桁数を掛けて行くと最終的な文字数になる。 途中三角数を求めたいのになぜかガンマ関数を使って階乗を求めようとしたり色々迷走しましたがうまいこと着地しました。
普通は扱う数字が大きすぎるので逆元取ったりするらしいんだけど、Rubyは整数の上限がないのでどこ吹く風状態で雑に解いても普通に正解出来た。
2022/12/22
競プロ典型 90 問: 084 - There are two types of characters(★3)
- 自力AC？ 🙆
- 所要時間: 17分
解説と解き方が違っていて、ちょっと一度やっておきたかったのでもう一度解いている。
atcoder.jp
処理時間的にはどっちも余裕でクリアしているものの、O(N)な分こっちの方がやっぱり速い。
最初に解いた方の考え方としては、
- 左端を決めて先頭から走査していって違う文字が出現した時点でそれ以降の部分文字列は全部条件を満たすので、その数を出していく
- 手前の文字と同じ文字であれば、条件を満たすタイミングが全く同じなので値をコピーして終わり
- 最後に出した値を全部足し合わせる(別にこれは都度やっても良さそうだけど)
という感じ。
解説の解き方ではランレングス圧縮を使う。同じ文字の塊の大きさを出しておいて、全体の数から同じ文字しか選べない組み合わせの数を順に引いていく方法。これだと前から素朴に操作していっても単純なN回のループなのでより処理時間が短く済むという寸法。
String#squeezeしたい…！とは確かに一番最初に思ったんだけど、ただsqueezeすると文字数の情報が欠落してしまうし、Array#tallyだと順番の情報がなくなっちゃうし、で考えるのやめちゃってたパターン。私こんなのばっかだな！
ABC282のD問題もそうだったけど、この手の「全体の数から数えやすい方を引いていく」という考え方にたどり着くことがまだ苦手っぽい。
2022/12/23
競プロ典型 90 問: 085 - Multiplication 085(★4)
- 自力AC？ 🙅
- 所要時間: 45分
ポイントは約数の性質を使って計算量をいかに減らすか。
最初にいきなり素因数分解をして組み合わせ計算をしようとしたせいでだいぶ道に迷ってしまい、結局解説を読んで素直に約数列を二重ループで全(?)探索する方向に落ち着く。理解が出来てしまえばこっちのもの……と言いたいところなんだけど、約数がちょうど平方根になるパターンのことをすっかり忘れるというあるあるをやらかしつつ、微妙にWA出したのちAC。 和か積かという違いはあるものの、ここまで来れば前に解いたやつの類題とも言えそう。これ自力で解きたかったなぁ。
ということでコツコツやっていた競プロ典型90問の★3★4潰しもこれで最後。よく頑張った～
他にもやりたいことがあるので毎日までは難しいけど、来週からは通常運転に戻る予定。
