yukicoder contest 242

　maspyさんの回ということでやる気はあったのに、不出来で残念。

コンテストへのリンク
コンテスト後のツイート

No.1017 Reiwa Sequence

　解説AC。
　鳩の巣原理を使うんだろうと思っても、使い方が意外と難しい。n個の要素を-1か+1を選ぶのは$2^n$通りなので早く発散しそう……と思えば、それらの和の値で抑えるのは自然なのだけれど。鳩の巣原理を使いなれていると思いつきやすいんだろうなぁ。

　その後の実装をどうするかも悩んだ。
　単純な$3^N$では間に合わないけど、半分全列挙するのは面倒だし……と。結局、解説の「計算方法（１）」の方法で実装したけど、この実装もちょっと思いつきにくい気がする。
　たとえば、indexの集合　S={1,2,4}, T={2,4,6,7}とで和が一致するとき、2,4という重複要素はどうするんだろう……と思ってしまった。この場合、同じ要素を足しても打ち消し合うのでそこは0にして、$A_1, -A_6,-A_7$が0になる。冷静に考えれば分かるけど……。

April Fools Day Contest 2020

　Codeforcesのエイプリルフールコンテストは、去年出たけど全然分からなくて辛かった記憶があった。それを考えれば今年は健闘したと思う。

コンテストへのリンク
コンテスト後のツイート

C. ...And after happily lived ever they

　題名の文法がおかしくて、"... and they lived happily ever after"の並び替えになっているというところに気付かなくちゃいけない。英語力の問題だけど、これが分からなかったのは情けない。

　その後、二進数にしたものを並び替えるパートも難しい気がするけど……。そこまで気付いてればできるものなのかな。たどり着いていないので何とも言えない。

D. Again?

　今解説読んだら、OEISはミスディレクションだったのですね。

E. Jordan Smiley

　ペイントに画像をコピーし、内側を黒で塗りつぶした後、Pythonで処理した。

　そのコードはこんな感じ。x=13.5というのは、切り取ったときの一マスの幅です。

from PIL import Image
import numpy as np

im = np.array(Image.open('jor.png'))

x=13.5
ANS=[[0]*64 for i in range(64)]

for i in range(64):
    for j in range(64):
        if (im[int(i*x+x/2)][int(j*x+x/2)]==[0,0,0]).all():
            ANS[i][j]=0
        else:
            ANS[i][j]=1

yukicoder April Fool Contest 2020

　エイプリルフールコンテストらしい問題と、普通の問題があった……くらいの感想しかないなぁ、と問題を見直していたらとんでもないことに気付いた。

コンテストへのリンク

No.3063 幅優先探索

　壁を通っても良かったらしいです。

　コンテスト中、このことに気付いてなかったのに一発で（一回TLEは出してるけど）ACしている！

　ということは実装を間違っていて、「壁はいけない」という条件を書かずにBFSしたということで……えーっと。

　かなり恥ずかしいミスですが、それでACになってしまうと気付かないですね。

　全然普通の問題じゃなかった！

No.3070 ソラニン

　これが解けなかったのは悔しい。

　検索して片方は見つけていたのだけど、fとg二つがあるということは、片方が「イイネ」で片方が「RT」だと思い込んで分からなくなってしまった。

　思い込みはよくない。

Codeforces Round #630 (Div. 2)

　Eまで解いた。Fはあまり考えなかったよう。

コンテストへのリンク
コンテスト後のツイート

D. Walk on Matrix

　 "bitwise AND"の演算では、0を作るのは簡単だし、桁が定まっているなら二進数表示で1111111という形の数とかけても値が変わらない。

　それを考えれば、0とkを作ろう、とするのは自然だと思う。

E. Height All the Same

　偶奇だけ考えれば良い問題であることは、実験すれば分かる。

　n*mが奇数のときはどのような場合でも構成できるが、n*mが偶数のときは、最初に置かれた個数が偶数個でなければ上手くいかない。その場合の数は大体半分に思えるけど、筋の良い証明方法が分からなかった。

　うーん、ただ、公式解説も結構技巧的だった。

　$k=R-L$として、（座標を適切に順序つけて）k個積み重なっていない最初の座標を xor 1する。そうすると、偶奇が変わるので、条件を満たすものと条件を満たさないもののペアができる。ただし、kが偶数のときは、条件を満たす方が一つ余る。だから、答えは、全体の半分か、半分+1になる、というもの。

