yukicoder contest 235

　遅解きの五完でした。五問目でC++を使ったのが遅くなった原因ですね……。慣れない言語を使うと、そんなに上手くいかなくても達成感があります。良いのか悪いか。

コンテストへのリンク

No.975 ミスターマックスバリュ

　MaxValuは知っていたけど、ミスターマックスは聞いたことなかった。そんな店があるんですね。

No.976 2 の 128 乗と M

　Pythonだとpow(2,128,M)と書けるので楽。

　多倍長を扱える（し、128乗ならたいして大きくない）ので、$2^{128}$を実際に計算することもできます。

No.977 アリス仕掛けの摩天楼

　全体が連結な場合、Bobが必勝なことは分かったけど、それ以外の条件を探すのに苦労した。まあ、こういう問題は試行錯誤するしかなさそう。

No.978 Fibonacci Convolution Easy

　数列aの値を求めておき、累積和をとりつつ和を求めていく。

No.979 Longest Divisor Sequence

　DP[a]で、最後にaを使ったときの、Divisor Sequenceの最長の長さ、として、iを一つずつ更新していった。毎回約数列挙が必要になるけど、各$A_i$の値が小さいので、$O(N*\sqrt{A_i})$で収まる。

　Aが小さいのでこの方針でやりましたが、解説のようにDP[index]とした方が普通だったかも……。

　なお、コンテスト中はPyPyで通すことができず、C++を使って通しました。

　が、予め、エラトステネスの篩の要領で$3*10^5$までの約数を列挙を列挙しておくとPyPyで通せた模様。勉強になりました。

No.980 Fibonacci Convolution Hard

　主にけんちょんさんのブログの記事を参考に解説AC。kmjpさんの記事やmaspyさんの解説も参考になりました。

　形式的ベキ級数や母関数を理解したとは言い難いですが、少し使い方が分かったのは良かった。勉強になりました。

Educational Codeforces Round 81 (Rated for Div. 2)

　Dまでの四完。
　それほど失敗した気はしなかったのに、順位はイマイチでした。

コンテストへのリンク

A. Display The Number

　各数字を点灯させるのに何本の電灯が必要かを考えると、1の二本と7の三本が少ない電灯で済むことが分かる。

　基本的には1を使い、最後に1余るようなら、一番上の桁を7にする。

B. Infinite Prefixes

　s一回書き終ると、（1の個数）-（0の個数）が何個変化するかを計算。

　また、その間に、0を基準として、（1の個数）-（0の個数）がどのように変化するかを計算。

　たとえば、s="1101"なら一回ごとに（1の個数）-（0の個数）は+2し、

　0→+1→+2→+1→+2

　のように変化するので、

0: 一回

+1: 二回

+2: 一回

　の値を取る。……というようなことを利用して計算した。

　xの値になりうるのは何回繰り返したときかを計算し、そのそれぞれの回で、何回ずつxを取るかを探索して和を取った。

　ただ、ながたかなさんのブログのように、sの文字のindexに着目する方が賢かったようです。変化が±0のとき以外は、各indexのときにxになることは一回しかありえない。

　なるほど確かにそうですね。

C. Obtain The String

　けんちょんさんの、「部分文字列を走査する DP」の記事のDPを使って解く問題。特に、

・next[i][c]:= S の i 文字目以降で最初に文字 c が登場する index

　を求めておくのが本質だと思います。

　なお、AtCoder Beginner Contest 138　E - Strings of Impurityとほぼ同じ問題でした。コンテスト中は全く思い出せなかった……。

D. Same GCDs

　a以上a+m-1以下のxで、gcd(x, m)=gcd(a, m)となるようなxの個数を求めれば良いので、gcd(a,m)を素因数分解し、約数包除を用いて計算した。

　ただ、ユークリッドの互除法を考えれば、gcd(m+i, m)=gcd(i, m)なのだから、0～m-1の範囲で数えればOKだったようです。

　さらに、mをGCD(a, m)で割れば、x=m/GCD(a, m)としたとき、xと互いに素なx以下の自然数の個数ということになり、これはオイラーのφ関数として知られているものなようです。

E. Permutation Separation

　ARMERIAさんのブログの記事やけんちょんさんのブログの記事を見て通した。コンテスト直後のTwitterで、「そんなに難しくない」という意見も見たけど、個人的には難問だと思っています。

　まず、

・最初にどう分けるか

・最終状態がどうなってるか

　を考えるのは自然。

　ただ、さらに、コストの計算もするとなると、O($n^3$)かかってしまいそう。

　三乗オーダーだと、高速化したとしてもACできる計算量にはなりそうもない……コンテスト中はそう考えて、何か天才的な方法があるんじゃないか……と迷走してしまった。が、実際は上記の方法を高速化すればO(nlogn)まで落ちる。

　その高速化も簡単ではない。私は上記の解説ブログを読んでもなかなか理解できず、初期状態と最終状態を変化させた場合のコストを表にしてみてようやく理解することができた。

　まあ、「高速化できるはず」という気持ちになれば、差分を取ってみるのは自然だし、思いつけない内容ではないと思うけれど……。

　無理そうに見えても、

・高速化できないか試す

　ことが大事か。

