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へ。