Codeforces Round 1060 (Div. 2) ABD。Cが分からず。何?
— titia (@titia_til) October 19, 2025
A 言われた通りに左から決めるだけだがちょっと難読。
B 最初に操作1を全部やってしまう。
C 素数列挙or約数列挙せずに解く方法あるの?
D 木は二部グラフ。ゴールからの距離が遠いところから消していく。
2025年10月22日水曜日
Codeforces Round 1060 (Div. 2)
ABDの三完。Cが分からなかった。
コンテスト後のツイート
C1の時点で分からなかったのですが。
他の方のACコードや、maspyさんの解説などを参考にしてAC。コンテスト中の考察は普ちゃんと間違っており、結構難しい問題に感じてしまった。
コンテスト中は、A[i]たちの素因数の個数*nくらいの計算量が必要な気がしてしまったが、それはさすがに間に合わない。
Bをソートしたとき(SBとする)、SB[0]+SB[1]が明らかに答えになるので、これより小さくなる可能性があるものを探せば良いと考えると、SB[0]に対応するindex以外は、0回か1回足すことしか考えなくて良い。
そうすると、他の素数たち全てを見る必要はなく、A[ind]の素因数が、「A[i]の素因数たち(i=indを除く)の集合」に含まれるかどうかさえあれば良いので、setを使って判定できる。
これでC1は解ける。
SB[0]に対応するindexについては「A[i]の素因数たち(i=indを除く)の集合」全てに対して計算を行えば、C2も解ける。
2025年10月14日火曜日
AtCoder Regular Contest 208
AB二完。Bを解いた後長いことDを考えていたが、Cに行くべきだったみたいですね。それでCが解けたかは怪しいけれど。
コンテスト後のツイート
AtCoder Regular Contest 208 (Div. 2) AB二完。CもDも分からず。
— titia (@titia_til) October 12, 2025
A ひたすら実験したら立っているbitの和が正の偶数であることが勝利条件らしかった(未証明)
B Nが大きければ2 3 4 5……とする。小さいときは、最初の値を二分探索。A[i]=A[i-1]*2-1としていって、K以上を取れるか調べる。
C - Mod of XOR
解法ツイートを参考にAC。
実験するのは良いとして、実験の際、
・答えが出ているとき、(n^C)/Xという商がいくつになっているかに注目
するのが重要だった。これが0か1らしいと分かると
・商が0のときは、n=C^X
・商が1のときは、n^C=n+C-2(n&C)を使って変形
することで、どういうnが候補かが分かる。
コンテスト中は、どういうnが答えになるか? は見ていたけど、商に注目できていなかった。
ある程度簡単な式変形(今回なら、余りが書いてあるので割り算の形に直す)をして、実験する際も何に注目すれば良さそうか考えるべきでしたね。
2025年10月11日土曜日
Codeforces Global Round 29 (Div. 1 + Div. 2)
Dまで四完。
コンテスト後のツイート
Codeforces Global Round 29 (Div. 1 + Div. 2) Dまで。Cで苦戦。Eが解けず。
— titia (@titia_til) September 20, 2025
A 答えは2か3。2回でできないときはx方向に一歩進む。
B 6 5 4 3 2 1 6 1 2 3 4 5
C 1の海の中で、01010(0が奇数回)が現れるとダメ。実装ミスし、ランダムテストと比較して気付いた。
D 奇数個のもので多い方から取る。
E. Maximum OR Popcount
こたつがめさんの放送を見てAC。
解法を聞くと、貪欲ベースのアルゴリズムで、かなり自然なものに思えた。
結構時間は残っていたはずなのに、これを思いつかなかった/試せなかったのは情けない。
この前にI1を考えたりしていたから、こっちの考察はちょっと適当になってしまったのかなぁ、という気もする。
2025年10月10日金曜日
Codeforces Round 1052 (Div. 2)
D1まで。
D2. Max Sum OR (Hard Version)
(コンテスト直後に多少解説を見たかもしれないけど)大体自力でAC。
たとえば、l=0, r=15のとき、(7, 8), (6, 9)……のようにペアを組んでいくのが最適。
これは、最上位bitを見て、最上位bitが切り替わる場所から左右に順にペアにしていけば良いということ。
これを再帰的にやればOK。
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番目の関係性が出てくる。それを使えば、一番目が決まれば他全て決まることが分かる。
として解けたけど、やっぱり結構難しく感じる。あまり速く解けるビジョンが湧かない。
D. Batteries
自力AC。
使った回数の和が少ない方から貪欲に投げていくとACできた。が、未証明。
これでいけるのでは? と思うまで結構時間がかかった。Cを飛ばしていたとしても、こっちをACできたかは怪しい感じ。
AtCoder Japan Open -予選- (AtCoder Regular Contest 207 (Div.1))
B一完。
コンテスト後のツイート
AtCoder Japan Open -予選- (AtCoder Regular Contest 207 (Div.1)) Bのみ。BのあとAを見たが解けず、最後はDを実験していた。
— titia (@titia_til) October 5, 2025
B Nが偶数のとき、N/2以下とN/2より大きいもので分け二部グラフにする。xに対して、N+1-x以外とマッチングさせれる。奇数のときはN-1のグラフを作った後NとN/2以下を繋ぐ。
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位。
レートが落ちているときに突然過去最高順位が取れてびっくり。
コンテスト後のツイート
D bit DP。テストケースごと、(1<<W)^2かけても大丈夫なはず、と思って書いたのでTLEが不安だったが結構余裕があった。
— titia (@titia_til) September 20, 2025
E heapqに(値,個数)を入れてシミュレーション。
F 乱択+セグ木。BITでいけると思ったが混乱したのでセグ木を使った。この前ABCで乱択が出たので思いつきやすかった。
G - Set list
正しい解法は理解できていないけれど、DPで解けるらしい。
自分はビームサーチで通したのだけど、ナップザック問題に貪欲&ビームサーチの嘘解法を投げたら落とすのは大変だと思うので、結構落としにくい解法だったのかもしれない。
登録:
コメント (Atom)