第4回 RECRUIT 日本橋ハーフマラソン 本戦（オープンコンテスト）

　ハーフマラソンは結構楽しみにしていたので、頑張ったのだが……。

コンテストへのリンク

A - ハイパー覆面すごろく

　サイコロを振る問題ということで、乱数があるはずなのに、同じ提出で同じ答えが返ってくることがちょっとピンと来なくて、適当な提出だけして飛ばした。

　実際は、乱数の作り方（xorshift）に問題があり、そこをついて高得点を得る作戦が可能だったらしい。

　xorを使って乱数を作っていることはコンテスト中確認したのだが、知識がなかったので、それ以上突っ込めず。

　当たり前だけど、勉強が役に立つことは多い。

B - ハイパーお掃除ロボット

　ある列を基準にして、文字数が最も多い文字を集めるものをとりあえず書こうとした。左右にその文字があったらそれを取りに行き、基準の列へ戻る。そしたら次の行へ……というのを繰り返す。

　が、それすら書けずに終わった。

　ハーフマラソンは、「とりあえずこれくらい書いておこう！」と思ったものすら書けずに終わることが多いのが厳しい。

yukicoder contest 240

　Eまでの五完でした。Fは難しかったので仕方ないかな、という印象。
　ただ、たくさんWAを出しているのはよくないですね。yukicoderはペナルティなどないので、ついたくさん提出してしまう。

コンテストへのリンク

No.1006 Share an Integer

　エラトステネスの篩の要領で全てのiについてD[i]を列挙するのが自然だと思うけど、解説(writer解)では違うことをやっていた。

　うーん、解の絞り方が難しい（よく分からず……）。

No.1008 Bench Craftsman

　解説AC。

　cに関する単調性は見えるので、二分探索がまず思い浮かぶ。しかし、愚直にやると判定にO(NM)かかり困る。

　困って、違う方法がないか……と考えてしまったのだけど、二分探索の方針は正しかった。

 ｃを固定して判定問題を考えたとき、各人の重さのベンチへの寄与が山形の一次関数（等差数列）二つになるので、それらの和をimos法（など）で計算できないか？　と考える方針が正しかった。
　二回累積和を取るという方法は見たことなかったと思う。覚えておきたい。

　なお、二分探索を考えたとき、一点への寄与が上手く式で表されるのでは？　と考えたのだが、これでは上手くいかない。0とのmaxを取る部分のせいで簡単な式に表せない。

　一点に着目する方針を考えて上手くいかなかったのなら、次は一人に着目するというのは自然な流れなはずだけど……。

　なかなか視点を変えて考えるのは難しい。

2020 Humbleool Cup Prelims

　オンサイトか何か（？）の予選で、Div.1、Div.2混合回。
　Div.2の難易度で、全完しないとまずいセットだったのに、Hardをミスして落とす。
　それでも、緑から青に戻ったけれど、これは出なくても良かったかなぁ、という気持ちになりました。

　なお、MedはPython最速だったらしく公式ページに自分の実装が載っています。

CardDrawPoints

　カードの枚数の制約が少ないことからも分かる通り、bit DPをする問題。

　どのカードを使った/使ってないか、の期待値をbit DPで計算すればOK。

　floatで割り算して誤差が大丈夫か不安だったけれど、それも問題なかった。

　コンテスト中は、残り枚数が0枚のときに、0除算して落としてしまった。ちゃんと気を付けないと！

　一応、システムテストを通ったコードを載せておきます。

class CardDrawPoints():
    def expectedScore(self, count):
        LEN=len(count)
        if max(count)==0 or len(count)==1:
            return 0

        LIST=[-1]*(1<<LEN)
        def calc(A):
            if LIST[A]!=-1:
                return LIST[A]
            
            rest=[0]*LEN
            NOW=0

            for i in range(LEN):
                rest[i]=count[i]
                if A & (1<<i)!=0 and count[i]>0:
                    NOW+=i
                    rest[i]-=1

            SUM=sum(rest)

            if SUM==0:
                return NOW

            ANS=float(0)

            for i in range(LEN):
                if A & (1<<i)!=0:
                    continue
                else:
                    ANS+=float(calc(A|(1<<i)))*rest[i]/SUM

            if NOW>ANS:
                LIST[A]=NOW
                return NOW
            else:
                LIST[A]=ANS
                return ANS

        for i in range((1<<LEN)-1,-1,-1):
            calc(i)

        return LIST[0]

