2026年7月16日木曜日

Codeforces Round 1109 (Div. 3)

　Eまでしか解けずひどい順位に。

コンテスト後のツイート

F. Anya Loves Trees!

　コンテスト中は何かの実装ミスかと思っていたが、考察が間違っていた。

　あるノードの子の番号たちが、（9が最大だったとき）

・8 9 1 2

　のように、一つながりになっていたら良いと考えていたが、これだと最終的にぐるっと連番になることはできたとしても、1をスタートにできない！

　なので、一番小さい数字から初めて、全て連番になっているようにしなくてはいけない。

　番号が連続になっているかどうかを判定するのには、左右を管理するやつを利用した。







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

2026年7月4日土曜日

yukicoder contest 503

　Eを考えていたが解けず、Cのみ一完。

コンテスト後のツイート

No.3580 二成分の和

　解説AC。

　一目見て、連立方程式だから行列……と思ってしまったが、それが間違いだった。
　グラフの問題だと思えば、自然と、連結成分ごとに一つの要素の値を決め打つ、というのが思いつく。

　行列で上手くいかないと思えば、この解法に至るのがそう難しい気はしないんだが……。一旦思い込んだものを方針転換するのは難しい。

No.3581 分数対称差更新区間計数取得

　TLEが取れず、ChatGPTにPyPy→RUSTに変換してもらってAC。

　各クエリにおいて、変更すべき点が√i個に収まるので、BITで管理してACした。

　だが、解説を見ると、平方分割した方が高速になるらしい。言われてみればそういう高速化を要求されたことがあった。忘れていた。


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

2026年7月3日金曜日

CodeQUEEN 2026 予選 (AtCoder Beginner Contest 462)

　Fまで。

コンテスト後のツイート

G - Completely Wrong

　解説放送を見てAC。包除原理で解ける。

　Cを並び替えたもののうちk箇所が一致（C_i=G_iとなる箇所がk箇所）しているものを求めたい。
　これを、各色ごとに求めて、それを合わせることにより求められる、と考えるのがポイント。具体的には、FFT（畳み込み）を使って計算できる。

　最後に、包除原理を用いて、kが奇数のとき-1の係数をかけて足し合わせれば良い。（解説放送では-1を掛けるのをFFTする前にやっていたけど、最後にやってOKですね。その方が分かりやすいと思う）




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

2026年7月2日木曜日

Codeforces Round 1106 (Div. 2)

　Dまで。Eは解法はあっていたので、Fを考えていた時間がなければ間に合っていたかも？

コンテスト後のツイート

E. Cake Trial

　ツイートしていた解法で正しく、定数倍高速化を頑張ったら通った。
　時間があれば他の言語に直してACしたと思うけど、そんな時間なかったから仕方ないね。
　AtCoderならcodonを使えば通せていたはずなので、あまり気にしないようにしたい。


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

Codeforces Round 1107 (Div. 3)

　Eまで。Fを（実験せずに）考えていたら寝てしまった。


F. A Bit Odd

　解説AC。

　難しくないか？　実験せずに思いつける気がしないし、実験したとしても規則性に気付くのは簡単ではないと思う。
　実験せずに解くなら、一回で勝つための条件は……と考えるのだろうけど、思いつくのは困難に思える。そもそも実験したとして解けていたかもあやしい。
時刻: 0 件のコメント:
ラベル:

2026年6月21日日曜日

yukicoder contest 480 (Gemini Tester)

　AB二完だが、BはHackされた。


No.3250 最小公倍数

　マージテクの練習問題だった。
　ただ、PyPyだとTLEし、PyPyで通している人もいなかったので、PyPyのコードをChatGPTにRUSTに翻訳してもらってAC。

　今はこういう翻訳もAtCoderでは禁止されているし、この問題はアルゴリズムの練習問題みたいなものだから、自力で書いた方が良いとは思うけど。
時刻: 0 件のコメント:
ラベル: ,

2026年6月19日金曜日

Order Capital Round 2 (Codeforces Round 1104, Div. 1 + Div. 2)

　Dまで。二時間近くあってE通せないのは悲しい。

コンテスト後のツイート

E. Permutation Commutation

　コンテスト後、落ち着いて考えたら自力でACできた。

　Functional Graphと見て、サイクルに分解する。

　たとえば、
A=[4, 5, 1, 3, 6, 2]
　を考えると、(1,4,3)と(2,5,6)というサイクルがある。

　これに対応するBは、(1番目, 4番目, 3番目)が(1,4,3),(4,3,1),(3,1,4)もしくは、(2,5,6),(5,6,2),(6,2,5)でなくてはならない。（2番目, 5番目, 6番目）も同様。

　ここまではコンテスト中に実験で分かっていた。i→A[i]とうつるとき、対応するいずれかのサイクルでindexを一つずらしたように入れなくてはいけない、と。
　しかし、さらにサイクル長に関して条件がありそうだとは思ったが、上手くまとまらなかった。

　実際は、同じサイクル長のものでないといけない。サイクル長3のものをサイクル長1のもので埋める……みたいなことができる気がして混乱してしまったが、こういうことができないと気付き、同じサイクル長のものしか使えないと分かった。
　なので、サイクル長で分類すればACできた。

　

G. Send GCDs

　解説AC。

・150個の素数を使うと、10^6までで1<<18個の数が作れる。
・bitごとに見るとn*20くらいの長さだが、これを18個ずつに分解すれば、上の対応表により変換できる。

　解法を聞けばまあ分かるが、これは10/9*nとか150とかいう怪しげな制約から類推するしかなさそう。推理力が問われる問題だったようだ。
　






時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)