2023/5/18~2023/5/24 - 仮のブログ

サークルの先輩が実に日記をつけていて良いなと思ったので今日から日記をつける.
過去に日記三日坊主経験もあり性格上長続きしない気がするがとりあえず続くところまで.

2023/5/18 (木)

8:30頃起床. ゴミ出しを済ませたり布団で本を読んだり朝ごはんを食べたりをし, オンライン講義の2限を受けるためPCに向かう. しかし, 勘違いをしており講義は1限であり, 既に終了していた. 出席等の概念は無いし, 講義ノートや動画が後からGCにあがるので被害は軽微.

その後はセミナー発表の確認をした後昼頃に青葉山へ.
昼食に豚野菜炒め丼を食した後, 原稿の確認をしていたらより簡潔な証明ができる場所を見つけたため修正.

15:00 からは四年セミナー. メンバーは5人であり, 2冊の本に分かれている. 木曜は楕円関数論に関する本で, 私ともう一人がこちらの班に属する.
そのもう一人が今日は都合でお休みだったため, ソロライブとなった.
本の流れ的には代数多様体の正則な点での局所環に離散付値を入れる話であったが, 相方が休みのこともあったので本の内容は余り進めずに離散付値環周りの話をした.
発表と担当の先生からのコメントを合わせて2時間半くらい.

その後友人宅に寄り道したのち帰宅. 適当な夕食を済ませた後, 競プロの精進をしようとして, そういえば昨日AtCoder黄色diffを埋め終わったことを思い出しTweet.

黄色以下を埋め終わった!! pic.twitter.com/ynd0ohkr2u
— 仮の人数学+競プロ (@kari_math) 2023年5月18日

結構反応がもらえてちょっと嬉しかった. (いつもよりFF外からの反応も多いのは先日に若干注目されたTweetをしたためおすすめとかに出やすくなっていたとかあるのだろうか?)

ここ数日していた黄diff埋めが終わってしまったので適当な橙diffを解くことにした.
F - Sorting a Matrix
これはコンテスト中にSubmitはしたけど解けていなかった問題.
改めて考えると, まず列と行を独立に考えて良いことに気づく.
行の並べ替えの方は簡単で, 列の方は少し厄介.
列の組で片方が片方の左側に来るといった制約が生えるので, それらが全て満たせるか, すなわち制約を有向辺と思ったときにDAGかの判定をすれば良い.
ただし, 愚直に辺をはると, 最悪で $\Theta(HW^2)$ 本もの辺が生えて大変なことになるので超頂点を適当に設けて回避する.
これらの方法は大体公式解説のものと一緒だった.

その後は布団でぐーたらしていたが, そのまま寝るのも味気なかったのでこどふぉのバチャをすることにした.
https://codeforces.com/contest/1800

A: Is It a Cat?

入力では大文字小文字の区別があるが, その後は区別する必要が無いのでまず大文字を全て小文字に変換しておく.
後は文字列を前から見ていって, "meow" の何文字目までが出現したかを見ていけばよい. 見ている段階で現れてはいけない文字が出てきたかも同時に判定する.
後から思えばランレングス圧縮的な方針の方が楽だったかもしれない.
https://codeforces.com/contest/1800/submission/206348403

B: Count the Number of Pairs

まずペアがあれば貪欲にペアにしてよい.
これが終わると, 各文字に対して, 大文字と小文字の一方のみが残る. そのうちの半分をもう一方に変換するのがペアを最大にする方法なので, 変換回数が残っている限りこれをする.
https://codeforces.com/contest/1800/submission/206348735

C1,2: Powering the Hero

操作を言い換える.
bonusカードを全て山に積み, heroカードが出た時は山に積んだbonusカードから好きな一枚を選ぶとする.
一見できることが増えているようだが, これで選びうるbonusカードの集合は元のルールでも選ぶことができることは容易に分かる.
言い換え後の操作では明らかに山に積んだbonusカードから最も大きいものを選べばよく, これは優先度付きキューなどで実装できる.
https://codeforces.com/contest/1800/submission/206349053

D: Remove Two Letters

最初は, 異なる箇所から2文字除いて, 同じ文字列となるのは, 同じ文字が連続する箇所だけかと思ったが, これは最後のサンプル ("ababa") で棄却される.
次に, ローリングハッシュを使うことを思いつく.
2つの文字列の連結も, 適当な冪を掛けることで可能なので, 取り除く $N-1$ パターン全ての文字列のハッシュ値を $O(N)$ で求めることができる.
ハッシュ値を決める多項式において, 冪の並ぶ順番を逆向きに勘違いしていたせいで実装に苦戦してしまった.
https://codeforces.com/contest/1800/submission/206353874