みすだぶりゅ冬合宿わくわく競プロ大会

　Dまで解いて、コンテスト期間が24時間もあるから残りは後で考えよう……、なんて思っていたらいつのまにか終わってしまった。（ごめんなさい）
　でも、復習したら、EもFも解けた気がしません……。頑張って検索すればいけたのかもしれないけど、自力では無理だったのは間違いない。

コンテストへのリンク

E - The Lowest Cost Trees

　解説AC。

　Aをソートするところは良いとして、n頂点の木の種類の求め方を知らなかった。ケイリーの公式というのがあるんですね。プリューファーコードによる木の全単射も面白い。

F - Was This Preordained?

　解説AC。

　ラグランジュ補間は分かっていなかった。今回調べても、ちゃんと分かったとは言い難いけど……おおよその原理は分かったかなぁ。

　ついでに、えでゅふぉの類題もACしました。

　これは、PyPyではACできず、KotlinでAC。ただ、全部Long型で処理しようとしたらTLEしたため、Intとの使い分けが大変だった。modintってこういうとき必要なのね。

　なお、この問題も、pajenegodさんはPyPy3でACしている（1sを切ってる）のですが、どうやっているのでしょう……。

CodeCraft-20 (Div. 2)

　Dまで四完でした。Bで手間取ったため順位はイマイチ。
　日本語の解説記事があったので、復習のときはEやFもACしよう、と思ったらかなり時間がかかってしまった……。

コンテストへのリンク

B. String Modification

　実験してみれば、操作後のSがどうなるか分かるので、それらの最小値を見れば良い。

　ただ、PyPyだと、それらをソートするとTLEになると思う。普通に、一回一回最小値を取っていけばOK。

　自分は、コンテスト中これが思いつかず、一文字目で枝狩りをしてソートしたらACした。

　なんか、最小値だけ求めれば良いところでList→ソートを使ってしまったり、上限の値が小さい正整数の、重複しない要素の個数を求めたいときにsetを使ってしまったり（上限の値までのListでOK）、本質的ではないところで遅い実装に走ってしまう癖がある気がする。気を付けたい。

C. Primitive Primes

　一見難しいけど、実は簡単。Codeforcesでレートを上げたいならこういう問題を落とさないのが結構重要。

　A, Bの係数のgcdが1でないので、素数pで割り切れない係数がA, Bのどちらにも必ず存在する。

　それらの最小のものを足せばOK。

D. Nash Matrix

　まず、動かない点を処理。

　次に、その点がゴールになっている点をゴールからのDFSで処理。

　その後、無限ループする点が、別の無限ループする点と接していればそちらへ向かわせる。

　これらの処理をして、ちゃんと全ての点が埋まればVALID、ダメならINVALID、とする。

　面倒だけど、やること自体は分かりやすい。

E. Team Building

　けんちょんさんの解説記事、akiradeveloperさんの解説記事を読んで解説AC。

　制約からbit DP（かbit全探索）だろうな、と予想できる。

　問題は、どうやってその枠組みへ落とし込むかだけど、応援力（Aで与えられるもの)をソートしてやると、i人目まで決め、その選手をどのポジションにも選ばないと決めたとき、応援にまわすか/まわさないか、が決まるのでbit DPできる。

　結構自然な解法なんだけど、なぜか正当性が分からなくなって悩んでしまった。この問題の正当性というよりは、bit DP自体の正当性について悩んだ。部分集合で最善？　それを二つに分けたとき、両方最善な必要がある？　とかって。

