第4回 RECRUIT 日本橋ハーフマラソン 予選

　短時間のマラソンは一番楽しみにしているのだけど、あまり良い成績が取れず悲しい。

コンテストへのリンク

A - ゲーマーXとモノス大会

　左端に高く積み上げていって、それ以外の列は、左端と同じ色が置けるなら置く……みたいな実装をしました。ただ、左端だけあまり高く積み上がってもよくないので、高さを抑制して、ある程度左端が高くなったら、別のところにも置くように調整。

　うーん……今見るとまず、クエリ先読み的なことをしていないのがおかしいですね。探

索をしないと。

B - イラストレーターXと不思議なペン

　Aで時間を取られてしまったので、慌てて実装。

　最初150回ランダムに動かし、その後三点以上を取れるものをランダムに選ぶ。

　これは、まあ、時間がなかったので仕方なし。

　全ての島に行ってから貪欲、という方針自体は思いついていました。上手く実装する自信がなかったのでこういう結果になってしまいましたが。

FII Code 2020 Round #1 (rated for all)

　約一年ぶりのCS Academyのコンテストでした。
　CS Academyは動的配点（解いた人数によって配点が変化）など、コンテストの仕組みは面白いのですが、問題の不備などは結構多い印象です。
　ただ、この一年の間にいつの間にかPyPyが使えるようになっていたのは嬉しかった。

　このコンテストはCまでの三完。Dは実質的にはできていたのですが……。

コンテストへのリンク

As easy as ABC

　配列Aが与えられ、そのうちのK個を+1したとき、中央値は最大いくつになるか、という問題。

　元々の中央値をMとすると、答えは高々M+1（全部に+1したとしても中央値は1しか増えないので）。

　結論としては、MがA中に何個含まれるかを調べれば良い。

　K個以上あればそのK個に+1することで、中央値も+1される。

Boring Operation

　$10^9/2$以上なら$10^9$から引く。

Cosmological Nightmare

　連鎖的に点が現れたり消えたりする場合に注意。

　逆に言えば、mod (x,y)$\in$ Vで一致している点の個数の偶奇を数えさえすればOK。

　その方針でACした提出

　コンテスト中は、一回移動したらどうなるか……みたいなことを考え、それで上手くいかなかったために解法に気付いた。そのせいで、コンテスト中のコードは無駄が多いものになってしまっている。

Driveaway

　コンテスト中、PyPyで提出してTLEでしたが、Python3で出せばACできました。PyPyだとheapq+tupleが遅いようです。注意。

　また、JOI春合宿2018　J - 飴 (Candies)とほとんど同じ内容だったようです。

　この問題のコードをそちらに合わせて修正すれば通りました。

　ただ、この問題の方が若干解法に辿り着きやすいかな、と思います。

　で、解法。

　おおまかに言えば、隣り合った二要素の和が最大になるものに貪欲にvoucher（商品券？）を使っていくのがベスト。ただし、voucherでの減額は最高Kなので、min(二要素の和, K)の最大値をheapqに入れて管理する。

　そして、単純に最大値を考えるのではなく、差分計算を考えなくてはダメ。

　たとえば、サンプル2。

・1 3 7 7 3 1

　なら、「3 7」「7 7」「7 3」のいずれかでK減額できる。たとえば、「7 7」にvoucherを使うと、残ったものは、

・1 3 3 1

　

　次にvoucherを使うのは「3 3」なのだけど、これにvoucherを使ったとき減額できるのは3+3=6ではない。実際は「3 7 7 3」に二回voucherを使っていることに注意。

　このとき、本当は「3 3」にvoucherを使っているのではない。でも、「7 3」「3 7」とvoucherを使えば「3 7 7 3」にvoucherを使うことは実現できる。

　そして、減額される額は、3+7+7+3から、前回までで減額されていた額10を引いた10となる。

　残りは、

・1 1

　で、最後にこの二つに使う。

　という感じでやればOK。

　あとは、実装だけれど、その際、ある数の左右に何があるか、を管理できれば良い。

　それを実現できるのが「隣接リスト」。それとも、「左右隣接リスト」と書いた方が良いのかな。（「隣接リスト」という名前は、以前Codeforcesでこういうデータ構造が必要な問題が出たときに、誰かがTwitterで使っていたのだけど、グラフ理論での隣接リストと意味的に対応しているのですね。なるほど。）