　技巧的ではあるけれど、「ペアを作る」という考え方も、「xor 1を取ってペアにする」という考え方も重要なものではある。

　この問題についていえば、「直感的に半分になりそう」で答えを導ければ良いと思うけど、この証明方法も扱えるようになりたい。

F. Independent Set

　公式解説を読んで方針を理解してAC。

　木DP……と言われて木DPが何かをすぐ思い出せなかったのはまずい。根から葉の方向にDPを更新していく気がして、分岐でどうするんだろう……と思ってしまった。最近、全方位木DPの問題は何度か見たけど、木DPの問題を見ていなかった。

　葉から根に向けてDPを更新していくのですね。

　今回は、nodeと、そのnodeから根に向かうedgeの組について、「色を塗るかどうか」「誘導部分グラフを構成するときに使うかどうか」で場合分けして、この四通りのDPテーブルを埋めていけばOK。

　図を描いて落ち着いて考えれば遷移が分かりました。

G. No Monotone Triples

　アルメリアさんの解説記事を読んで解説AC。

　解かれている人数も少ないし公式解説も長いしで、普段なら手を出さないのですが、アルメリアさんが記事を書いている問題はACしないと！　と思って頑張りました。

　解説を理解するのはそれほど難しくない（これは、アルメリアさんの記事が図も入っていて丁寧だ、ということも大きいですが）けれど、自力で思いつくのは難しいタイプの問題だと思います。そして、実装が大変……。

　解説記事を読んで方針は分かったのですが、二分探索が必要なのか？　BITが必要なのか？　あたりで戸惑いました。

　そのあたりは今の自分の力だと実際に実装してみないと分からないですね。使わないで書けるのでは？　と思って実装してみたら上手く書けず、解説記事のやり方に落ち着く、というのを繰り返しました。

　厳密には、「長さ3の場合」は二分探索もBITもなしでやれますが、「長さ4の場合」は二分探索やBITとBIT上の二分探索が（自分の考えた限りでは）必要そうです。長さ3の場合での二分探索を使うなくしたらTLEが取れ、PyPyでもACできました。

　アルメリアさんの記事では長さ3の場合でもBIT等を使っていますが、長さ4での説明をスムーズにするためにそういう書き方にしているんだと思います。

　問題への理解が深まるにつれ、解説記事（とその実装方法）の評価が高くなっていった……というのは良い解説だという証拠ですね。

JOI 感謝祭 2020

　二完で部分点もほとんど取れない悲しい結果。
　双子のコンテストは解説がしっかりしてることもあって好きなのだけど、最近は良い結果が出せていませんね。

コンテストへのリンク
解説PDF
コンテスト後のツイート

鏡のような分割（Mirror-like Division）

　公式解説を参考に実装したら80点は取れました。

　再帰を使っていて、あまり良い実装ではないと思うので、上手く実装すればPython/PyPyでも100点取れるのかもしれないけど……。

　Nが47以下ということで、半分全列挙や、bit全探索がまず思いつくと思う。

　で、結局、半分全列挙でこそないものの、「半分に分けてbit全探索」（の高速化）が正しい解法。自然で思いつきやすい方針だと思うのに、なんで考え付かなかったんだろう……。

　解説スライドの最後、bit全探索をDFSで実装した方が速くなる、というのは意外でした。

塗り箸2（Chopsticks 2）

　問題文を理解するのに苦労しました。やること自体は分かりやすいんだけど、読み解くのが難しい……。特に、クエリについて、区間L～Rが変化するという設定は必要あったんだろうか？　一点変更クエリだけじゃ何かまずいことがあったのかな。

　解説を読んで46点は取りました。そこまでやればBIT＋座標圧縮は思いつけると思うので、そこから90点までは実装問題に見えます。

　一番の本質は、「中央値を求めればOK」というところだと思います。

　そう言われてもなぜそうなるのかすぐには分からなかったのですが、図を描くと分かりました。

　「大きくしたい値」（今回であれば奇数個目）と「小さくしたい値」（偶数個目）がそれぞれ何個かずつあるとします。

