2025年10月22日水曜日

Codeforces Round 1060 (Div. 2)

 ABDの三完。Cが分からなかった。

コンテスト後のツイート

C2. No Cost Too Great (Hard Version)

　C1の時点で分からなかったのですが。
　他の方のACコードや、maspyさんの解説などを参考にしてAC。コンテスト中の考察は普ちゃんと間違っており、結構難しい問題に感じてしまった。

　コンテスト中は、A[i]たちの素因数の個数*nくらいの計算量が必要な気がしてしまったが、それはさすがに間に合わない。
　Bをソートしたとき（SBとする）、SB[0]+SB[1]が明らかに答えになるので、これより小さくなる可能性があるものを探せば良いと考えると、SB[0]に対応するindex以外は、０回か1回足すことしか考えなくて良い。
　そうすると、他の素数たち全てを見る必要はなく、A[ind]の素因数が、「A[i]の素因数たち(i=indを除く)の集合」に含まれるかどうかさえあれば良いので、setを使って判定できる。
　これでC1は解ける。

　SB[0]に対応するindexについては「A[i]の素因数たち(i=indを除く)の集合」全てに対して計算を行えば、C2も解ける。

　



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

2025年10月14日火曜日

AtCoder Regular Contest 208

　AB二完。Bを解いた後長いことDを考えていたが、Cに行くべきだったみたいですね。それでCが解けたかは怪しいけれど。

コンテスト後のツイート

C - Mod of XOR

　解法ツイートを参考にAC。

　実験するのは良いとして、実験の際、

・答えが出ているとき、(n^C)/Xという商がいくつになっているかに注目

　するのが重要だった。これが0か1らしいと分かると

・商が0のときは、n=C^X
・商が1のときは、n^C=n+C-2(n&C)を使って変形

　することで、どういうnが候補かが分かる。

　コンテスト中は、どういうnが答えになるか？　は見ていたけど、商に注目できていなかった。
　ある程度簡単な式変形（今回なら、余りが書いてあるので割り算の形に直す）をして、実験する際も何に注目すれば良さそうか考えるべきでしたね。
時刻: 0 件のコメント:
ラベル:

2025年10月11日土曜日

Codeforces Global Round 29 (Div. 1 + Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Maximum OR Popcount


　解法を聞くと、貪欲ベースのアルゴリズムで、かなり自然なものに思えた。
　結構時間は残っていたはずなのに、これを思いつかなかった/試せなかったのは情けない。

　この前にI1を考えたりしていたから、こっちの考察はちょっと適当になってしまったのかなぁ、という気もする。
時刻: 0 件のコメント:
ラベル:

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。


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

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の復元を行って答えを出した。

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



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

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できたかは怪しい感じ。
時刻: 0 件のコメント:
ラベル: ,

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

　B一完。

コンテスト後のツイート

D - Devourers and Cake

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

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

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



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