Codeforces Round 988 (Div. 3)

　時間ギリギリ全完。

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

コンテストへのリンク

コンテスト後のツイート

E [1,2],[1,3],...,[1,n]を聞く。全部0ならIMPOSSIBLE。一番はじめに1と返ってきたものから、左端の様子が分かる。
F 答え二分探索。判定は、どの範囲に自分の位置があれば良いか？　がn個でてくるので、平面走査みたいにやる。
G 素因数ごとに包除するDP。2^素因数の個数の計算量は必要な気がした。

— titia (@titia_til) November 17, 2024

AtCoder Regular Contest 187

　A遅解き一完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 187 AB両方を見てBを中心に考えていたが解けず、その後なんとかAをAC。
A N>=3ならYesだと気付くのが重要。
B 段々になるので、段を数えていけばいいはず→数えられず終了。

— titia (@titia_til) November 17, 2024

B - Sum of CC

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

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

C - 1 Loop Bubble Sort

　自力AC。

　実験して、-1がなく最後がNの場合は、pow(2,累積maxの更新回数)が答えになると分かった。

　そこまでも時間がかかったが、その数え上げがDPでできると分かるまでも長かった。

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

AtCoder Beginner Contest 380

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

G K個の部分、その前、その後の三つに分ける。K個の部分の転倒数は平均でK*(K-1)/2/2。ずらしたときどうなるかはBITで差分計算できると思う（が、サンプルが合わなかった）。

— titia (@titia_til) November 16, 2024

G - Another Shuffle Window

　自力AC。

　大まかな方針はあっていたけど、三つ分けたとき、左同士、右同士の転倒数も足さなくてはいけないことを忘れていた。

　結構本質的な考察ミスなので、コンテスト中に解き切るのは厳しかったか……。

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

　

Codeforces Round 971 (Div. 4)

　G1まで。

コンテストへのリンク

コンテスト後のツイート

F c回シフトしたときの[l,r]の和を計算できるようにしておく。あとは、l,rをmod n で0になるところまで持っていき、周回数*SUMを足す。
G1 B[i]=A[i]-iとしたとき、[l,r]での最頻値の出現回数。検索したらMoと言われて、https://t.co/5mOOOLsyNq　からお借りしてしまったけど、別の解き方ありそう。

— titia (@titia_til) September 3, 2024

G1. Yunli's Subarray Queries (easy version)

　そもそもクエリの種類がn種類しかないのにMoを使ったのはおかしかった。

　順番に求められますね。

G2. Yunli's Subarray Queries (hard version)

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

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

　典型ではあるかもしれないけど、簡単ではないね。

Refact.ai Match 1 (Codeforces Round 985)

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

D まずできるだけ辺を消す。次数2以上の頂点があれば、それを構成する三角形を消し、辺を減らす。すると森になるのでつないでいく。
次数2以上の頂点xに一回辺を減らす操作をしたら、そこはもう操作しなくていいと勘違いしてはまった。ランダムテストでなんとか気付けて良かった。

— titia (@titia_til) November 9, 2024

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が出たテストケースから、何文字のとき間違っているか？　などを推測しながらやらないと解けなかった。時間があったら解けたかもしれないけど、コンテスト中だったら、ランダムテストを書いて考えなければ解けなかっただろうから、短い時間で解くのは結構厳しいね。

Codeforces Round 986 (Div. 2)

　Dまで四完。Eは実装間に合わず。

コンテストへのリンク

コンテスト後のツイート

D 頭がこんがらがるけど、ある数字を取ったときq,j,kのどの数字まで使えるか遷移を考えれば良い。SortedSetをお借りしたけど、dequeで良かったかも？
E 一本道の場合、1,n-1/n,n-2/n,...,1/n,0となることを利用する。一番近い葉までの距離が分かればいけると思ったけど、実装間に合わなかった。

— titia (@titia_til) November 10, 2024

E. Alice's Adventures in the Rabbit Hole

　ツイートした方法であっていた。

　単純に、トポロジカルソート順にDPの値を更新していく……とかじゃなく、枝分かれしたら、そこから一番近い葉まで一気に値が決まる、みたいな感じなので実装に戸惑ったことが間に合わなかった原因か。

　トポロジカルソート順でも、どこから値が伝搬してきているか？　みたいなのを持てばできるとは思ったけど、それもちょっと大変。

THIRD プログラミングコンテスト2024（AtCoder Heuristic Contest 039）

　94位。悪くはないけれど……。

コンテストへのリンク

コンテスト後のツイート

・盤面を40*40に圧縮
・良さそうな長方形を一つ探す。（初期状態）
・そこから、長さの条件を満たしたまま、一マス加えたり一マス減らしたりする山登り。
三番目の実装（線を伸ばしたり縮めたり）は、https://t.co/w0nbkNdTBz
でやったことを流用した。別の方法を色々検討したんだけど思いつかず。

— titia (@titia_til) November 10, 2024