　なお、PyPyで通すには制限時間も結構厳しく、手持ちの遅延Segment treeでは通らなかったため、Starry Sky tree（？）を使って通しました。

　なお、ながたかなさんのブログ記事によると、そういったデータ構造を使わずとも通せるようですが……私は理解できていません。

F. Good Contest

　ARMERIAさんのブログの記事やけんちょんさんのブログの記事を参考に解説ACした。

　Eより解法は思いつきやすいと思う。

　DPしよう、という方針が見えれば座標圧縮は自然。

　ただ、DPの遷移は難しい。

　同じ区間を使い続ける場合の処理を一度に行う……という方法に気付けなければいけない。ただ、このDPは、キーエンス プログラミング コンテスト 2020　F - Monochromizationとかなり似ています。（この問題の応用がMonochromizationと思って良さそう）

　逆に言えば、こういう、順次更新していくだけではなく、（部分的に）一度に遷移させるDPというのは、典型の一つなのかもしれない。頭に入れておきたい。

AtCoder Beginner Contest 153

　約三十分で全完。
　かなり簡単な回だったのでたいして順位は良くなかったけれど、これくらいで全完できれば自分としては満足。

コンテストへのリンク

A - Serval vs Monster

　H/Aの小数点以下繰り上げ。

　Pythonなら、-(-H//A)と書くのが簡単。

B - Common Raccoon vs Monster

　Hとsum(A)を比較

C - Fennec vs Monster

　大きい順にsortし、K番目以降の和

D - Caracal vs Monster

　まず、「何回分裂するか」が分かれば攻撃の回数は分かるということが重要。たとえば、二回分裂した後、三回目の攻撃で消滅するなら、答えは、1+2+4回です。

　その上で、たとえば、H=12のときのHPの変化を考えると、

・12→6→3→1→0

　これは、H=4のときの、

・8→4→2→1→0

　と同じ。

　なので、$2^k\leqq x\leqq 2^{k+1}$の範囲にあるxは同じ挙動をすることが分かります。

E - Crested Ibis vs Monster

　あるHPの敵を倒すのに必要な魔力、でDPすれば解けます。

　「効率の良い魔法を使うのが良いのでは？」などと考えたくなりますが、DPすれば全部の場合を調べられます。

F - Silver Fox vs Monster

　左から貪欲でOK。

　一番左の敵を倒す際にできるだけ他の敵も巻き込みたいので、一番左の敵の位置+Dの位置で爆弾を使う。

　そのとき、一番左～一番左+2*Dまでの敵のHPを(一番左の敵/A)の繰り上げだけ減らします。二分探索により一番左+2*D番目の敵の位置を求め、遅延Segment treeを用いて区間のHPを減少させました。

　データ構造を使わない方法もありますが、思いついた方法で解けば良いよね。

TopCoder Single Round Match 776

　今年はじめてEasyがACできた！　と思ったらシステムテストで落ちて0完。単純なミスだったのでもったいない。

Div1 Easy EncloseArea

　斜めに線を引いて、指定された面積の多角形を作る問題。

　最小の正方形の面積は2で、その一辺を削って、隣に膨らませれば面積は+2される。

　なので、まず50*50の方眼紙の対角線上に斜めに長い長方形を作り、それを一つずつ膨らませる実装をした。一々、辺を増やして減らして……としているためかなり汚い実装になってしまった。

　そして、一番最初、面積2から始めてそこから求める面積まで増やしていく……というように書いてしまったため、面積2のときそのまま出力するのを忘れてしまってシステムテスト落ち。

・最小値・最大値で通るかチェック

　はきちんとしなくてはいけませんね。

　kmjpさんのブログの記事のように頂点に着目すればもっと簡単に実装できます。

　コンテスト中のコードを修正したものなので非常に読みにくいのですが、一応ACしたコードを載せておきます（載せるか迷ったのですが、ACした証拠として）。

class EncloseArea():
    def enclose(self, A):
        if A%2!=0:
            return tuple()
        if A>2402:
            return tuple()

        ANS=[["."]*50 for i in range(50)]

        ANS[0][0]="/"
        ANS[0][1]="\\"
        ANS[1][0]="\\"
        ANS[1][1]="/"
        S=2

        for i in range(1,49):
            if S==A:
                break
            
            ANS[i][i]="."
            ANS[i+1][i+1]="/"
            ANS[i][i+1]=ANS[i+1][i]="\\"
            S+=2

        if S==A:
            A=[]

            for ans in ANS:
                A.append("".join(ans))

            return tuple(A)

        NOWP=[0,1]
        NOWM=[1,0]

        def rewrite1(x,y):
            if ANS[x-1][y]==".":
                ANS[x-1][y]="/"
            else:
                ANS[x-1][y]="."

            ANS[x][y]="."
            ANS[x-1][y+1]="\\"
            ANS[x][y+1]="/"

        def rewrite2(x,y):
            if ANS[x][y-1]==".":
                ANS[x][y-1]="/"
            else:
                ANS[x][y-1]="."

            ANS[x][y]="."
            ANS[x+1][y-1]="\\"
            ANS[x+1][y]="/"
            
        while True:
            x,y=NOWP
            if 0<=x-1<50 and 0<=y+1<50:
                rewrite1(x,y)
                S+=2
            NOWP[0]+=1
            NOWP[1]+=1

            if NOWP[0]==49 or NOWP[1]==49:
                MIN=min(NOWP)
                NOWP[0]-=MIN
                NOWP[1]-=MIN
                NOWP[1]+=2

            if S==A:
                break
                

            x,y=NOWM
            if 0<=x+1<50 and 0<=y-1<50:
                rewrite2(x,y)
                S+=2
            NOWM[0]+=1
            NOWM[1]+=1

            if NOWM[0]==49 or NOWM[1]==49:
                MIN=min(NOWM)
                NOWM[0]-=MIN
                NOWM[1]-=MIN
                NOWM[0]+=2

            if S==A:
                break

        if S==A:
            A=[]

            for ans in ANS:
                A.append("".join(ans))

            return tuple(A)

Div1 Medium StringRings

　kmjpさんのブログの記事を参考にして通した。

　両端赤、両端緑、両端が異なる、のそれぞれのひもの個数をr, g, bとおき、実際に本数を求めてみよう、と式を書いてみたら、自然と再帰的に書け（多分、C++なら再帰のままでもACできる？）、それを整理したらさらに簡単な式になった。

・とりあえず立式

　さえしていればそれほど難しくなかった気がする。

　コンテスト本番では、Easyに時間を取られてしまったので解けなかったけど、ACしたい問題でしたね～。

　以下、ACしたコード。

class StringRings():
    def expectedRings(self, A, B):
        ANS=0
        for i in range(A):
            ANS+=1.0/(2*i+1)

        for i in range(B):
            ANS+=1.0/(A*2+i+1)

        return ANS

Codeforces Round #615 (Div. 3)

　なんとか全完できました。

コンテストへのリンク

A. Collecting Coins

まず、三人の最大値までコインを割り振る。（割り振れなければNO）
　その後、3で割った余りが0ならばYES、そうでなければNO。

B. Collecting Packages

　ソートした順番でしか回収できない。移動も辞書順なので、右に行ってから上、と進み方一意に定まる。

C. Product of Three Numbers

　（1を除く）約数を列挙。その中で最も小さいものを使うのが最善。これをaとする。

　次にbを、列挙した中から全探索する。a, bを定めたときn/(a*b)が正の整数になり、1, a, bと重ならなければOK。

D. MEX maximizing

　mod xで考えたとき、各要素が何個ずつあるかを管理しておきます。mexを大きくするためには、それらを小さい順に並べれば良いです。

　要素の個数の最小値をMINとすると、0～xのうちMINを始めて取るindexが分かれば答えも分かります。

　たとえば、Exampleの最後のクエリ、a=[0,1,2,2,0,0,10] のときを考えると、

0: 3個

1: 2個

2: 2個

　なので、MIN=2、はじめてMINを取るindexは1です。

　mexは、余り0～2を二周した後、もう一歩だけ進むことができるので、3*2+1のように求められます。

　よって、この二つの値を高速で求めれば良いのですが、コンテスト中は区間加算・区間最小を求めることができるSegment treeと二分探索を用いて処理しました。

　このようなSegment treeを使えば、全体の最小値は求めることができます。あとは、[0,i]における最小値がMINになる最小のindex iが分かれば良いですが、これは二分探索で求められます。

　なお、この問題はSegment treeを使わずとも解くことができます。mexが減ることはないし、高々qまでしか増えないので、「mod xで考えたとき、各要素が何個ずつあるか」という情報を持ってシミュレーションすればOKです。実装も楽だし、計算時間もこの方が速いですね。

E. Obtain a Permutation

　各列について、その数字がローテーションの結果一致するなら、何回ローテーションしたときか、を調べる。それを使ってローテーション回数を全探索する。

F. Three Paths on a Tree

　直径＋1点を全探索。その残りの一点と直径との距離を調べるところでLCAを使ってしまいましたが、DFSすればOKでした……。

　コンテスト後、直径で良いことの正当性がツイッター上で話題になっていたけど、一応コンテスト中に示したつもり。

　ただ、直径が二つ以上あるときがコンテスト中は良く分からなかった。
　そういう場合、中心Vに対して、V-a, V-b, V-cの距離が等しくなる三点a, b, cが存在するので、それらを取ればOKなのですね。（ながたかなさんのブログの記事を読んで気付きました）

　なので、適当な直径を一つ選んできて良いですね。

Codeforces Round #614 (Div. 1)

　時間がかかってBまでの二完でした。その後、CやEを考えていました。振り返ると、コンテスト中に、Cはほぼ正しい解法が思い付いていたようではあるのですが……。

コンテストへのリンク

A. NEKO's Maze Game

　縦、横、斜めを見て遮っている部分があるかどうか更新していく。その個数を更新する実装が分かりやすかったようです。
　コンテスト中は、setに遮っているindexのpairを放り込む実装をしていました。

B. Aroma's Search

　($x_i$, $y_i$)達が一直線にあるときを考えると、どこかの点に行って、右か左か一方向へ進むのが最善そう。

　今回は一直線上には存在していませんが、同じように考えても問題ないです。

　公式解説では、その理由として、d(i, j)を($x_i$, $y_i$)と($x_j$, $y_j$)のマンハッタン距離としたとき、d(u, v)+d(v, w)=d(u, w)となることを言っていますね。

　なるほど。ちゃんと考えていませんでした。が、まあ、証明できていなくても、正しいことを考えてはいたので、まあ良いかな、という気持ち。

C. Xenon's Attack on the Gangs

　考察自体はコンテスト中にできていた。（証拠のツイート）

　0、1、……と小さい重みから重みごとに別々に考える発想ができれば、ある葉から葉までのpath上に重みを割り振ることがベストだし、重みwまで割り振った後、次の重みはそれまでに割り振ったedgeと隣接しているedgeに割り振った方が良いことが分かる。

　これは、けんちょんさんのブログの記事に詳しく書いてあります。ここまではコンテスト中に分かっていたし、だから区間DPをすればいいだろう、という方針も立っていた。問題は実装だと思う。

　まず、部分木に含まれる頂点の個数が欲しい。これは、全方位木DPが必要そうに思えるけど、求めた値を全部の頂点個数から引くことで、普通の木DPで求まる。

　この部分は、yukicoderのNo.872 All Tree PathやAtCoder Beginner Contest 149のF - Surrounded Nodesと同じですね。

　その後、けんちょんさんの記事では、点を追加する向き（根に対して遠ざかる方向か、近付く方向か）を求めるのにLCAを使う＆再帰を使って実装しているみたい。

　これは非常に関心しました。結構実装の大変な問題だと感じたけど、そういう方針でやればある程度機械的にできそう。

　ただ、PyPyで通そうと思うと、logがつくと厳しそうだし、再帰を使っても多分ダメ。で、まず、向きを求める方は、

・木の辺の向きは親の方向により定まる

　です。そもそも、根を一つ定めたとき、辺の向きは根へ向かう方向か、遠ざかる方向かの二通りしかない。なので、各頂点の親の頂点を記録しておけば向きも分かる。親に対する相対的な向きが欲しいので、思い付いてしまえば当たり前なのだけど、私はなかなか気付けなかった。

　再帰については、普通の直線上の区間DPと同様に、幅1の区間から順番に広げていけば再帰を使わずに書ける。幅1の区間をdequeへ入れておき、BFSの要領でそこから一つずつ広げていく実装が可能。
　さらに、区間両方を広げられるか試す必要はなく、片側は固定しても良い。

　ここまでやってようやく制限時間ギリギリでACできました……。

　いわゆる考察部分はそれほど難しくないと思うけど、実装は結構大変だし、PyPyで通そうと思うと意外と辛い問題でした。

AtCoder Beginner Contest 152

　Fが解けずの五完でしたが、後で見直したらFは難しくなかった。直後にCodeforcesがあったので疲れないようにやろう、とは思っていたけど、実装が大変な問題でもなかったし……。

コンテストへのリンク

A - AC or WA

　N=Mか調べる。

B - Comparing Strings

　小さい数字を繰り返した方がお得。

C - Low Elements

　今までで一番小さい数字を管理

D - Handstand 2

　最初、桁DPのようなことをしなくちゃいけないのか、と思って飛ばした。

　冷静になると、1以上N以下の「最初の数字がiで最後の数字がjとなるような数字の個数」が全探索できるので、それを使って計算できる。

E - Flatten

　Aの最小公倍数を$A_i*B_i$とすれば良い。

　Pythonなら直接最小公倍数を求めて解くことも可能だったらしいけど、私は各素因数を何回使うかを調べて、modを取りながら最小公倍数を求めました。

F - Tree and Constraints

　コンテスト時の書き換えのファイルを見たら、

DP=[0]*(1<<M)

　とか書いて止まってたのですが、ここで止まるのはおかしい。この方針（bit DP）で解けます。

　各制約が満たされているかどうかを状態を持つDPをします。

　各制約のpathに含まれる頂点が何かを前計算しておいて、各辺を白く塗るか/黒く塗るかでDPを更新。

　初期値はDP[0]=1

　辺を見る順番もどうでも良いので（なので、本質的に木であることを使ってない。直線と解き方同じ）、1から順番に見ていくとすると、k番目の更新は、path中にkを含むものの和集合をBとして、各i(0<=i<2^M)について、

DP[i|B]+=DP[i]

　とすればOK。
　1<<Mから0へ、大きい順に見ていけば、DPテーブルを使い回すこともできる。

　これで、（前計算を除いて）計算量は$2^M*M$となるので解けます。（前計算はM回DFSしてO(N*M)でしましたが、もっと速くなるはず）

　今、公式解説を見たら包除原理って書いてあって驚いた（他の解説ブログ等も見たけど、大体包除原理を使ってそう？）のだけど、この方針の方が自然では？

　この後、解説放送を見たりして包除原理の解法を理解しました。いや、でもやっぱりこの解法の方が簡単では？
（youtubeのコメントでこの解法に言及されている方がいました。コメント内では、本質的には包除原理と同じ解法という話になっていたみたいです。うーん、私には違う解法に見えるんですが……。）

キーエンス プログラミング コンテスト 2020

　時間ギリギリでEを通して五完。橙パフォは出なかったものの、自分としては上出来でした。

コンテストへのリンク

A - Painting

 一回で、H, Wのうち大きい方だけ増やせる。

B - Robot Arms

・とりあえずソート

　して考えたいけど、普通に左端でソートしても上手くいかないので、右端でソートしたら上手くいった。

　「区間スケジューリング問題」そのものだということは、コンテスト中には気付いてませんでした……。

C - Subarray Sum

　Sそのものを置けば区間が一つ作れる。残りはできるだけ大きい数字を置けば邪魔しない。

　こういうギャグっぽい問題がAtCoderで出ることは少ないので面食らった。

D - Swap and Flip

・あるカードの位置を決めたら、その偶奇を見ればAかBかが分かる

　ということに気付くのが重要。

　あとは、各iについて、A, Bのどちらを使うかで全探索した。そうすると、「奇数番目で使うか偶数番目で使うか」も分かる。奇数番目で使いたいもの、偶数番目で使いたいものそれぞれをソートしたものをS0, S1とすると、

$S0[0]\leqq S1[0] \leqq S0[1] \leqq S1[1] \leqq \dots $

　となっていれば良い。そのときの必要Swap回数は転倒数。

　公式解説放送では（bitDPによる解説の後に）この方法についても触れていて、同じ数字があったときの処理を気にしていた。
　でも、同じ数字があったときは、元の順番が小さいものが最終的な順番としても小さい箇所にあった方が良いので、普通に実装すれば気にせずに済むと思う。

E - Bichromization

　結構焦っていたので、嘘解法かも、と心配していたけどどうやら嘘じゃなかった。

・移動コストが最小の点を考える

　のが重要。最小全域木のクラスカル法のイメージだと思う。

　そもそも、同じ色同士の点をつないでもコストの増加にしか繋がらない。白い頂点同士が重みwで繋がっているとき、それらの点のコストの最小値の候補は「もう片方の点のコスト+w」となるので。

　だから、頂点の配色や辺の重みを決めていく際に、今まで使っていない二点でコスト最小（で一致する）の二点があれば、その二点を白と黒で繋がないとダメ。

　あとは、残っている頂点の中で最小のものを探して、それが、既に使われた頂点と隣接していれば、その頂点と同じ色で塗って、重みは差分にする……というようにした（この辺もクラスカルっぽく考えていた）。

　が、解説を見ると差分を取る必要はなかったようで。

　別な色に塗って、重みはDをそのまま使えば良かったらしい。そりゃあそうですね。

　木が作れたら、残りの辺の重みは$10^9$にすればOKです。

F - Monochromization

　公式解説放送を見た後、ARMERIAさんの解説記事、けんちょんさんの解説記事、kmjpさんの解説記事を交互に読みながらなんとか解説AC。

　前半の判定問題のパートは、解説放送を聞けば理解できたけど、その後が……。

　解説を読んでも、サンプル2のような元の盤面に黒マスが一つもない場合すらよく分からなかったので、絵を描いてみた。この場合の最短経路Combi(6,3)=20通りを絵に描いて、それぞれの下の部分が黒くなったものの行・列の入れ替えでできる盤面を調べた。計算してみたら確かに230個になった。それを見ながら解説を読むとDPの方針が分かってきた。

　これがDPでできるというイメージがなければ、前半のような判定ができたとしてもあまり意味がないと切り捨ててしまいそう。類題経験がないと厳しい気がするけどなぁ……。

　個人的には、「最初の盤面に黒マスが一個もない場合」を部分点で出しても良かった気がする。これだけでも十分難しい（600点以上はある）と思うけど、部分点で出すなら400～500点？　誘導にもなるし、良いと思うんだけど。

　ただ、黒マスが一個もないと、H, Wの入力二つから答えを求めることになるので、予測等で解かれかねないんですかね？

　なお、計算量が$O(2^{H+W}*H*W)$で、$10^8$オーダーとかになるので、PyPyだと厳しいかと思ったのですが、特に変な高速化をせずとも自然に書けばACできました。（自然に書けなかったので、何度かTLEの提出をしてしまいましたが）

yukicoder contest 234

　四問目に苦労して四完で終了。コンテスト中に六問目を見ていれば解けた気がするけど、四問目で力尽きてしまった。

コンテストへのリンク

No.969 じゃんけん

　Xが0, 4, 10のときに、あいこの可能性がある。

No.970 数列変換マシン

・とりあえず立式してみる

　のが重要か。

　立式したら、とりあえず、$b_1+b_2+...+b_n$を考えてみる。それを使って$a_1+a_2+...+a_n$を表せる。

No.971 いたずらっ子

　南か東にしか行けない、というのを読み落とさないのが大切。

　また、あるマスのいたずらっ子には一度しか妨害されないので、再度そのマスに行くためには、前と同じルートを通れば妨害されずにそこまで行ける。

　なので、マス(i, j)までの最短時間は(i-1, j)または(i, j-1)までの最短時間から計算できる。

No.972 選び方のスコア

・とりあえずソート

　した上で、

・中央値→二分探索

　を考えるのは自然。問題は、どういう判定問題にすべきか。

　ソートされた数列、$a_1, a_2, ... ., a_n$の中央値が$a_i$で、残りが$2*k$個のとき、それらは一番大きい方からk個と、$a_{i-1}$から大きい順にk個とれば良いと分かる。

　ここで、kを一つ増やすことを考えると、取るべき数値は左右どちらもk個目に取った値より小さい。つまり、求めたいスコアへの寄与は単調減少だと分かるので、二分探索が使える。

　なお、取る個数が偶数個なときが最善じゃないことは、（公式解説の通り）一つ小さい個数へ帰着させることで分かる。

　中央値の位置で全探索することを思いつけば、取る個数で二分探索する発想は浮かぶと思うけど、何で探索すべきか思いつくのは結構難しい気がする。

　私は最初、左右からの累積和とかを考えてたけど、もっと落ち着いて、どういう風な値を選ぶのが最善か考えるべきだった。

No.973 余興

　こういうゲーム系は、

・真似っこなどの最適戦略

　がなければ、

・ゲームDP

　を考えるのが良さそう。（Grundy数を考えると分かりやすいこともあるか）

　今回は、制約を見ると区間i～jが残ったときに勝てるか？　をDP[i][j]として区間DPができそう。ただ、更新にO(N)かかってしまい全体でO($N^3$)になりそうで困りコンテスト中は解けなかった。

　その後、公式解説や、けんちょんさんの記事、kmjpさんの記事では累積和を使えば良いと書いてあって、その方針を考えたんだけど、それでも私には分からなかった。

　結局、次のようにして解いた。

　DPを区間の小さい方から更新していく。その際、

・i～jの区間を使ったとき負け（DP[i][j]=0）だったら、そこへ遷移できる区間i~kやk~jでは勝ち

　なことを利用して、DP[i][j]=0となる場所が現れたときに、勝ちとなる区間を更新した。

　あるiを固定したとき、DP[i][k]=1を引き起こすDP[i][j]=0は一ヶ所だけなので、DP[i][j]=1を更新する更新回数は、左右からの高々二回。なので、この更新回数はO($N^2$)で収まる。

　だから、累積和など使わなくてもO($N^2$)で収まったと思う。

　最後の更新部分に累積和が使えると思うんだけど、正直よく分かっていない。この解法の方が自然じゃないかなぁ。

No.974 最後の日までに

　一応、今やったら自力ACできた。

　現時点での（お金, 好感度）を持ってDPし、「お金も好感度も低い状態」を枝狩りしたらACできた。

　解説の半分全列挙はなるほど、という感じ。

　でも、いくつか提出を見た感じ、枝狩りで通してしまっている人が結構いそうだった。

　ただ多分、この枝狩りでは本質的な計算量は減ってない気がする。Hack caseが作れる気がするんだけど、どうなんだろう。

　追記：test caseが追加され、MLEになっていました。半分全列挙しないと通らなくなったのかな。

TopCoder Single Round Match 775

　Easyを見て、ちゃんと時間をかければできそうだけど詰めるのは辛そう、とMedへ行くも、Medが分からずの0完でした。Easyをやるべきだったかな、とも思いますが、結局ACするのは難しかった気がします。

Div1 Easy IterateOverACube

　kmjpさんのブログの記事やかっつさんのブログの記事を参考にしましたが、少し違う方法です。

　合計がxになるタプルが何個あるか？　を調べれば良い。場合分けが必要で混乱するけど、

・三次元の問題は断面を考える

　とすれば良いと思う。
　たとえば、N=3で、z軸が0, 1, 2 の場合に分けて考えると、合計が0～6のときの点の位置は、

　 [1, 0, 0]　(0, 0, 0)の一つ
→ [2, 1, 0]　(1, 0, 0), (0, 1, 0)の二つがz=0に、(0, 0, 1)がz=1にある。
→ [3, 2, 1]
→ [2, 3, 2]
→ [1, 2, 3]
→ [0, 1, 2]
→ [0, 0, 1]

　のように変化する。
　なので、L = [1, 2, 3, 2, 1] という配列の長さ3の区間の和となっているので、尺取り法で求めることができる。

　合計が求まった後も、xを固定して同じように考えられる。こちらは、二次元平面上で考えられるので上よりは分かりやすい。

　しかし、この方法だと、色々工夫してもPython2じゃMLEやTLEになってACできなかった。
　えー辛い。私の書き方が悪いだけで、この計算量ならPythonでいけると思うんだけど……。

　Pythonで通せなかったので、C++で実装しました。以下、システムテスト通ったコードです。コメント付けてないし、C++は全く書き慣れていないので読みにくいと思いますが、ACできた証拠に。

#include <bits/stdc++.h>
using namespace std;

class IterateOverACube {
 public:
      vector <int> findCell(int N, long long index){
          index+=1;
          vector <int> L;

          for (int i=1;i=0;i-=1){
                    L.push_back(i);
          }
          for (int i=0;i<=N;i+=1){
                    L.push_back(0);
          }

          int LEN=L.size();
          int i=0;
          int j=0;
          vector<long long> S;
          S.push_back(1);
          long long SUM=1;

          while (i=index){
                       SUM=i;
                       rest=index-(NOW-S[i]);
                       break;
                    }
          }

          NOW=0;
          int x=0;

          for (int i=0;i=rest){
                        rest=rest-(NOW-L[SUM-i]);
                        x=i;
                        break;
                     }
          }

          int SYZ=SUM+1-x;
          int z=min(SYZ,N)-rest;
          int y=SUM-x-z;

          return {x,y,z};

      }
};

