2024年11月27日水曜日

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

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

コンテスト後のツイート

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

時刻: 0 件のコメント:
ラベル: , ,

2024年11月26日火曜日

AtCoder Grand Contest 069

　A一完。一問も解けなかったとしてもレート-8だったらしく、結果的にはローリスクのコンテストでした。

コンテスト後のツイート

B - Pair Guessing

　解法ツイートを参考にAC。

　「同じ行か列に0があるマスを選ぶ」というアイディアはコンテスト中から考えていたが、それだけではACには遠かった。

　一番重要なのは、
011
111
111
　がYesで、

0111
1111
1111
1111
　はNoだと気付くこと。

　それに気付くと判定しやすい。

　なお、同じ行・列で0が最も少ないものから選んでいく、という方法でACした（解法ツイートにあった）けど、この解法は正当なのだろうか。正当な気もするけど……。
　解説放送で正式な方法も理解した。

時刻: 0 件のコメント:
ラベル:

2024年11月19日火曜日

Codeforces Round 988 (Div. 3)

　時間ギリギリ全完。
　ARCの後だったせいもあり、序盤やる気が出なかったけど、全完できて良かった。

コンテスト後のツイート


時刻: 0 件のコメント:
ラベル:

2024年11月18日月曜日

AtCoder Regular Contest 187

　A遅解き一完。

コンテスト後のツイート

B - Sum of CC

　解法ツイートを見てAC。DPでできるのでは？　と考えたくなるが、主客転倒で考えなくてはいかなかった。

　階段状になることを利用するのは正しくて、そこから、段に関して主客転倒して考えようと思わなくてはいけなかった。主客転倒はちょっと考えたはずなんだけど、うまく考察できなかった。

C - 1 Loop Bubble Sort

　自力AC。

　実験して、-1がなく最後がNの場合は、pow(2,累積maxの更新回数)が答えになると分かった。
　そこまでも時間がかかったが、その数え上げがDPでできると分かるまでも長かった。

　時間があれば自力で解ける問題だったことは分かったが、コンテスト中に通すためにはどうすれば良いんだろうか。
時刻: 0 件のコメント:
ラベル:

2024年11月17日日曜日

AtCoder Beginner Contest 380

　Fまで六完。

コンテスト後のツイート

G - Another Shuffle Window

　自力AC。

　大まかな方針はあっていたけど、三つ分けたとき、左同士、右同士の転倒数も足さなくてはいけないことを忘れていた。
　結構本質的な考察ミスなので、コンテスト中に解き切るのは厳しかったか……。

　しかし、解けなくてはいけない問題でした。
　



時刻: 0 件のコメント:
ラベル:

2024年11月14日木曜日

Codeforces Round 971 (Div. 4)

　G1まで。

コンテスト後のツイート

G1. Yunli's Subarray Queries (easy version)

　そもそもクエリの種類がn種類しかないのにMoを使ったのはおかしかった。
　順番に求められますね。

G2. Yunli's Subarray Queries (hard version)

　こたつがめさんの放送の振り返りを見てAC。

　Div.4だから、という先入観があったからかもしれないけど、遅延セグ木を使うと思いつかなかった。
　典型ではあるかもしれないけど、簡単ではないね。


時刻: 0 件のコメント:
ラベル: ,

2024年11月12日火曜日

Refact.ai Match 1 (Codeforces Round 985)

　Eまで五完。

コンテスト後のツイート

F. Palindrome Everywhere

　parityが関係するというツイートをヒントにAC。

・RRとBBが同時にあるとダメ
・Rが一個以下、または、Bが一個以下ならOK

　はコンテスト中に分かっていたが、

・RBBRBBはなぜダメなのか？
・RBBBRBBBRBBは良いのか？
・RBRBBRBBは良いのか？

　などは分かっていなかった。

・RBBRBBがダメなのは、相対位置の偶奇を考えれば分かる。（RBRBや、RBRBBBも同様）
R(x)BBR(y)BBのxからyを考える（x,yから同じ文字の方向を挟む方へ動かせる、と考える）と、xがRをまたぐときyもRをまたぐためxからyへたどりつけない。

・RBRBBRBBは良い。偶奇（Rの間に入っているBの個数）両方含まれるなら偶奇をずらせるので良さそう。

　ただ、さらに、
・「RBBRBB」（Rの間に偶数のものが二つある）が含まれていたら即ダメ、にも気付かなくてはいけない。
R(x)BBRB(y)Bのxからyを考えると、xの左右どちらかがRのとき、yの左右は両方Bなのでダメだった。

　これらが分からなくてはいけなかった。

　WAが出たテストケースから、何文字のとき間違っているか？　などを推測しながらやらないと解けなかった。時間があったら解けたかもしれないけど、コンテスト中だったら、ランダムテストを書いて考えなければ解けなかっただろうから、短い時間で解くのは結構厳しいね。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)