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を一つ求める方法で解ける。