Educational Codeforces Round 80 (Rated for Div. 2)

　時間ギリギリでDまでの四完。なんか遠回りばかりしてしまった。順位はあまり良くなかったけど、妙な解法でもACできたことで満足感はあった。

コンテストへのリンク

A. Deadline

　繰り上げを無視して式を整理すると、

・$x+\frac{d}{x+1}\leqq n$

　のようになるので、コンテスト中は、左辺を微分してxの最大値を求め、その付近を探索しました。

　実際は、移項すれば二次式になるので平方完成でOK。この時点でちょっとおかしかった。

B. Yet Another Meme Problem

　実験（もしくは式変形）してみると、B=99…99　という形のときに条件が成り立つことが分かる。

C. Two Arrays

　まず、"non-descending order", "non-ascending order"の意味が分からずタイムロス。いや、日本語では「広義単調増加」って言うから分からなかった気がしたけど、「単調非減少」も普通に使いますよね。これくらいの英語は読み取れないと……。

　その上で、コンテスト中は、A, Bの要素を左から決めていき、

・DP[i][j]=（Aの最後の値（つまり最大値）がi, Bの最後の値（つまり最小値）がjのときの場合の数）

　として、このDPをm回更新していきました。

　更新の際、新たなDP[i][j]は、前のDP[k][l]のk<=i, l>=jを満たす全ての要素を足したものになる（絵を描くと分かります）ので、累積和を使って更新することができます。

