2020年のまとめ

　2020年のレート遷移

・AtCoder　2030→2062（Highest　2030→2111）

・Codeforces　2155→2211（Highest　2232→2342）

・TopCoder SRM　1438→1423（Highest　1493→1721）

　SRMは一年前より下がっていた！

　AC数は3409問。

　一昨年、去年の大晦日のsolved数と比べると、

642→1952→3409

　で、去年解いた数が1310で、今年が1457。で大差なし。

　今年は結構頑張ったつもりなんだけど、そうでもなかった。結構難しい問題を解説ACしたと思ったんだけど、そういうのじゃAC数は増えないから、仕方ないのかな。

　特に今年前半は、このブログに書くため、今まで手を出さなかった問題まで手を出したつもりだったんだけど、途中から更新できなくなってしまったからね。来年はもっと簡略化（ほぼツイートそのまま、くらいでも）しても更新したい。

　レートはあまり上がっていないけれど、自分の気持ちとしては、青上位だったのが黄色下位まで来た、と思っている。上を狙えるところまで来たかな、と。

　特に得意分野も苦手分野もないつもりでずっといたんだけど、ABCやPASTの成績が同じくらいのレートの人に比べてやや落ちるので、苦手なのかなぁ、と思ってきた。青～黄色の人なら典型と感じるべき問題を典型と思えてないのかな、と思う。

　自分は、特に難しい問題を解くのが好きというわけではなく、どちらかというと簡単な問題をさくさく解くことに喜びを覚えるタイプなのに、典型問題に弱い（？）という成績になっているのはちょっと意外です。どうにかしたい。

　あと、最近、Python/PyPyで通せなそうな問題はKotlinを使おう、と決意しました。「型を書かなくてもいい」「;を書かなくていい」が大きい。この二つがないだけでストレスが大分違う！！

　典型問題攻略のためにも、ABCで苦戦した問題をKotlinで解きなおし……とかすれば良いかもしれないけど、データ構造の実装とかが面倒くさいんだよね……。今一つやる気が起きないけど、できたらやりたい。

　あとは、マラソン系（Codingameも）に手を出せたのは良かった。

　元々、アルゴリズムコンテストよりマラソン系（ハーフマラソンのような時間の短いものなら特に）の方が楽しいと感じていたので、そういうコンテストにはもっと積極的に参加したい。

Codingame「Fall Challenge 2020」

　Codingameの「Fall Challenge 2020」に参加しました。ルールはtsukammoさんのブログ記事が分かりやすいと思います。英語のルールを読むのは自分には結構大変で、この記事でルール概要を把握してから挑めたのはありがたかった。正直なところ、この記事がなかったら参加していたか怪しいです。

　結果は、全体513位/7011人、Gold League内で433位/464人でした。最終日にGold Leagueにはなんとか上がれたものの、そこで何もできず終わった感じですね。初参加にしてはまあまあ良かったとみるか、まだまだ頑張りが足りなかったとみるか。微妙なところですね。

　始めるとき、密かに目標していたのは、（あまり交流があるわけではないですが）ツイッター上で良く見かけるprd_xxxさん、AT274さんでした。prd_xxxさんは偶然（後述しますが、偶然としか言いようがない）上回れましたが、AT274さんはLegend League入りを達成され、ライバル視できるような状況には全くなりませんでした。それはちょっと悔しいです。

各リーグで書いたもの

・WOOD２

　BREWしかないので、貪欲にpriceから高いものから使っていきました。　→　一発クリア（11/13）

・WOOD1

　基本スペルが追加され、CASTできるようになりました。

　とりあえず、使えるアクションをランダムに選択したものを書く　→　ルピーを得られずダメそうなので提出せず。

　各成分の価値を1,3,4,5と決め、price/価値のもっとも高いものを作り、BREWするようにしました。　→　これを提出してクリア（11/14）

・BRONZE

　ここでルールが出揃います。

　各成分の価値を1,2,3,4と普通に戻しました。

　まず、LEARNする呪文の戦略として、得られるコストの差分からtaxを引いたものが3以下なら覚えるようにしました。

　その後、盤面に対する評価関数を（適当に）作成。次のターンで評価値が最も大きくなるような行動を取るようにしました　→　クリア（11/19）

・SILVER

　一手先しか読まないのはさすがにダメだろう、とは思っていたので、再帰を用いてDFSで全探索するものを実装します。しかし、BRONZEのとき+1手しか読めず（これでもときどきTLEした）、もう一手読もうとTLEしてしまいます……。

　困ったものの、評価関数を多少直して提出　→　SILVER内50位くらいまで上がる！

　さらに、ちょっとバグを修正して提出　→　順位が若干落ち、SILVER内103位。このとき、prd_xxxさんが102位で上下に並ぶ！

　しかし、時間が経つと順位が上がり、SILVER内15～20位前後に来る。ただ、対BOSSの勝率はあまりよくないため、GOLDに上がるのは厳しそう。

　そして最終日。あまり良い改善を思いつけていないまま、でもGOLDには行きたい、という気持ちで評価関数の調整や多少の高速化・バグ修正をしていると、朝7:30頃にGOLD昇格のお知らせが来た！

　提出していないのに、こんなことあるんですね。なんかこの頃、ボスと対戦させたら、（サーバーの具合で？）ボスがTLEして負けたりしていたので、そのせいかもしれません。

・GOLD

　GOLDに上がったコードはそのままGOLD250位あたりまで行ったが、その後だんだんと落ち、300位を割った。

　そのあたりで、修正していたコードを提出。明らかな改善はしていないものの、一応、前の提出には勝ち越しそうだった。　→　GOLD450位付近（最下位付近）でも勝ち越せず、順位が上がっていかない。

　このとき、余裕がなかったので、前の提出の簡易なバグだけ修正したものを投げたりするも、やはり400～450位程度。さらに、元の250位あたりまで上がった提出を再提出したりしたけど、400～450位程度。

　この辺り、混乱してしまいましたが、まあどれも実力はそう変わらないはずなので、最初のコードも、時間が経てばGOLD最下位付近まで落ちたのでは、と思っています。

　でも結局、GOLDに上がった提出と新たに作った提出の良いとこどりをしたつもりのものを作って、最終提出しました。

やったこと

