2025年6月27日金曜日

AtCoder Beginner Contest 408

　Fまで。

コンテスト後のツイート

G - A/B < p/q < C/D

　解説AC。

　公式解説の方法は賢いが、Stern–Brocot木は知っていたのだが、それを使って解くことはできるべきだったのかもしれない。（ただし、今回Stern–Brocot木を使う解法ではACしてない）


時刻: 0 件のコメント:

2025年6月25日水曜日

Educational Codeforces Round 180 (Rated for Div. 2)

　Dまで。
　Bは難しい方法で解いてしまったが、単調増加や単調減少だとダメだけど、そうでなければ一回、という簡単な解法があった。単調増加or単調減少じゃないなら、山や谷の箇所があるので、確かに、という感じだが、気付かなかった。

コンテスト後のツイート

E. Tree Colorings

　根以外で枝分かれのない木の場合はコンテスト中にできていて、その場合は、素因数分解して、x*y*zなら、1+x/2+y/2+z/2みたいに求まる。
　それを応用して解こうと思ったが、結構苦労してしまった。

 木を、根からではなく、葉から作っていこう、と考えると良い。

・木Aと木Bを根同士を合わせる形で合体させると、node数はその和-1で、mの値はその積のような木になる。
・木に親をつけると、mの値は+2する。

　この二つの遷移でDPすればOKでした。



時刻: 0 件のコメント:

2025年6月23日月曜日

第六回日本最強プログラマー学生選手権-予選-（AtCoder Regular Contest 201）

　ABの二完で青に落ちる。Dの解法は分かっていたのに実装できず。最近、実装力が落ちているのかも。まずいなぁ。

コンテスト後のツイート

C - Prefix Covering

　Trie木、木DPというキーワードを見てAC。

　コンテスト中は、Trieを使うのだろうとは思ったが、数え上げ方が分からなかったため飛ばした。
　しかし、木DPだと言われたらすぐ解答が思いつけたのだから、もう少し粘るべきだったかもしれない。とはいえ、考えていたときに木DPは浮かんでいなかったので、本当に解けたかは分からない。

D - Match, Mod, Minimize

　WAの原因は、累積和用のLISTを円環用に2*Nの長さにしていたのに、累積和を取るときNまでしかしていなかったせいだった。
　ちゃんと累積和取ったらWAはなくなってTLEになり（二分探索中に二分探索してるので仕方ない）、RUSTに直したらAC。
　その後、尺取りに直してPyPyでもAC。

　しかし、bisect→尺取りに直すのでも3WAしておりまずい。

　実装力というか注意力みたいなのが落ちているのかも。それってどう対策したら良いんだろう？






時刻: 0 件のコメント:

2025年6月22日日曜日

ユニークビジョンプログラミングコンテスト2025 夏（AtCoder Beginner Contest 411）

　Eまで五完。

コンテスト後のツイート

F - Contraction

　自力AC。

　コンテスト後の冷静な状態ならすぐ分かるだろうと愚直書かずにやろうとしたらペナ量産。一時間くらいして諦めて愚直＆ランダムテストを書いたらようやく分かってAC。消すべき辺を消していないところがあったためのWA（やRE）でした。

　愚直を書いた方が速く解ける場面が多いのはそうだけど、これくらいの問題で愚直を書くのも……という気持ちも間違ってないと思うので、どうしたら良いのかね。

G - Count Cycles

　一応自力ACだが、bit DPでいける……みたいなツイートは目にしていた。

　素直にbit DPを書くとN^3 * 2^Nくらいの計算量になるが、定数倍高速化をしていればなぜか通る。ただし、自分の場合はPyPyでは通らず、RUSTに直さなくてはいけなかった。

　が、これは、start位置を固定してそれぞれでbit DPを行っていると考えられるためで、そう考えると実は（ならし）計算量が減っている（解説を見て理解）。
　その方針ならPyPyでもACできた。



時刻: 0 件のコメント:

2025年6月21日土曜日

yukicoder contest 471

　A一完。
　AtCoder 創立13周年記念 企業対抗 Team Battleの放送を見ながら考えていたらBが思いつけず、疲れてそのまま撤退。