　……と、これは制約を見ると自然な解法に思えますが、もっと簡単に解けますね。

　A+reversed(B)を考えると、これが単調非減少であればOK。その場合の数は、重複組み合わせを用いて、Combi(n-1+m*2,m*2)と簡単に表せます。　

D. Minimax Problem

　　じゅぴろさんの解説動画が分かりやすい。

・最小値・最大値（や平均値・中央値）を考える問題は二分探索を使うと良いことが多い。

→今回は、判定の際にmが小さいことを利用できる。「答えがX以上にできるか」という判定問題を考えたとき、各行の数字はX以上か、X未満か、の二通りなので、判定に利用するbit列は$2^8$通りしかなくなる。それを全部試しても$2^{16}$通り。

　……なんだけど、コンテスト中は、後半の判定を別のやり方でしようとしていた。$2^8$通りの二乗回探索すると間に合わない気がして、各bit列に対して「それと or をとったときに全てのbitが1になるようなbit列」を列挙しておこう、と思った。

　これを前計算しておく方針なら悪くなかった思うんだけど、実際は、各列に対して素数を割り振り、「bitが立っている列に対応する素数の積」によりコード化。その値に対して約数を列挙し、（列に対応する全ての素数の積）/（約数の一つ）となる値が存在するかどうかで判定した。

