2025年10月9日木曜日

Educational Codeforces Round 183 (Rated for Div. 2)

 若干遅刻してCまで三完。BやCに苦戦し、Dは間に合わず。


D. Inversion Value of a Permutation

 自力AC。

 実験したら、たとえば、

1 2 3 4 5 6 7

を、

4 5 6 7 1 2 3

 にすると、4*3の値が加算される、というように、配列を分割すると、その分割したときの値+小さい配列の場合の値になることが分かった。

 それを使ってDPしてどんな値を作れるかを列挙し、DPの復元を行って答えを出した。

 解法が分かっても結構難しい気がする。
 実験するとき、解かれている人数が多かったので、全部の値を列挙して埋め込めるのでは? などと思っていたけど、そういうわけでもないしねぇ……。



Codeforces Round 1056 (Div. 2)

 Bまで二完。Cを考えていたら睡魔に襲われた。


C. The Ancient Wizards' Capes

 解説AC。
 実は答えが少ないのでは? とはコンテスト中も思ったのだが、どうしてそうなるかが分からなかった。
 コンテスト中、寝る直前に思ったことが正解で、式にしてみると良かった。

 右に立っている人を1、そうでない人を0とし、各A_iについて式を立てると、A_i-A_{i+1}を考えることで、i番目とi+1番目の関係性が出てくる。それを使えば、一番目が決まれば他全て決まることが分かる。

 として解けたけど、やっぱり結構難しく感じる。あまり速く解けるビジョンが湧かない。

AtCoder Japan Open -予選- (AtCoder Regular Contest 207 (Div.1))

 B一完。

コンテスト後のツイート

D - Devourers and Cake

 解説AC。
 中央のみが影響する、というのを見て、中央の4*4くらいを取り出し、(コンテスト中、実験のために愚直を書いていたので)愚直コードで判定したらAC。

 コンテスト中、実験して、端が関係しないんだなぁ、とは思っていた。なのになぜ、中央だけ影響する、と気付けなかったのか。

 どうもAが解けた可能性は低そうなので、Bの後すぐDに行くのが正解だったっぽいけど、解かれている人数を考えるとそうするのは難しかったと思う。仕方ない。



ALGO ARTIS プログラミングコンテスト2025 夏(AtCoder Heuristic Contest 054)

 pretest253位、本番270位。


 得意問題に見えたのに全然順位が伸ばせず悲しかった。

 最初に斜めにいっぱい線を引き、後はゴールに近付いたらちょっと処理……みたいなのをした。

 敗因は、渦巻の良さに気付けなかったこと。
 渦巻は、思いつきはしたけど、その良さが分からず実装せずに棄却してしまった。
実装したら気付けたかもしれない。

 長期なんだからそれくらい試してみないとダメです。反省。

AtCoder × Engineer Guild オンサイトコンテスト ~集結!高レート人材~予選(AtCoder Beginner Contest 424)

 全完14位。
 レートが落ちているときに突然過去最高順位が取れてびっくり。

コンテスト後のツイート


G - Set list

 正しい解法は理解できていないけれど、DPで解けるらしい。
 自分はビームサーチで通したのだけど、ナップザック問題に貪欲&ビームサーチの嘘解法を投げたら落とすのは大変だと思うので、結構落としにくい解法だったのかもしれない。