AGC038

2完。Bを通したあと37.1。いいAGCだったけど、結果として平凡な順位なのがね。まあ結果はいいか悪いか普通かなので、普通のときまで落ち込んでたらやってられんけど。

A - 01 Matrix

各行で少ないほうが0であるような個数をXとして、同様に各列についてY、方程式を作り様子をうかがう（W*Aとか出てきてWAは嫌だなあと思う（縁起が悪いとかじゃなくて単純に精神ダメージがあるから困る））。とりあえずNoのケースを持ってこようと思い少し試すが見つからない。サンプルを見るが、ない！これはあからさまに怪しい。ただ、そんな都合よく作れるかなあという感覚があり、Noが存在しないと決めつけはしない。10分くらいして順位表を見ると青の人もけっこう通している。少しして、何も考えず構成しにいったら作れた。これがAGCだ！最近のAGCのAは変化球が多かったので、いいストレートが来ても打てなかった。悔しいけど、仕方ないところでもある。さて、書いて出したらWAになった。AとBが逆。入力が「H W A B」なのに、Hに対応するのがBっていう。まあ、サンプル2の出力をちゃんと視界に捉えながら何も考えず提出したのが悪いけど。でも、問題も悪いと思う。

小さいほうって条件がまるっきりわかってなかったね。最大公約数とか考えてかなりうまい数になってないと無理って感覚だった。一見同じように見えて実は全然違う世界に放り込まれてる。気づけないにしても、同じだと確信できないなら疑いたい。

B - Sorting a Segment

ある区間が昇順かは累積和でわかる。K=1がなくてK=Nはあるのか。操作はN-K+1通りしかない。K=4で124356みたいなケースを考え、昇順にした結果が同じになるなと気づく。そうなる条件を探って、隣の区間と同じになる条件を考えることに思い至り、それは（長さK+1の区間の中で）先頭が最小値で末尾が最大値になることだ。とりあえずセグ木でそれを実装してサンプルを試してみるが、さすがにこれだけでは通らない。そもそも順列が変化しない操作があり、それが2個以上あったらそれだけ種類数は減る。最初に考えたようにそれは累積和で検出できる。改めて考えを整理する。N-K+1個の操作を隣と結果が同じものをつなげて区間とし、違う区間同士が同じであるケースについては、変化しない操作の数を区間の末尾だけカウントすればいい（全体を数えて各区間の長さ-1を引く）。元から昇順の区間は連続して現れるか被らず離れて現れる、1243576みたいに断絶したら再び123457が現れることはない、そういうところも一応全部詰めて大丈夫そうなので実装（雑ではあるんだけど）。けっこう複雑だったんで、一発ACは嬉しい。

C - LCMs

まあ100万なので1000までの素数168個を列挙して素因数分解したい。単純に行くと各A_iに注目して他のAたちとの和をO(N)かけずに何とか求める、その際に最大公約数で求めてもよさそう、みたいな。ただ、これ「和」なんだよね。掛け算した結果の和。積ならまだ希望がありそうだけど。だから他の方針を考えようとするが、わからない。和。これは無理だ。

D - Unique Path

3頂点を選んで0 0 0ならOKみたいな。全体をグラフにしちゃうのありそうだよね。しかし、1 1 0で多重辺はダメだから他の頂点を経由する必要があるし、とんでもなく複雑。これは時間内には無理だ。

ABC141

Eを通したあと37.1、終了後36.6。得意セットだったみたいで、5完早解きに成功。調子はよかった。Fがわからず。1時間以上やってて解けないの力のなさを感じて本当に嫌な気持ちになる。全完できてないのに「コンテスト時間がもっと長ければ」と思わないときはあまり楽しめてない。今回は、（100分じゃなくて）80分でよかったんじゃないのという感じ（80分までは楽しめてた）。

A - Weather Prediction

3回コピペする必要があるので面倒。今気づいたけど1回のコピペで「Sunny, Cloudy, Rainy」が得られるのか。コピペが済んだらループを書くだけ。

B - Tap Dance

「RUDのいずれかである」は「Lでない」と言い換えられる。if文を2つ書きかけたが、きれいに書けてよかった。

C - Attack Survival