　基本は、評価関数を決めて貪欲。一手先を全探索して評価値を調べているけど、評価値を調べるときもう一回探索しているので、実質二手後を見ていました。

　評価関数は、

・素材の価値は30, 55, 70, 85（BRONZEの頃とは変えています）、スコアは200点。種類数ボーナス有。

・一つの素材が多くなり過ぎても意味がなさそうなので、個数で補正。

・序盤LEARNしやすく、後半LEARNを減らすため、CASTのlengthで補正。

・CASTの中身を評価。製造前と製造後の価値の差、repeatableか、製造前素材の価値が少ないほど評価（作りやすいので）、製造後の個数が少ないほど評価（作りやすいので）

・BREWしにくい組み合わせになってハマるのを避けるため、「今の素材から初期呪文でどれかBREWできるようにできるか？　大体、何ターンでいけるか？」で補正。

　あたりを考えて実装しました。

良かったこと

　普段競技プログラミングの問題を解くばかりで、こういう、ある程度長いコードを書いた経験がなかったので、それが書けたのは良かったです。

　普段はIDLE（Pythonデフォルトのエディタ）を使っているのですが、今回はVSCodeを使いました。色々とありがたかったです。特に、「定義した関数のところに飛べる」というのは有難いですね。

　IDLEは軽くて、電卓代わりに使うにはとても良いと思っているのですが、まともにプログラムをしようと思ったらエディタもちゃんと考えなければいけないですね。勉強になりました。

反省点

　コンテスト終了時に思っていたのは、

・どうやれば良いかはよく分からないものの、パラメータ調整のためにローカルで動かす環境を作らなくてはいけなかった

　というのが一番でした。

　しかし、他の方のブログやValGrowthさんの反省会を見て、ちょっと印象が変わりました。

　一番反省すべきは、ゲームの本質が分かっていなかったことかもしれない。BREWした後に素材を残し、repeatableな呪文を使って連鎖的に素材を作っていく……というのをあまり重要視していなかった。素材がなくなってもBREWした方が良いと思っていた。この辺りが分かっていれば（もしくは、検索などで調べていれば）評価関数をちょっと変えられたかもしれない。

　あと、高速化をもっとすべきでした。

　本当に高速化したいならC++など他言語への移植を考えるべきだけれど、Pythonのままでも高速化できるところはあった。どうせPythonのままだと限界があるので……という甘えがあった気がします。

　DFSのとき、全部のデータを送ってましたが、idだけにすれば速くなるはず、というのは気付いていたのに実装しなかった。

　単純なDFSじゃなく、枝狩りを入れる（これをビームサーチって呼ぶんですね）ことは考えましたが、上手くいかなそうと思ってしませんでした。これは、その時点の評価値だけだと、BREWのしやすさが分からず、枝狩りしてしまう可能性があると思ったためです。

　しかし、他の方の記事を見ると、今回はビームサーチが正解だったようです。

　連鎖させることの重要性が分かっていれば、BREWした後の素材の組み合わせが大事なので、評価値で枝狩りすることは有用だと思えたはず。そうしたらもっと深くまで探索するため、高速化を追及できたかもしれない。

　このあたり。技術力がなかったせいではなく、考えが浅かったため上手くいかなかったというのは悔しいですね。

　次回もし参加できたら、もっと良い順位を取りたいです。

Hokkaido University Programming Contest 2019 Day 2 D: Two Colors Sort

　問題はこちら。 

　積み残していたこの問題をACしました。

　解説pdfの通り、蟻本で「個数制限付き部分和問題」と紹介されている問題に帰着できるのですが、bitsetによる高速化ができることもあり、計算量解析が話題になりました。（参考：noshi91さんの記事）

　……が、今試してみたところ、特に工夫せず、Pythonのbit演算で普通にDPすれば間に合いました！　Pythonで2秒程度なので、十分速いですね。

　今は、Kiriさんのこんな記事もあり、自分も（単純なものなら）0と1のみのDPテーブルを一つの数を代用する方法に慣れてきたと思いますが、当時は分かってなかったんですね。

グラフの直径と半径

　九月からブログ再開すると言っていたのに、いつのまにか10月になってしまった。なんでもいいから書こう。（とはいえ、こんなので良いのかな……）

東京大学プログラミングコンテスト2013　C - 直径

　を解いたが、最初、WAを出してしまった。

　まず、答えを書く（解説pdf通りです）と、

・グラフの直径：出来上がるグラフ上で最も遠い２点間の距離

・グラフの中心： もっとも遠い頂点への距離がもっとも小さい頂点

・グラフの半径：グラフの中心から最も遠い頂点への距離

　としたとき、

・最大値：直径の和+1

・最小値：半径の和+1もしくは、元の直径のうち大きい方

　となる。

　そこまでは分かったのだけど、自分は、半径＝（直径+1）/2（切り捨て）と勘違いした（これは木なら成り立つはず）ためWAを出してしまった。変な先入観を持つのは避けなければ。

　次のようなグラフを考えれば、これは成り立ちませんね。

　このグラフだと直径＝2、半径＝2となる模様。

九月

　八月はこのブログをサボってしまった（その間に、AtCoderでは青に落ちてしまった……）のですが、九月になったしぼちぼち復活させていくつもりです。

　今までのように、「復習が終わったら記事を書く」としていると、どんどん書くコンテストが溜まってしまうので、すぐに書けるものはすぐに書くなど、ちょっと変えていきたい。

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だったようですが、（非再帰遅延セグ木を持っていれば）計算時間にも余裕があるし、自慢にはなりませんね。

Codeforces Round #628 (Div. 2)

　Dまでの四完でした。
　コンテスト中は、EやFはあまり考えずに寝てしまった……。

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

E. Ehab's REAL Number Theory Problem

　解説AC。

　約数が7個以下ということで、

・素因数は高々二つ。

　に気付くのが重要。また、

・$x^2$を因数に持つとき、$A/x^2$を考えても同じなので、平方数を約数に持つならそれで割っておく。

　というのにも自力で気付けた。

　ここでグラフを考えるのはまあ自然だと思う。

　各A[i]を頂点とし、たとえば、6=2*3と、22=2*11のように、同じ素因数を持つもの同士に辺を繋ぐ。そして、最小のサイクルを検出すれば良い。

　……という方針は自分で思いついたのだけど、それだと難しいと思う。これでも上手くやれば解けるかもしれないが、サイクル検出を効率よくやるのが難しい。

