estie プログラミングコンテスト2024 （AtCoder Regular Contest 188）

　Bまで二完。Aは本質が分かっていなかった（DPの状態数が少ないはず、と思って投げただけ）ので、通って運が良かった。

コンテストへのリンク

コンテスト後のツイート

estie プログラミングコンテスト2024 （AtCoder Regular Contest 188） AB二完。
A 計算量が分からないDPを祈って投げたら間に合った。（score,なし,A,B,C,AB,BC,CAで終わっている個数をもつ）
B Nが奇数ならgcd(2*K,N)=1。偶数ならgcd(2*K,N/2)=1。
C 2-SATっぽさを感じたが考察進まず終了。

— titia (@titia_til) November 23, 2024

C - Honest or Liar or Confused 

　2-SATを使って解けるという情報を得て、考えてAC。

　人の状態は、「正直」「嘘つき」「混乱正直」「混乱嘘つき」の四通りだが、これそのままでは扱いにくい。

・0:正直 or 混乱嘘つき, 1: 嘘つき or 混乱正直, 2: 正直 or 混乱正直, 3: 嘘つき or 混乱嘘つき

　の四通りの状態を考えると、0と1は背反、2と3は背反であり、各証言について辺を引くことができる。たとえば、AがBを正直と証言したことは、Aの0→Bの2と、Bの3→Aの1、と辺を引くことになる。

　これで、矛盾するかどうかの判定はできる。

　が、その後、誰が混乱しているか一つ挙げる方法が分からず時間がかかった。（というか、そもそも2-SATでvaluationを一つ求める方法を忘れていた。SCCした後ろから順に見て、先に現れたvaluationにすれば良いのですね）

　重要なのは、最初あげた四つの情報のうち、二つが分かれば、「正直」「嘘つき」「混乱正直」「混乱嘘つき」のどれか確定するということ。

　これに気付ければ2-SATでvaluationを一つ求める方法で解ける。

Codeforces Round 944 (Div. 4)

　最後の問題が解けず。

コンテストへのリンク

H. ±1

　2-SATという情報を得てAC。

　この前のABCでは2-SATじゃないかと嘘考察してハマったのに、実際に2-SATが出たら解けなかったのは情けない。

　ただ、最初見たとき2-SATは疑ったので、時間があって落ち着ければ解けていたと思う。

yukicoder contest 344

　最後二問残しの13完。

コンテストへのリンク

コンテスト後のツイート

J グラフを作って、遠いところへ飛んだボールから、そこへ届く人を探す。
K 差分を管理してシミュレーション。どこを消したかはBITで管理。
L 桁が一つずつずれていくので、途中の桁は一気に計算。
M あるxでの個数score(x)が分かれば二分探索。score(x)は再帰で実装できた。

— titia (@titia_til) May 20, 2022

No.1954 CHECKER×CHECKER(2)

　解説は見たけど、（パッと読んだだけではよく分からなかったので）大体自力でAC。

・まず、市松模様の片方のマス達を反転させる。

・S[i][j]とS[i+1][j]が異なる色なら、iまでの範囲を反転させる操作が必須。（jについても同様）

・S[i][j]とS[i+1][j]が異なる色なら、全てのjについてS[i][j]とS[i+1][j]は異なっていなくてはダメ。（jについても同様）

　を実装したらACでした。

　これで必要十分なのかはあまり分からずに書いたけれど、これで大丈夫そうですね。

　解けても良かった問題ではあるのだけど、もっと「これ」というような典型手法を使うんじゃないかと思ってしまい、こういう方向性では考えていなかった。

No.1955 Not Prime

　解説で2-SATだということを知ってAC。

　2-SATを使うのが久しぶりで、内容を忘れていた。

　論理式をCNFに変形し、$(a\vee b)=(\neg a \rightarrow b)\wedge (\neg b \rightarrow a)$と変形する。$\neg a $から$b$への辺と、$\neg b$から$a$の辺を貼り、SCCを作って、$x$と$\neg x$が同じ強連結成分に含まれないか調べる、という流れ。

　今回は、「Sに含まれる」を$x$とすると、「Tに含まれる」が$\neg x$となることに注意して論理式を書けばOK。

　2-SATだと分かった後も苦戦してしまったのは反省。

　

AtCoder Beginner Contest 210

 　ABCEの四完。Dは結構思いつきにくい気がする。Fは難し過ぎませんか？

コンテストへのリンク

コンテスト後のツイート

D - National Railway

　解説AC。

　難しい！　DPは全く思い浮かばなかった。マンハッタン距離だから、45度回転ばかり考えてたのが敗因か。

F - Coprime Solitaire

　色々解説を読んだけど、主にkyopro_friendsさんの公式解説でAC。

　2-SATに帰着する問題。

　2-SATに帰着できるということは、コンテスト中は思いつかなかったけれど、言われれば確かに、という感じ。少し慣れている人なら思いつけそう。

　だけど、その後の処理は難しすぎませんか？

　累積和を使えば二乗から線形に計算量を落とせる、と。これは思いつける気がしない。

　結構すんなり解けている人もいるようなのだけど、典型テクニックなのだろうか……。

　さらに、データの持ち方が悪いとTLEしたり、再帰を使ったSCCだとTLE+MLEしたりと大変でした。（ので、SCCは借りてACしました）

　非再帰のSCCは実装しないとまずいですね。