面白そう。簡単そう。それはただの第一印象なので、具体的に解いていく。ポイントが増えることはなく、誰かが0になってもマイナスになっても全員がそうなっても最後までやる。Q回とわかっているので、全員のポイントからQを引いて、正解した人に1を足していけばいい。これもきれいに実装できた。

D - Powerful Discount Tickets

まず、「Y枚の割引券を使う」ことと「1枚の割引券をY回使う」ことが同じかどうかを知らないことに焦る。紙に2進法で適当な数を書いてみると、同じでありそうだとわかる（どっちも小数点の位置をYずらすだけ）。あとは大きいA_iから順に1枚ずつ適用していくだけ。優先度付きキューは最近使ったのですぐ思いついたが、ソートして何か上手くできないかも考える（こっちのが好みなので）（完全に解けてたわけではないので無駄な時間ではない）。しかし難しそうなので優先度付きキューで実装（今気づいたけどソートしてあっても割引したらバラバラになっちゃってまるっきりダメそう）。優先度付きキューなのに決まった回数だけ処理するのが珍しくて面白かった。これもきれいに実装できた。

E - Who Says a Pun?

問題を概ね理解して制約を見るとNは5000以下。2乗が通る。何かN通りあるものを固定して処理できる。最初の部分文字列の開始位置とか部分文字列の長さとか色々あるけど、第一感は「2つの部分文字列の開始位置の差」。他のも少し探ったけど、結局はこれで当たりだった（ローリングハッシュは一瞬考えたけど、どんなテストケースでも99.9%大丈夫と思えなければ使えないと思いすぐ後回しにした）。SとSをdずらしたものを重ねて文字が一致するところを光らせる。最大で何文字連続で光ってるかはO(N)でわかる。あとはdをO(N)通り試せばいい。被ったらダメなので最大でd文字までしか取れないことに注意する（ここがかなりややこしい（実装は簡単だが））。ここまで早解きに成功して黄パフォ。

F - Xor Sum 3

提出できなかった考察コメント。提出できない悲しさがあることを忘れていた。始まる前は、力を発揮できるか心配してるからね。発揮してこれだよっていう。碁盤（碁石を手で動かして考えるのが便利な問題たまにある）と向き合っていた時間が長かったので、もうちょっと頭の中だけで考える時間もあってよかったかなと、あとから思った。

//xorするより足したほうが得 0個にしてもいいとしてよい
//2つに分ける できるだけ立ってるビットが被らないようにしたいよねー
//あるビット位置に注目すると、全体が奇数個なら仕方ないとして、偶数個なら奇数と奇数に分けたい
//偶数個のときしか分け方影響しない 上位から正の偶数個のやつを見て決めていく
//奇数と奇数に分けることは確定 その奇数がいくつかわからないし、その位置のビットが立ってないやつも影響しない
//swapするなら、上位のビットが同じでその位置のビットが異なる同士 swapだけではダメなケースがある
//上位を見て実現できないことが判定できればいいが
//上位Kビットで達成できれば片方で立ってるのは合計K+偶数ビット
//N個のうちいくつかを使ってAll1にできるか こう書くと難しく感じるなあ

ABC140

終了後36.8。最近ABCは、過度な緊張をせずそれでいて始まったら体温が少し上がる程度に集中できて、いい感じだ。レーティングが低い状態なので、この結果でも微増。それはそうとtokuminiさんに追いつけないのは悔しい。コンテスト内容はわりと満足。Fを全然考えないまま残り10分になって完全に失敗したと思ったが、想定誤解っぽいのを提出することができた（Fをやらずに終わるのがすごく嫌だったが、最低限できた）。

A - Password

3乗。一瞬3^Nと迷う（Nが桁数という言語化できないレベルでの誤解かな）。

B - Buffet

めちゃんこ難しいB。最近簡単すぎたのでこのくらい難しいのを望んでいたけど、こういう系統の難しさは別に面白くないからなあ（単に苦手分野なだけでは？）。満足度Cを得る条件をAの入力時に処理したが、実装はすぐ浮かんだけどちゃんとした理解は本当に難しかった。

C - Maximal Value