　そういうことを考える必要はなくて、bit DPの正当性は、「最後にxを選んだとき」を考えて帰納法を回していく感じで言えますね。

　なお、この問題はPython/PyPyでは通せずKotlinでACしました。Kotlin Heroesが近付いているので、久々にKotlinを使ったけど、結構書きやすい！

F. Battalion Strength

　けんちょんさんの解説記事、idsigmaさんの解説記事を読んで解説AC。

　ゆるふわ競プロオンサイト #3のSweets Distribution(Hard)もそうですが、

・値変更などのクエリ→セグメント木

　は定番なんですね。

　ただ、どうやってセグメント木で処理するか、何をセグメント木に乗せればいいかも難しい。idsigmaさんの解説記事にはその辺りも全部書いてあるのですが、それでも理解するのに苦労しました。

　「求めたい値を、セグメント木で自分の下に位置する二つのノードから求めるためには何が必要か？」とちゃんと式を書いて考えれば分かると思います。

　さて。

　解法は理解できたのですが、TLEやMLEのためPyPyでACすることはできず、結局C++でACしました。（AtCoderのコードテストだとランダムケースで三秒ほどの実行時間なので間に合いそうなのですが、Codeforcesだと15秒くらいかかってしまう）

　ただ、pajenegodさんはPyPy2で通しているんですよね。他の人がPyPyで通している問題で、PyPyでのACを断念するというのは悔しいのですが……。仕方ない。

Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!)

　Hack caseがあるE, F（どちらもコンテスト後に自分でHackしました）がシステムテストを通って、薄橙に復帰した回。
　Fは嘘と思いつつ書いたら通ってしまって驚いた。悪あがきでもしてみるものですね。

コンテストへのリンク

B. Kuroni and Simple Strings

　Bにしては難しいと思う。

　左から"("の個数を、右から")"の個数を数えたとき、二つの個数の最小値が最大になるところで区切る。そして、その個数ずつ、一番右から")"を、一番左から"("を削る。

　この一回で操作は終了する。

　この削り方だと、「最大になるところ」という性質から、その区切り目の「右側にある")"」か「左側にある"("」は全て消されている。

　それでももう一回操作が行えるとすると、残った片側に"("と")"のペアが存在している場合だけど、これは最大になるときをとったので、あり得ない（その間が区切り目になるはず）。

C. Kuroni and Impossible Calculation

　mが小さいところに注目。

　mod mで同じ数が二つあれば答えは0。そうでなければ、要素の個数はm未満なので、愚直に計算できる。

D. Kuroni and the Celebration

　直径を入力して候補を減らしていったが、実は葉を二つならどれでも良かった。確かに。

E. Kuroni and the Score Distribution

　A=1, 2, 3, ... , nという数列のとき、$A_i+A_j=A_k$というi, j, k (i<j<k)の個数は最大になる。それ以下のmは全て構成可能。

　1, 2, 3, ... とギリギリまで並べ、もう一個をmに合うように調整。残りを適当に大きい数にすればOK。

　調整する数は5000を超えているので、「残りを適当に大きい数にする」というのを適当にやってしまった（自分は、$10^9$から5001ずつ減らした）ためHack caseができてしまっていました。

　まあでもこれは、解法はほぼあっていたので……。

F. Kuroni and the Punishment

　はまやんはまやんさんの解説記事が分かりやすい。

・素数が与えられたら、各数字をその素数の倍数にするのに何回かかるか調べられる

　なので乱択を考えるのは良いとして、

・素数「2」の場合を考えたときを考えると答えは高々N

　ということから、「操作回数が1以下である要素を選ぶ確率が1/2より大きい」と気付けば、乱択する素数の候補が絞れる。

　コンテスト中は、小さい素数たちと、小さいA[i]の素因数のみを考慮したらACしてしまった。

　「+1、-1の候補を考慮する」というのはこの問題の胆なので、A[i]達だけの素因数で通ってしまったのはまずいはずだけど、小さい素数を列挙したり、AではなくソートしたAを使ったりしたのがシステムテストを通った原因かもしれない。

