yukicoder contest 239

　Cまでの三完でした。DもEも難しかったので、仕方ないかな。

コンテストへのリンク

No.1000 Point Add and Array Add

　まず、クエリBだけの場合を考える。

　これは、BITを使って処理できる。

　たとえば、

・B 2 5

　というクエリに対しては、BIT上の2に+1、6に-1をしておけば良い。

　最終的にそれぞれの要素を何回ずつ使ったかが分かるので、できあがる数列が分かる。

　次にクエリAを処理する。

　「A x y」というクエリだったら、このクエリが来る前にxを何回処理していたかが分かれば良い。最終的に何回使ったかはBITにより分かるので、そこから引けば、増加分yが何回寄与するかが分かる。

No.1001 注文の多い順列

　kmjpさんのブログの方針で解説AC。（包除原理を使う方針は理解できていません）

　kmjpさんの記事の、「前者だが逆に考えよう」以下の説明が難しいけれど、これは本当に逆に考えれば良さそう。

　つまり、「もし逆に、大きい数字から埋めてきたとしたら」と考えたとき、この数字を埋める方法は何通りあるか？　と考えると、掛けるべき係数が得られる。

　これでDPが回るのはちょっと不思議で、正当性を説明・証明しろと言われると自信がないんだけど……。でも、確かにこれで立式できているし……。

Kotlin Heroes: Episode 3

　前日に三問ほど解いてKotlinの書き方を練習して出てみましたが、実際にやってみると文法で困る部分が多かった……。
　Dまでの四問解きましたが、問題を考えるより文法を検索していた時間の方が長かった印象。

　ただ、Kotlinという言語に対する印象は結構良かった。
　変なセミコロンを書いたりする必要がない（個人的にこれは凄く大きい！！！）し、型も結構省略できる。慣れたら書きやすそうな言語でした。

　来月にはKotlin Heroes: Episode 4があるようなので、それに合わせてちょっと勉強しておきたい！

コンテストへのリンク

Codeforces Round #624 (Div. 3)

　時間ギリギリで全完！　と思いきや、DでミスしていてHackされて全完を逃した。

コンテストへのリンク

A. Add Odd or Subtract Even

　x,yの大小や、差の偶奇で場合分けする。

B. WeirdSort

　A[i]>A[j](i<j)となっている箇所があれば、i～jは全てスワップ可能でなくてはダメ。

C. Perform the Combo

　i番目でミスしたとき、各文字を何回ずつ使っているか？　を累積和を使って前計算。

D. Three Integers

　1～$10^5$（もっと小さくても良いと思うが、一応）の範囲で、約数のリストを作っておく。（約数の個数はN=$10^5$として、Nlog(N)程度）

　その上で、bの値を1～$10^5$の範囲で全探索。aは、bの約数のうちでaに一番近いものを、cはｂの倍数に一番近いものを取る。

　Hackされたのは、bを、cの最大値程度までしか変更しなくて良いと思い、1～$10^4$で全探索したためでした。

E. Construct the Binary Tree

　（自分が出ていた頃の）LeetCodeっぽい問題。なんかこういう二分探索木系の問題たくさん出ていたよね……。今も出ているんだろうか。

　まず、木の深さの合計が最小になるのは、完全二分木（子ノードが常に二つ）に近いとき。それを基準にして、深さの和が求められたものになるように構築していく。

　完全二分木にBFS順にノード番号を振ったようなものを考えると、左端のノードは、1,2,4,8,...と2ベキになっている。これを幹にする。

　ノード番号が大きい、葉に近いノードを考えると、その親を入れ替えることにより深さの合計を増やすためには、幹を伸ばすしかない。

　そうやって、幹をどんどん伸ばしていき、最後の一個、幹を伸ばすのでは深さの合計が大きくなりすぎてしまうとき、どの幹のノードにくっつければ良いかを調べて調整する。

F. Moving Points

　近づいていくなら距離は0になる。離れていくなら、互いの距離が最小になるのは初期値のとき。

　左にある点から見ていくとする。

　そのとき、今見ている点Aが、Aより左にある（x座標が小さい点）点Bとぶつからないのは、その点よりBの速さよりAの速さが大きいとき。

