April Fools Day Contest 2025

　ADの二完。

コンテストへのリンク

B. Plinko

　自力では解けず。

　0～17におくとゲームをプレイしなくてはいけないが、その外側におけば良かった。これは思いつきたかった。

C. Would It Be Unrated?

　解説AC。

　一つACが出るまでできることがなくないか？

D. Where Am I?

　写真を検索するとラスベガスだと分かるので、その緯度と経度を書く問題。それっぽい提出をしても「very close!」などと返ってきて、submitデバッグするしかなかった。

　……が、もっと狭い範囲に絞れたらしい。

AtCoder Beginner Contest 399

 　Eまで。

コンテストへのリンク

コンテスト後のツイート

E Sの各文字にTのどの文字が対応するかを見る。Sの一文字にTの二文字以上が対応していたら-1。グラフを考え、各連結成分について、サイクルなら頂点数+1、x→xが含まれるなら頂点数-1、それ以外なら頂点数回必要。ただし、サイクルで26個が覆われたら-1。私の書き方だとS=Tでの場合分けが必要だった。

— titia (@titia_til) March 29, 2025

F - Range Power Sum

　解説AC。

　「積の和典型」とも呼ばれる、組み合わせに帰着して解く問題。この解法、何度見ても解けるようにならないのだが……。

　コンテスト中に「積の和典型」で検索したのに解けておらず、辛い。

yukicoder contest 462

　AHCがあるのでAだけ解いて撤退した。

コンテストへのリンク

No.3075 Mex Recurrence Formula

　自力AC。

　実験するとN+1周期になると分かった。MEXを求めるところを愚直にやってしまったためTLEしたが、heapqを使えば良いと気付きAC。

No.3076 Goodstuff Deck Builder

　自力AC。これは迷わなかった。

　コストが大きい方から使うのが良い。残りのコストと、カードを使った回数をもってDPすればOK。

Codeforces Round 1013 (Div. 3)

　全完。

　Div. 3も最近は全完を逃していたことが多いので、今回は全完できて良かった。

コンテストへのリンク

コンテスト後のツイート

G sが大きい（s>k*kなら明らか。もっと小さくても良いと思うけど……）と答えはkかmax(1,k-2)になりそう。あとはシミュレーション。

— titia (@titia_til) March 25, 2025

AtCoder Regular Contest 195 (Div. 2)

　三完はしたがレートは落ちた。Bは同じ解法で通している人を何人か見かけた。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 195 (Div. 2) Cまで通したけど、Bは嘘解法だと思う……
A 前からと後ろから
B k=A_1+B_1を固定すれば判定可能。kの絞り方が分からない。結局、a in A,b in Bについてa+bを列挙し個数を見て、その個数がOKになりうるもののみ判定した。
C Rが奇数ならダメ。あとは地道にやる。

— titia (@titia_til) March 23, 2025

B - Uniform Sum

　嘘だと思ったが、（嘘かもしれないけど）それほど嘘ではなかった。

　A, Bがdistinctだとすると、S=A[i]+B[j]が何個ずつ現れるかをカウントすれば、それを見るだけで判定できる。

　今回はdistinctじゃないのでもう一工夫必要だが、大体それで良かった。

　distinctなら上手くできるのでは？　と考えるべきでした。

D - Swap and Erase

　解説AC。

　コンテスト中に考えていた貪欲（左から見ていき、A[0]==A[2]ならA[1]とA[2]をswapする）がどういうときまずいのか気付けなかったのが敗因。

　たとえば、

・1 2 1 1 1

　のときまずかった。A[0]とA[1]をswapしなくてはいけないときもある。

　Aの各要素が高々一回しかswapされないというのは言われてみれば自然だし、貪欲でダメと分かればDPしようと思えた可能性はあるかもしれない。

E - Random Tree Distance

　解説AC。解説放送も見た。

　まず、lcaを考える（u,vの距離を、D[u]+D[v]-2*D[lca]とする。D[x]は1からxまでの距離です）のはすべきだった。lcaがどこにあるか分からないから、lcaを考えることで状況が良くなるとすぐには思えないけれど、これはまずして良いですね。

　あとは、D[lca(u,v)]が、u<vのときvの値によらないと気付けるか、だが、これは実験していれば気付けるかもしれない。しかし、その後、D[lca]に関する漸化式を立てる部分が理解できず、解説を見ながら悩んでしまった。lcaが再帰的に決まっていく、と考えれば難しい式ではないのだが……。

　発想があった方が良い部分（D[lca(u,v)]が、u<vのときvの値によらないと気付く部分）もあるけれど、それ以外の定石的な部分でも詰まっているので、その部分はどうにかしたい。

　

AtCoder Heuristic Contest 044

　98位。

　コンテスト中バグらせて書き終わらなかった方針を最後まで書いていれば30位くらいにはなったので、惜しかったといえば惜しかった。

コンテストへのリンク

コンテスト後のツイート

AtCoder Heuristic Contest 044 98位。
答えの配列をANSとすると、NOW=[0]*Nと初期化したとき、
NOW[ANS[i][0]]+=T[i]//2
NOW[ANS[i][1]]+=T[i]-T[i]//2
としたときのNOWがTとできるだけ一致して欲しい。
→Tが大きいindexから貪欲に割り振るとそこそこ強い。

そこからほとんど伸ばせず終了。

— titia (@titia_til) March 16, 2025

Codeforces Round 1011 (Div. 2)

　Cまで三完というまずい成績。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 1011 (Div. 2) DもEも解けずまずい！
A 高々1回でOK
B 最初の0とその隣に処理。まだ0が含まれているなら、残りを処理。
C max(x,y)にkを足して桁が変わるところを見る。
D 考えていたのは嘘貪欲だったぽい。
E a=A[i]について、{a-B[i]の約数}が候補ということから絞ろうとしていた。

— titia (@titia_til) March 22, 2025

D. Serval and Kaitenzushi Buffet

　解説AC。

　heapqを使って上手くやる問題だと見てすぐ思い、それはあっていたのだが……。

　後ろから見てheapqで、それまでで最も良いのを出していく感じだと考えてしまったが、これだと上手くいかない。

　寿司を取る回数の最大回数が決まり、その回数だけ取るべき、というのが重要。そうすると、一回目、二回目……について、どの範囲の寿司から取れるかが定まり、heapqで答えを求めることができる。

　各回について、どの範囲の寿司を取ることができるかと考えなくてはいけなかった。愚直解（DP）と比較し、自分の解法がどういうケースで落ちるかも分かったのだけど、答えにたどりつけず。こういうときはどうすれば良いのだろうか……。

E. Serval and Modulo

　解法ツイートを見てAC。

　kはsum(A)-sum(B)の約数になる。言われてみれば確かに……。