コンテスト後のツイート
E sizeだけ考えればOK。最上位ビットを大きい方から見ていき、最上位bitが同じものが二つあればそれ以下全て1にできる。一つなら、xor 最上位bitを加える。
— titia (@titia_til) July 18, 2024
F NPCが立っている分についての次数を考え、NPCが立っていないものを使って次数を偶数にできるか？ が解けなかった。
F. Stardew Valley
こたつがめさんの放送の振り返りを見てAC。
使っても使わなくても良い辺たちの連結成分ごとに見て木DPするという方針は思いついていなかった。
この問題が類題だったようだけど、思い出せなかった。
ただ、この部分が解けたとしても、オイラー閉路を構築する部分で躓いていただろう。DFSして帰りがけ順に見ていけば良い（！）とは知らなかった。
G. Minecraft
こたつがめさんの放送の振り返りを見てAC。解けなきゃいけない問題だった。
繰り上がりの数を持ってDPする方針は問題を見てすぐ思いつたのに、繰り上がりの値が大きくなるかも、と思って実装できなかった。
高々nになる、というのは言われれば当たり前。Fを考えている合間に見たため長いこと考えたわけではないが、思いつかなかったのは悔しい。
なお、定数倍高速化をしないと自分のPyPyの実装では通らなかったので、コンテスト中に通すならChatGPTを活用しなくてはいけなかったかも。
0 件のコメント:
コメントを投稿