　なお、Aの候補を絞るために、set(A)について乱択すると、「操作回数が1以下である要素を選ぶ確率が1/2より大きい」の根拠が崩れるため乱択が上手くいかなくなることに注意。

　このケースはシステムテストに入っています。コンテスト後解きなおしたとき、なんで通らないかが分からず苦労してしまった。

Codeforces Round #625 (Div. 1, based on Technocup 2020 Final Round)

　A, Bの二完。Cはやり方は分かったけど実装が終わらず、という苦しい回。

コンテストへのリンク

A. Journey Planning

　A[i]-iを考える問題は結構よく出題されてますね。

　（類題を貼ろうと思ったけど、思い出せなかった……）

B. Navigation System

　終点からBFSをしておけば、各点から次にどの点たちへ行くときが最短経路に含まれるかは分かる。

C. World of Darkraft: Battle for Azathoth

　Misterさんのブログや、けんちょんさんのブログに解説があります。

こういう問題は二次元平面上に図示すると分かりやすい。（というか、そうしないと考察するのは無理だと思っている）

・二次元平面上に図示→x, yの片方を固定

　という流れは頻出（たとえば、SRM778のDiv1 Easyとか）。
　特に、xとyが対称のとき、対称性を崩すことに躊躇いを覚えてしまいがちだけど、片方固定で解ける（計算量が落ちる）ことは良くあるので注意しておきたい。

　その後の実装も大変だけど、できなくてはいけないのかなぁ。

　なお、PyPyだと時間制限がやや厳しいです。
　まつかわさんとのやりとりで、こういう知見が得られました。

　INF=1<<31　と1<<31で型が違うのは、前者だと値が変化するかもしれないので、多少安全を取って型を決めているのかなぁ、と想像しています。（本当のところは分かりません）

D. Reachable Strings

　けんちょんさんの解説記事を読んで解説AC。

　同じ方針で解くのは芸がないので、Suffix-arrayを使おうかと思ったけれど、上手くやることができず、結局同じ方針（Rolling Hash）でACしました。

　ところで、Rolling Hashのmodの選択の仕方が理解できてませんでした。2ベキ+1を愛用（？）していたのですが、それをいくつか重ねてもWrong Answerが出てしまった。ランダムな奇数に変えたらACできたけれど……。

　この辺も理解しなくちゃなぁ、と思ったらmaspyさんがまとめてくれていました。証明は追えていませんが、そもそも基数を乱択すべきということすら知らなかった……。

AtCoder Beginner Contest 157

　Fが解けぬままこどふぉへ向かった。

コンテストへのリンク

C - Guess The Number

　条件から各桁の数字を決定する、Nが3以下じゃなくてもいける方針で解こうと思ったらWAが取れず、結局全探索した。

　今見返したら、最上位の桁が0のときの処理がおかしかったようです。

E - Simple String Queries

　BITを26個生やした。

　Pythonで解くならこれが自然だと思う。

F - Yakiniku Optimization Problem

　AtCoder Beginner Contest 151のFの解説pdfの内容が頭に入っていたら解けるはずの問題でした。

　しかし、逆にその問題のせいで三分探索に飛びついてしまった人も（自分も含め）多いはず……。時間いっぱい考えていてもACできなかったと思います。

　二分探索は思いつくだろうけど、その後の、「円と円の交点や円の中心」全探索で良いというのはなかなか気付きにくいと思う。その上、幾何特有の誤差の処理も必要で、典型かもしれないけどなかなか難しい問題でした。

butsurizuki Beginner Contest 003

　物理好きさんによるコンテスト。
　全完で四位と良い出来だったと思う。
　Fみたいな問題がABCで出ることはあるんでしょうか。

コンテストへのリンク

CROSS†SOUL

　「逆順が最適」だけど、全探索でも解けるように作られている教育的問題。

　解説スライドにある通り、この最適性の証明は競プロにおいて重要ですね。

DEATH†ZIGOQ ～怒りの高速爆走野郎～

