ABC - D/E/F を埋めていく記事

こんにちは、あるたいるです。

現在ABCをひたすらに埋めているのですが、その中でも解説ACしてしまったものや、「これは大事だな〜」と思うやつを自分用に書き留めていきたいと思います。

ネタバレには注意！厳密さはないので注意！

ABC140 E - Second Sum

my submission

キーワード：「主客の転換」「setの上手な使い方」「大きい方から探索」

　第一印象としては、左側を固定して考える典型が見えたが、ちょっとうまくいかなそうなので、 が 答えになるような連続部分列を数え上げることにする。 より大きい値を に近い方から左右それぞれ2つ探せばOKだが…　ここまではたどり着いたものの、実装が思いつかず断念。大きい方からsetに入れつつ探すのね、納得。setのイテレータはインクリメント・デクリメントができるので、そいつをうまく使えばかなりあっさり実装できる。0-index なら と番兵をおいてシンプルにできる。

ABC155 D - Pairs

my submission

キーワード：「K番目の言い換え」「解を決め打って二分探索」「気合の場合分け」

　典型。億マス計算の上位互換バージョン。「小さい方から番目の数が である」を「 以下の数が個以上となる最小の 」と言い換えて、 を決め打ちして二分探索すればよい。ただし、正負が入り混じっているので、場合分けが必要で実装が重い。しんどい。

ABC172 E - NEQ

my submission

キーワード：「対称性」「包除原理」「撹乱順列」

　対称性から、]と決めてよく、この に対して の個数を数えればよい。ここで、「全ての に対し、」の余事象「 なる が存在する」を考える。この数は包除原理で求めることができる。「少なくとも種類の が存在し、」であるものの個数を とすれば、これは計算で出すことができ、 の偶奇によって足し引きすれば、求める数列の個数となる。

N=3,M=4 のときのメモ書き

　ちなみに、 のときの ] に対するのことを撹乱順列と呼ぶらしく、この問題は撹乱順列の個数を求める問題の拡張バージョンということができる。

ABC162 E - Sum of gcd of Tuples (Hard)

my submission

キーワード：「主客の転換」「約数系包除」「大きい方から探索」「調和級数」

　数列自体を考えるのはあまりに多すぎて厳しいので、答えが となるような数列を数え上げる。このとき、 で求まるのは「答えが の倍数となる数列の個数」であるので、これから「答えがちょうど となる数列の個数」を引けば、「答えがちょうど となる数列の個数」となる（これを約数系包除というらしい）。大きい方から計算していけば、 について考えるときには、 以上の数に対する答えがすでに求まっている。それぞれの に対し、引く数は 程度になるので、調和級数の和より となる。

ABC146 E - Rem of Sum is Num

my submission

キーワード：「indexと和の関係」「累積和」「区間の左側を固定する」

　いつもこういう系の問題をなんとなくで解いてしまっている（手で書いて試して無理やり合わせている）ので、式変形でちゃんと導けるようにしたい。この問題の場合は、累積和を取った数列を とすると、「」となるが、これを変形すると「 かつ 」となって、各 に対し、mapを用いてで求められるようになる。ABC166-E はこの問題の下位互換だが、これとほとんど同じ式変形がEditorialに乗っていたので、覚えていなかったのは反省。 

ABC132 E - Hopscotch Addict

my submission

キーワード：「頂点倍加」「Dijkstra(BFS)に帰着」

　ぱっと見強連結成分分解かなと思い、SCCあんまりよく知らないんだよな〜と言いながら解答を見たら、全然違くてびっくりした。天才解法か？と思ったけれどどうやらかなり典型っぽい。頂点倍加というよりは、状態を持つDPなんかに近い感じがする。頂点数が3倍のBFSをするだけに帰着できる。

ABC128 E - Roadwork

my submission

キーワード：「イベントソート」「座圧してデータ構造パンチ」

　ある時間に出発する人がぶつかりうる道路工事とその時間区間を管理して、時刻 における最小の要素を取り出してやればいい。ここでよくわからなくなったが、こういう「区間とその値がいくつも与えられたうえで、ある地点の値に関する何かを求めるクエリを処理する」みたいなときはイベントソートというのが典型らしい。 なる区間に対して という値が与えられたとき、これを「追加イベント 」と 「削除イベント 」に分解して記録し、ソートしてクエリごとに前からmapに追加・削除してから、mapの最小値を出力すれば良い。

