キーエンス プログラミング コンテスト 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