No.3184 Make Same

　解法ツイートを見てAC。

　クエリの30回ってbitの長さくらいだね、とは思ったはずなのに、思いつけなかったのはダメ。

No.3185 Three Abs

　自力AC。
　いわゆる耳DPですね。これはすんなり解けました。

No.3187 Mingle


　もらうDPで二乗になるのを配るDPにすると区間加算になるとは気付けなかった。
　さらに、どのような区間になるのか？　という部分でも結構困った。実験したり、式を書いたりしてなんとか理解し、AC。
　実装には双対セグ木を使いました。

　
時刻: 0 件のコメント:

2025年6月20日金曜日

Codeforces Round 1032 (Div. 3)

　Fまで六完。Div. 3で二問解けないのはまずい。

コンテスト後のツイート

G. Gangsta

　解説AC。典型かもしれないけど難しく感じた。

　まず、0と1の個数のうち多い方、というのを

・((0の個数)+(1の個数)+(0の個数と1の個数の差))/2

　と言い換える。

　そうすると、あとは、全ての区間について、(0の個数と1の個数の差)の総和を求めれば良い。

　このために、"1"を+1、"0"を-1とした累積和を考える。この、任意の二項の差の絶対値を求めれば良い。
　ここでBITを使って、BITに個数や総和を載せて解く方法もあるようだ（よく分かっていない）。

　が、公式解説はもっと簡単。
　累積和の配列をAとし、Aをソートする。
　二項の差の絶対値を考えるということは、自分より大きい項からは引かれ、小さい項については足されるということ。
なので、

・A[i]*(i-(len(A)-1-i))

　の和を求めれば良い。

　前半も後半も見たことあるような内容ではあるが、とはいえこの二つを繋げるのは結構難しい気がする。

　




時刻: 0 件のコメント:

2025年6月18日水曜日

CodeQUEEN 2025 予選 (AtCoder Beginner Contest 410)

　Fまで。

　Fはうまくやればdictは必要なかった。どの数字が何個あるかを配列に記録し、差分計算すれば良かった。PyPyで通せなかったのには理由がありました。

　ただ、思いつくべき内容ではあったが、個人的にはこういうlog外しはあまり重要に思えないのよね。AHCで焼きなましの回数を増やしたい！　とかなるとこういうことも重要になってくるけども。しかしそれも、高速な言語に書き換えた上での話な気もする。

コンテスト後のツイート

G - Longest Chord Chain

　解説放送を見てAC。解説を見てしまったけど、多分時間があれば自力で解けたと思う。

　[a,b]と[c,d]の区間が交わらないような最長のものを求める感じなのは分かるが、円環の問題なので、どこかで切り分けなくてはいけないのが難しい。

　これを、[a,b]だけでなく、[b,a+2*N]も考えることで、ただのLIS（今回は、最長減少部分列の方だが）を求める問題になるというのは驚き。こうすると実装しやすいね。



時刻: 0 件のコメント:

2025年6月16日月曜日

AtCoder Regular Contest 200 (Div. 2)

　ABの二完。若干レートは下がったが、それほど失敗したという感覚はないため厳しい。Aは、最初から紙で立式すべきだったかなぁ。

コンテスト後のツイート

C - Movie Theater

　後ろから決めていけばいい、というツイートを見てAC。

　どこでWAになっているかの判断を誤っていたのがダメだった。今回は、人の順番の配列を求めた後、その逆写像が答えになるわけだけど、「人の順番の配列」の辞書順最小を求めても、その逆写像が辞書順最小にはならない。
　ここに気付かず、もっと別の条件の部分で間違っていると思ってしまってダメだった。

　逆写像を辞書順最小にするためには、後ろから決めていけばよい。
　このことは知らなかったけれど、この部分が間違っていると気付けたら試したと思う。

D - |A + A|

　自力AC。