　公式解説では、素数を頂点にし、6があれば2と3に辺を結ぶ。7があれば1と7を結ぶ……というにグラフを構成している。これでも同じく、最小サイクル検出問題に帰着できる。

　さて、最小サイクル検出は普通にやると、頂点数の二乗くらい（この問題では、辺の数も頂点数*2くらいで抑えられるので）の計算量がかかってしまう（と、公式解説にはあった。確かに各頂点ごとにBFSすればそれくらいでできるけど……もっと良い方法はないの？）。が、ここで、$A[i]\leq 10^6$に着目。$10^3$上以上の二つの頂点が結ばれることはないため、サイクルの端点は$10^3$以下として良いので、それらからBFSすれば良い。

　これをふまえると、計算量が大きく減らせる。

　これでACできるのだけど、実際はその後の実装にも苦戦してしまった。途中で座標圧縮したりしたらTLEが取れたけど、もっと良い実装があるはず。

F. Ehab's Last Theorem

　解説AC。

　ついでに、最近出た類題もAC。この類題の方が簡単なので、これを先にやってから取り組んだのは良かった。

　公式解説には、DFS木を使うものと、次数を考えるものの二通りが載っており、前者はじゅぴろさんの日本語の解説もあります。

　ただ、私は後半の、サイクルがなかったときの独立集合の取り方がよく分かってません……。

　なので、後者の方法でやりました。

　次数が少ない順（heapqで管理）に点を取ってきて、独立集合に付け加えていきます。

　ある点を使ったら、その点の近傍の点は使えず、さらにそこから繋がっている点の次数を一つ減らす……というようにやっていく。

　ここで、最小の次数が$k-1（k = \lceil \sqrt{n}\  \rceil $とする）以上になったら方針転換、k以上のサイクルを検出する方針に切り替えます。

　なぜなら、残りの点の次数が全てk-1以上なら、必ずk以上の頂点のサイクルを含むからです。ちゃんとした証明ではないけれど、その理由を以下に書きます。

　k頂点のサイクルを含まない時、一番次数を増やせるのは、k-1頂点の完全クラフです。なのでk-1頂点の完全クラフを考えると、各頂点の次数はk-2なので、各頂点からもう一個辺が出ていないといけません。そこから出る点と点が結びつけば、k以上のサイクルになるのでOK。

　そうじゃないとすると、またk-1頂点の完全グラフに結び付かなくてはいけない。だが、他の頂点からはやはりもう一個辺が出ていないといけないので……と、以下その繰り返しになるため、k以上のサイクルが存在しないとダメですね。

　で。

　サイクルの検出はDFSでOK。

　DFSで使っていない頂点をたどっていった配列$a_1, a_2,...,a_n$をしたとき、その一番最後の頂点$a_n$と繋がっているような最も最初の頂点を$a_i$として、$a_i, a_{i+1}, ... , a_n$の個数がk以上になります。

　どの頂点の次数もk-1以上という強い条件なのでこれが成り立つはず。（成り立つはずだけど、証明はよく分かっていないかも……）

　

パナソニックプログラミングコンテスト2020

　ABC形式の企業コンテスト。Dまでの四完と、成績は今一つでしたが、writerのりんごさんらしさが出た印象に残る問題でした。

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

B - Bishop

　H=1やW=1がコーナーケースの問題。TopCoderっぽい問題な気がします。

C - Sqrt Inequality

　誤差に気を付けましょう、という教育的な問題。幾何の問題だと、誤差に気を付けるのが重要かつ本質になることが結構あります。そういうとき対応できるように、普段から気を付けておかねば。

D - String Equivalence

　DFSで列挙する。最近のABCで何度か出題されていますね。

　私は、「再帰を使って列挙する」のは、結構難しいと思っています。

　DPで遷移を考えるのと本質的には同じかもしれませんが、大抵のDPでは、部分を切り取って考えれば良いのに対して、再帰では全体の構造を頭に入れておかないと混乱しやすい、というような。

　（あくまで印象です。本質的にはこの二つは同じはず）

E - Three Substrings

　貪欲したくなる気持ちを抑えて全探索する問題。

　コンテスト中も、全探索をしなくちゃいけないはず、とは気付いたのですが、実装に困って解けませんでした。

公式解説に書いてある方法をやるだけなのですが、意外と実装に苦労する問題ではないかと。

F - Fractal Shortest Path

　一応コンテスト後に自力でACしたけど、かなり時間がかかって大変だった……。

　

　「避けなければならないブロックは高々一つ」ということに気付けたら、後は二点の間にブロックがあるかどうかを大きい方から調べていく、という感じで解けるけど、この方針が立っても、実際に実装するのはかなり大変だと思う。

　AGCっぽい問題に見えるので、なんでABCで出題したんだろう？　というのはちょっと不思議。確かに、発想すべき点は「避けなければならないブロックは高々一つ」くらいなので、発想より実装よりの問題、ということなのかな……。

FII Code 2020 Round #3

　Bまでの二完でした。A, Bの後Dを考えていて、実装終わらずに終了。とはいえ、仕方ない面もある。

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

（このブログの記事は、主に、当時の自分のツイートを参考にして書いています。なら、そのツイートも載せておいた方が良いのでは？　と思ったので、今後はできるだけ載せます）

Confused Robot

　これを飛ばしてDにいった。

　Sをひとまとめに見て、「それぞれの地点から、S一回分進むとどこへいくか？」を考えてダブリングするのが自然。

　が、これだとPython/PyPyで間に合うのか分からず（制限時間が長めなのも不安材料）飛ばした……んじゃないかと思う。あまり記憶にないけど。

　二個ほど他の人の提出を見たけど、大体そういう方針で解いているようだった。

　公式解説には、ダブリングを使わず、「S一回進んでも動かなくなる回数」を前計算すれば良いと書いてある気がする。けど、これって最大N*M回かかるのでは？　よく分かりません……。

　O(N*M*S)でいけるなら実装してみようと思ったけど、よく分からないので実装してません。

　ダブリング解でもPyPyでちゃんと書けばACできそう……？

追記）ダブリングなしで「S一回進んでも動かなくなる回数」は求められることに気付きました。グリッドの各マスについて、「S一回でどのマスにいくか」を調べておけば、