　つまり、その点から一つ左にある要素、右にある要素を持っておき、要素が取り除かれるごとにそれを更新していく。

　時々出てくるデータ構造なので、自分はしていないけど、ライブラリ化している人もいると思う。

yukicoder contest 237

　Cまでの三完でした。
　Dは解けるべきだったし、今見るとFも難しくないですね。

コンテストへのリンク

No.987 N×Mマス計算（基本）

　これは計算するだけ。

No.988 N×Mマス計算（総和）

　足し算の場合は、縦の和*（横の個数）+横の和*（縦の個数）

　掛け算の場合は、縦の和*横の和

No.989 N×Mマス計算（K以上）

　各列に対して、ソートして二分探索

No.990 N×Mマス計算（Kの倍数）

　一時間半かけてもこの問題を解けなかったようなのですが……反省。

　足し算の場合、mod Kで分類すればOK。

　本番では、「余りがqの個数と余りがK-qの個数の積」で計算していたので、余りが0同士の場合にWAを出していました。今見るとマヌケですね。

　掛け算の場合。

　約数を調べるのは良いのだけど、「Kの約数」だけを調べれば良いのを忘れていた。

　たとえば、K＝2*(奇数)の場合に、A=2*3, 4*3, 8*3...みたいなのを全部別に考えてしまうコードを書いてしまいTLE。

　こっちはちょっと気付きにくいけど、時間はあったんだし、ACしたかった。

No.992 最長増加部分列の数え上げ

　コンテスト中は読まなかったと思うけど、LISについてちゃんと理解できているなら解けなくてはいけない問題でした。

　解説を読んだ後にACしたけど、解説とは若干違う方法で解きました。

　公式解説はLISの長さを主役に、ここの解説では、$A_i$の値を主役にしています。

　後者と似た方針で、iの順番を変えなくても解くことができます。

　まず、座標圧縮（今回は最小の数を1にしています）して、$A_i$の値を$2*N^5$以下にした後、DP[0]=(0, 1), DP[$A_i$]=(-1, 0)（初期化値は小さい値なら何でも良い）というDPテーブルを作ります。

　DP[$A_i$]は、最後の値が$A_i$になるような、LISの長さと個数です。

　

　その上で、

　i番目の要素が$A_i$のとき、DP[$A_i$][0]が「DP[0][0]～DP[$A_{i-1}$][0]の最大値」より大きければ、既に$A_i$が出現しており、かつ、DP[$A_i$]の長さは更新されないので、長さはそのまま、個数を「DP[0]～DP[$A_{i-1}$]で第一要素が最大値を取っているようなものの、第二要素の和」だけ増やします。

　そうでなければ、DP[$A_i$]の長さはそれまでの最大値の和+1で、個数はそれらの個数です。

　文章で書くと分かりにくいですが、これはSegment treeで実装できます。（ちゃんと考えていないけれど、多分BITでもできるはず）

　自分の提出はこれ。

Codeforces Round #619 (Div. 2)

　Dまでの四完。Dで手間取ったわりに、順位はまあまあでした。

コンテストへのリンク

A. Three Strings

　各indexについて、a[i]==c[i] or b[i]==c[i]

B. Motarack's Birthday

　-1と隣り合っている数字の最大・最小を調べ、その平均で穴を埋める。

　ただし、求めたい、「「隣接要素の差の絶対値」の最大値」は、-1でない二要素によることもあることに注意。

C. Ayoub's function

　fで出力されるのは、「”0”が連続している区間」以外の区間。

　たとえば、"10001"であれば、全部で5*(5+1)/2=15個の区間から、3*(3+1)/2=6個の区間が除かれる。

　なので、1を均等に配置すればfは最大値を取る。そして、そのとき何個0が連続する区間がいくつあるか、が分かれば計算できる。

D. Time to Run

　一筆書きできるのが重要。

　最初気付かなかったけど、絵を描いているうちに気付いた。

　その後は、一旦、一周する命令を書いた後、問題にあわせてどこで切るか決める……という実装がやりやすい。

E. Nanosoft

　アルメリアさんの解説記事を参考にAC。

　けど、考察部分はコンテスト中に大体できていました。データ構造の問題ですね。

　二次元セグ木や二次元Sparse tableに馴染みがなかったため、その後何をすれば良いか分からなかった。

　二次元Sparse tableを使ってどうにかACしましたが、実装も非常に辛かったです。