　このとき、境界より下にある「大きくしたい値」の個数と、境界より上にある「小さくしたい値」の個数が同じだけあれば、そこを境界にするのが最適です。（図を描いて考えると、そこからずれたらもっとコストがかかることが言えます）

　で、今回は、「大きくしたい値」と「小さくしたい値」の個数が同じなので、中央値を境界にすると、境界より下にある「大きくしたい値」の個数と、境界より上にある「小さくしたい値」の個数は同じになり、条件を満たします。

　こういうタイプの問題で中央値を考えるのは一つの定石だと思うので、思いつけるようになりたい。

AtCoder Beginner Contest 160

　Eまでは結構順調だったのに、一時間以上かけてFが解けず。全方位木DPだということは分かっていたのですが。

コンテストへのリンク
コンテスト後のツイート

F - Distributing Integers

　部分木のノード数と、答えをもって全方位木DP（rerooting）。
　この問題でも全方位木DPの実装にかなりの時間を取られている。

　コンテスト中TLEしてしまったのは、全方位木DPをしようとしているのに、前計算を利用できていないところがあり、二乗の計算量になってしまったためでした。
　これに気付けないのはまずい。


　復習のためと思ってもう一度書き直してみたのだけど、やはりかなり時間がかかってしまった上、また二乗で提出して一回TLEしてしまった……。

　全方位木DPは辺に関するDPとして理解している（一回目は葉から根の方向に、二回目は根から葉の方向に値を決める）のだけど、DPテーブルとしてはDP[node]=valueとするため、一回目と二回目で見る部分が違ってしまうのが混乱のもとだと思う。
　（一回目では、DP[x]でnode x→P[x]の辺に関する値を求めるため、xの子供たちを見れば良いけど、二回目では、DP[x]でnode P[x]→xの辺に関する値を求めるので、P[x]に繋がる辺たちを調べることになる。それが紛らわしい）

　これでいつも戸惑ってしまうのだけど、どうにかできないだろうか……。ちゃんとライブラリ化しなくちゃいけないのかな。

Thanks Kosen 2020

　ツイッターで見かけたので参加。
　今見たら、Gも解けるべき問題でした。ただし、実装は大変ですね。

コンテストへのリンク
コンテスト後のツイート

E - インターン

　端での挙動を考える。

　一番端のゲートから出てきたとき、その次に向かうゲートはその隣のゲート以外ない。一番端とその間の座標からスタートし、最初に一番端のゲートに入った場合も、めぐりめぐって、隣のゲートから元の位置に戻ってくる。

　ということは、端のゲートとその隣のゲートは連続して通ることが分かる。なので、ゲートを二つずつペアにして考えれば良い。

F - 卒業RTA

　科目群と全体とで二回DPすれば良いということは分かるけど、実際に実装しようとするとなかなか大変。

　コンテスト中苦労したけど、どの辺りがポイントだったかは覚えてません……。

G - 答辞

　今やったら自力でACできました。

　累積和と二分探索を使えば、「各indexが左端のとき、右端はどこより先か」、「各indexが右端のとき、左端はどこより先か」が分かる。そう整理すると、このブログで何度か引用しているアルメリアさんのこの記事に帰着できる……と思って見に行ったら、この問題も例題として扱っていましたね。

　何度か似た問題を解いたおかげとはいえ、自力でこの方法だと気付けたのは嬉しい。ただ、実装にはかなり時間がかかってしまうんですよね……。このタイプを早く解くのは厳しい。

Codeforces Round #629 (Div. 3)

　Eを考えながら寝てしまった。
　Unratedだと（時々Ratedでも）、詰まったときに寝てしまうことがあるのは良くないですね。そもそもこのEは詰まらずに解けておくべき問題でした。

コンテストへのリンク

E. Tree Queries

　なんか、クエリごとに木を探索してもOKな気がして、計算時間が間に合っていないものを間に合っていると勘違いしてコードを投げてしまった……。コンテスト後で気楽に考えられるはずなのに、こういう間違いをしてしまうのはちょっとまずい。

　解法としては、深さと各ノードの親ノードを求めておき、一番深さの大きい点Mと、それ以外の点xについて、LCA(M,P[x])=MとなればOK。

　Senさんの解説記事には、オイラーツアーだけでやる方法も書いてあります。

F. Make k Equal