そこそこ悩む、いい感じのC。問題文にはmaxと書いてあるのに実装にはminが出てくるのが面白い。最初、b[0]だけ特別扱いしてn-1回ループを回そうとしてた。n-2回なのね。解けるかどうかという意味では簡単なんだけど、解き進める中で「へーそれ知らなかった」というのがいくつか出てきてやりがいがあった。

D - Face Produces Unhappiness

難しそうに書いてあるけど典型じゃんと気づく（ややがっかり感ある）。こうなると、問題文から真面目に考えるのではなく、LとRの切り替わり回数だけが重要だとほぼ確信したうえでそれを証明する方向で考えることになる。ちゃんと証明できたわけではないが、まあよさそうなので提出。

E - Second Sum

1番目ならできるかなあとか考えつつ。最初に考えたのは、全体の1番と2番を取ってきてそれらを両方含む区間を処理して、あと1番だけを含むのと2番だけを含むのと1番と2番の間にあるのと場合分けする（そういえば1番も2番も含まず1番と2番の間にもない区間を見落としてたな）。しかし、複雑すぎてこの方針では解ける気がしない。ここでセグ木の匂いを感じ取る（昨日yukicoderでセグ木コンテストがあり、AtCoderではめったに使わないよねとツイートした）。でもBITで済むねｗ。Pを大きいほうから追加していく。すると、自分より大きいものが指定区間に何個あるかがO(logN)でわかる。方針は、各P_iが2番目になる区間の数をカウントするというもの。すぐ左の大きいやつを含むかすぐ右の大きいやつを含むかしかないのでいける。BITは二分探索できるけど、さすがに使い慣れないので普通に（10^5なのでO(Nlog^2N)も余裕）。左右両方を書かないといけないので（今思うと実装量増えても右だけにするって方法もあったな）かなりしんどい。両側について一番近い大きいやつの位置を求め、右側の大きいのをとるときは、左側が0個の範囲*右側が1個の範囲。右側が2個以上も含めてたり左側にそもそもないときの扱いとか無限にバグらせてINF時間が過ぎた。左側の二分探索ほんとに苦手。これ捨ててFに行くことも考えたけど、まあ今回は簡単な（）Eを手堅く取りに行く。色々な立ち回りができてるのいいね。最後にn * (n - 1) / 2を足すように最初してたけど、期せずしてちょっとした検算になった（0-indexedにすると1が0になって答えに寄与しなくなるのもなんか混乱して時間食った）。実装に1時間近くかかってる（つらい）。復習のしがいはある。

F - Many Slimes

Eの実装に注力する前に一応読んだ（読んで寝かせると時間を有効に使えそう）。ただちゃんと読めてなかった感がある（Eの早解きになる可能性もあるわけであまり時間かけたくなかった）。なんか「最初のスライム」と「生成されるスライム」の区別がわからなくて、「あなたは最初にスライムを生成します」みたいな話かと思ってた。スライムによって生成されるスライムのことね。

最初のスライムは（体力を変えないまま）最後まで残る。大きい順にソートしてよい。一番大きいやつが、最初のスライムなのは確定。その次も確定では？その次も小さいのを生成するメリットないよね？ということで貪欲を書いて提出、WA。なにげに5分くらいでこれ実装できててすごい。4分前のWAで実装ミスでもなさそうなので望みはうすい。でも、「この方針の穴はどこだろう」と悩むところまで短時間で行けたのはうれしい。Fに挑戦することもないまま終わるのかと思ってたから。これはちゃんと挑戦できている。短時間だけど、最低限よかった。

（追記）当時考えていたのは下のような例。

5
9 8 8 7 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1

貪欲にとっていくと3が多くて無理になる。これを、先に3を使うことで改善できないかと考えていた。しかし、小さい数をとるメリットはない。よってこの貪欲は正しいという結論になってしまった。さて、布団の中で次の例を思いついた。

3
9 8 8 8 3 3 3 2

8が多いからダメと判定するか？いや、9は8を何回でも生成できる！つまり、これも最初の例もYesだ。残った中で最大のものを常にとる必要はない。大きいのがあるのに小さいものをとるメリットはないが、とれる中で最大なら残った中で最大のものを後回しにできる。なぜ気づかない。まあそれは問題が絶妙に難しいからだが、なぜ証明できないのに納得してしまった。証明が苦手すぎる。ゴミのような感情に頼って問題を解いている。