E1,2: Unforgivable Curse

まず隣合う二文字がswapできるかを考えたい.
一番swapさせにくいのは真ん中の文字であるので, これとその隣がswapできる条件というのを探ることにする.
すると, 真ん中の文字が1回でも動かせれば, その隣の文字とのswapが可能と気付く.
手順は以下の通り. (真ん中の文字 $s_m$ とその左隣 $s_{m-1}$ をswapする場合)

$s_{m},s_{m+k}$ をswap
$s_{m-1},s_{m+k}$ をswap
$s_{m},s_{m+k}$ をswap

これで, 元の状態からは $s_{m},s_{m-1}$ のみが入れ替わることになる.

真ん中以外もほぼこれと同様に出来るので, 結局1回でも動かせるもの同士は任意にswap可能.
(これはバチャ中にこう思っただけで, 実際には動かせる文字, 動かせない文字, 動かせる文字が並んでいる場合に動かせる文字同士をswapできるかはこの段階では非自明であるので別途証明する必要がある. )

よって, 動かせない文字の場所が2つの文字列で一致しているかを判定すればよい.
https://codeforces.com/contest/1800/submission/206349991

F: Dasha and Nightmares

この問題は結構好きである.
まず, 使わない文字を1つ固定すると, その文字を含まない文字列同士の組で, それ以外の文字は全て計奇数個含むようなものを数えればよいことになる. (文字列長の偶奇は自動で満たされる.)
まず, 使わない文字を含む文字列は省いておく.
各文字列について, どの文字を奇数個持つかを表す集合を用意して置くと, 二つの文字列がペアになれる必要十分は, それらの集合が交わらないかつ, 和集合が全体になることである.
よって, 集合をbitで管理するなどして, 連想配列に入れる等すれば良い.
固定した使わない文字を変えた時に同じ組を重複して足す恐れはないため, 単純に足し合わせればよい.
https://codeforces.com/contest/1800/submission/206355184

G: Symmetree

問題名が好き.
解法自体は, 各頂点に対して, その頂点を根とした部分木が左右対称かを木DPでボトムアップに求めていけばよい.
遷移の際に, 木の同型判定が必要なので, 事前に各部分木のハッシュ値を求めておく.

木DPの遷移は, 各子のハッシュ値を並べ, 同じもの(=同型なもの)があれば, ペアにする.
その後は,

ペアにできなかったものが複数あれば, 左右対称でない.
ペアにできなかったものが1つあれば, その残った子の部分木が左右対称かに依存する.
ペアにできなかったものがなければ, 左右対称である.

という判定ができる.
木の同型判定パートは実装が簡単な $O(N\log{N})$ の決定的なものでも余裕で間に合って良かった.
https://codeforces.com/contest/1800/submission/206358160

総括

91分全完32位. 良い方な気がする. Cの後間違えてEを開いてしまったが, Dの方が時間がかかる問題だったため, 結果としてスコアが良くなった.

その後この日記に解法をメモって就寝.

2023/5/19 (金)

6:30起床. 朝食身支度を済ませて大学へ向かおうとした瞬間雨が降り始めた. ただでさえ混む地下鉄がより混んでいてややげんなり.

1限から昼過ぎまでは4年セミナー.
今日はSerreの『数論講義』(の英語版)を読む班で, 昨日あった楕円関数論班でない3人がこちらに属する.
私はこの本を和書版で3年講究セミナーをしていたのでしばらくは既習内容が続く.
そのため, 適度に助け船とかを出しやすいというメリットはあるのだが, 早起き+ある程度既知の内容を聞くということで睡魔と闘う必要もあり大変.
今日は $Q_{p}$ の乗法群まわりの話だった.

13時頃にセミナーが終わり, 辛口カレー丼を食べた後下山.
どうやら同級生が卒業アルバムの写真を撮りにいくらしいので便乗することにした. 相変わらず眼鏡のせいで限界まで顎を引くよう指示されてしまうのでかしこまった写真は苦手である.

