ABC249感想・反省
A問題
最近よく見る問題。6分半でコードは書けていたが、手元の環境が重くatcoder-toolsでTLEとなってしまったのでその原因を考えていて、結局8分余りでAC。
B問題
やるだけ。5分でAC。
C問題
bit全探索。7分で書けたが、バグ取りに1分半ほどかかった。
D問題
最近調和級数で痛い目を見ていたのですぐ気付いた。実装も軽かったので9分ほどでAC。
この時点で31分経過しており、500位台と悪くはなかったもののCまでで時間を食ってしまったことから焦っていた。順位表を見てEとFのAC数が同程度なのを確認し、Eを見た。
E問題
解法自体はすぐ分かったが、実装で混乱。結局コンテスト内には終わらず、76分かかってAC。しかし、22:39:30時点のコードの軽微なバグを１つ直すだけで通ったので、落ち着けば通せたかもしれない。
F問題
問題を見て割とすぐに解法が分かった。しかしt=1と2を逆にしていたり、t=1のクエリを見た後に無視できる数を１つ減らすのを見落としていたりで時間がかかり、結局34分でAC。
反省
序盤で手間取ると焦ってしまい全ての問題を見る精神的余裕がなくなる。焦らないようにするのと、そもそも早解きができるようになるべき。
ABC155F Perils in Parallel
問題文
AlDebaran 王国の侵攻によって、AtCoder 王国の各地に爆弾が仕掛けられてしまいました。
幸いにも AtCoder 王国 ABC 隊の健闘により制御装置の一部が手に入ったので、あなたはこれを使って解除を試みることにしました。
仕掛けられた爆弾は N 個あり、1 から N の番号がついています。爆弾 i は座標 Ai にあり、電源は Bi=1 のときオンに、Bi=0 のときオフになっています。
制御装置には M 本のコードがあり、1 から M の番号がついています。コード j を切ると、座標が Lj 以上 Rj 以下の全ての爆弾の電源のオン・オフが切り替わります。
切るコードをうまく選ぶことで全ての爆弾の電源をオフにできるか判定し、できるならばそのようなコードの組合せを 1 つ出力してください。
制約
- 入力はすべて整数
- 1 ≤ N ≤ 105
- 1 ≤ Ai ≤ 109 (1 ≤ i ≤ N)
- Ai は互いに相異なる
- Bi は 0 か 1 のいずれか (1 ≤ i ≤ N)
- 1 ≤ M ≤ 2 × 105
- 1 ≤ Lj ≤ Rj ≤ 109 (1 ≤ j ≤ M)
競プロ道場鯖の set e の 2-6 。
「[l, r]を反転」は、
「[0, l-1]及び[0, r]を反転」
と言い換えられる。また、隣接する要素同士のxorを取った数列 {Ci} (C1 = B1, C2 = B1 xor B2, C3 = B2 xor B3, ... , Cn = Bn-1 xor Bn, Cn+1 = Bn)を考えると、
「ClとCr+1を反転」
と言い換えられる。
また、グラフを考え、Ciをグラフの頂点 i に対応させると、
「頂点lと頂点r+1の間に辺を張る」
と言い換えることもできる。ただし、Ciは頂点iの次数だけ反転されるものと考える。
ここで、{Ci}は要素がn+1個になっており、余分な自由度が1増えているように見えるが、この数列の要素の全てのxorを取ると0になる、という隠れた制約があるので自由度は変わっていない。（各Biが2回登場するため）
{Bn} = (0,0,...,0) ⇔ {Cn} = (0,0,...,0) なので、頂点iの次数の偶奇が{Cn}の初期値と一致するように辺を張ればよい。これは各連結成分について適当な全域木を取って葉から考えればよい。
全域木を考えればよい理由だが、「全域木に含まれる辺だけでは条件を満たす解が構築できない⇒元のグラフでも条件を満たす解が構築できない」が示せればよい。
全域木で条件を満たす解が構築できないのは、葉から順に考えて最後に残った頂点が条件を満たさない場合である。ある辺について、その辺を使うにしても使わないにしても全頂点の次数の和の偶奇は変わらない。考察を進めると、連結成分に含まれる頂点のうち、次数が奇数となるべきものの数が奇数となることが条件を満たす解が構築できない必要十分条件であることが分かる。逆に解が構築できるなら、全域木で考えて葉から考えていって残った最後の頂点は条件を満たしていることが分かるだろう。よって、全域木で考えればよい。
葉から順に考える方法として、オイラーツアー風にDFSをする方法と、辺を削除（実際には各頂点の次数を記憶しておいて、それを減らしていけばよい）していく方法がある。どちらでも計算量は変わらず実行時間もほぼ同じだ。
以下の実装ではオイラーツアーを採用している。
ABC219E Moat 深さ優先探索でお堀を調べ上げる別解
問題文
xy -平面上のいくつかの点に村があります。
高橋君はこれらの村を民兵や魔女などの外敵から守るため、これらのすべての村を囲むようなお堀を建設します。0 と 1 からなる 4 × 4 行列 A = (Ai, j) が与えられます。
Ai, j = 1 を満たす整数の組 (i, j) (1 ≤ i, j ≤ 4) ごとに、座標 (i-0.5, j-0.5) に村があります。お堀は平面上の多角形です。 高橋君は以下の条件をすべて満たすお堀を建設します（入力例１・出力例１の説明も参考にして下さい）。
- 自己交差がない
- 内部にすべての村を含む
- すべての頂点の x 座標と y 座標は 0 以上 4 以下の整数
- すべての辺は x 軸と y 軸のどちらかに平行
- それぞれの内角の大きさは 90 度または 270 度
高橋君が建設するお堀として考えられるものが何通りあるかを出力して下さい。
制約
- Ai, j ∈ { 0, 1}
- Ai, j = 1 となる (i, j) が少なくとも 1 つ存在する
模範解答ではお堀の候補を調べるのではなく、お堀の内部に含まれるマスの集合の候補を216通り全探索している。自分にはこれは思いつかなかったので、お堀の候補を調べることにした。
そうするとこの問題は
- 平面上の閉路（お堀）を全て列挙する
- 列挙された閉路にたいして、閉路の内部に全ての点（村）が存在するか調べる
1.については類題として
競プロ典型90問 072 - Loop Railway Plan（★4）
があり、自分は解けていなかったが問題の存在は覚えていたので模範解答のコードを元に今回の問題のコードを書いた。
2.については、村は高々16個なのでそれぞれの村についてお堀の内側にあるか外側にあるかを判定すればよい。点の多角形に対する内外判定については以下のサイトに載っている。
今回用いたのはCrossing Number Algorithmで、内外を調べたい点から半直線を出し、その半直線が多角形の辺と交差する回数を調べるという方法。奇数回交差するなら点は多角形の内側にあり、偶数回交差するなら外側にある。今回は閉路の水平な辺としてありうる4×5=20通りの辺に対し、その辺が閉路を構成するかどうかを記憶しておいて、各村の真上にある水平な辺のうち、閉路を構成するものの数を調べることにした。
なお、辺が閉路を構成するかしないかの2値で記憶していると、ある辺が閉路において2回以上使用されている場合に内外判定がバグることに注意。基本的にはこのような閉路はそもそも調べる段階で除外できるが、長さが2の閉路は特別に除外しなければならないので、閉路を調べる際にその長さも記憶しておこう。
コード
Submission #25961803 - Sciseed Programming Contest 2021（AtCoder Beginner Contest 219）
