AtCoder Beginner Contest 363

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

E heapqでAの最も小さいものを取っていく実装だとTLE。最初にソートし、水に面しているか？　水面以下の高さか？　を別に管理してlogを外したらACした。
F 中央の数を全探索し残りをbit全探索する解法を終了6分後に書き終わったがTLEでした。

— titia (@titia_til) July 20, 2024

C - Avoid K Palindrome 2

　Pythonで通す方法の一つとして、

・from more_itertools import distinct_permutations

　を使うというものがあったらしい。

　知らなかったので仕方ないか。

F - Palindromic Expression

　ツイートした解法で、bit全探索の部分で、「Nより大きくなるなら探索をやめる」という枝狩りをしたらACできた。

yukicoder contest 437 ('09 Contest 002 day2)

　A一完。

コンテストへのリンク

No.2812 Plus Minus Blackboard

　コンテスト中に、プラス、マイナスそれぞれ絶対値の小さいものについて操作を行っていけば良いのでは？　と思いついたが証明が分からず、証明を考えていたら終わってしまった。

　コンテスト後、証明は分からないけどとりあえず投げてみたらACだった。

　解説を見るとこの方法で正当そう。

　ただ、この方法を直接示しているわけではないので、「この方法を示そう」と考えるのでは難しかったか。

No.2816 At Most Two Moves

　解説AC。

　1以外の点について、1から一歩でいけない確率は1/2で、2歩でいけない確率はいくらだろう……と考え、中継点と繋がっていないときだな、と思ったはずなのに答えが出せなかった（解説を見た）。そこまで考えたならすんなり分かって欲しいのだが。

　

Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

E sizeだけ考えればOK。最上位ビットを大きい方から見ていき、最上位bitが同じものが二つあればそれ以下全て1にできる。一つなら、xor 最上位bitを加える。
F NPCが立っている分についての次数を考え、NPCが立っていないものを使って次数を偶数にできるか？　が解けなかった。

— titia (@titia_til) July 18, 2024

F. Stardew Valley

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

　使っても使わなくても良い辺たちの連結成分ごとに見て木DPするという方針は思いついていなかった。

　この問題が類題だったようだけど、思い出せなかった。

　ただ、この部分が解けたとしても、オイラー閉路を構築する部分で躓いていただろう。DFSして帰りがけ順に見ていけば良い（！）とは知らなかった。

G. Minecraft

　こたつがめさんの放送の振り返りを見てAC。解けなきゃいけない問題だった。

　繰り上がりの数を持ってDPする方針は問題を見てすぐ思いつたのに、繰り上がりの値が大きくなるかも、と思って実装できなかった。

　高々nになる、というのは言われれば当たり前。Fを考えている合間に見たため長いこと考えたわけではないが、思いつかなかったのは悔しい。

　なお、定数倍高速化をしないと自分のPyPyの実装では通らなかったので、コンテスト中に通すならChatGPTを活用しなくてはいけなかったかも。

yukicoder contest 436 ('09 Contest 002 day1)

　A一完。BでWAが出て、10分以上見直したがどこが間違っているか分からず、頭が働いていないと思って寝てしまった（こんなのばっかり）。

コンテストへのリンク

No.2804 Fixer And Ratism

　WAが出たテストケースを見て、「同時に帰った人々の名前をレートが低い人から順に出力」するなら、パソコンを使用可能にしていない人→パソコンを使用可能にした人の順ではいけないことに気付いた。

　結構気付きにくいところだと思うので仕方なかったか。

No.2805 Go to School

　自力AC。

　スタートとゴールからダイクストラですね。

No.2806 Cornflake Man

　自力AC。

　小さい順に調べていけば良さそう→0以上M以下の全ての整数について調べなくてはいけないかと思ったが、よく考えたらAに入っているものだけ調べれば良いと気付いてAC。

No.2807 Have Another Go (Easy)

　自力AC。

　確率を求めると思って答えが合わず（計算量も間に合いそうになく）悩んでしまったが、場合の数を求めると気付いたらDPでできた。

No.2809 Sort Query

　テストケースを見てデバッグしたけど方針は自力でAC。ただ、タグの「クエリ先読み」は見た。

　最初、SortedMultisetを使えばそのままできそう？　と思ったけど、全くそのままではなかった。クエリの2（ソート）が与えられてから、再度クエリの2が与えられるまでの間はSortedMultisetの中身は変更せず、クエリの2が来るたびに変更するようにすれば良かった。

　

トヨタ自動車プログラミングコンテスト2024#7（AtCoder Beginner Contest 362）

　Fが解けず。

コンテストへのリンク

コンテスト後のツイート

トヨタ自動車プログラミングコンテスト2024#7（AtCoder Beginner Contest 362） F飛ばして六完
C 最小からの差を考える。
D ダイクストラ。Cより簡単。
E （長さ、公差、次の数）を持ってDP
G aho-corasick。ライブラリを改造したりChatGPTにC++に直してもらったりしてたらたくさんの人に解かれていた

— titia (@titia_til) July 13, 2024

F - Perfect Matching on a Tree

　解説AC。

　重心で分けることはコンテスト中も考えていたが、正当性が分からなかった。主客転倒を考えるのはなるほど。

G - Count Substring Query

　以前自分で書いたAho-Corasick法の実装を参考に書き直したが、こっちの方が汎用性がある気もする。今度書くときはこっちを元にすべきか。

Codeforces Round 957 (Div. 3)

　Fまで六完。

コンテストへのリンク

E. Novice's Mistake

　（n, a）を定めると、bは高々一つ。また、単調なので二分探索で求めた。

　そして、その個数が少なそうなので、n=1以外のときは埋め込んだ。

　でも、n*aは高々7桁なので、二分探索も埋め込みもいらなそうですね。

G. Ultra-Meow

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

　二項係数でやる方法は考えたはずなのだけど、三乗だと思って棄却してしまった。ちゃんと計算量を見積もらないと。

　その後、nを増やしていったときDPでできるのでは？　とその方針ばかり考えてしまった。

Codeforces Round #956 (Div. 2) and ByteRace 2024

　Cまで解いた後、Dをすぐに思いつかず睡魔に襲われ途中でやめてしまった。パソコンを消した後でDの解法に気付いたが実装する気力が湧かなかった。

コンテストへのリンク

D. Swap Dilemma

　いくつか実験したら、転倒数の和の偶奇では？　と気付いた。

　まあ、見てすぐ分かるものではないし、すぐ分からなかったのは仕方ないかなぁ。

E. I Love Balls

　自力ACしたが時間がかかった。

　specialじゃないカードは交互に二人のプレイヤーにわたるので、その回数で分配すれば良い。

　specialなカードは、specialじゃないカードと一緒にわたる or 全部配り終わってからわたるのいずれか。なので、n-k+1回わたる回数があるので、それで分配すれば良い。