ラベル マージテク の投稿を表示しています。 すべての投稿を表示
ラベル マージテク の投稿を表示しています。 すべての投稿を表示

2026年6月21日日曜日

yukicoder contest 480 (Gemini Tester)

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


No.3250 最小公倍数

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

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

2024年7月23日火曜日

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

　Fまで六完。

コンテスト後のツイート

G - Sum of Tree Distance

　解説AC。

　マージテクで解けると聞き、マージテクで通そうと思った後も自力で解けなかったのは情けない。「ある頂点から根の方向へ何歩進んだか？　の総和」を持たなければいけない気がし、それだと一歩一歩全ての色について更新しなくてはいけないと思ってしまった。

　が、根からの距離の総和さえ持てば代用できるため、マージテクが適用できる。



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

2024年4月22日月曜日

AtCoder Beginner Contest 350（Promotion of AtCoderJobs）

　G解けず。Fで苦戦したため順位は悪い。

コンテスト後のツイート

G - Mediator

　解説AC。

　マージテクで解いた。コンテスト終盤にマージテクが使えるんじゃないか？　というアイディアは思いついたけど、具体的な解法には思い至れなかった。
時刻: 0 件のコメント:
ラベル: ,

2024年2月25日日曜日

Educational Codeforces Round 162 (Rated for Div. 2)

　Dまで四完。さらにレートを落とした。ひどい。

コンテスト後のツイート

E. Count Paths

　マージテクでAC。

　最近のABCで似た問題が出題されていることに引きずられてしまったが、マージテクでも解けると言われたら普通に解けた。
　コンテスト中もマージテクを検討したので解けておかしくなかったはずなのに、なぜかライブラリを持っていない解法に突撃したのがひどい。
　このABCをまだ復習していなかった、というのも反省。
時刻: 0 件のコメント:
ラベル: ,
登録: 投稿 (Atom)