この後は睡魔が限界になってきたので帰宅して仮眠をとった.
19時頃に起床して夕食.
この日は試しに冷凍させていたもやしを使うことにした.
買い物した後しばらく数日バタバタすると足の速いもやしが痛んでしまうので冷凍もやしを試してみて良さそうなら購入後即冷凍することにしようという魂胆である.
調理方法はひき肉と卵でとじながら炒めて中華調味料で味をつけるというシンプルなものにした.
結論から言えば十分美味しく食べられるが, 冷凍しないものからは遥かに劣るといった感じであった.
もやし内の水分が凍って解凍時に流れるようで, シャキシャキ感がかなり弱まってしまった.
消費期限が迫ってきたら冷凍庫で数日延命くらいの向き合い方が良さそう.

夕食後は昔買った小説を読んでいたが内容があまり面白くなかったので今日もこどふぉのバチャをすることにした.

https://codeforces.com/contest/1811

A: Insert Digit

前から見ていって, 追加する数より真に小さい数が現れたらその直前に追加するのが最適である. そのような箇所が無ければ末尾に足す.
https://codeforces.com/contest/1811/submission/206475276

B: Conveyor Belts

外周からの距離の差を考えればよい.
https://codeforces.com/contest/1811/submission/206479563

C: Restore the Array

両端は直ちに分かる.
それ以外のところは, $a_{i+1}=\min(b_{i},b_{i+1})$ とすれば良い.
この変換は, $b_{i}\le max(a_{i},a_{i+1})$ を $b_{i}\le a_{i}$ かつ $b_{i}\le a_{i+1}$ と思うと気付きやすい.
こうしてできた数列が条件を満たすとは限らないが, 今回は条件を満たす数列が存在することが制約で保障されているのでOK. https://codeforces.com/contest/1811/submission/206481969

D: Umka and a Long Flight

各サイズの正方形は2個以下とあるが, この制約を満たそうとすると, $n+1$ 個のピースは1辺を $F_{1},F_{1},F_{2},F_{3},\dots,F_{n-1},F_{n}$ とするものに限られる.
さらに, これらの正方形の位置を決定しようとすると, 可能性は左右(上下?)のどちらかに詰めて配置するしかない.
すると, 残りのマス目及び正方形は, 全て $n$ を $n-1$ に置き換えた状況になる.
また, ここで配置した正方形に, $(x,y)$ が重ならないような配置は, 存在するなら1つだけである. (すなわち左右どっちに詰めるかで再帰的に場合分けが増えることはない.) https://codeforces.com/contest/1811/submission/206490500

E: Living Sequence

この位置の問題としてはかなりeasyに感じた.
10進法の数が与えられるので9進法に変換するだけである. (ただし用いる数は4を除いた9個の数)
https://codeforces.com/contest/1811/submission/206493130

F: Is It Flower?

問題文が弱い上にサンプルが不親切(YESケースをもう一個置いてくれ～～)だったので飛ばして結局戻ってこなかった.

G1,2: Vlad and the Nice Paths

DP $\lbrack c \rbrack\lbrack i \rbrack\lbrack k \rbrack$ を, 既に $i$ ブロックが決まっていて, 色 $c$ を $k$ 個目まで列を作っている場合の数として定める.
但し, 丁度 $i$ ブロック作り終わった状態というのは別で持たせておく.
これは一見状態数 $O(n^3)$ , 遷移 $O(1)$ で間に合わないような気がするが, 作れるブロックの数が最大で $n/k$ 個なので, 状態数 $O(n^2)$ , 遷移 $O(1)$ となって間に合う.
しかし, この方法には一つ問題があり, mod をとった後 $0$ となったのかもともとが $0$ なのかが区別がつかないのだ.
そのため, 同様の方法で, 存在/非存在のみをbool値でもたせるDPを追加したが, これがかなり大変だった.
二つのDPを同時にするとMLEしてしまい, 分けるとTLEしてしまい, お茶を濁したらWAになった.
結局, 定数倍高速化+二つのDPを分けるという方法でなんとかなった.
https://codeforces.com/contest/1811/submission/206539959

総括

7完7ペナ106位. G問題があちらをたてればこちらが立たずでとても苦しかった.

バチャが終わったらdiscordに人がいたので雑談を聞いた後就寝.

2023/5/20 (土)

起きたら15:00で布団でごろごろしていたら19:00に. 買い物と夕飯を済ませたら20:00を過ぎていた. ABCにも出ずにそのままグダグダしていた.

2023/5/21 (日)

午前はセミナーの資料作りをした. 夕方ごろから前日のABC302のバチャをした.
https://atcoder.jp/contests/abc302

A: Attack

切り上げ.

B: Find snuke

8近傍直線探索.
dy={1,-1,0}, dx={1,-1,0} として, $3\times 3$ の方向を探索すると楽.

C: Almost Equal

順列全探索で通る.

D: Impartial Gift

$A_i$ を固定したら $A_i+D$ 以下の最大の $B_j$ を選ぶのが最適.
考えるよりコピペで書くのが早そうだったので $B_j$ を固定したverも書いておいた.

E: Isolation

次数を愚直に管理する.
削除される辺の本数の総和は高々追加された辺の本数の総和であるので十分少ない.

F: Merge Set

集合の番号と集合に含まれる数の間に辺を張ると最短経路に帰着される.

G: Sort from 1 to 4

1,2,3 のスワップで正しい位置に来るものをカウントしておくと, 少ない方から貪欲が最適らしい. かなり早解きされていたので投げたら通った.

Ex: Ball Collector

UndoDSUを持っていなかったので人のコードを見ながら整備も兼ねて解いていたら細かい所を詰め切れず時間切れになった. 後からAC.

21:00 からはAGC062に参加. 1完で激冷え.

AGCがあまりにも悔しかったのでその後こどふぉのバチャをした.
https://codeforces.com/contest/213

A: Game

コンピュータ間の移動が複雑なようだが, 実は $1\to2\to3\to1\to\dots$ の移動のみで良い.
また, できるタスクがあれば常にしてよい.
よって, 最初のコンピュータを決め打ったら後は貪欲に出来る仕事をしながら上記の移動をするのが最適となる.
https://codeforces.com/contest/213/submission/206763377

B: Numbers

先頭の数を固定する.
DP $\lbrack i\rbrack\lbrack j\rbrack$ を, $0,1,\dots,i$ まで数字を計 $j$ 使ったときの, $\prod_{k=0,1,\dots,i}\frac{1}{b_{i}!}$ とする. $b_{i}$ は数字 $i$ を $b_{i}$ 個使うことに対応する.
条件を満たすようなところだけ遷移させれば目的の値が得られる.
https://codeforces.com/contest/213/submission/206764701

C: Relay Race

良くあるグリッド上のDPで, 現在地の情報を2点分持たせて更新すればよい.
その時, 同じ位置を通ったかの処理が面倒になるので, 常に2点の, $x$ 座標 $+y$ 座標が同じ値になるように遷移させていく.
また, なんかバグらせを踏んでしまったので, 始点と終点の両側からDPして, 真ん中で結果をマージした.
https://codeforces.com/contest/213/submission/206767288

D: Stars

水平に $N$ 本分対角線を一直線に引き, 始点に戻りながら星を形成していく.
https://codeforces.com/contest/213/submission/206769844

E: Two Permutations

時間が足りず見ていない.

総括

4完で30位.

その後就寝.

2023/5/22 (月)

8:30に起きてゴミ出しやら掃除をした後, セミナーの資料作成の続きをした. 週末中に完成させるつもりが怠惰していたら月曜になってしまい申し訳なさみ.

昼過ぎからはコドフォのバチャ https://codeforces.com/contest/1833

A: Musical Puzzle

連続二文字をsetに突っ込んでサイズを出力.
https://codeforces.com/contest/1833/submission/206798484

B: Restore the Weather

$a,b$ をどっちも昇順に並べればよい.
https://codeforces.com/contest/1833/submission/206798658

C: Vlad Building Beautiful Array

偶奇を固定する.
すると, 目標と偶奇が一致していない場合, 奇数を引くことで調整しなければいけないが, この奇数は最小の物をとればよい.
実際は, 奇数の有無等で最終的な偶奇も一方のみが適することが分かるがどっちも試しても問題ない.
https://codeforces.com/contest/1833/submission/206798981

D: Flipper

$N=1$ の時は良い.
基本的には, $N$ を先頭にすることができる. これができないのは, もともと先頭が $N$ の時で, この時は先頭が $N-1$ となる.
先頭が決まれば, それを先頭に持ってこれるような $(l,r)$ の組は $O(N)$ 個となるので, 全て試して辞書順最大を求めればよい.
具体的には, 先頭に持ってきたい数のindexを $m$ とすれば, $r=m,m-1$ の時が適する.
https://codeforces.com/contest/1833/submission/206799709

E: Round Dance

隣り合う人に辺を結ぶと, サイクルかパスとなる.
サイクルはそれ以上手を施すことができず, パスは他のパスとつなげるか, 両端を閉じてサイクルとするかを選べて, 前者をたくさんすれば最小値を与え, 後者をたくさんすれば最大値となる.
https://codeforces.com/contest/1833/submission/206800237