・S一回後に自分自身に戻るマスは0回（以後Sを実行しても動かなくなる）
・S一回後に0へ行くマスが1回

　という風にして、DFS/BFSで求められますね。

　ただ、それを求めても、「S一回進んでも動かなくなるギリギリの回数」は最大N*M回あると思うので、O(N*M*S)では無理な気が……。（やっぱりダブリングが必要では？）

Double Palindromes

　コンテスト中ずっと考えていて、コンテスト後実装が終了したので提出したらTLEでした。

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

　その上で、アルメリアさんが解説している方法が使えます（この解説の例題の中に、この問題があります）。いや、この記事は勉強になりますね……。こういう観点で問題を見たことがありませんでした。

　これを読むと、コンテスト中に考えていたセグ木を使う方法は本質的には間違っていなかったようですが、BITを使うことで高速化できそうです。

　というわけで、もしかするとアルメリアさんの方法を使えばTLEにならないのでは？　と思い実装してみたのですが、いつの間にか、CS AcademyではPyPy/Python3が使えなくなってました！（え？）

　「Non zero exit code = 127」というエラーが返ってきてどうしようもありません。

　Python3だとTLEなのは仕方ないですし……。まあ、しょうがないですね。

　勉強になったので良かったと思っておきます。

Codeforces Round #627 (Div. 3)

　時間ギリギリでFまで解き終ったのだが、BをHackされてしまった……。

コンテストへのリンク

A. Yet Another Tetris Problem

　「縦に二個」のブロックしかおけないので、mod 2で全要素が揃っていることが条件。

B. Yet Another Palindrome Problem

　四文字以上の回文があれば、その部分列で三文字のものを得られるので、三文字の回文を見つければ良い。

　三文字の回文は、「A B A」という形をしている（A=Bでも良い）ので、隣同士でない位置に、同じ数字があるか判定すればOK。

　Hackされたのは、実装方法がおかしくて（隣同士に文字があったとき消去するような実装をしていた）、同じ文字が三文字続いたときにダメという判定を返していたためでした。

C. Frog Jumps

　連続する「L」の個数の最大値+1。DP まとめコンテストのせいで、Frogという単語をみるとDPかと身構えてしまうけど、この問題ではDPは不要でした。

D. Pair of Topics

　式変形すると、$a_i-b_i>a_j-b_j$となるので、$a_i-b_i$をソートしてbisectを使って求める。

E. Sleeping Schedule

　結構読解に苦労した覚えがある。

　DP[h]を、時刻hに寝たときの「良い睡眠回数」の最大値とし、これを更新していく。

F. Maximum White Subtree

　全方位木DP（rerooting）を使う問題。このときも、かなり時間がかかってしまった……。

　いまだに全方位木DPには慣れないし、ライブラリ化もできていないけど、どうしようかね。色々な記事をパラパラと読んではいるのだけど、今一つピンと来ていないんだよね。

Educational Codeforces Round 83 (Rated for Div. 2)

　Eが解けなかった上、CがHackされて悲惨な出来。

コンテストへのリンク

B. Bogosort

　大きい順（降順）にソートすればOK。

・まず極端な場合を考えてみる

　という意味でもソート状態を考えてみるのが良い。

　また、立式して考えるのも良い。

　$A_i-i=A_j=j$でi<jのとき、必ず$A_i<A_j$なので、そうならないようにする、という方針でも思いつけると思う。

C. Adding Powers

　$k\geq 2$のとき、$k^n$は$k^1, k^2, ... , k^{n-1}$の和より大きい、ということを利用する問題。

　これが成り立つので、kのベキ達の和である数を作るためには、できるだけ大きいベキを使わなくてはいけない。

D. Count the Arrays

・Combi(m, n-1) : m個の数から、互いに異なるn-1個を選ぶ。（一組の数字が一致しているので、互いに異なるのはn-1個）

・n-2 : 一致する数を選ぶ。増加列と減少列の間には最大の数が来るしかないので、それを除いたn-2個から選ぶ。

・$2^{n-3} : 最大値と、一致する数を除いた残りn-3個の数を増加列か、減少列かのいずれかに割り振る。

　これで題意の配列が定まるので、この積が答え。

E. Array Shrinking

　コンテスト中に区間DPだと思いつつも解けなかった。

　DP[i][j]で、区間[i, j]が一つの数字に縮約できたときの値、とすれば良い。

　この定義は今見ると自然に見えるけど、確かに、「縮約したときの最小の長さ」をDPの値に持ちたいと思ってしまうと、ハマってしまうか……。

　そのDPテーブルを利用して、長さの最小値も求められる。（あるいは、けんちょんさんの記事のように、同時に求めることもできる）

　また、かっつさんの記事にありますが、もっと計算量は速くなるらしいです。

F. Attack on Red Kingdom

　一応、自力AC。最近Grundy数を復習したのを覚えていたから解けただけで、コンテスト時に解くことは無理だったと思う。

　こういうタイプのゲームはGrundy数を考えるしかない。

　x, y, zが小さいので、それぞれについてGrundy数を前計算しておく。

　問題は、$a_i$が大きいことだけど……。

　まあ、Grundy数はどこからか周期的になっているはずで、大きくても2520（1~10の最大公約数）周期にはなっているだろう、と思い、$a_i\geq 5400$のとき、$a_i =a_i$ %2520+2520$としたらACした。

　公式解説を見たら、周期もちゃんと調べてますね。

G. Autocompletion

　アルメリアさんの解説記事、けんちょんさんの解説記事があったので解説ACしました。アルメリアさんの記事はかなり詳しく書いてあり、ありがたかった。

　Trie木について理解していなかったこともあって、問題文の読解から苦労してしまったのですが、やること自体はそこまで難しくないですね。

　ただ、「ある点から子孫の点へワープするときのコストの減少幅」がどの子孫へ行くときも一定というのは、意外な気がしてしまいました。これが直感的に正しいと思えれば解くのは難しくなさそう。

　Trie木の勉強にもなったので良かったです。これを機に、Trie木を使う問題を一つくらい解くべきかなぁ……。

日立製作所 社会システム事業部 プログラミングコンテスト2020

　Cが解けなかった上、Aで1ペナ出してしまい、レートを大きく下げてしまった……。それでも黄色に留まれたのは失敗に優しいと言われるAtCoderのレートシステムのおかげ。