　最小全域木の作り方、もしくは、ダイクストラ法といったあたりを知っていれば解けると思う。

何でもダガー打ちゃいいってもんじゃねぇぞ†2020

　「部分文字列を走査するDP」を使う問題。これ系の問題は何度も解いているはずなのに、出題されると結構時間がかかってしまう……。

"✝"

　十字架の区間はの管理は、縦パートと横パートで分けてimos法を使えばできそう。（解説スライドでは正方形に対して操作しているけど、縦横で分けた方が考えやすくないですか？）

　あとは、駒の種類だけど、どうするか→駒をHash化すればいけそう。

　計算量の見積もりはしていないけれど、Pythonだと計算時間が厳しそうなので、雑に二次関数でHashを作ったらWAが出て困った。最終的にはACできましたが、13回も提出した。

　こういう問題はAtCoderよりもCodeforcesで出やすいと思うのですが、CodeforcesだときちんとHashをrandom化しないとHackされやすい。だけど、乱択系の問題は制限時間が短く設定されていることが多いためPython/PyPyだと辛くなってしまいやすい……。

　Hackがなければどうにかなることが多いのですが。

ゆるふわ競プロオンサイト #3 (Div. 1)

　三完＋部分点で終了。
　結構がんばったのだけど、難しい問題は解けず悔しい出来でした。
　しかし、改めて復習すると、解けなかった問題はどれも解けそうになかった気がしてしまった。

コンテストへのリンク

解説スライドはここ

Bananas Multiplier

　LCAは書けますか？　という問題。

Banana Game

　解説AC。

　Grundy数を知っていればやるだけの問題。

　Grundy数についてはふるやんさんのブログが分かりやすいと思う。

　……が、その「やるだけ」のはずのパートが難しくないですか？

　Grundy数を調べるのも、そこから規則性を見つけるのも結構難しい。コンテスト中は、Grundy数の記憶が曖昧だったから飛ばしたけど、飛ばさずやったとしても非常に時間がかかった（もしくは、終わらなかった）気がする。

Sweets Distribution(Hard)

　解説AC。（Python3でACしましたが、同じコードをPyPy3で提出したらTLEでした）

　公式解説も分かりやすいし、検索すれば他にもいくつか解説（私にはアルメリアさんの解説が分かりやすかった）が出てきます。

　こういうものがセグメント木に乗る、ということを初めて見たので驚きました。面白い。

　「二点変更クエリを処理する」と思えば、セグメント木を使うのは不自然ではないですが、とはいえ、似たようなことをやったことないとセグメント木を使うという発想は出にくい気がします。

Yet Another Cake Division

　アルメリアさんの解説やけんちょんさんの解説を見て解説ACはしました。
　（答えの式が書いてあったので、それを書いただけとも）

　最初の一手も、その後の考察も難しい……。

Digit Sum Multiple

　解説ACはしました。

　公式解説を読んだとき、「下k桁が$2^k$の倍数であるような整数」を見つける部分をどうすれば良いか分からなかったのですが、けんちょんさんのブログ記事に構築の仕方が書いてありました。
　いや実際は、公式解説にも帰納法で証明できる旨は書いてあったので、それをちゃんと実行すれば分かったんですよね。

FII Code 2020 Round #2 (rated)

　Dまでの四完でした。まあ実力相応か。

コンテストへのリンク

Big String

こういう問題は実験してみるしかなさそう。
　実験してみると、「Sの最後の文字」が、一回目だけS[-1]でそれ以後はS[0]と分かります。

Connecting the Graph

　最小全域木を作るアルゴリズムをそのまま適用したのでは、計算時間が間に合わない。

　では、コストが小さいのはどういうものか？　と考えると、A_iとA_jの差が小さいとき。なので、Aをソートして、ソートした隣あった二項が候補。それらの差が小さい（つまり、コストが小さい）方から同じグループへ入れるかを決めていく。

Disproportionate Tree

　Kを二進数に直すのがポイント。

　あとは、下の桁から適切に割り振っていく感じで。