yukicoder contest 291

 　ABの二完。Bで唖然とするようなミスをして、Cも分からぬまま終了……。

コンテストへのリンク

No.1478 Simple Sugoroku

　自力AC。

　ワープを使う場合、「後ろx個へワープで辿りつけたらそこからは歩く」という戦略を取るのが良く、このxを全探索すればOK。

No.1479 Matrix Eraser

　フローの練習で解いた。自力でグラフは構築したがTLEが取れず、他の人の提出などを見てAC。

・start→縦でまとめられるもの→(i, j)→横でまとめられるもの→goal

　というグラフを考えたが、これだとMLE・TLEしてしまった。

　（i, j）の部分は省略することが可能。また、A[i][j]の値ごとにflowを流せば良いので、H+Wの大きさのflowをHW回流す感じで解ける。

　こうすればACできた。

　ただ、言語とかDinic法の実装とかで工夫したら最初の方針でもACできたはず。そういうライブラリも持っておきたいね。

Educational Codeforces Round 165 (Rated for Div. 2)

　Dまで。

コンテストへのリンク

コンテスト後のツイート

D heapqを二つ使う。一つ目のheapqにある要素で儲けを出すとし、その要素を無料で与えるとしたときの損失を入れておく。二つ目のheapqにはA[i]の値を入れる。一つ目のheapqから二つ目のheapqへ入れ、二つ目のheapqの要素を常にkにするようにして、答えを計算。

— titia (@titia_til) April 29, 2024

E. Unique Array

　解説AC。

　このG問題の類題で、似た解法で解ける。

　各要素が唯一である区間を長方形と思って管理するところまでは同じ。その後、それを使って貪欲に処理していく。

　最近解いた問題なのに、コンテスト中も、今復習しようとしたときも全く思い出さなかったのはひどいのでは。

AtCoder Beginner Contest 352

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 352 Eまで。
A X<Z<Y or Y<Z<X
B 尺取り
C B-aが一番大きいものを最後に。
D SortedSetをお借りしました。
E Cの小さい順に。
F 2-SATで解けそう！　と実装し始めたが上手くいかず終了。あれ、2-SATで解けないの？

— titia (@titia_til) May 4, 2024

 F - Estimate Order

　解説AC。

　重み付きUnion-findで連結成分ごとにまとめた後、bit DPする。bit DP部分をDFSっぽくやって高速化した。

　コンテスト中もまずbit DPできないか考えたはずなのだが上手くいかない気がし、2-SATでいけると勘違いして突き進んでしまった。「どれか一つが真」って条件は2-SATで表せないですね。

　色々ひどかったけど、2-SATの復習は多少できたかもしれない。

G - Socks 3

　解説AC。

・前半の、期待値を場合の数に置き換えるパート

・後半の、場合の数を多項式の積で表し、形式的べき級数で計算するパート

　どちらも典型なのだが、身に着いていない。

　どちらかというと、後者は問題演習を積めば身に着く気がするので、前者の方がより身に着けたい内容か。期待値を、「i回以上である確率P_i」の和で表すという方法は覚えておきたい。

Codeforces Round 942 (Div. 1)

　B2まで。CombinedじゃないCodeforces Div. 1はちょっと避けたりしていたけど、今回は参加。レートが落ちず良かった。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 942 (Div. 1) B2まで。
A 少ない数字から増やす。最小の個数+1まで使ったときの和-(n-1)
B1 bを固定すると、aはb*b-bからb*bごと
B2 a+b=cとするとcが平方数のk倍でa:b=i:c-iとなるようなiがあればOK。
C 増え方が等差数列という間違った考察をしていた。

— titia (@titia_til) April 30, 2024

 C. Fenwick Tree

　解説AC。

　各成分の、k回後に対する寄与が二項係数になるということに気付けなかった。それが分かればすんなりAC。

　なお、コンテスト中考えていた解法だとΣのベキ乗の係数が必要そうになったのだが、その方向でも正しい答えを得る方法はあったらしい（が、理解できていない）。

Codeforces Round 943 (Div. 3)

　時間ギリギリ全完でした。

　G2の方針自体はもっと速く思いついていたんだけど、これで計算量が良いかで迷い、またSortedSetを使わなくては実装できないのか？（使ったらTLEするのでは？）　といったあたりでも迷って時間かかってしまった。

　あと、並列二分探索でできないか？　などとも考えた（できなかった）。

　実際に実装してみたらACでした。

コンテストへのリンク

コンテスト後のツイート

F 累積xorを取りこれをXORとする。l～rのxorが0ならOK。違うときは、間に、XOR[r]と同じもの、XOR[l-1]が含まれれば良い。
G1 Z algorithmした後二分探索
G2 x文字をLCPに持つものは何個取れるか？　を全探索しても、次の場所を二分探索していけば、二分探索のlogと調和級数のlogの二つで済む。

— titia (@titia_til) May 2, 2024

AtCoder Regular Contest 176 （Sponsored by Mynavi）

　Cまで三完。ARCでこれくらいの順位が取れると嬉しい。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 176 （Sponsored by Mynavi） Cまで三完。
A (j-i)%NをM個選び斜めにおいていく。
B M=K+1の場合は別に計算。N<Mなら答えは2^N。そうでないとき、K=0に帰着。2^N%(2^M+1)は2^(N-M)%(2^M+1)と一致する。
C Cが小さい方から見て頑張って場合分け（ABより考え方は楽だと思った）

— titia (@titia_til) April 21, 2024

D - Swap Permutation

　けんちょんさんの解説記事を参考にAC。

　解法ツイートで行列累乗で解けるというのを目にしたが、ある(a,b)というペアが最終盤面でどのような位置にあるか？　という遷移を考えてしまい、上手くできなかった。

　index i, i+1が最終的にどの数字になっているか？　に着目するのは言われてみれば自然。コンテスト中に解けなかったのは仕方ないにせよ、行列累乗で解けると言われたら思いつきたかった。

E - Max Vector

　解説AC。

　問題を読んでフロー（最小カット、燃やす埋める）じゃないかとは思ったが、どうやってグラフを作れば良いのか。

　とりあえず、

・Nが多いことはあまり本質的ではない。N=1の場合に関するグラフを構築すれば、一般のNでのグラフも（今回は）同じように構築できる。

・X_i+Y_iなどというのはフローで扱いにくそうだし、X_j, Y_j, A_ijが500以下という条件があるので、各数字に関する頂点を作りそう。

　というあたりを手がかりにすれば良かったか。

　ただ、劣モジュラ関数についての一般的な知識は得ていた方が良いのは間違いない。theory and meさんのこの記事を理解すべきだよね……。

Educational Codeforces Round 163 (Rated for Div. 2)

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

Educational Codeforces Round 163 (Rated for Div. 2) Eまで。
A AAとBBを繰り返し。
B 今までの最大値を管理。
C DPというかDFSした。
D 幅hでh個連続で一致していれば、答えをhにできる。
E たとえば頂点5k=5なら 4 5 1 2 3とすればクリークにできる。この繰り返し。

— titia (@titia_til) March 15, 2024

F. Rare Coins

　解説AC。

　自分になじみのない解法が必要かと思って解説を見たのだが、普通の方法で解けた。

　ちゃんと問題を整理し、1/2の確率で自分のお金が増える、相手のお金が増える、というのを元のお金を調整して、「1/2の確率で差を減らす」と解釈するとシンプルな二項係数の和になる。