Processing math: 100%

2025年4月11日金曜日

AtCoder Grand Contest 071

　A一完。

コンテスト後のツイート

C - Orientable as Desired

　解説AC。解説放送も見た。

　全く惜しくはなかったが、サイクルがあってもYesになる条件を考える、という方針自体は良いのかも。そういうグラフを列挙していけば正しい条件にたどりつけるかもしれない。

　ただ、解法を理解した後も、二重頂点連結成分分解を実装したことがなかったため、自力で実装できなかった。LOWLINKを使った関節点や橋は実装したことがあるので、あと一歩なはずなのだが……。

　とりあえず、二重頂点連結成分分解をChat-GPTに実装してもらいAC。原理は理解したつもりだけど、実装がよく分かっていない。ちゃんと自力で実装しなきゃなぁ。



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

2025年4月3日木曜日

April Fools Day Contest 2025

　ADの二完。


B. Plinko

　自力では解けず。
　0～17におくとゲームをプレイしなくてはいけないが、その外側におけば良かった。これは思いつきたかった。

C. Would It Be Unrated?

　解説AC。
　一つACが出るまでできることがなくないか？

D. Where Am I?

　写真を検索するとラスベガスだと分かるので、その緯度と経度を書く問題。それっぽい提出をしても「very close!」などと返ってきて、submitデバッグするしかなかった。
　……が、もっと狭い範囲に絞れたらしい。

E. Pair Count

　解説AC。リンクがあればそこを押す、ということさえしていれば、順を追って解ける問題でした。

　エイプリルフール部分の後にもk=0というコーナーがあるのも面白い。


G. Definitely a Geometry Problem

　解説AC。
　制約に引っ掛けがあるだけで普通の（注意力を要する）問題だった。問題文は丁寧に読まないとね。
時刻: 0 件のコメント:
ラベル:

2025年3月30日日曜日

AtCoder Beginner Contest 399

 　Eまで。

コンテスト後のツイート

F - Range Power Sum

　解説AC。

　「積の和典型」とも呼ばれる、組み合わせに帰着して解く問題。この解法、何度見ても解けるようにならないのだが……。
　コンテスト中に「積の和典型」で検索したのに解けておらず、辛い。





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

yukicoder contest 462

　AHCがあるのでAだけ解いて撤退した。


No.3075 Mex Recurrence Formula

　自力AC。

　実験するとN+1周期になると分かった。MEXを求めるところを愚直にやってしまったためTLEしたが、heapqを使えば良いと気付きAC。

No.3076 Goodstuff Deck Builder

　自力AC。これは迷わなかった。

　コストが大きい方から使うのが良い。残りのコストと、カードを使った回数をもってDPすればOK。
時刻: 0 件のコメント:
ラベル:

2025年3月27日木曜日

Codeforces Round 1013 (Div. 3)

　全完。
　Div. 3も最近は全完を逃していたことが多いので、今回は全完できて良かった。

コンテスト後のツイート

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

2025年3月24日月曜日

AtCoder Regular Contest 195 (Div. 2)

　三完はしたがレートは落ちた。Bは同じ解法で通している人を何人か見かけた。

コンテスト後のツイート

B - Uniform Sum

　嘘だと思ったが、（嘘かもしれないけど）それほど嘘ではなかった。

　A, Bがdistinctだとすると、S=A[i]+B[j]が何個ずつ現れるかをカウントすれば、それを見るだけで判定できる。
　今回はdistinctじゃないのでもう一工夫必要だが、大体それで良かった。

　distinctなら上手くできるのでは？　と考えるべきでした。

D - Swap and Erase

　解説AC。

　コンテスト中に考えていた貪欲（左から見ていき、A[0]==A[2]ならA[1]とA[2]をswapする）がどういうときまずいのか気付けなかったのが敗因。

　たとえば、

・1 2 1 1 1

　のときまずかった。A[0]とA[1]をswapしなくてはいけないときもある。

　Aの各要素が高々一回しかswapされないというのは言われてみれば自然だし、貪欲でダメと分かればDPしようと思えた可能性はあるかもしれない。

E - Random Tree Distance

　解説AC。解説放送も見た。

　まず、lcaを考える（u,vの距離を、D[u]+D[v]-2*D[lca]とする。D[x]は1からxまでの距離です）のはすべきだった。lcaがどこにあるか分からないから、lcaを考えることで状況が良くなるとすぐには思えないけれど、これはまずして良いですね。

　あとは、D[lca(u,v)]が、u<vのときvの値によらないと気付けるか、だが、これは実験していれば気付けるかもしれない。しかし、その後、D[lca]に関する漸化式を立てる部分が理解できず、解説を見ながら悩んでしまった。lcaが再帰的に決まっていく、と考えれば難しい式ではないのだが……。

　発想があった方が良い部分（D[lca(u,v)]が、u<vのときvの値によらないと気付く部分）もあるけれど、それ以外の定石的な部分でも詰まっているので、その部分はどうにかしたい。
　
時刻: 0 件のコメント:
ラベル:

2025年3月23日日曜日

AtCoder Heuristic Contest 044

　98位。

　コンテスト中バグらせて書き終わらなかった方針を最後まで書いていれば30位くらいにはなったので、惜しかったといえば惜しかった。

コンテスト後のツイート




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