　普通のSparse tableは理解できるので、やることのおおまかなイメージは分かるのですが、二次元だと、三次元的なイメージがないと全体像はどうも掴めない。

　すぐ、今何を書いているかが分からなくなり混乱しました。

　どうにかACできたものの、もう一回書け、と言われたら辛いです……。二次元セグ木も書かなきゃなぁ。

Educational Codeforces Round 82 (Rated for Div. 2)

　Cの実装に苦労して、遅解き四完。
　Eは解きたい難易度なんだけど、コンテスト後も自力ACできなかった。

コンテストへのリンク

A. Erasing Zeroes

　"1"がなければ0

　そうでないとき、最初に"1"が現れる位置と、最後に"1"が現れる位置を調べ、その間の"0"の個数を出力。

B. National Project

　天候の良い日が多ければn日で終わる。

　そうでないときは、高品質の舗装をするのに何日かかるか調べる。

C. Perfect Keyboard

　隣り合っている文字を管理して、それらをグラフと見た（各文字が頂点、隣り合っている文字へ辺を張る）ときに、一直線にできるかどうか。

　コンテスト中はUnion-findを使ったのですが、特に必要なかったですね。連結成分が二つ以上になる場合があると思ったのかな……。

D. Fill The Bag

　mが2ベキなので、bitで考える。

　nを二進数で表したとき、立っているbitは必ず埋めなくてはいけないので、下の桁から埋めていく。

　箱が足りなければ上の桁から取ってくる。箱が2個以上余っていたら、一つ上の桁へ運ぶ。これを繰り返して、合計nにできるか調べる。

E. Erase Subsequences

　公式解説を読んでAC。

・tを二つに分けて、それぞれがsの（連続しなくて良い）部分列になっており、共通部分がなければ良い

・sの長さが400なので（三乗で？）DPしそう。

　というあたりは分かっていた。

　これらを組み合わせれば、

・まずtをt1, t2の二つに分けるのを全探索→その上でDPを使って判定

　と考えるのは自然かもしれない。けど、気付けなかった。

　気付かなかったのは、DPを考え過ぎたせいかもしれない。今回は、

・全探索→DP

　なので、最初からDPを考えるのはちょっと筋が悪かった。「何かで場合分けした上でDPを使う」というのは常套手段。頭に入れておきたい。

　t1, t2に分けた後は、二次元DPが必要そうだけど、

・DP[i]でt1をi文字まで使ったとき、t2を最長何文字まで使えるか

　として、sについて一文字ずつ更新していけば、一次元のDPで済む。

yukicoder contest 236

　Aの一完でした。解説を理解できない……。

コンテストへのリンク

No.982 Add

　A, Bが互いに素でなければ-1

　互いに素なときは全探索。

　で、解けますが、解説を読むと、O(1)で求められるのですね。言われてみれば確かに。

No.983 Convolution

　解説を読んでACはしましたが、解説を理解できていません。

　畳み込みまわりは勉強しないと……。

Codeforces Round #618 (Div. 1)

　Cまでの三完でした。
　Cで、PyPyで出たTLEを除くことができず、C++に書き直した……というトラブルを除けば上出来。PyPyでTLEになっていた原因は、気付けば当たり前のことだったんですが、ちょっと気付きにくいことな気もするので、まあ仕方ないかなぁ、という気もしています。

コンテストへのリンク

A. Anu Has a Function

　bit演算に関する問題なので、bitごとに考える。

・(1 or 1) - 1=0

・(1 or 0) - 0=1

・(0 or 1) - 1=0

・(0 or 0) - 0=0

　というのが各bitについて成り立つ。だから、今、k番目のbitが立っていても、もし後で「k番目のbitが立っている数」と演算しなければいけないなら、そのbitは0になってしまう。

　なので、「一つの数でしかbitが立っていない最上位の桁」を持っている数を最初に置けばOK。

B. Aerodynamic

　点対称ならOK。

　こういう問題は厳密に証明できずに提出してもまあ良いかな、という気がする。

C. Water Balance

　スライムを合成させていくイメージで考えた。

　コンテスト中、DP まとめコンテスト　N - Slimesを見に行ったけど、あまり関係なかったね……。

　右のスライムのコストが左のスライムのコストより小さければ合成させる、という方針で良い。

　このとき、

・4, 2 → 3, 3

