2025年1月28日火曜日

Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2)

　Cまで三完で紫に落ちる。

コンテスト後のツイート

D. Balanced Tree

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

　全方位木DPが必要などと思っている時点で解法には遠かった。
　（全方位木DPのためにトポロジカルソートはしていたが）根付き木にして考えて良いということも分かっていなかったため、正しい解法まではかなり遠かった。

　惜しいところまで行っていないため、まず根付き木で上手くいかないか考えましょう、くらいしか言うことがない。

E1. The Game (Easy Version)

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

　コンテスト中に似たことは考えていた時間はあった気がするが、まとめられなかった。ただ、実際の敗因は、実装（LCAと比較する）が思い浮かばなかったことだと思う。この放送を見たときも、まず思ったのは、実装どうやるんだろう？　だったので。

　木の問題で、subtreeについて問われているのだから、LCAを考えるのは自然。そこを元に考えていたら正しい解法を見つけられたかもしれない。



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

2025年1月27日月曜日

AtCoder Regular Contest 191 (Div. 2)

　Bまで二完。

コンテスト後のツイート

C - A^n - 1

　解説AC。

　オイラーのトーシェント関数などを考える方針は悪くはなかったようだが、そこからどうすれば良かったか。原始根などに関する知識がもっとちゃんとあれば良かった？

　想定解の方はどうやって思いつけば良かっただろう。
　実験はしたがそこから進めなかった。n乗が絡むので、二項定理に思いを馳せるべきだったか？
　

D - Moving Pieces on Graph

　解説AC。

　場合分けがちゃんとできたとしても実装で引っかかる部分が多く、難しい問題だった。2nd shortest pathを求める必要がありそうだが、実際は必要ない……といったあたりも混乱しやすい。
　



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

2025年1月26日日曜日

AtCoder Beginner Contest 390

　ABCEの四完。

コンテスト後のツイート

D - Stone XOR

　冷静にDFSを書いてAC。
　全探索する問題なのは制約を見れば分かる。あとは、どうやって書くかなのだが……。コンテスト中は、部分集合ごとにbit全探索しており、「ただ全部見る」というのより明らかに時間がかかっていた。

　DFSし、今ある分け方のどこへ次の要素を加えるか？　を見るようにしたらAC。制約が厳しいのか？　と思ったけど、PyPyでも問題なく通る問題でした。


F - Double Sum 3

　解説AC。

　コンテスト中にあまり考えず、コンテスト後すぐ解説を見てしまったけど、主客転倒と言われれば確かに、となる問題。

　[L, R]のLの方を基準に考えるのは自然だし、A[i]=Lとなる範囲はどれくらいか？　と考えるのもそんなに思いつきにくい感じはしない。
　Dを中心に考えていたとはいえ、問題を読んだのなら解けなくてはいけない問題でした。反省。
時刻: 0 件のコメント:
ラベル:

2025年1月25日土曜日

Codeforces Round 1000 (Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Triangle Tree

　苦労したが、公式解説など色々参考にしてAC。

　まず、木DPでできそう、と思ってしまったのが筋が悪かった。
　主客転倒的な考え方でいくべきだった。

　その後は、うーん、どうすれば良かったんだろう。
　min$(d_u$, $d_v)$ の総和と、$d_{LCA}$の総和に分けて考えれば良い、というのは立式を見れば分かるが、その時点でちょっと思いつきにくい。

　さらに、それぞれの求め方も簡単とは言えず……。


　とはいえ、立式し、式を簡単な形に分解しようと思う部分は自然。
　その後、主客転倒でいこう、と思えるかどうかが勝負なのかな。
　



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

2025年1月23日木曜日

Codeforces Round 998 (Div. 3)

　Eまで。Div. 3なのにFから難しい……。


F. Multiplicative Arrays

　こたつがめさんの放送の振り返りを見てAC。理解した後でも難しい気がするが……。

　二項係数でどうにかする問題というのは分かるが、そこで止まってしまった。

　たとえば、k=6でn=4のときの場合の数は、2を入れる位置と3を入れる位置を考えて、4*4となる。なので、n以下のを足し合わせる場合、4*4+3*3+2*2+1*1＝30となる。

　……のように考えて、上手くいかなかった。


　このように考えるのではなく、数字を入れる箇所を何個にするか？　と考えると二項係数の和になり高速化できる。
　先程の6の場合だと、[6], [2, 3], [3, 2]の三通りがある。

　[2, 3]の順で入れるとすると、Combi(4, 2)通り。n=3, 2, 1の場合を考えると、Combi(3, 2), Combi(2, 2), 0通りとなり、その和は（公式により）Combi(5, 2)と計算できる。

　単純に素因数分解するのではなく、何をどういう順番で掛け合わせてkにしたか？　と考えなくてはいけなかった。
時刻: 0 件のコメント:
ラベル:

2025年1月22日水曜日

ALGO ARTIS プログラミングコンテスト2025 冬（AtCoder Heuristic Contest 041）

　413位という苦しい成績。

コンテスト後のツイート

　高さ10の頂点をできる限り増やしたい、というのは分かるのだけれど、どうすれば実現できるか分からず上手くいかなかった。
　山登りなども考えた（し、どうやらそれをやった方が良いスコアが出たらしい）が、子たちも一斉に変えなくてはならないず、高さが10より大きいものが出た場合どうすれば良いのか？　というあたりで躊躇してしまった。


　このツカモさんのツイートを参考に、コンテスト後に話題になった貪欲を実装してみた。

　根にできるだけ小さい値を割り当てたい、という気持ちは良いのだが、そのために、「Aを小さい順に見て、全点にいきわたるよう必要なだけ取る」、というのではなく、「Aを大きい順に見て、その点がなくても全点にいきわたるようなら除く」としているのが技巧的に感じた。
　ただ、その方法にさえ気付けば後は自然ともいえるか……。



　コンテスト中どうすべきだったかは悩ましい。

　自分がコンテスト中考えていた方とこの貪欲解法は結構似ているので、そこへ辿り着けたら良かったのだが、上手くいかなかった。

　DFSを試すべきだったとは思うけど、普段再帰でのDFSを書いていないため、解説放送にあるようなDFSにはちょっと慣れていないんだよね……。解説放送のDFSを再現するのに時間がかかってしまった。それだとあまり良いスコアが出なかったので、DFSの良さに気付くのもそんなに容易でなかった気がする。

　シンプルな解法を考えて、山登り/焼きなましなり、ビームサーチなりを試す、という方針の方が良かったのかなぁ。
時刻: 0 件のコメント:
ラベル:

IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)

　Eまで。

コンテスト後のツイート

F1. Kevin and Binary String (Easy Version)

　端から貪欲で良いという情報を目にしてAC。

　ツイートにも書いた通り、コンテスト中も端から貪欲で良いのでは？　と思ったのだけれど、「SとTで端に同じ文字があったら消去する」という処理を入れていたためWAになっていました。
　いやこれ、まずいかも、とは思ったのだけど、検討したら大丈夫に思えたため、実装の都合で入れたんですよね。実際はそれほど実装が楽になるわけでもないのに、無駄な処理を入れたためWAになったのは悲しい。ACしなくてはいけない問題でした。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)