　また、出てくる座標を全部座圧して遅延セグ木で殴ることもできると書いてあった。たしかに。実装でバグらせる気しかしないが…

ABC127 E - Cell Distance

my submission

キーワード：「要素の寄与を考える」「主客の転換」「マンハッタン距離はXY独立」

　「A全体に対するBの総和」に対しては、特定の要素を固定した上で、その要素が総和に与える寄与を考えるのが典型らしい。今回は特定の2点を考えて、これが全部で何回カウントされるかを考える。これは、 マスの中から マスを選ぶ通り数に等しく、 となる。このことから、この問題を「全ての点対に対するマンハッタン距離の総和を求める」という問題に帰着できた。このままでは だが、マンハッタン距離はXYを独立に考えても良いことから、主客を逆転して、「X方向の距離がで、Y方向の距離がであるものの個数を数え上げる」と考えると、 に落とすことができる。

ABC205 E - White and Black Balls

my submission

キーワード：「数え上げを経路数に落とし込む」「カタラン数」「鏡像」

　コンテスト中は包除とかを頑張って考えていたが頭がパンクした。カタラン数の概念は知っていたものの、そもそも数え上げをグリッドの経路数に落とし込むという発想がなかった。グリッドに落とし込むと跨げない直線 が現れるので、 を跨いでしまうものを引けば良い。 を跨ぐことは、 を+1だけ上側に平行移動した直線 を踏むことと同じ。ある経路が初めて を踏んだら、 に対してその前の経路の鏡像をとると、 を跨ぐ全ての経路が点 を始点とすることがわかるので、そいつらを全体から引いてやれば良い。「カタラン数を知っていますか？」というよりは、「カタラン数の導出を知っていますか？」である。

ABC163 E - Active Infants

my submission

キーワード：「greedyからDPへ」

　むずかしい… 最初はフローかと思ったけれど明らかに制約が大きくて間に合わない。そこでまず Greedy な方針を考える。ぱっと見大きい方から振り分ければいいように思えるが、それだとうまくいかない。しかし、「頂点を2つの集合 に振り分けて、その中で が大きくなる順に両端から配置する」ようにすれば正しくなる。そうなったら、DPに落とし込むことができて、「大きい方から 個使って、そのうち 個を左端に寄せた時の最大値」としてやればOK。このテーブルを思いつくのが結構しんどそうではある。

HHKB2020 D - Squares

my submission

キーワード：「余事象」「長方形の重なり判定」

　しんどい数え上げ。まず、重ならないやつを数えるより重なるやつを数えた方が良さそうなのは比較的すぐ見える。ここから、片方の正方形を固定して考えようとしたが、これはかなりの泥沼。長方形が重なっている条件は『「縦の辺が共通部分を持つ」かつ「横の辺が共通部分を持つ」』であるので、縦横分けて考えてOKだということに気付くのがポイント。こうすることで、1次元上で重なる2線分の数え上げに帰着できる。これはゴリゴリ場合わけをしても数えられそうだが、もう一度余事象に登場してもらって、重ならない2線分を数え上げるのが簡潔。

ABC197 F - Construct a Palindrome

my submission

キーワード：「回文は両側から見る」「操作に対応するグラフを考える」「Dijkstraに帰着」

　前と後ろの両方から辿るのが良さそうというのはすぐに思いついたが、ここで行き詰まった。典型テクとして、「操作に対応するグラフを再構築する」というものがある（頂点倍加の発展系）。今回は(前,後ろ)の状態を頂点として、遷移可能かどうかで辺を張れば良い。あとは頂点 からDijkstraして、 あるいは （u-w間には辺が存在する）までの距離を調べればOK。

ABC206 F - Interval Game 2

my submission

キーワード：「盤面を分割する」「Grundy数」「区間DP」

　不偏ゲームなので、Grundy数が使えそう。Grundy数は盤面に振り分けられるので、順当に考えると盤面は 通りある。しかし、ある操作を行うと盤面が右と左に分かれるので、もとの盤面のGrundy数 「右のGrundy数」xor「左のGrundy数」で表される。したがって、「区間 [left,right) におけるGrundy数」とすれば、区間DPができる。