　実装はやや面倒くさいですが、こっちの方がEより簡単ですね。「ある数字まで左から最小値を押し上げていったときのコスト」、「ある数字まで右から最大値を下げていったときのコスト」を計算できるので、「最終的にk個にする数字」を全探索すればOK。

　……で済まそうと思ったら9WAもしてしまった。

　自分が間違えていたのは、たとえば、「2,2,2,5」の2を二個5にしたい、というとき、(5-2)*3で計算してしまったことでした。これは間違いで、全ての2を4にしてから二個5にしなくてはダメ。

　これで42caseまで通ってしまった（！）ので、くだらないミスかと思い添え字を変えたりとか迷走してしまいましたが、根本的に間違っていました……。

Educational Codeforces Round 84 (Rated for Div. 2)

　Dより簡単なはずのEが解けず、DもHackされたという失敗回。Rateが付かなくて助かった。
　こういうことを何度もやっているため、Educational Codeforcesには苦手意識がある。

コンテストへのリンク
コンテスト後のツイート

D. Infinite Path

　（ツイッターに書いた通りだけど）あるindex iからi→P[i]→P[P[i]]→……と変化するものが、どういう風にループするかを調べる。

　このループ上で同じ色が無限に続く可能性があるのは、このループの長さの約数のみ。なので、約数個飛ばしで同じ色が続いているものがあるかどうかを調べる。

E. Count The Blocks

たとえば、n=1の長さ1と、n=2の長さ2で答えは同じになる。
　一般に、n=kの長さlとn=k+1の長さl+1で答えが同じになることは、長さlのブロックに一つ数字を加えて長さl+1のブロックにすることで、全単射が構成できることから分かる。

　なので、各nについて、長さ1のブロックの個数を求めれば良い。

　余事象を使って漸化式を立てる方針が分かりやすいと思う（が、自分はコンテスト中この方針でやろうとして立式を失敗した）。
　が、端かそうでないかで場合分けすれば、そのまま立式することもできる。

F. AND Segments

　解説AC。アルメリアさんの解説記事、けんちょんさんの解説記事に分かりやすく解説されている。

・各桁ごとに独立に考えて良い

・DP[i]を、index iが0の（iまでの条件は満たしているような）個数とおく

　の二点に気付ければ、その後の累積和を用いたDP高速化はそれほど難しくないと思う。

　前者については、bitのandを考えるので、各桁ごとに考えようと思うのは自然。そう考えていれば各桁ごと独立というのも見えるはず（気付く前に解説を見てしまったけど……）。

　後者に気付くのは難しそう。

　ただ、「l～rのうち少なくとも一つが0」という条件を満たす個数を求めたいので、0が入る位置に着目するのはまあ自然か。

　その後の発想は、アルメリアさんのこの記事の方法と似ていると思う。与えられた条件を左から順番に見ていこう！　というのはCodeforcesでは典型といって良いと思うし、自然にできるようになりたいね。

　なお、解法を理解した後、実装にも苦労してしまいました。添え字はどうするのが分かりやすいのかな……。

AtCoder Beginner Contest 159

　Eまでは比較的早かったけど、Fが解けなかった。

コンテストへのリンク

F - Knapsack for All Segments

　maspyさんの解説（形式的べき級数を使った方法）が分かりやすい。公式解説動画もこの方法を使っていた。

　この問題に出会うまで形式的べき級数に関して勉強する気はあまり起きなかったけれど、この問題に出会ったことで勉強する機運が高まった。（maspyさんの記事は一応読みました）

　しかし、その後に出た類題を解けなかった（訂正：一応時間内にACはしていました。すごく時間がかかったし、形式的べき級数を思いつきませんでしたが）のを見ると、理解が足りていなかったようだ……。

Kick Start Round A 2020

　Dが解けず。
　コンテスト中もTrie木を使うのかな、とは思ったようですが……。

コンテストへのリンク
コンテスト後のツイート

Bundling

　（英語だけど）この動画解説を参考にした。……けど、Trieが頭に入っていればそれほど難しくないね。簡単な木DPで解けます。

　Trieについては、kami634さんの記事が詳しいし分かりやすい。上の動画でTrieの概要は理解できたのだけど、実装をどうすれば良いか分からなくなったときこの記事が参考になった。感謝。

　実装方針が分かってしてしまえば意外と書くのは簡単だったけれど、自分で最初実装を考えたときは、辞書を使って云々しなくてはいけない気がしてしまい困った。ノードが追加されるたびに、新しいidを割り当てるようにすれば良いですね。

　ACした提出を一応載せておきます。（見ての通り、Trieをclassにしたりはしてません）

import sys
input = sys.stdin.readline

T = int(input())
for testcases in range(T):
    N,K=map(int,input().split())

    # Trie木

    Next_node_id=[[-1]*26] # "A"～"Z"それぞれについて、対応する次のノードのid
    Parent_id=[-1] # 親ノード
    Depth=[0] # Trieのノードの深さ
    Count=[0] # Trieのノードの重複度

    Nodes_id=1 # 以下、標準入力で与えられたN個の文字列を追加する実装
    for i in range(N):
        S=input().strip()
        L=len(S)

        NOW=0
        for s in S:
            NEXT=ord(s)-65
            
            if Next_node_id[NOW][NEXT]==-1: # Nodeを追加する場合
                Next_node_id[NOW][NEXT]=Nodes_id

                Next_node_id.append([-1]*26)
                Parent_id.append(NOW)
                Depth.append(Depth[NOW]+1)
                Count.append(0)

                NOW=Nodes_id         
                Nodes_id+=1

            else: # 追加しない場合
                NOW=Next_node_id[NOW][NEXT]

        Count[NOW]+=1 # 終端に印を付ける

    TOP_SORT=sorted([(dep,id) for id,dep in enumerate(Depth)],reverse=True)

    Rest=[0]*len(TOP_SORT)
    ANS=0

    for dep,n in TOP_SORT:
        c=Count[n]+Rest[n]
        ANS+=Depth[n]*(c//K)
        Rest[Parent_id[n]]+=c%K

    print("Case #"+str(testcases+1)+": "+str(ANS))

            

AtCoder Grand Contest 043

　遅解き二完だけど、なんとかBを解けて助かった。

コンテストへのリンク
コンテスト後のツイート

B - 123 Triangle

　最初、絵を描いてみたとき、結構すぐにパスカルの三角形に似ているのでは？　と思った。なのに、それを捨てて迷走してしまった……。

　最終的にパスカルの三角形を使う発想へ戻ってこれたのは良かったけれど、もうちょっと最初の発想を追及してみようという気持ちがあれば、速く正しい解法へ到達できた気がする。

C - Giant Graph

　公式解説動画を見てAC。

　ゲーム以外の場面でGrundy数を使う問題は初めて見たと思う。ゲーム以外の問題で使える概念だと思っていなかったので驚いた。けんちょんさんやアルメリアさんもブログで似た感想を書いていますね。

D - Merge Triplets

　公式解説放送や、けんちょんさんの解説記事やアルメリアさんの解説記事を参考に解説AC。

　解き方よりも、けんちょんさんの記事にある、

さて、こういう「操作の結果出来上がるものが何通りありますか」という問題では、操作過程をまともに追いかけてはいけないと痛感している。まずはじめに「こういう順列を作れますか？」という判定問題を解くのだ。

　を心に留めておきたい。

　コンテスト中もコンテスト後も、操作を追いかける方向でしか考えなかったし、判定問題を解こうという気持ちになれなかった……。強く反省。
　なお、DPの立式の部分はアルメリアさんの方法が分かりやすいと思います。公式解説の方法やけんちょんさんの記事の方法はそれに比べるとやや難しい（理解するのに苦労しました）。

OUPC β

　Fが解けずの五完でした。writerさんの解説記事まとめはここ。

コンテストへのリンク
コンテスト後のツイート

Product Grid

　KがLCMになるのは分かるけど、その後の計算量削減部分は難しい。

　Kの素因数はすごく多い（かもしれない）けど、各$A_{1, i}$は小さく素因数も少ないことを利用する。コンテスト中よく思いつけたな……。

Increasing Path

　Pathの長さが短い辺から処理していくと良さそうなのはそうで、それを実現するため、（最後に通った辺の長さ, 今までの総距離, 点の番号）を持ってダイクストラしました。

　ただ、今、解説を読んで後で考えるとこの解法は怪しそう。「ある点での最短距離が何度も更新される」「その点からたくさんの辺が出ている」ようなグラフだとTLEになりそう。

　この問題だと、「通る辺の距離が真に大きくならなくてはいけない」ので、そういうグラフでも計算量はある程度抑えられる気がします（ちゃんと考えていないけど）が、広義単調増加でOKだったらこの解法は完全にダメでしたね。

ビブンケイスウ

・二字以上の項は必要ない→セグ木に乗る

　という問題。

　コンテスト後、writerさんはギャグだとツイートしていて、当時自分もそう思ったけど、「こういうのがセグ木に乗る」というところはなかなか本質的ですね。

　二字以上の項が必要ないと分かっても、セグ木に乗せる部分を自力で思いつけたかは疑問です。

TopCoder Single Round Match 781

　EasyをHackされて0完でした。
　いや、これは解けなくちゃいけない問題でしたね。こういう、それほど難しくない構築は取りたい……。

Div1 Easy EpicPartition

　公式解説を読むと、色々方法がある、と書いてある（としか書いてない）。kmjpさんの解説もあるけど、色々な方法があるらしいので、別な方法を考えた。

　cの位置を決めることを考える。
　kmjpさんの解説にもある通り、cを埋めた残りが全て二個連続していれば（適当な四個を前半二個、後半二個に分けて）"abba"とすることで、aとbの和を一致させることができる。
　なので、できるだけ連続している位置にcを埋めたい。

　ここで、"c"を埋め込むときの平均値を考える。
　たとえば、N=6のとき、全体の和は300、"c"の和は150で8個なので、平均は18.75。なので、18と19を中心に、15~22を"c"にしようとすると2だけ不足する。のえ、最後の22を24に変えれば辻褄が合う。

　一般にこういう構成で良いことは立式すれば証明できる（できた）。
　1～24xの中から1/3を"c"にするとすると、"c"の和は$144x^2+6x$で、18.5x中心に構成した和は$144x^2+4x$。後者の構成の最大の数は18x+4xなので、それを1～24xの中で最大の数である24xにすれば辻褄が合うことが分かる。

　以下、システムテストを通ったコード。

class EpicPartition():
    def createPartition(self, N):

        if N%4!=0:
            return ""

        k=N*6
        ALL=k*(k+1)//2
        CK=(ALL//2)//(k//3)

        ANS=["a"]*k
        ANS[-1]="c"
        for i in range(CK-k//6,CK+k//6-1):
            ANS[i]="c"

        f=0
        for i in range(k):
            if f< k//3 and ANS[i]!="c":
                if f%2==0:
                    ANS[i]="a"
                else:
                    ANS[i]="b"
                f+=1

            elif ANS[i]!="c":
                if f%2==1:
                    ANS[i]="a"
                else:
                    ANS[i]="b"
                f+=1

        return "".join(ANS)

Codeforces Global Round 7

　Dまで四完でした。復習すると、Eが解けないのはまあ仕方ないかな、という気もしてしまう。
　FもACしようと思った（F2は厳しくてもF1は結構解かれているので、F1だけでも）のですが、公式解説を読んでも理解できなかったので飛ばします。無念。

コンテストへのリンク
コンテスト後のツイート

D. Prefix-Suffix Palindrome

　Sの一番最初の文字(prefix)と一番最後の文字(suffix)が同じであれば、それは必ずtに含まれるので、前処理でその部分を求めておく。

　それらを除いたものを改めてSとすると、求めたいものは、「Sのprefixかsuffixになっていて、かつ回文である最長の長さのもの」。これは、Manacherを使うことで求められる。

　Manacherの解説はすぬけさんのブログ記事が有名かつ分かりやすいですね。（ただし、この記事自体は分かりやすいと思いますが、Manacher自体が結構難しいので理解するのはそんなに簡単ではないと思う）

E. Bombs

　アルメリアさんの解説記事を読んでAC。
　問題を正しく把握するのも結構難しいけれど、把握したうえで、

・答えがある値kより大きいか？

　という判定問題にすれば良いと気付くのが難しい。ただ、これさえできれば後は結構自然か。
　クエリが進むごとに答えがだんだん小さくなっていくので、

・尺取り法（風）

　に計算量を抑えることができるのも、なるほど、という感じ。

　解説通り書いて提出したらPyPy3での初ACだったようですが、（非再帰遅延セグ木を持っていれば）計算時間にも余裕があるし、自慢にはなりませんね。