　あとは実装問題。BITで管理して解くことができる。(x, v)の図（グラフ）を描いて考えれば分かると思う。

Codeforces Round #623 (Div. 1, based on VK Cup 2019-2020 - Elimination Round, Engine)

　Aのみ一完でレートを落としましたが、結構厳しい回だったのでしょうがなかったかな、という印象です。

コンテストへのリンク

A. Recommendations

　今読んでも難読だと思う……。

　結局、全てのiに対して、A[i]全てが異なるようにしたい。各A[i]を+1するコストがB[i]という内容。

　私がやった解法は、

・各A[i]について、B[i]の和を前計算 & B[i]たちをheapqに入れておく。

・A[i]が小さいものから見て、（そのA[i]の地点でのB[i]たちの和）ｰ(B[i]の最大値)を答えに加え、差分計算。

　という方法。結構面倒だった。他の人の提出を見ると、もう少し良い方法がありそうだけど、そこまで楽にはならなそうかな……。

B. Double Elimination

　公式解説を読んでAC。

　言われてみれば自然な解法だけど、解説を読んでも長い時間理解できなかったし、実装にも苦しんでしまった……。

　とはいえ、状況を整理できいれば思いつけて良い解法に思えます。

　たとえば、5～8番目の人を考える。

　その人たちは、二回試合をすると勝者はただ一人になる。

　敗者組についても同じ。敗者組の試合が二回行われた後、敗者組の中での勝者も一人。

　つまり、勝者組二試合、敗者組二試合が行われた後では、それぞれの勝者は一人ずつしかいない。なので、「その二人の中にfanがいるかどうか」でDPできる。

　具体的には、DP[n][left][Upper][Lower]を、

　n試合後、[left番目～left+$2^n$)番目の人で、

・Upper=1: ファンの人が勝者組で勝ち残っている Upper=0: 勝ち残っていない

・Lower=1: ファンの人が敗者組で勝ち残っている Lower=0: 勝ち残っていない

　ときの、そこまでのファンの試合数の最大値。

　と定義すればDPが回る。

　そう理解した後も実装に苦しんでしまったけど、上手くやれば結構綺麗に書けるのかな……。

D. Tourism

　公式解説にもある乱択解法でAC。

　コンテスト後に「乱択で通した」というツイートを見た記憶はありましたが、その場では理解できず、復習してようやく理解しました。

・全ての町を0と1の色で塗って、「次の町は別の色でしかいけない」という条件で最短経路を求める

　と条件を満たすルートになっている。そして、

・経由するのは高々9個の町なので、$2^9$分の1の確率で条件を満たす。

　ということですね。

　分かってしまえば難しくないけれど、「二色に塗り分ける」という方針がそれほど容易に思いつくものじゃない気が。

AtCoder Beginner Contest 156

　このブログ更新に少し時間が空いてしまった……。二か月前だと記憶も薄れていってしまう。ある程度時間が経ってから問題を見直すのは復習として悪くないと思うけど、二ヶ月は長すぎる。書く内容を少なくしても更新速度を上げていきたい。

　この回は、Fで1caseのTLEが取れず五完でした。まあ、解法はあっていたので良いとします。

コンテストへのリンク

D - Bouquet

　n種類の花から花束を作る方法は、$2^n$通り（これは、「花のないの花束」も含んでいるので、答えはここからｰ1）

　そこから、ちょうどa種類の花束nCa通りと、b種類の花束nCb通りを引く。

　立式は単純だけど、これをこの問題の制約で解くにはベキ乗計算やコンビネーション計算をmod 素数で行わなくてはいけなくて、「繰り返し二乗法」や「フェルマーの小定理」を勉強させる教育的な問題だったんですね。

　この辺は、知らないとどうしようもない知識ですよね……。

E - Roaming

　制約が優しい問題。

　n=2やk=1の場合が入っていたらもっと難しかった。

　そういうのがないので、n人を(n-k)個以上の部屋に割り振る重複組み合わせと、k個の空き部屋の組み合わせで計算できる。

F - Modularness

　mod kでa+dがaより大きくなるのはどんなときか？　と考える。aもdもmod kで考えて良い。このとき、d=0でなく、また、a+d>=kとならなければ、大きくなっている。

　つまり、「繰り上がらなければOK」と気付くのが最大のポイント。