コンテストへのリンク

C - ThREE

　コンテスト中、「木が二部グラフである」ことを利用することはすぐに思いついた。両方の色がN/3より大きいときの考察は上手くできていた。

　だが、片方の色がN/3より小さいときの方法を思いつかなかった。余り1か余り2のものを少ない方へ割り振らなくてはいけない気がして、少ない方に3の倍数を割り振る発想が起きなかった。

　そのせいで、もっと細かい連結成分をみたりしなくてはいけないのでは？　と迷走。

　割り振るべきものは、「3の倍数、余り1、余り2」の三種類、色は二種類ある、ということを落ち着いて見直すべきだった。

D - Manga Market

　解説AC。

・ソートしてDP

・（待ち時間が）指数的に増加することに気付くと計算量を減らせる

　の二つを組み合わせた問題。

　どちらもそれほど発想し難いものではないけど、落ち着かないと厳しそう。

　特に前者については、

・とりあえず立式

　が重要。

E - Odd Sum Rectangles

　解説AC。

　公式解説動画を見ても、どうすればこの構築を思いつくのかが分からなかった。

　けど、正当性を証明することはできるので、こういう構築方法があると頭に入れておくのが良いのかな。

F - Preserve Diameter

　解説AC。解説を読んでからACするまで一週間以上かかっている気がするんですが、さすがに非効率過ぎない……？

　公式解説動画を（何度か）見れば、どういう計算をすれば良いかは理解できると思う。この問題は、発想するのは難しいけれど、解説を理解するのはそれほどではない、という印象。
　あとは確かに木DPをするだけなのだけど、その実装が難しくて戸惑った。

　解説pdfやkmjpさんの解説記事に書いてある通りなんだけど、それでも難しいと思う。

　自分の実装はこんな感じです。

・まず、木の中心を見つける。(cとする。今回は中心が一点のときを書く)

・cからDFSする。親や、cからの距離を求めておく。直径をDとする。

・葉から木DPを行う。

　DP[x][p][m]($0\leqq p\leqq 2,0\leqq m\leqq 2$)を、頂点x（の部分木）まで見て、cからの距離が+D/2の葉がp個、cからの距離が-D/2の葉がm個のものの場合の数、とする。

　ただし、p=2, m=2は+D/2の葉が2個以上、-D/2の葉が2個以上、の意味。

　なので、最初に葉を見るとき、cからの距離がD/2か、そうでないかで初期状態を変える。あとは、一つ親のノードへ移るとき、この3*3の行列の遷移がどうなるかを考えれば良い。

（遷移もかなり難しいけど、辺に「+1, 0, -1」を割り振るとどうなるか？　と、子が二つ以上あるときどうなるか？　をちゃんと考えれば分かった）

TopCoder Single Round Match 780

 Easyが通ってレートは微増。

Div1 Easy BeatTheStar

点数が1点もらえる試合～N点もらえる試合が一試合ずつあり、二人のうちどちらかにその得点が入る。G点の試合が勝負の分かれ目になる（つまり、その試合を勝てたら合計得点でも勝ち、負ければ合計得点でも負け）確率は？　という問題。

　余事象を考えると、G点の試合以外で、片方の点数が合計何点以下ならそういう状況にならないか、が分かる。なので、片方の点数がそれ以下になる場合をDPで求め、$2^{N-1}$で割って、1から引く。
　
　Python内fastestだったようなので、自分のコードはここで見ることができます。

Div1 Medium Prominence

コンテスト中は問題内容を把握できていなかった。kmjpさんのブログ記事で問題内容を把握しました。

　内容を把握できれば解法を理解するのはそんなに難しくないですね。

　kmjpさんの解法では前半パートにsetを使っていますが、公式解説を読むと平衡二分木は必要ない模様。左右から山を見ていけばできるのですね。
　後半パートもセグメント木ではなくSparse Tableを使えばO(N)になるのかな。（Pythonでは実行時間が厳しそうだし、実装はサボります。とはいえ、一応O(N)なので、上手く書けば通ってもおかしくはないですか）

AtCoder Beginner Contest 158

　時間ギリギリで全完。

コンテストへのリンク

D - String Formation

一々文字列を反転させていたら時間がかかってしまうので、反転は最後にまとめて行い、文字列追加の際、反転の回数が偶数なら後ろに、奇数なら前に追加する。
　先頭への文字の追加は、Pythonならcollections.dequeを使う。

E - Divisible Substring

　各桁に注目して、たとえば1234という四桁の数字を

4+3*10+2*10^2+1*10^3

　に分けて考える、というのはよくあるテクニック。

　この要領で、1桁目～各桁までの値をPに関する剰余で分類し、それが一致している範囲を求める。

　ただし、P=2や5のときに気を付けなくてはいけないことに注意。これらは10と互いに素でないので、この方法では上手くいかないため、例外処理しなくてはいけない。

　コンテスト中はこれに気付かずWAを出した後、全探索のコードを書いて比較することで気付けた。

　結構気付きにくいようにも思うので、上手くリカバーできて良かった。

F - Removing Robots

　とりあえずソート。

　すると、「そのロボットを起動させたとき、どのロボットまで連動して起動するか」が分かればDPで答えを求められそう、と分かる。

　なので、それをセグメント木を用いて求めていく。

Codeforces Round #626 (Div. 1, based on Moscow Open Olympiad in Informatics)

　A, Cの二完でレートが上がった。Div. 1回でレートが上がるのは嬉しい。

コンテストへのリンク

A. Unusual Competitions

　カッコ列に関する問題。結局、")"と"("の個数が同じときは、")"のとき-1、"("のとき+1としたときの累積和が負になっている部分の長さを足せば良いのだけど、これが最小かはちょっと悩むところな気がする。

B. Present

　AtCoderのTwo Sequencesとほぼ同じ問題だった。

　この問題は、PyPyだと制限時間が厳しいため苦労して解いたことをよく覚えている……のだけど、コンテスト中は全く思い出せなかったし、復習時も解法を思い出せなかった（AtCoderの公式解説を読み返せば分かったが）。うーん……。

・xor→桁ごとに考える

　というのは良いとして、その後が難しい。

　「和を取ったとき、ビットが立っている個数」を各桁について求めれば良いのだが、繰り上がりがあるので、その桁だけ見ているのでは分からない。「その桁以下の桁」を見て実際に和を取らなくてはいけない。

　そうすると、結局O($n^2$)かかってしまいそうなのだが、実は、二分探索を使って求めることができる。

　たとえば、四桁目を考えたとき、0000～1111までの二つの和は、0000～11110の範囲に収まるので、四桁目が1になるのは、1000～1111か、11000～11111の二つの範囲になる。

　和がその二つの範囲に入るindexを二分探索で求めれば良い。なお、PyPyだとそれではTLEになる（と思う）が、二分探索ではなく尺取りを使えば間に合う。

C. Instant Noodles

　問題設定は複雑だけど、内容を正しく把握すると、ユークリッドの互除法が分かっていますか？　という問題になる。

　なお、コンテスト中は、Counter[tuple()]という書き方をしたらTLEしたので、Counter[hash(tuple())]という風に書いてACしたのだけど、普通に、dict[tuple()]という書き方でACできた模様。

　中に入れるものによっては、Counter()とdict()で時間に差がつくのですね。気を付けよう。

D. Reality Show

　公式解説を読んでAC。

　検索しても日本語での解説が出てこなかったので、さらっと解説を書きます。

（問題概要。制約は書いていませんが、二乗が通りそうな制約です）

　n人の人が順に並んでおり、それぞれにA[i]（aggressiveness）と、C[i]（cost）という整数が与えられている。index順にその人々を選ぶか、選ばないかを選択する。ただし、選ぶ場合は、A[i]の値が、今まで選んだ人の最小値より小さくなくてはならない。

　各人を選んだ時に、コストと利益が発生する。コストはC[i]、利益はaggressivenessの値によって決まり、aの人を選んだ時、P[a]である。（Pは負の値も取る）

　ただし、aggressiveness aの人が二人以上いた場合、そのうちの二人は戦い、残った一人のaggressivenessがa+1になる。この際、さらに利益がP[a+1]加算される。

　利益 - コストを最大にするような選び方をしたときの利益 - コストの値を求める。

（解説と雑感）

　公式解説でもある通り、まず、

・同じaggressivenessの人達を選んだなら、どのような順番に選んだとしても利益は同じになる

　ことに気付くのがポイント。

　設定が複雑なため分かりにくいけど、これは当たり前。
　人が二人で戦う、というイメージではなく、値aのスライム二匹合成されると、a+1のスライムになる、というイメージで捉えると納得しやすいと思う。
（今後、人ではなくスライムと書くことにします）

　このとき、indexを後ろから（aggressivenessの小さい方から）見ようと考えるのはまあ自然。そうすると、aggressiveness aのものを選んだら、今後a未満のものを考えなくてよくなる。

　ただ、こう考えても、今までのスライムたちがどう合成され、どんなaggressivenessのスライムが残っているか、を一々考えていては大変。

　だが、順番を変えても同じならば、一々合成させずとも、そのaggressivenessのスライムの個数さえ分かっていれば良い、と気付くのがもう一つのポイント。

　つまり、

・DP[k][cnt] = Aのmaxがkで, そういうスライムがcnt匹いるときの利益 - costの最大値

　としておいて、この値が更新されたときに、そのスライムを合成させたときを考えて、DP[k+1][cnt/2]などの値を更新していけば良い。（※）

　計算時間ですが、今見ているスライムのaggressivenessがaのとき、a+1の部分の更新ヶ所は1/2、次の箇所は1/4……なので、（更新順番を工夫すれば？）大体二乗になるようです。

　ただ、（※）を毎回行った自分の提出でもACできてしまいました。三乗でTLEになるだろうと思って投げたのですが。
　更新箇所がそれほど多くないので、三乗（のはず）の書き方をしても通ることが多いのかも？

　Div. 1のDということで身構えてしまうけど、解説を読むと意外と素直な問題でした。とはいえ、自力ACできるか、と言われると厳しそう。そもそも、コンテスト中にDを読みにいこうとはなかなか思えないですが……。

第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を二進数に直すのがポイント。

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

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++で書ける力を身に着けなきゃいけないのだろうけど。

第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の類題といっていいと思う。

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

　いやぁ、難しい。

　

yukicoder contest 235

　遅解きの五完でした。五問目でC++を使ったのが遅くなった原因ですね……。慣れない言語を使うと、そんなに上手くいかなくても達成感があります。良いのか悪いか。

コンテストへのリンク

No.975 ミスターマックスバリュ

　MaxValuは知っていたけど、ミスターマックスは聞いたことなかった。そんな店があるんですね。

No.976 2 の 128 乗と M

　Pythonだとpow(2,128,M)と書けるので楽。

　多倍長を扱える（し、128乗ならたいして大きくない）ので、$2^{128}$を実際に計算することもできます。

No.977 アリス仕掛けの摩天楼

　全体が連結な場合、Bobが必勝なことは分かったけど、それ以外の条件を探すのに苦労した。まあ、こういう問題は試行錯誤するしかなさそう。

No.978 Fibonacci Convolution Easy

　数列aの値を求めておき、累積和をとりつつ和を求めていく。

No.979 Longest Divisor Sequence

　DP[a]で、最後にaを使ったときの、Divisor Sequenceの最長の長さ、として、iを一つずつ更新していった。毎回約数列挙が必要になるけど、各$A_i$の値が小さいので、$O(N*\sqrt{A_i})$で収まる。

　Aが小さいのでこの方針でやりましたが、解説のようにDP[index]とした方が普通だったかも……。

　なお、コンテスト中はPyPyで通すことができず、C++を使って通しました。

　が、予め、エラトステネスの篩の要領で$3*10^5$までの約数を列挙を列挙しておくとPyPyで通せた模様。勉強になりました。

No.980 Fibonacci Convolution Hard

　主にけんちょんさんのブログの記事を参考に解説AC。kmjpさんの記事やmaspyさんの解説も参考になりました。

　形式的ベキ級数や母関数を理解したとは言い難いですが、少し使い方が分かったのは良かった。勉強になりました。

Educational Codeforces Round 81 (Rated for Div. 2)

　Dまでの四完。
　それほど失敗した気はしなかったのに、順位はイマイチでした。

コンテストへのリンク

A. Display The Number

　各数字を点灯させるのに何本の電灯が必要かを考えると、1の二本と7の三本が少ない電灯で済むことが分かる。

