yukicoder contest 397(群論コンテスト)

　ABDの三完。

No.2381 Gift Exchange Party

　解説AC。

　こういう問題で、iからA[i]に辺を張ったグラフを考えるのは典型。Pが素数なので、そのグラフにおけるサイクルが全て1かPになれば良い。

　コンテスト中は、Pが素数だということを読み飛ばしていた。が、このグラフすら考えていなかったのは反省。サイクルが～みたいなことをぼんやりと考えていたはずだが、何を考えていたのだろう……。

　また、実装はTester解説の方法でやったが、累積積による高速化が必要なことに気付かなかったりして手間取った。

　DPでやるのが簡単なのですね。今まで使っていない最も小さな数に注目するのが良いのか。それならPが素数じゃなくても解ける。形式的ベキ級数でも扱えるらしい。

No.2383 Naphthol

　バーンサイドの公式について、高校数学の美しい物語を参考にしながらAC。

　modを取っているのに、（*pow(4,mod-2,mod)とせず）4で割っていて答えが合わず困ったのは恥ずかしい。

　

AtCoder Regular Contest 163

　AB二完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 163 Cが分からず終了……。
A 全探索
B 尺取り法
C 「2 3 6」のそれぞれにxをかけると1/xが作れることを利用しようとしてもがいていた。解説の方法は全く思いつかなかったのでどうしようもない……。

— titia (@titia_til) July 2, 2023

C - Harmonic Mean

　解説AC。

　部分分数分解を利用するというのを見て実装しようとしたら、全体二倍にするというのを思いつかず苦戦してしまった。

　部分分数分解を利用する方針は全く思いつかなかったので解けなくても仕方なかった……とも思うが、他の方針で（やや強引に）通している人も結構いる模様。それを見るとどうにかして通したかったという気持ちになるが、どうすれば良かったかね。

　コンテスト中は、和が1になるものx個を使って、それらをx倍したものを合併させる。もしくは、3個を2, 3, 6倍したものを合併させる……というような方針を考えていたが、Nが100～150あたりまでしか作れなかった。

D - Sum of SCC

　解説AC。

　問題を見て、主客転倒的なテクニックを使いそう、とは思ったが、グラフを二つに分けて考えるという発想はなかなか難しい。

　SCCをs0→s1→s2→……のように表してみて、この矢印をどこで区切れば良いか？　と考えれば思いつけるのかなぁ。

　また、解説通りのDPをしたつもりが答えが合わずに苦労した。

　解説の一行目の「以下の値-1に等しいです」というのは、A側が空の場合とB側が空の場合をダブルカウントしているため、ということなのですね。

　これを踏まえて、最終的な答えを求めるときも、i（解説のdp内の添え字）の範囲を[0, N)もしくは(0,N]にしなくてはいけなかった。

　類題だと話題になっていたこの問題も解いておいた。

　が、今回の問題の解法に引っ張られて二乗のDPで解く方法しか思いつかず、oeisを使ってなんとかAC、としてしまった。

　解説（のコード）を見ると、簡単に立式できましたね……。

yukicoder contest 395

　ABの二完。

コンテストへのリンク

No.2366 登校

　解説AC。

　ダイクストラを使いそうなのは分かるので、どういうダイクストラを使ってどうすれば計算量を減らせるか考える問題。

　疲労度の最小値を求める問題なので、

・DP[座標][時間]=疲労度の最小値

　とするのは自然。ただ、これだと時間をどの範囲で取ればいいか分からないのだけれど、どの地点からもN+M-2歩以内で行けることから時間を絞れる、という考察が必要でした。

　こう書くと自然な考察で解けるので、解きたかったね……。

　そして、解説を読み直しながらこの文章を書いていたら、実装ミスしていたことに気付いたので、再提出＆自分のコードにChallengeにしておいた。

　時間を巻き戻すとき、昔過ぎる時間に巻き戻る遷移を禁じた実装をしていました。

Codeforces Round 880 (Div. 1)

　A一完のみ。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 880 (Div. 1) Aしか分からなかった。
A aを全探索。
B mの制約が小さければできそうなのだが……。
C 鳩ノ巣原理を使うのかなーと考えていたけど、そこから考察が進まず。

— titia (@titia_til) June 18, 2023

B. Lottery

　こたつがめさんの実況放送を見てどうにか理解した。

　この解法に思い至れなかった要因は、当たりの位置をずらすことを考えていて、「何番目を買うとしたら当たりくじの位置はどこからどこまでか？」という考え方を全くしなかったこと。その後の考察も難しいけど、少なくともこれはどちらも考えてみるべきだった。

　PyPyだとTLEしたためRUSTに直したが、そこでも苦戦した。特に、

・RUSTのbinary_searchで、その要素が複数個入っていたときは、そのうちどのindexをわたすか分からない（多分。自分で実験した限りはそうだった）

　というのを知らなかったため原因に気付かず大変だった。今度RUSTで二分探索を使うときは気を付けよう。

C. Twin Clusters

　こたつがめさんの実況放送で理解。ただ、実装は乱択で通した。

　区間xorの値が同じになるのが二つあれば、それを使って答えが作れるのだろう……とは思っていたが、0が一つだけある場合はそれを除いて考えて良いということが分かっていなかった。そうすると、端点が同じ（[l, r]、[l2, r2]でl=l2の場合）な場合に答えが作れるということも。

　これを思い付いていれば、乱択しようと思えたかな……。

　乱択じゃない解法については、鳩ノ巣原理を利用したいという気持ちを強く持てば下半分と上半分の桁で分けようと思えるのかな、と感じた。

　ただ、この鳩ノ巣原理はかなり余裕があるからできているわけで、それなら乱択で通るよね、という気持ちになった。

TOYOTA Programming Contest 2023 Summer（AtCoder Heuristic Contest 021）

　最終順位319位で、予選通過はダメでした。（ツイッターで317位と書いてしまったけどまだジャッジ中だったみたい）

コンテストへのリンク

コンテスト後のツイート

ツイートを見ていたら同じ勘違いをしていた人が何人かいたけど、各数字が、0,1,2,..と並べたときと同じ段にならなくてはいけないと勘違いしていました。
コンテスト開始30分後あたり～終了まで。
それで132くらいは出ることも、勘違いを気付きにくくする原因になってしまった。

— titia (@titia_til) June 25, 2023

　解法は、ツイートの通りで、

・大きい順に、経路のコスト（置きたい段との差をコスト）を求めるDPをしてコストが小さいものを採用、としました。

　ただ、これは勘違いしていたせいです。ツイートを見ていたら同じ勘違いをしていた人が何人かいたけど、

・各数字が、0,1,2,..と並べたときと同じ段にならなくてはいけない

　と勘違いしていました。それで最初言ったような解法になってしまった。

　アルゴリズムの問題でもそうだけど、誤読とか、勘違いとかを一度してしまうと修正するのは難しい。

　今回は、最初に「適当に上下で値が入れ替わっていたら交換しまくる」というのを提出しているので、それでOKだったことを振り返る余裕があれば気付けたはずなのだけども……。まあそんな余裕はなかった。

　ただ、この勘違いがなくても、上手くできたかどうか。

　今回は、「13426585点が取れる貪欲アルゴリズム」を思い付けるかどうかが鍵だったが、これで上手くいくというのはそれほど明らかじゃない気がした。

　さらに、その改善ともなると、うーん。Kiri8128さんの解説の評価関数も全く思いつかなかった。これを実装したら確かに改善したけど、自分で思いつけたかというと……。

　ただ、コンテスト中、順位表で上位に同じ点数の人がたくさんいるのは見て、「何か簡単な解法があるはず」とは気付いていたのだから、とにかく色々な貪欲を試してみるべきだった、とは思う。

・小さい数字から試す

・上の二つのうち大きい方と交換

　というの自体は両方とも考えたことはあったのだから。

　それで自分の点数より伸びるとは思わなかった（ことと、勘違いしていた）から試さなかったのだけれど、それでも実装してみて、他にどんな解法やパラメータがあるか探らなくてはいけなかったのだろう。

東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 307）

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

G x=sum(A)/Nとすると、各要素をxかx+1にしたい。x+1にした個数とかをもってDPかと思ったが上手くいかなかった。今までで使った最後のA[i]ももって雑にDPしたがWAが出た。

— titia (@titia_til) June 24, 2023

F - Virus 2

　解説AC。

　（感染した日, 感染した場所からの最短距離）を持つダイクストラでやった。これだと、「l日以降でx以上の数字がXに表れる一番最近のindexはどこ？」に答える必要があったので、セグ木二分探索を使った（使わなくてもできるらしいが、よく分からず……）。

　ダイクストラすることは明らかで、どんな解法でもできそうに思えるけど、実際に実装しようとするとつまる……みたいな問題だと思う。

　多分、解説見なくてもごちゃごちゃやっていれば解けたと思うけど、素早くこなすためにはどうすれば良いのかね。

G - Approximate Equalization

　解法ツイートを見るとツイートで書いた内容で大体あってそうで、

・x+1にした個数をもってDP

　だけ持てば良かった。

　それだと次の数字が何か分からない（一意に定まらない）気がしてしまったが、累積和を取っておけば、そこまでで使ったxやx+1の個数が分かっているため、差分計算で求まり、一意に定まる。

　制約を見ても二乗DPできそうなので、ツイートした内容のところまでいけば、正しい解法に至ることはできそうなのにねぇ。うーん。

　なお、解法が分かったつもりで実装しようとしたら、再度、「やっぱり次の数字は分からないのでは？」と思ってもう一度再考してしまったし、その上、一番最後にx+1を使う場合を考え損ねてWAを出したりした。

　解けなきゃいけない問題だったと思うのに、この様はまずい……。

yukicoder contest 394

　AB二完。

コンテストへのリンク

コンテスト後のツイート

yukicoder contest 394 ABの二完
A 何も分からず実験コードを書いた。
B 適当に書いたらTLE。（chatGPTさんにお願いして）RUSTに直して提出。
C imos法っぽくやったらTLEでした。heapq使ったのがまずそう。

— titia (@titia_til) June 23, 2023

No.2359 A in S ?

　解説は見たけど自力（？）AC。

　コンテスト中、「X, Yの条件がなければimos法だなぁ」と思い、XとYの条件があっても、それらをまとめて計算すれば計算量が落ちるのかも？　と思ってheapqを使って（小さい(index, X)から処理するためにheapqを使った）書いたがTLE。heapqを使わずに書けそうなので、そこからlogは落とせると思ったが、計算量に自信がなかった（のと、BでRUSTに直してACしたので、この問題もRUSTに書き直そうか迷っていた）ため書き直さなかった。

　解説を見たら、それで実際計算量が落ちると書いてあったので、書き直してACしました。