F: Ira and Flamenco

現れる数を重複を取り除いて昇順に並べた物を $p_{1},p_{2},\dots,p_{k}$ とする.
すると, $p_{i+M-1}-p_{i}=M-1$ となるような $i$ に対して, $p_{i},p_{i+1},\dots,p_{i+M-1}$ の値を持つ人を一人ずつ連れてくれば良い集合になって, またこれに限る.
後は各値を持つ人を数えておいて人数の累積積を用意しておけば各 $i$ に対して $O(1)$ で組み合わせ数を計算できる.
https://codeforces.com/contest/1833/submission/206800718

G: Ksyusha and Chinchilla

木DPで葉側から貪欲に枝を作っていく. 子の頂点のうち, いくつが枝に属していないかを計算していく.
枝に属さない子が多い場合は枝分割が不可能. そうでない場合は, 上に持ち上げる.
https://codeforces.com/contest/1833/submission/206801566

総括

ノーペナ全完12位!! 素晴らしい!!

適当に夕食をとった後, TLに流れて来た問題を解いたり院試の過去問を解いたり.

院試は東北大のH26年度.
解析が若干面倒だが後は簡単目な気がした. 位相やその他枠が簡単なので望む傾向とは結構離れて居るけど解けたっぽいのでヨシ.

就寝前にこどふぉのジムにある良く分からんコンテストのバチャ

Dashboard - Олимпиада школьников РС(Я) (5-8 классы) 2022-23, 1 день - Codeforces

ルールが分からんのでコピペなし, 翻訳機OKとした.
難しくは無いし, これと言って面白い問題も無かったので詳細は書かないことにする.

2023/5/23 (火)

7:30 起床. あさかつに出る. まずはあさかつARCから
あさかつARC
A: Sum and Product O(sqrt) のいつものやつである. 積の方が圧倒的に候補を絞りやすい.
B: Copy and Paste Graph ワーシャルフロイドで, 対角線の初期化をしなければ良い.
C: String Invasion 前からみて, 同じ文字が2つ並んでいたらその文字に何回変更するかはほぼ残り文字数で決まる. 変更予定の文字と同じ文字が出てきたらごにょごにょする.
D: Swaps 2 A_i+i が操作によって変わらないことが分かる. よって, この変換をすれば, 単に隣接swapで並べ替えられますかという問題となる.
E: I Wanna Win The Game 2進法の下の桁から決めるDPをする.
総XORが0というのは全ての桁でbitが立っているような変数の数が偶数個という事である.
下から何桁確定させて, 今の総和がいくつの場合の数を持っておく.
遷移は対称性を生かして二項係数で計算できる.
F: LEQ and NEQ 1週間前くらいに解いたので解法を覚えていた.
stackを使って包除原理させながら遷移をする.

その後時間が余ったのであさかつnotARCの方にも出たがラスト問題の実装が間に合わなかった.

シャワーを浴びた後青葉山登山.
2限は代数の講義で, 前回から層の話に入った.
前回休んだことをすっかり忘れており, 1回分のブランクがあったので話についていくのが大変だった.

昼食後は資料室に行って本を漁った後, 学生室で競プロと院試の勉強をした.
競プロはLibrary Checkerを適当に解いた. LCAをずっと人のをパクっていたので一度一から書き直して, Jump on tree にも対応させた.
院試は東北のH27の共通を途中まで解いたところで飽きたのでH26の専門を解いた.
代数2問はとんとん解けて残りの一問は見た目が面白かった大問6を解いた.
二項係数に関する問題で, 非自明な結果が出てきて見た目に違わず面白かった.

下山後サークルの定例会.
最後の問題が面白かったが途中嘘考察をはさんでしまったまま実装してしまって間に合わなかった.

帰宅後布団にごろんてたら転寝してしまい, 目を開けた時には一日がほぼ終了していた. かろうじて買い物に行き, そのまま就寝.

2023/5/24 (水)

昼頃起床.
数学等をした後, 2時頃からこどふぉバチャ

https://codeforces.com/contest/1816

A: Ian Visits Mary

1回で行けない場合, $(x-1,1),(1,y-1)$ のどっちかを挟めば2回で到達可能.
https://codeforces.com/contest/1816/submission/207007845

B: Grid Reconstruction

各マスを通った場合正の寄与か負の寄与かは一意に定まる.
正の寄与に大きいのを配置し, 負の寄与に小さい値を配置.
後はいい感じにしたら通った.
https://codeforces.com/contest/1816/submission/207008190