　基本的には1を使い、最後に1余るようなら、一番上の桁を7にする。

B. Infinite Prefixes

　s一回書き終ると、（1の個数）-（0の個数）が何個変化するかを計算。

　また、その間に、0を基準として、（1の個数）-（0の個数）がどのように変化するかを計算。

　たとえば、s="1101"なら一回ごとに（1の個数）-（0の個数）は+2し、

　0→+1→+2→+1→+2

　のように変化するので、

0: 一回

+1: 二回

+2: 一回

　の値を取る。……というようなことを利用して計算した。

　xの値になりうるのは何回繰り返したときかを計算し、そのそれぞれの回で、何回ずつxを取るかを探索して和を取った。

　ただ、ながたかなさんのブログのように、sの文字のindexに着目する方が賢かったようです。変化が±0のとき以外は、各indexのときにxになることは一回しかありえない。

　なるほど確かにそうですね。

C. Obtain The String

　けんちょんさんの、「部分文字列を走査する DP」の記事のDPを使って解く問題。特に、

・next[i][c]:= S の i 文字目以降で最初に文字 c が登場する index

　を求めておくのが本質だと思います。

　なお、AtCoder Beginner Contest 138　E - Strings of Impurityとほぼ同じ問題でした。コンテスト中は全く思い出せなかった……。

D. Same GCDs

　a以上a+m-1以下のxで、gcd(x, m)=gcd(a, m)となるようなxの個数を求めれば良いので、gcd(a,m)を素因数分解し、約数包除を用いて計算した。

　ただ、ユークリッドの互除法を考えれば、gcd(m+i, m)=gcd(i, m)なのだから、0～m-1の範囲で数えればOKだったようです。

　さらに、mをGCD(a, m)で割れば、x=m/GCD(a, m)としたとき、xと互いに素なx以下の自然数の個数ということになり、これはオイラーのφ関数として知られているものなようです。

E. Permutation Separation

　ARMERIAさんのブログの記事やけんちょんさんのブログの記事を見て通した。コンテスト直後のTwitterで、「そんなに難しくない」という意見も見たけど、個人的には難問だと思っています。

　まず、

・最初にどう分けるか

・最終状態がどうなってるか

　を考えるのは自然。

　ただ、さらに、コストの計算もするとなると、O($n^3$)かかってしまいそう。

　三乗オーダーだと、高速化したとしてもACできる計算量にはなりそうもない……コンテスト中はそう考えて、何か天才的な方法があるんじゃないか……と迷走してしまった。が、実際は上記の方法を高速化すればO(nlogn)まで落ちる。

　その高速化も簡単ではない。私は上記の解説ブログを読んでもなかなか理解できず、初期状態と最終状態を変化させた場合のコストを表にしてみてようやく理解することができた。

　まあ、「高速化できるはず」という気持ちになれば、差分を取ってみるのは自然だし、思いつけない内容ではないと思うけれど……。

　無理そうに見えても、

・高速化できないか試す

　ことが大事か。

　なお、PyPyで通すには制限時間も結構厳しく、手持ちの遅延Segment treeでは通らなかったため、Starry Sky tree（？）を使って通しました。

　なお、ながたかなさんのブログ記事によると、そういったデータ構造を使わずとも通せるようですが……私は理解できていません。

F. Good Contest

　ARMERIAさんのブログの記事やけんちょんさんのブログの記事を参考に解説ACした。

　Eより解法は思いつきやすいと思う。

　DPしよう、という方針が見えれば座標圧縮は自然。

　ただ、DPの遷移は難しい。

　同じ区間を使い続ける場合の処理を一度に行う……という方法に気付けなければいけない。ただ、このDPは、キーエンス プログラミング コンテスト 2020　F - Monochromizationとかなり似ています。（この問題の応用がMonochromizationと思って良さそう）

　逆に言えば、こういう、順次更新していくだけではなく、（部分的に）一度に遷移させるDPというのは、典型の一つなのかもしれない。頭に入れておきたい。

AtCoder Beginner Contest 153

　約三十分で全完。
　かなり簡単な回だったのでたいして順位は良くなかったけれど、これくらいで全完できれば自分としては満足。

コンテストへのリンク

A - Serval vs Monster

　H/Aの小数点以下繰り上げ。

