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しました。

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

　

Codeforces Round #621 (Div. 1 + Div. 2)

　pretestは四完でしたが、システムテストでCが落ちてしまいました。

コンテストへのリンク

B. Cow and Friend

・まず、一歩でいける場合を調べる。

・一歩でいける最大の距離max(A)を考え、それで何歩でたどりつけるか。最後の二歩でどんな距離でも調整できるので、進みたい距離/max(A)の繰り上げが2ならそれが答え。進みたい距離がmax(A)未満なら、答えは2

C. Cow and Message

　”abc"で等差数列をなしているものの数と、"ab"で等差数列をなしているものの個数を比較すると、前者なら必ず後者に含まれます。

　なので、一文字・二文字の場合だけ調べればOK。

D. Cow and Fields

　新たにsからtまでの道を作るとする。

　1から各点までの距離、nから各点までの距離を求めておく。

　s→tがショートカットになるとすると、1からsの距離より1からtの距離は長く、nからsの距離よりnからtの距離は短い。

　なので、できるだけショートカットにならないようにするには、１からの距離が長い順に点を見ていき、考慮している点より、「さらに1からの距離が長い点たち」のうちでnからの距離が長いものを選ぶ。

E. Cow and Treats

アルメリアさんのブログの解説記事を大いに参考にしてACしました。全く思いつかなかったのですが、解説されてみるとシンプル……。

　まず、

・左右の牛たちのために、草も左右で分ける

　すら思いついてなかった。その上で、

・重複して数えないため、境界の一つ左側の草は必ず使う

　という条件で数えるのが重要。
　二点目はかなり難しそうだけど、一点目すら思いついていなかったのでコメントしにくい。でも、重複して数えないためにある要素を固定して数える、というのは重要そう。


　ただ、やり方が分かっても実装が大変ですね。（実装部分は大体自力でやったこともあり）非常に苦労しました。

　なお、PyPyだとアルメリアさんの実装そのままだとTLEすると思います（自分の場合はそうでした）。

　ここの実装方針では、牛の総和・総積を取っていますが、ここも差分計算でできます。総和・総積のうち、今見ている草と一つ前の草以外については同じなので、その差分だけ計算すればOKです。（modが素数なので、積も逆元が取れます）

　これをしたらACできました。

　この変更をしても計算量のオーダーは変わらない……と思っていたのですが、これをすればO(nlogn)になりますね。
　でも、実装は複雑になるので、C++使いにはあまり意味のない改善かも……。

AtCoder Beginner Contest 155

　Dができず三完でした。
　順位的にはひどいのですが、
　Eが多く解かれているのには気付いていたけどDの解法は分かっていたので実装したかった、かつ、Dは若干Pythonに不利な問題だった、という事情があるので、まあ。

コンテストへのリンク

D - Pairs

・二分探索を使って、答えの数より大きい数がK個以上あるかを調べる

　という方針はOK。

　あとは、Aをソートしてあれば、N*Nのマス（の半分）のうちで、Kより大きいものが何個か？　を各行について二分探索で求めればOK。（ただし、負の数に注意）

　……なのですが、Python/PyPyだと実行時間的にこれを通すのは厳しい。（numpyを上手く使えば通るのかな）

　よく考えると、これは尺取り法を使って実装することもでき、これならPython/PyPyでも通せます。

　いやでも、二分探索→二分探索の方が実装が楽だと思うので、これで通すのが厳しいのはちょっと辛い気がしてしまう。

E - Payment

　コンテスト中に問題文は読みましたが、解法がすぐ思いつかず、思いついているDに専念しました。

　DPだと言われれば解けますが、ちょっと気付きにくい。言われてみれば。

F - Perils in Parallel

・区間の操作を考えるのは大変→階差を取ることで、二ヶ所切り替える操作になる

　ということを思いついた上で、

・グラフへ帰着

　すればOK。

　どちらも重要そうだけど、どちらも全く気付けなかった。頭に入れておきたい。

　二つ目に関しては、以前書いた通り、Codeforces Round #616のC. Prefix Enlightenmentと似た発想だと思う。短期間に二回同じ手法が出題されているので、身に着いていて欲しいなぁ。

　この問題は、グラフに帰着した後の実装は難しくないので、ちゃんと解法が身に着いているかが問われている印象。

TopCoder Single Round Match 778

　0完の上、Hack失敗して大きくレートを落としてしまった。（そして、一回Hack失敗したのだからダメ元でもっと試してやろう、と思ったのだけど、なんかそれ以上Hackできなくなった）

　……けど、まぁ仕方ないかな、という気持ち。

　Hack case作りに失敗したのは良くないけれど、Hackしようとした提出はシステムテストで落ちたので、「落ちそう」と思ったこと自体は間違ってなかった。

Div1 Easy KRectangleIntersection

　kmjpさんのブログに解説があり、解法は理解しました。

　が、想定解がO($n^3$log(n))ということで、多分Pythonでは通らないと思うのでACしていません。

　x座標を固定することは思いついていたのだけど、その後、何をすればいいか分からなかった。結構愚直な方法だし、想定計算量がO($n^3$log(n))だと分かっていれば思いつけたのでは？　という気もする。

　ただ、Pythonだと三乗の時点で厳しいので、もっと速い解法を探してしまうのもまあ仕方ないかな……。SRMで戦うには、これくらいさっとC++で書ける力を身に着けなきゃいけないのだろうけど。