　のように合成させていると、制限時間に間に合わない。そこで、もともと何匹のスライムだったか、という情報を持って、

・(4, 1), (2, 1) → 3, 2

　のように書くようにすると、O(n)になり間に合う。

　コストkのスライム達が並んでいて、その一個左隣のスライムのコストがkより大きければ、「一番左のスライムと何匹か合成されたスライム」のコスト（平均）は必ずkより大きいので、全部合成されるまで（左のスライムのコスト）>（右のスライムのコスト）となる部分ができてしまう。

　だから、こうやってまとめて良いことが分かる。

　さて、TLEになった原因は、出力の際に毎回for文を書いたせいでした。(x, y)に対して、

for i in range(y):

    print(x/y) 

　のように書いてたんだけど、こういう風に毎回for文を生成するのは遅い。

(str(x/y)+"\n")*y

　を出力するようにしたらTLEが取れました。

AtCoder Beginner Contest 154

　47分1ペナで全完でした。まあまあかと。

　この回は、コンテスト後のツイートに補足することがあまりないですね……。

コンテストへのリンク

B - I miss you...

　len(S)*"x"

C - Distinct or Not

　len(set(A))がlen(A)と一致するか調べる。

D - Dice in Line

　各サイコロの出る目の期待値は(1+p)/2。

　あとは累積和を使って、K区間の期待値の和を順に求めていきます。

E - Almost Everywhere Zero

　桁DP。

　Kが3以下、ということでもっと簡単な解法がないかとちょっと考えましたが、結局桁DPで解きました。自信なかったけど、15分ほどで書けたのは嬉しかった。

F - Many Many Paths

　長方形区間の二項係数の和。

　絵を書いた後、どうやってもとめるんだろう？　と公式を検索してたけど、ふと各行の累積和を見たら一つ上の行と一致していることに気付いた。

　う～ん、でもこれ、二項係数の有名公式からも導かれるし、最短ルートの道順を考えても分かるはずだし、「気付く」というような内容じゃない気が。もっとすんなり分かっても良かった気もする……。

Codeforces Round #617 (Div. 3)

　変な勘違いでE2が通らず全完を逃した……と思ったらFもHackされてしまった。

コンテストへのリンク

A. Array with Odd Sum

　和を奇数にしたいので、mod 2で考えると分かりやすい。

　元々の和が奇数ならOK。

　和を変えるためには、mod 2で0のものと1のものが存在していないといけない。

B. Food Buying

　効率よくキャッシュバックをもらうには、10の倍数のものを買うのが良い。n円お金があるとき、n//10円のものを買う、としてシミュレーション。

C. Yet Another Walking Robot

　同じ場所を二度通っていたら、その区間は削って良い。

　ので、まずロボットがどう動くかシミュレーションして、同じ場所を二度通っていたらその区間を一つ出力。

D. Fight with Monsters

　「モンスターを倒した次は自分のターン」というclarがないと問題文が不明確でした。もし、「自分が倒したら、次は相手のターンでスタート」だったら、大分面倒になりそうです。

　今回の問題では、各モンスターについて、何回テクニックを使えば経験値を得られるか計算できるので、ソートして貪欲に使っていけばOK。

E1. String Coloring (easy version)

　これは先にE2を見るべきでした。

　二色ということにこだわってよく分からない実装をしてしまった。結局は、LISをO($N^2$)でやるのと同じことをしたと思うんだけど……。

E2. String Coloring (hard version)

　index i, j (i<j)で、S[i]>S[j]のとき、その二文字は交換しなくちゃいけないので、別の色を割り当てなくてはダメ。

　この考え方はLIS（今回はこの逆で、最長減少部分列）と同じですね。
　本番では、LISと転倒数を混乱して、ライブラリを貼り間違えて悩んでいるうちに時間切れ……。

　けんちょんさんの解説記事では、ABCの問題と同一であると指摘されているけど、これが同一と理解するのは難しいと思う（私はまだよく分かってません……）。「LDSに帰着できる」、ということさえ分かればこの問題は解けます。

　ただ、見た目の結構違う問題を同じと気付ける（言い換えられる）かどうかは、もっと難しい問題を解く上では大切ですよね……。

F. Berland Beauty

　最初、全ての区間の美しさを$10^6$に設定しておき、美しさの最小値が大きい質問から順に、その区間のうち$10^6$の部分をその値に更新→十分性チェック、という方針でやった。