　コンテスト中に書いた実験コードを利用してAC。
　コンテスト中は実験しても偶数のときの構築が分からなかったのだけど、落ち着いて実験結果を見たら、6以上なら、0, 1, 2, 4のように、0から連続する数＋一つ飛ばしでできていた。
　2は、偶数のときは0とM/2で良い。（奇数だとダメ）
　4のときでWAを出してしまったが、2のときと同じように、Mが4の倍数なら0, M/4, M/2で作れる。

　コンテスト中は、Dを20分くらい考えた後、分からなそうと思ってCに行ったのだが、その判断はどうだったんだろう。
　一応、今考えてACするまで30分はかかっていない気がするが、コンテスト後に落ち着いて
実験結果を眺められたからという気もするし、WAの修正に12分もかかっている。

　Dに集中していたら解けた可能性がなかったとは思わないけど、望み薄だったかなぁ。
時刻: 0 件のコメント:

2025年6月14日土曜日

yukicoder contest 470

　Cまで三完。


No.3180 angles sum

　tangentの加法定理を使って書いたら1case（コンテスト後追加されたHackのcase）以外AC。y座標が0の場合が問題なため、場合分けしてAC。

　コンテスト中は、ベクトルの内積でcosを求め、加法定理を使って式変形をしていたが、答えが合わなかった。誤差のせいなのか式変形がまずいの分からず困っていたら終了。
　tangentの加法定理でも解けるだろう、ということはコンテスト中から気付いていて、そっちで式を書いてみるとその方が簡単だった。

　ただ、どっちの方法でも解けるはずなので、早く方針転換すべきだった、というのも違うような。

No.3181 find H

　三角形の五心について、何かと何かの距離が1:2になるというのは覚えていたが、どれとどれかが覚えておらず検索した。
　知識問題ですね。

No.3182 recurrence relation’s intersection sum

　解説AC。

　解説を読むと行列累乗の典型問題なので、自力で解けなかったのが悔やまれる。
　行列累乗に持ち込むため、A_nやS_nだけではなく、1やn, n^2といったもの（関数）を行列の要素に入れるという手法は見たことあったはずなのに思い出せなかった。
時刻: 0 件のコメント:

2025年6月10日火曜日

yukicoder contest 469

　AHCの途中だったため、Aだけ解いた。

コンテストへのリンク

No.3172 三角関数べき乗のフーリエ級数展開

　何も分からなかったので、サンプルからOEISを経由してAC。
　まあ、二項係数じゃないか？　とは思ったので、OEISを見なくてもACできたかもしれないけど。
　自力で解答にたどりつけたかもしれないけど、式変形して正解を得られる気がしない。

No.3173 じゃんけんの勝ちの回数

　ツイッターで、フローで解けるというのを見てしまったため、それでAC。（minだけフローを使った）
　解説を見たら、フローを使わなくても解けるのね。
時刻: 0 件のコメント:

yukicoder contest 468 Desire for Approval ~Ash blown by the draft leads to the door to a new beginning~

　AHCを頑張ろうと思っていたのでAだけAC。


No.3166 [Cherry 7th Tune *] 桜の守人

　解説AC。

　二分探索は分かったが、その後分からなくなり解説を見た。

　分からなくなってしまったのは、全ての整数座標、もしくは整数/2の座標の頂点が守られているか？　と考えてしまったせいだった。座標圧縮が必要なはずだけど……などと考えて混乱。
　守る範囲は区間なのだから、[x-p,x+p]に全ての区間が含まれているか？　と考えるのは自然。これは、イベントソートを使って解くことができる。

No.3167 [Cherry 7th Tune C] Cut in Queue

　自力AC。そこそこ苦労したが解けて良かった。

　クエリ先読みを使い、クエリ2の削除しないものとして、最終的なAの配列を求める。
　クエリ1で、何の直前に何が付け加わるか？　というのが与えられている。これをなぞるのは、木構造でDFSして求めていく感じになる。

　あとは、Bit_indexed_tree上の二分探索を駆使したら解けた。

No.3168 [Cherry 7th Tune D] Manhole

　自力AC。

　図を描いて相似を見つけたら解けた。空間図形には苦手意識があるため、図を描いた後しばらく分からなくて焦った。
時刻: 0 件のコメント: