AtCoder Grand Contest 052

　A一完で、そのAも未証明でした。

コンテストへのリンク

コンテスト後のツイート

A - Long Common Subsequence

　"0"をN個、"1"をN個並べる解法は、問題を見た当初考えた。それで、どんなS+Sに対しても、前半部分から"0"N個を、後半部分から"1"N個を抽出できる。

　その最初や最後に"0"や"1"をつけるという方法も考えたのだけど……。

　S="111000"のときS+S="111000111000"で、

　ANS="0"+"111000"とすると、

　前半で三つの"1"を使ったら、その前に"0"が置けないので無理！　と思ってしまった。が、実は後半で"111000"全て消費できるので、部分列になっていた。

　これに気付かず迷走。Sを元に作る解法を考えてWAを出した後、

　最終的には、"0"*N+"1"*Nの前後に"0"や"1"を付け加えたもの全てに対して、実際に部分列になっているかどうか確かめるコードを書き、なっていたら答えとするものを書いてACした。

　未証明だったけど、長さ2*Nで、部分列になっているものは作れているのだから、2*N+1もそれに近いもののはず！　と、信じられたのは良かったか。

　そこそこ正しそうな方針を思い付いたら、その方針を元に考えた方が良いことが多いと思うので。（全然間違ってたってこともあるんだけど。まあ、そのときは仕方ない）

B - Tree Edges XOR

　解説AC。

　辺に関する条件は扱いにくいので、頂点に関する条件に読み替えられないか？　と考えるのがポイント。

　その後も難しいけど、読み替えができたならいけそう。難しい問題だと、なんとか別の問題に言い換えられないかと考えるのは重要ですね。

 

　

Codeforces Round #748 (Div. 3)

　pretestは全完。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round #748 (Div. 3)　pretestは全完
C ソート
D1 gcd
D2 判定問題はn回で解ける。10^6*nでもいけそうだけど（？）、xでダメならkxでもダメなことを利用して削減。
E 葉からDP
F DP。復元が面倒。
G 偶数番目の[と奇数番目の]がペアになるので、偶数個目の[]と奇数個目の[]を累積和で前計算

— titia (@titia_til) October 13, 2021

　システムテスト全部通っていたら、ツイート貼り付けただけで記事書かなくても良いかなー、とか思っていたら、D2はWA、FはTLEと二問も落ちてしまった。

　Fは累乗を前計算したらOK。

　D2は、解の上限を見誤っていたためダメで、そこを直したらTLE。約数全列挙で解を絞るという方法でAC。

　ツイートした解法でも速い言語ならいけるかもしれないけど、良い解法ではなかった。

Educational Codeforces Round 116 (Rated for Div. 2)

 　Cまで三完。

コンテストへのリンク

E. Arena

　ツイッターでDPの定義を見てAC。

・DP[i][j]=残りi人で、残った一人の最大値がjのとき一人だけが勝つ場合の数、とする。

　答えは、DP[n][1...x]を全体から引いたもの。

　遷移は、最大値がi-1だけ減るので、そのとき何人いなくなるかで場合分け。k人いなくなるなら、pow(i-1, k)*Combi(i, k)を掛ける。

　計算量は三乗だと思うけど、定数倍が小さくなるのでOK。

　DPを疑うのは自然だし、分かってしまえばDPの定義も自然に思えるけど、思いつけなかったね……。

技術室奥プログラミングコンテスト#6 Day1

 　EまでとH、Jの七完。

コンテストへのリンク

F - Frog and Tadpole

　自力AC。

　xマスにいたカエルがyマスへジャンプするとする。このとき、x+1～y-1にあるマスは、白マスでも黒マスでも良い。

　なので、マスiまでたどりつく場合の数をDP[i]とする（つまりDP[N]が答え）と、

・DP[y]=DP[y-1]+2*DP[y-2]+...2^(y-x-1)*DP[x]

　となる。

　このままだと二乗の計算量だが、累積和を使って高速化すると間に合う。

G - At Most Two

　最長共通部分列 (LCS)は二次元DPにより求められる（たとえば、この解説）。

　だが、実質的に値が変わるのは、A[i]とB[j]で同じ値が含まれる箇所のみ。

　B[j]と一致するのがA[k]とA[l]のとき、

　DP[k][j]=DP[k-1][j-1]+1, DP[k][l]=DP[k-1][l-1]+1

　と変更されうるのは二か所のみ。

　他のxについて、DP[x][j]は、DP[x][j-1]と一致している。

　なので、区間最大値を取得できるセグメント木を使ったDPで更新していける。

　……と、文字で書くとこんな感じだけど、二次元の絵を描かないと分からないと思う。LCSは二次元DPだから、今回もとりあえずその絵を描いてみる、というのが重要。

I - 1<->k

　解説AC。

　コンテスト中なら、実験エスパーを目指すのが最善だろうけど、なぜか実験していなかったよう。

　解説二行目、「中国剰余定理よりf(n)は乗法的関数」というところがなかなか理解できなかったので、そこを埋めておきます。

　中国剰余定理（参考）は、

　p, qを互いに素な生整数としたとき、任意のa, bについて、

・x=a (mod p)

・x=b (mod q)

　を満たす整数xが[0, p*q)　にただ一つ存在する。

　というもの。

　この定理で、a=b=1の場合を考えると、x=1は「x=1 (mod p), x=1(mod q)」を満たすので、

・x=1 (mod p), x=1(mod q)　を満たすのはmod p*qでは x=1 のみ（*）

　と分かります。

　ここで、

・y^2=1 (mod p)

・z^2=1 (mod q)

　となるy, zを考えます。中国剰余定理を使うと、

・x=y (mod p)

・x=z (mod q)

　となるxが[0, p*q)　にただ一つ存在しますが、x^2=1 (mod p)、x^2=1 (mod q)なので、（*）より、x^2=1 (mod p*q)　と分かります。

　長くなってしまったけど、こんな感じで良いはず。ここを乗り越えれば、その後の解説は追えるはずです。

K - Dial Key

　解説AC。

　自分では、

　各要素について、「区間に+1/-1」した後、「ある要素に+1/-1」を用いて調整するしかない。ので、一つ前の要素について「区間に+1/-1」でいくつへ変更したか？　を持ってDPすれば良い。

　……みたいなことを考えていたが、これではダメ。先の方まで区間を使った後、前の部分を処理することがある。

　正しくは、「区間へ+1する処理」→「区間の前と後の二か所で差が変わる」と考えるのがポイント。これは典型の一つなのに思いつかなかった。反省。

　ただ、その後貪欲にやって良いというのもピンと来なかったので、自力ACは結構遠かったかな。

サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

F - Cleaning Robot

　解説放送を聞いてAC。

　方針が思いつけなかったけど、

　文字列一回で移動する量(x, y)が重要そう　→　(x, y)の何回かの移動で一致するものをひとまとめにして考えよう

　というのは結構自然に思える。

　理解できた後も、「どうしてこんな解法思いつくんだろう？」みたいな問題は仕方ないけど、分かってしまえば簡単、のような問題には食らいつきたいね。

G - Propagation

　平方分割と言われれば解ける。

　しかし、平方分割に気付けなかったのは問題。類題経験もあったのに。

AtCoder Beginner Contest 221

　Fまで六完でした。

コンテストへのリンク

コンテスト後のツイート

G - Jumping sequence

　解説放送を聞いてAC。

　45度回転すればx軸、y軸を独立に考えることができ、部分和問題に帰着できる。

　マンハッタン距離を扱うときに45度回転はよく登場するけれど、こういう風に使うことがあるとは知らなかった。

　bitset高速化の方針でACしたけれど、MLEなども気を付けねばならず結構大変だった。

　解説放送後半にある、部分和問題のもっと計算量の良い解法はこれから理解したい。→解法は一応理解したけど、実装が大変そうなので放置します。

H - Count Multiset

　解説放送を聞いてAC。

　ヤング図形との対応に気付けばDPへ持ち込むことはそれほど難しくなさそう。

　また、分割数と似ていると思えれば、（分割数の求め方を知っていれば）ヤング図形との対応を考えるのは自然だった。

　というわけで、「写像12相」をちゃんと理解していれば解ける問題、と言えそうだけど、ちゃんと理解するのは結構大変。

大和証券プログラミングコンテスト2021（AtCoder Regular Contest 128）

　Cまで三完。橙パフォで2100復帰。ただ、Cまでがたまたま速く見えただけで、一時間以上残せたのにD以降の難しい問題に手が届いていないのは悲しい。

コンテストへのリンク

コンテスト後のツイート

D 最後二要素のあるなしをもってDPかと思ったが答えが合わず終了。23/51個ACだからちょっとは惜しかった？
……と思ったけど、解説を見たら全然違いそうだ。

— titia (@titia_til) October 16, 2021

D - Neq Neq

　解説AC。

　前半の考察部分と、後半、それをDPにする部分、どちらもすごく難しいというわけではないのだけど、結構考えにくい。

　コンテスト中、一時間以上時間を使ったけど、考察も正確ではなかった。

　まず、

・「1 1 1」のように同じ数字が連続する場合は全部残すしかない。

　ことには気付く。そして、

・「1 2 1 2 1 2 1 2」のように二つの数字が繰り返される場合、その間二個の数字を両方消すことはできない

　かと思ったが、それは間違い。「1 2 1 2 1 2 3」なら、右から順番に消していけば「1 3」まで消すことができる。

　とは気付いたのだけど、二番目の内容を正確に記述することができなかった。

　公式解説の通りで、

・種類数が2で長さが4以上のとき、両端を残して間を消すことはできない

　と記述できる。

　言われればなるほど、という感じだけど、正しく分かっていたかは疑問……。

　さて、それをDPに直すところも難しい。私は、公式解説のdp[i]の定義が分からず困ってしまった。

　ここでは、

・DP0[i]=i番目のボールを残したときの（i番目までの）場合の数

・DP1[i]=i番目のボールを除いたときの（i番目までの）場合の数

　とする。

　一番初めのボールは残すしかないので、DP0[0]=1、DP1[0]=0。

　また、特に制約がなく、残すことも除くこともできる場合は、DP0[i]=DP1[i]=DP0[i-1]+DP1[i-1]となる。また、同じ数字が連続する部分では、DP1[i]=0となる。

　あとは、「種類数が2で長さが4以上」の条件について考える。

　たとえば、

・A=[1, 2, 1, 2, 1, 2, 1]

　のとき、

DP0=[1, 1, 2, 3, 5, 8, 13]

DP1=[0, 1, 2, 4, 7, 12, 20]

　となる。

　これは、DP0[i]=DP0[i-1]+DP1[i-1]から、ダメな場合を除く、と考えると求められる。

　たとえば、DP0[3]=3は、DP0[2]+DP1[2]=4からDP0[0]を除いている。このとき除いているのは、「1, _, _, 2」と、間にある二つを取り除いた場合だ。

　同様に、DP0[4]=5は、DP0[4]+DP1[4]=7から、DP0[0]とDP0[1]を除いている。それぞれ「1, _, _, _, 2」と、「?, 2, _, _ ,1」に対応している。

　DP0[5]=8は、DP0[5]+DP1[5]=12から、DP0[0]とDP0[1]とDP0[2]を除いている。

　こんな感じでDP0とDP1を求められる。

　あとは、DP0に関する累積和を考えると、O(N)になる。

yukicoder contest 318

　A一問解いて、Bを考えているうちに意識が……。

コンテストへのリンク

No.1708 Quality of Contest

　コンテスト後、自力AC。

　思いついてしまえば当たり前に思える解法なのに、なかなか思いつけなかった。

　ただソートするだけの解法を考えて、それと比較すれば正しい解法が分かった。

No.1709 Indistinguishable by MEX

　解説（というか、解法ツイートを見て）AC。

　mexの値を小さい方から見る、というのは自然ですね。

　これを思い付けなかったのは良くない。

yukicoder contest 317

　ABCEGの五完で終了。

　今回は簡単だったようで、もっと解かなきゃいけなかったみたいだけど、問題文がちょっと分かりにくかったせいもあって厳しかった。（Eが分かりにくいという声が多いみたいだけど、私にはDの方が分からなかった）

コンテストへのリンク

No.1702 count good string

　結局読解できなかった。

　正しく読み解くと、

・Sの部分列で、"yukicoder", "?ukicoder", "y?kicoder", ..., "yukicode?"のいずれかとなるものが何個あるか？

　という問題だった。

　一旦分かってしまえば、確かに問題文もそう読めるのだけど、私は「良い部分列のうち Tに含まれる部分列」というのが解釈できなくて止まってしまった。

　サンプルの説明は書いて欲しかったなぁ……。と思うけど、コンテスト中に90人くらいに解かれているのだから、自分の読解力がまずいのでしょう。（とはいえ、読解力ってどうすれば鍛えられるか分かりにくいんだよねぇ）

　題意が読み取れればDPで解けます。

No.1704 Many Bus Stops (easy)

　これは誤読していた。

　1.5秒かけて別のバス停に到着したらまたすぐ動き出すものと思い（ただし、同じバス停に残ったものは1秒後に動き出すのかと考えていた。不思議）、行列累乗だとは思ったものの、遷移を書くのが難しいな……と考えていた。

　うーん、質問の「iは整数」というのも読んだはずなのに、こんな誤読をするのは良くない。

　行列累乗と分かれば、

・バス停xにいるか

・バス停xに向かう途中か

という6状態を考えて行列累乗すればOK。

　さらに、バス停A以外を区別する必要はなく、Aとそれ以外にだけ分ければOKと気付けば（これに気付かず、一回MLEなコードを投げてしまった）、hardの方も解ける。

Kotlin Heroes: Episode 8

　Eまで五完で終了。Kotlin Heroes以外ではほとんど書いてはいないけど、Kotlinはそこそこ書けるつもり。なのに、前半の問題で解くスピードがかなり遅いのは、書き慣れていないということなのかなぁ。

　このコンテストで50位以内に入ることは目標の一つなのだけど、今回は掠りもしなかった。

コンテストへのリンク

コンテスト後のツイート

F. Kotlinforces

　制約が本質の問題。

　$t_i$が1か2ということに気付かないと始まらないが、コンテスト中はそこまでに結構時間がかかってしまった。

　$t_i$が1のやつは端から詰めれば良いので、$t_i$が2のやつについて考える。

　$t_i$が2のやつは、

・偶数番目の端から詰める

・奇数番目の端から詰める

　の二通り考えなくてはいけない。どちらかが最適となる。

　これは、二次元DPでDP[i][j]で、偶数番目が残りi個、奇数番目は残りj個、とやればできるが、これだとTLE。（コンテスト中、ここまで考えた）

　だが、よく考えると高速化できる。

　それまで何文字使ったかは分かるので、偶数番目が残りi個のとき、奇数番目が何個使ったかは、「奇数番目の個数 - 偶数番目に今まで使った個数」で求めることができるのだ。

　これで一次元のDPになり、計算量は二乗になる。

　そして、DPした後、DPの復元を行うことで答えが求められる。

　DPの復元パートもあるし、そこそこ実装が面倒で、コンテスト後ACするまでには結構時間がかかってしまったけど、もっと楽に書く方法はあるんだろうか。

　

yukicoder contest 316

　（途中で休憩してしまったけど）Bまで二完で終了。

コンテストへのリンク

No.1694 ZerOne

　解説AC。

　01と10を入れ替える問題になることには気付いたが、そこから進まなかった。一つの01, 10は一回しか動かないのかな？　と思ってDPを書いたけど、そんなことはない。

　01と10が入れ替わるということは、片方の1のindexが1増え、もう片方は1減る、ということなので、各1のindexの和の合計が不変量になるのがポイント。

　これは気付きたかったね……。