　無駄に面倒なことをしていて（計算時間も遅くなっているはず）、よくこれでACできたなぁ、と今思うと感心する。

E. Messenger Simulator

　今やったら自力ACできました。けんちょんさんのブログの解法（BITを使っている方）と同じ方法でした。

　シミュレーションを行うのは時間的に厳しいので、最小値、最大値がどこで変化するかを考えると、自分が選ばれていないときの位置変化は「±0か+1」なので、単調非減少。

　それをふまえると、各数字は変な位置変化はしないので、

・最初

・最後

・自分が選ばれたときの前後

　だけを考えれば良いと分かった。

　あとは、自分が選ばれたとき何番目の位置にいるかが分かればOK。これは、平衡二分探索木/C++のsetを使えばできそうな気もしたけど、私は持ってない。じゃあ、

・平衡二分探索木はしばしばBITで代用できる

　ので、できないか、と考えた。結局、

・各数字の位置を管理するリスト

を作り、

・BITで各位置までの出現個数を管理

して、選ばれた数字を一番最初（先頭の数字のさらに一つ手前）へ移動するよう更新していけば、BITにより選ばれた数字が何番目の位置かを調べることができた。

yukicoder contest 233

　時間ギリギリで全完したものの、反省の多い回。

コンテストへのリンク

No.964 2020

　コンテストのときは1、2、3、……、9、0の順番に並べましたが、9から大きい順番に並べた方が簡単でした。

No.965 門松列が嫌い～No.968 引き算をして門松列（その３）

　一問一問、場合分けが必要な実装をしてしまい、時間がかかってしまった……。この四問が似た問題なので、これら全問に通用する実装を心掛けるべきでした。

　……という反省では不十分で、そもそも

・汎用性のある実装

　を心がけるようにしていれば良かったと思う。

　今回は、制約がそう厳しくないので、「引き算する数字の候補」を全通り試せば良い。その上で、「引き算した結果が門松列になるか実装」をすればこの四問をほとんど同じ実装で通せる。

　ただ、今改めてそういう気持ちで気楽に実装したらTLEしてしまった（結局、多少定数倍した上でPyPyでAC）。あまりにも計算時間を考えずにやってしまってもダメですね。

AtCoder Beginner Contest 151

　Dで混乱してEにいったらどちらも解けずに終了という散々な出来。Unratedで助かった。

コンテストへのリンク

A - Next Alphabet

　Pythonならchr(ord(C)+1)と書けます。

B - Achieve the Goal

　N*Mから今までの合計を引きます。満点がKなので、Kより大きいとき-1。

C - Welcome to AtCoder

　実装問題。今、コンテスト時の提出を見るとちょっと面倒くさいことをしていた模様。全ての問題に対して、その問題でACできたか？　を前処理していました（ので、インタラクティブだったら対応できないコードになっていました）。そうしなくてもできますね。

　けど、それを前処理した方が分かりやすい気もするので、一概に悪いとも言えないか。

D - Maze Master

　全点からBFSしました。

　ワーシャルフロイドやダイクストラも考えましたが、BFSが書きやすいかな、と。

E - Max-Min Sums

　ABC150のE、第6回 ドワンゴからの挑戦状 予選のBと似たタイプの期待値の問題。

　ただし、この問題では、最大値・最小値を別々に考えるという工夫が必要だった。それに気付きさえすれば大体同じように考えられる。

F - Enclose All

　典型問題だそうですが、知りませんでした。

　私がした実装は、

・まず、全体を正方形にする

・その正方形を100*100に分割し、その中で一番、最小包含円の半径が小さくなる点を見つける。

・その点を中心に、元の正方形の一辺の長さの1/2の正方形を作って、同じことを繰り返す。

　といった感じです。

　最初は、ある点からx,y方向それぞれへの傾きを調べて……みたいなことをしようとしたのですが、WAになったので切り替え。

　最小包含円の半径を値として持つ関数を考えたとき凸性が成り立つので、ACした解法は、嘘じゃないと思うけど……。