　あとは、Dが周期的に変化するので、「周期的に変化する部分」と「その後の部分」を分けて考える。ただ、今回は初期値が変わるので、「一周ごと」は考えにくい。「周回中」と「それ以後」で分けて考えればOK。

なので、

・周回中の(n-1)/k周で何回繰り上がるか、d=0なのは何回かを求める。

・その後の初期値を求め、残りはシミュレーション

で解ける。

　なお、本番中はTLEでした。

　この解法だと、sum(D)とD.count(0)を求める必要があるけど、こうやって組み込み関数二回使うより、自分でfor文で実装した方が速いらしい。

　確かに、計算回数は2*k→kに減ってるけど……。組み込み関数は速い印象があったので意外でした。

　

TopCoder Single Round Match 779

　Easyを落として緑に落ちた。

　TopCoderのレートはあまり気にしていないつもりだったけど、緑に落ちたのは結構ショックだったので、もっと真剣にやらないと、と反省しました。
　それに、このEasyは通さなくてはいけない問題だったので、そこも反省。

Div1 Easy ArraySorting

　数列Aの要素をいくつか変更し、Aを広義単調増加にしたい。

　変更する要素の個数が最小になるようにし、辞書順最小のAを求める。

　まあ、LISを復元する問題といって良いと思う。

　LISに関する理解がちゃんとしていれば解けたはずなので、解けなかったのはLISの理解ができていなかったということでしょう。

　「辞書順最小」というのに惑わされるけど、「DP[i]で、長さiのLISの最終要素の最小値」を取る、という方法（たとえば、ここの説明が分かりやすいと思う）でLISを求める際に、復元用のリストを用意していれば、自然と辞書順最小のものが求められる。

　この問題も、yukicoder contest 237のNo.992 最長増加部分列の数え上げも、それほど捻った出題じゃないのに意外と難しく感じてしまうのは、LISのアルゴリズム自体がそもそも簡単じゃないからだと思う。

　とはいえ、基本的なアルゴリズムなのだから、ちゃんと身に着けておかないと……。

　以下、ACコード。

import bisect

class ArraySorting():
    def arraySort(self, A):
        N=len(A)
        DP=[1<<31]*N
        fr=[-1]*N # 復元用のリスト

        for i in range(N):
            a=A[i]
            pos=bisect.bisect_right(DP,a)
            DP[pos]=a
            if DP[pos-1]==1<<31:
                fr[i]=1
            else:
                fr[i]=DP[pos-1]

        ANS=0 # LISの長さ
        for i in range(N):
            if DP[i]!=1<<31:
                ANS=i
                LASTV=DP[i]

        NEXT=LASTV

        B=[]

        for i in range(N-1,-1,-1):
            a=A[i]
            if a==NEXT:
                B.append(a)
                NEXT=fr[i]
                
            else:
                B.append(NEXT)

        return B[::-1]

yukicoder contest 238

　Dが解けず。行列累乗を使う問題が二問もあったのが面白かった。

コンテストへのリンク

No.994 ばらばらコイン

　一見難しいけど実は簡単、という問題。このタイプは結構得意にしているつもりなんだけど、これは手間取ってしまった。

No.995 タピオカオイシクナーレ

　まず、求める答えは各タピオカの美味しさの期待値の総和です（これが期待値の線形性っていうやつのはず）。

　あとは、漸化式を立て行列累乗する問題。

　……と思ったら、解説のwriter解は行列累乗を使ってなくて驚いた。

No.996 Phnom Penh

　解説AC。

　基本的には、phnomomomomomみたいなやつのomの数を数えればいいのだけど、omの間にeやhが含まれていると、操作の途中でそれらが消えて、操作が行えるようになる、というところが難しい。

　ただ、解説にあるように「最適な操作」が定まっていることに気付くと、実際にそれを数回やってみることで解決する。邪魔だったhやeが消えれば、omの数を数える問題になる。

・何回か操作をすると定常状態に落ち着く

　から、そこまでシミュレーションしてから考える、という方針で上手くいくことは結構あるはず。

No.997 Jumping Kangaroo

　tester解と同じ行列累乗でACしました。

　形式的冪級数を使う方法が解説に書いてありますね。なるほど、こういうときに使うのですね。