　Pythonなら、-(-H//A)と書くのが簡単。

B - Common Raccoon vs Monster

　Hとsum(A)を比較

C - Fennec vs Monster

　大きい順にsortし、K番目以降の和

D - Caracal vs Monster

　まず、「何回分裂するか」が分かれば攻撃の回数は分かるということが重要。たとえば、二回分裂した後、三回目の攻撃で消滅するなら、答えは、1+2+4回です。

　その上で、たとえば、H=12のときのHPの変化を考えると、

・12→6→3→1→0

　これは、H=4のときの、

・8→4→2→1→0

　と同じ。

　なので、$2^k\leqq x\leqq 2^{k+1}$の範囲にあるxは同じ挙動をすることが分かります。

E - Crested Ibis vs Monster

　あるHPの敵を倒すのに必要な魔力、でDPすれば解けます。

　「効率の良い魔法を使うのが良いのでは？」などと考えたくなりますが、DPすれば全部の場合を調べられます。

F - Silver Fox vs Monster

　左から貪欲でOK。

　一番左の敵を倒す際にできるだけ他の敵も巻き込みたいので、一番左の敵の位置+Dの位置で爆弾を使う。

　そのとき、一番左～一番左+2*Dまでの敵のHPを(一番左の敵/A)の繰り上げだけ減らします。二分探索により一番左+2*D番目の敵の位置を求め、遅延Segment treeを用いて区間のHPを減少させました。

　データ構造を使わない方法もありますが、思いついた方法で解けば良いよね。

TopCoder Single Round Match 776

　今年はじめてEasyがACできた！　と思ったらシステムテストで落ちて0完。単純なミスだったのでもったいない。

Div1 Easy EncloseArea

　斜めに線を引いて、指定された面積の多角形を作る問題。

　最小の正方形の面積は2で、その一辺を削って、隣に膨らませれば面積は+2される。

　なので、まず50*50の方眼紙の対角線上に斜めに長い長方形を作り、それを一つずつ膨らませる実装をした。一々、辺を増やして減らして……としているためかなり汚い実装になってしまった。

　そして、一番最初、面積2から始めてそこから求める面積まで増やしていく……というように書いてしまったため、面積2のときそのまま出力するのを忘れてしまってシステムテスト落ち。

・最小値・最大値で通るかチェック

　はきちんとしなくてはいけませんね。

　kmjpさんのブログの記事のように頂点に着目すればもっと簡単に実装できます。

　コンテスト中のコードを修正したものなので非常に読みにくいのですが、一応ACしたコードを載せておきます（載せるか迷ったのですが、ACした証拠として）。

class EncloseArea():
    def enclose(self, A):
        if A%2!=0:
            return tuple()
        if A>2402:
            return tuple()

        ANS=[["."]*50 for i in range(50)]

        ANS[0][0]="/"
        ANS[0][1]="\\"
        ANS[1][0]="\\"
        ANS[1][1]="/"
        S=2

        for i in range(1,49):
            if S==A:
                break
            
            ANS[i][i]="."
            ANS[i+1][i+1]="/"
            ANS[i][i+1]=ANS[i+1][i]="\\"
            S+=2

        if S==A:
            A=[]

            for ans in ANS:
                A.append("".join(ans))

            return tuple(A)

        NOWP=[0,1]
        NOWM=[1,0]

        def rewrite1(x,y):
            if ANS[x-1][y]==".":
                ANS[x-1][y]="/"
            else:
                ANS[x-1][y]="."

            ANS[x][y]="."
            ANS[x-1][y+1]="\\"
            ANS[x][y+1]="/"

        def rewrite2(x,y):
            if ANS[x][y-1]==".":
                ANS[x][y-1]="/"
            else:
                ANS[x][y-1]="."

            ANS[x][y]="."
            ANS[x+1][y-1]="\\"
            ANS[x+1][y]="/"
            
        while True:
            x,y=NOWP
            if 0<=x-1<50 and 0<=y+1<50:
                rewrite1(x,y)
                S+=2
            NOWP[0]+=1
            NOWP[1]+=1

            if NOWP[0]==49 or NOWP[1]==49:
                MIN=min(NOWP)
                NOWP[0]-=MIN
                NOWP[1]-=MIN
                NOWP[1]+=2

            if S==A:
                break
                

            x,y=NOWM
            if 0<=x+1<50 and 0<=y-1<50:
                rewrite2(x,y)
                S+=2
            NOWM[0]+=1
            NOWM[1]+=1

            if NOWM[0]==49 or NOWM[1]==49:
                MIN=min(NOWM)
                NOWM[0]-=MIN
                NOWM[1]-=MIN
                NOWM[0]+=2

            if S==A:
                break

        if S==A:
            A=[]

            for ans in ANS:
                A.append("".join(ans))

            return tuple(A)

Div1 Medium StringRings

　kmjpさんのブログの記事を参考にして通した。

　両端赤、両端緑、両端が異なる、のそれぞれのひもの個数をr, g, bとおき、実際に本数を求めてみよう、と式を書いてみたら、自然と再帰的に書け（多分、C++なら再帰のままでもACできる？）、それを整理したらさらに簡単な式になった。

・とりあえず立式

　さえしていればそれほど難しくなかった気がする。

　コンテスト本番では、Easyに時間を取られてしまったので解けなかったけど、ACしたい問題でしたね～。

　以下、ACしたコード。

class StringRings():
    def expectedRings(self, A, B):
        ANS=0
        for i in range(A):
            ANS+=1.0/(2*i+1)

        for i in range(B):
            ANS+=1.0/(A*2+i+1)

        return ANS

Codeforces Round #615 (Div. 3)

　なんとか全完できました。

コンテストへのリンク

A. Collecting Coins

まず、三人の最大値までコインを割り振る。（割り振れなければNO）
　その後、3で割った余りが0ならばYES、そうでなければNO。

B. Collecting Packages

　ソートした順番でしか回収できない。移動も辞書順なので、右に行ってから上、と進み方一意に定まる。

C. Product of Three Numbers

　（1を除く）約数を列挙。その中で最も小さいものを使うのが最善。これをaとする。

　次にbを、列挙した中から全探索する。a, bを定めたときn/(a*b)が正の整数になり、1, a, bと重ならなければOK。

D. MEX maximizing

　mod xで考えたとき、各要素が何個ずつあるかを管理しておきます。mexを大きくするためには、それらを小さい順に並べれば良いです。

　要素の個数の最小値をMINとすると、0～xのうちMINを始めて取るindexが分かれば答えも分かります。

　たとえば、Exampleの最後のクエリ、a=[0,1,2,2,0,0,10] のときを考えると、

0: 3個

1: 2個

2: 2個

　なので、MIN=2、はじめてMINを取るindexは1です。

　mexは、余り0～2を二周した後、もう一歩だけ進むことができるので、3*2+1のように求められます。

　よって、この二つの値を高速で求めれば良いのですが、コンテスト中は区間加算・区間最小を求めることができるSegment treeと二分探索を用いて処理しました。

　このようなSegment treeを使えば、全体の最小値は求めることができます。あとは、[0,i]における最小値がMINになる最小のindex iが分かれば良いですが、これは二分探索で求められます。

　なお、この問題はSegment treeを使わずとも解くことができます。mexが減ることはないし、高々qまでしか増えないので、「mod xで考えたとき、各要素が何個ずつあるか」という情報を持ってシミュレーションすればOKです。実装も楽だし、計算時間もこの方が速いですね。

E. Obtain a Permutation

　各列について、その数字がローテーションの結果一致するなら、何回ローテーションしたときか、を調べる。それを使ってローテーション回数を全探索する。

F. Three Paths on a Tree

　直径＋1点を全探索。その残りの一点と直径との距離を調べるところでLCAを使ってしまいましたが、DFSすればOKでした……。

　コンテスト後、直径で良いことの正当性がツイッター上で話題になっていたけど、一応コンテスト中に示したつもり。

　ただ、直径が二つ以上あるときがコンテスト中は良く分からなかった。
　そういう場合、中心Vに対して、V-a, V-b, V-cの距離が等しくなる三点a, b, cが存在するので、それらを取ればOKなのですね。（ながたかなさんのブログの記事を読んで気付きました）

　なので、適当な直径を一つ選んできて良いですね。