　ともかく、凸性を利用した解法を考えていたのですが、コンテスト中はその凸性にあまり自信を持ててませんでした。（だから、厳密に凸じゃなくてもACできそうにも思えるコードを書いていたと思う）

　公式youtube解説放送も、凸性を利用して三分探索していますね。解説放送を見たせいもありますが、（証明を厳密に記述するのは多少難しいかもしれないけど）凸になるのは当たり前な気もしてしまう……。

　少なくとも、コンテスト中に「一次元のときと同様に上手くいくよね」くらいの気持ちは持ちたかった。

TopCoder Single Round Match 774

　Easyは解けたつもりだったのですが、システムテストで落ちて0完でした。

Div1 Easy LandSplitter

 kmjpさんのブログに解説があります。

　まず、元の問題文には三個の分割と二個の分割が乗っているが、結局コストは同じなので、二個の分割だけ使うと考えて良い。また、コストは分割の順番によらない。

　その上で、できるだけ大きな要素を作るのが最善。これは、A<B<C<Dのとき、A*D<B*Cなので、(B, C)という分割より(A, D)という分割の方が良いことから考えていけば分かる。

　ここまではコンテスト中に分かっていて、Bを使う回数を大きい順に試していく実装を考えていました。

　まず、

・残りxのとき, A～Bを使って分割可能か

　は簡単に計算できる。これは、Aを使える回数をt=x//A回としたとき、t*A+(Bを使うときの誤差分である（B-A）*t)　以下にxがあれば良い。

　なので、Bを大きい順に試し、分割可能だったら、それがBを使う回数。（A=Bのときを例外処理しておけば、計算量は抑えられる。Bを使う回数は最大N/B回だが、Bを最大に使ったときの余りが高々B-1で、Bを使う回数を減らすごとに最低でも1ずつ縮まるので、高々min(B/(B-A), N/B)回にはなる。なので、$O(\sqrt{N})$か。）
　
　で、コンテスト中はその後の実装がまずく（次に何を使えばいいかをB-1から大きい順に試していた）TLEになってしまっていた。

　できるだけ大きい要素を作るように分割しているので、残りの分割が「Aが何個かとA以上B未満のものが1個」になると言える。それを考えると、NからBを使った残りをM、残りのAを使う回数useaとすると、

・M-A*usea<B

　を満たす最大のものがuseaとなり、O(1)で求めることができる。

　TopCoderは他人のコードが見られなそうなので、一応コードを載せておきます。これでシステムテストは通りました。
　なお、TopCoderはPython2なのでrangeじゃなくxrangeにしています（rangeだとMLEした）。

class LandSplitter():
    def cheapest(self, N, A, B):
        if A==B:
            if N%A!=0:
                return -1
            else:
                x=N//A

                return A*A* (1+(x-1))*(x-1)//2

        def check(x,A,B): # 残りxのとき, A～Bを使って分割可能か調べる
            t=x//A
            s=B-A
            if x<=t*(A+s):
                return 1
            else:
                return 0

        for useb in xrange(N//B,-1,-1): #Bを使う回数を大きい方から探索して,
            if check(N-useb*B,A,B)==1: #分割可能なときにBを使う回数とする.
                break
        else:
            return -1 # 分割可能なことがなければ、不可能

        
        M=N-useb*B # Bを使った残り
        ANS=M*(useb*B)+B*B*((1+(useb-1))*(useb-1)//2) # ここまでのコスト

        usea=max(0,-(-(M-B)//A)) # Aの使用回数
        
        if usea==0: # Aを使わなくて良いときは既に分割できている
            return ANS
        
        S=M-usea*A # Aを使った残り
        ANS+=S*(usea*A)+A*A*((1+(usea-1))*(usea-1)//2) # 残りのコスト
        return ANS