ABC139

E以外簡単というイメージで解き進めていた。コンテスト中に顔が熱くてしんどいと思って体温測ったときは37.0だった。

A - Tenki

数えます。

B - Power Socket

電源タップを使うと差込口がA-1個増える。差込口をB-1個以上増やしたい。それはまあすぐわかって簡単なんだけど、見慣れない式になるから分子が負にならないか心配したりした。さすがに大丈夫だろうと思って提出したけどけっこう不安だった。

C - Lower

Cっぽい問題。高くなったらリセットでインクリメントしてくんだけど、初期値やインクリメントのタイミングが感覚でわからなかった。C問題として、こういう場所も残ってたんだなという感じ。

D - ModSum

いくら実装が軽いと言われるAtCoderでも限度があるでしょ。紙の上で少し試してこうしたら大きそうと思って、それより大きくならないことが示せたので提出。さすがにこのコード量を提出するのは勇気要った。

E - League

疲労感があるところへ体温が高くしんどい。しんどいから知ってる問題しか解きたくないという気分になり、EとFを読んでEをパスしてFへ行った。

Fを解いて戻ってきた。40分あればいけるやろ（いけなかった）。全部のカードに通し番号を付けてAの各行を合成することを考える。隣の行とは1個だけかぶってる。しかし、全体ではO(N^2)のかぶりが生じる、というかまさにそれが総当たりの全試合なわけで。うーん、グラフか？自信ないが、とりあえずトポロジカルソートしてみる。たまにしか使わないので理解もしてなくて時間がかかる。閉路があったら-1を出力するが、閉路検出もよくわからんので力づくでやる。うまく動かないが、x-yとy-xを同一視する（正規化する）処理を忘れていた（最初はわかってたのに）。グラフの頂点の一部しか使わないのでけっこう混乱する。さて、トポロジカルソートできたからってここからどうするか。時間もないので適当に。k日目から出てる辺の先はk+1日目以降でないといけない。何回か提出したかダメだった。ここはちゃんと考えてないので仕方ない。

F - Engines

双子の片方がwriterなのか？そうだとして、この位置に出してくる問題は面白いのが多そうだし、実際面白そう。えらく簡単そうに見える。とりあえず向きでソート。(0, 0)はスキップして、コーナーケースは先にやっておく。atan2の使い方をググる。まず、最大値を与える向きを固定したらそっち向きの成分を持つやつだけを足せばいいと思いつく。何を足すかは向きがちょっと変わっても変わらない。試すべき向きは高々N通りしかないので行けそう。ソートした隣同士の角の二等分を候補にするのが自然だが、同じ向きのエンジンがあったときやエンジンが1個や2個のときなどが自信ない。そのうち、単純にあるエンジンから180度未満まわるまでのやつを全部足せばいいと思いつき、実装、提出、WA。速度重視だったので、じっくり考察し直すが、考えるほど正しそうに思える。誤差かなあ。この制約で（向きが異なる）2エンジンのなす角の最小値ってどのくらいなんだろ。かなり小さそうだけど。さて、向きが正反対の同士は一緒に入りそうにないが、誤差で入ってしまうこともあるかと思い（希望を見出し）ちょっとマージン入れて提出、WA、しかもWAの個数が変わってない。いやあ、向きさえ決めたら、その向きへできるだけ伸ばすにはその向き側の180度ぶんを取るしかないはずなのになあ（例えば90度ずれた方向のを足すと長くなることもあるけど向きを決め打っているのでそれでいい（最大値をとる向きのときはそういうことは起こらない））。ここで思いつく。例えば、最大値をとる向きから左へ30度と右へ30度のエンジンの和で最大値をとるとする。このとき、右へ120度の向きのエンジンは使わないけど、左へ30度のやつから150度しか離れてない！180度ぶんとっちゃダメなんだ。そして、連続するやつを取るのは間違いないんだから全探索しちゃえばいい。O(N^3)だ。いや簡単すぎるだろ。なぜ思いつかない。ACしたのでEへ。