　毎回DFSで区間を求めてもO(N*M)だから大丈夫なはず……と思ったらTLEでHackされてしまいました。

　解法を少し変更して、更新された値が一つでもあればOK、として十分性チェックをなくしたりしてもダメ。

　結局、TLEが出ていた原因は、node aとnode bを繋ぐedgeの番号を調べるとき、dict D[a,b]とtupleを使っていたのが不味かったようで。そこを(a<<13)+bのようにしたら通りました。

　なお、初期値を0に設定して、質問された全ての区間を質問の値に更新していく……という方針もありますね。他の方のコードを見て知りました。

AIM Tech Poorly Prepared Contest (unrated, funny, Div. 1 preferred)

　これ、書く意味あるのかな。
　SRMの後だっけ、やってたからちょっと問題を見てみたけど、一問もできずに終わった。

コンテストへのリンク

A. Nash equilibrium

　問題自体は簡単。なのに通らない。なんで？　と言っているうちに終わった。

　頭が固かった……。

　コンテストの説明文は読んでいたはずなのに、"funny contest"の意味を全く考えようとしていなかった。その上、あとで解説を読んでも何言っているのかずっと理解できず……。

"As you may notice, it is just one night before the competition, so we should start preparing the problems. We hope that we'll manage not to do very stupid bugs in the tests. See you at the competition!"

（https://codeforces.com/blog/entry/73543　より）

　こんな文章をね、字面通りにしか読めていなかったのが恥ずかしいです。

TopCoder Single Round Match 777

　一完できたのでレートは上がりましたが、あまり腑に落ちない問題でした。

Div1 Easy PreviousOccurrence

　愚直に探索するだけ。

　ただ、defaultValue = 1　のときは、0, 1, 1, 1,...となり、2以上の数にならないので気を付ける。

　良い方法が思いつかずとりあえず書いてみた後、適当な数で探索してみたところ、Pythonでも間に合いそうだったので提出したらACでした。

　本当は全探索すべきなんだけど、Pythonではかなり時間がかかりそうだったので適当に切り上げました。

　一応、ACしたコードを。

class PreviousOccurrence():
    def findValue(self, defaultValue, query):
        if query==0:
            return 0
        if defaultValue==1:
            if query==1:
                return 1
            else:
                return -1

        NOW=0
        LAST=[-1]*(5000000)
        ANS=0

        while True:
            if LAST[NOW]==-1:
                NEXT=defaultValue
                LAST[NOW]=ANS
                ANS+=1

            else:
                NEXT=ANS-LAST[NOW]
                LAST[NOW]=ANS
                ANS+=1

            NOW=NEXT

            if NOW==query:
                return ANS
                break

Codeforces Round #616 (Div. 1)

　A, Bの二完でした。ですが、実はBも落ちておかしくなかったので、もっと酷いことになってもおかしくなかった。
　Bは、考察で勘違いがあったものの、実装もミスってたためシステムテストを通って救われました……。

コンテストへのリンク

A. Mind Control

　何人に前を取ってもらい、何人に後ろを取ってもらうか、さえ決めれば、何番目の人を説得しても変わらないと気付くのが重要。

　あとは、前を取るよう何人説得したか、で全探索（で、できるものの、結構混乱しやすく難しい）。

B. Irreducible Anagrams

　これは実験してみるしかない気がしますが……。

　「1文字目～k文字目まで」(k=1から最後の一つ前)が全てアナグラムになってないことが必要なので、そうなる条件を考えていく感じかなぁ。

　sampleにある、"abb"に対して"bba"がirreducible、ということから最初と最後の文字が重要そう、と気付いた後、同じ文字でも、"abca"→"caab"のように、他に二つ文字があれば構成可能、と気付ければ解ける。

　どうすれば速く解けるかはよく分からない……。

C. Prefix Enlightenment

　主にアルメリアさんのブログ記事を参考に解説ACしたものの、理解にも実装にも苦しみました。

　とりあえず、こういう問題はグラフへ帰着すると良い、という点ではAtCoder Beginner Contest 155　F - Perils in Parallelの類題といっていいと思う。

　その後は、一つ一つ変化したときに状況がどう変わるかをじっと調べる感じか。スイッチの重なりが高々二つなので、場合分けをする……というのも言われてみれば自然ではある。

　いやぁ、難しい。