C: Ian and Array Sorting

奇数の時は, 上手く操作すると, 一点加算, 一点減算ができるので, 任意の数列を昇順にできる.
そうでない場合, 一点操作ができないため, 端から貪欲に前 $n-1$ 項が等しくなるように操作をしたのちに最後の一項が小さくないかを判定すればよい.
https://codeforces.com/contest/1816/submission/207008695

D: Sum Graph

面白い.
$x=n+1,n$ をすると, グラフが直線グラフになる.
その後の $n-1$ 回のクエリで, 端を確定させる.
その後の $n-1$ 回のクエリで, 端からの距離を確定させる.
これで, 確定させた端がどちらの端にするかによる2パターンの順列が求まる.
https://codeforces.com/contest/1816/submission/207010807

E: Between

$b\to a$ で辺を張り, 頂点 $1$ から最短経路距離 $+1$ を求めると, これが数列にその数字を置ける数の最大値になる.
ただし, 到達できない頂点があれば答えはINFになる.
最大値を求めた後は, 以下の通りに配置すればよい.
丁度 $n$ 個配置する数の集合を $D_n$ とすると,
$D_m\to D_{m-1}\to D_{m}\to D_{m-2}\to D_{m-1}\to D_{m}\to\dots,D_{1}\to D_{2}\to\dots D_{m}$
とすれば良い. 但し $m$ は適当な最大値.
https://codeforces.com/contest/1816/submission/207012305

F: XOR Counting

$m=1$ の時は考えることは無い. (mod とり忘れでぺなったけど) $m\gt 2$ の時は, $n$ との偶奇が一致している $n$ 以下の数が作れる全て.
( $a,\frac{n-a}{2},\frac{n-a}{2},\dots$ とすればよい. )

$m=2$ の時は, $1$ の位から再帰的に確定させる.
https://codeforces.com/contest/1816/submission/207013893

総括

途中でdiv1があることに気がついた.
高レート帯の人がそっちに出ているのでdiv2順位表で相対的に超高順位となった.
全完5ペナ3位.
div1の方に放り込んでもかなり上位な結果で満足.

夜はサークルの新歓があった.
新入生が結構来てくれてとても嬉しい. 競プロのことはもちろん数学科のこととかも結構話した.

帰宅後豆乳を飲んだら頭が痛くなってきたので気分転換にこどふぉのバチャをした.
https://codeforces.com/contest/1594

A: Consecutive Sum Riddle

良くある二冪の奴ですね～と思ったら負も許されていたので $l=-(N-1),r=N$ でOK.
https://codeforces.com/contest/1594/submission/207053264

B: Special Numbers

2進法展開して $2^k$ の代わりに $n^k$ を掛ける感じ.
https://codeforces.com/contest/1594/submission/207053700

C: Make Them Equal

$gcd(n,n-1)=1$ であるので, 最大でも2回で達成可能.
よって, 1回以下で出来うるかを判定すればよい.
変更する必要のある箇所を変えられるindexの集合に共通部分があるかを判定すればよく, これは補集合をとって, 変更できないindex集合の和集合が全体にならないかを判定する方が楽.
https://codeforces.com/contest/1594/submission/207054536

D: The Number of Imposters

clue判定がされたなら, 嘘正直問わず, 指名した人された人は同じ陣営.
impo判定がされたなら, 嘘正直問わず, 指名した人された人は異なる陣営.
この時点で矛盾が生じたらその時点で切る.
よって, clue判定された人同士をdsu等で一つのまとまりにマージした後, impo判定された関係で辺を張って, 二部グラフかを見ればよい.
二部グラフであれば, 大きい方の集合をimpoとしてよい.
https://codeforces.com/contest/1594/submission/207055767

E: Rubik's Cube Coloring

easyの方は1か所自由に決めれば後は4通りから選べる.
hardの方は分からんかった.

F: Ideal Farm

$s,k$ を決めた時に, 条件を満たさない最大の $n$ を考える.
これは, $s+1$ 個のマスがあり, $0,s$ マス目は黒くなっている. $i$ マス目と $i+k$ マス目の少なくとも一方は黒く塗らない.
最大で何マス黒く塗れるか? という問題になる.
$2k$ マス毎をブロックとすると, 各ブロック中前より $k$ マスは黒くでき, ブロックに含まれない $(s+1)%(2k)$ マスの内, $k$ マス以下なら黒く塗れる.