ABC151

なんとか全完。Dではまってもう俺はダメなのかと思ったが、lowestは更新せずに済んだ。さすがに精神状態がよくないなあ。

A - Next Alphabet

予想はできていたけどcout << c + 1 << endl;ではダメ（足し算した時点でintになって、代入とかもないのでcharに戻らない）。charにキャストして提出したが、提出後、c++;しとけばいいと気づいた。今、cout << ++c << endl;でいいと気づいた。いい問題だな。

B - Achieve the Goal

Bで既に問題文が読めない。いやさすがに読める。合計点をN*M以上にしたいという話。K点取ってもダメなときは-1を出力。K点超え（スキーのジャンプを連想してた）だけでなく0点未満もないことに気づかずサンプルで引っかかる。直して提出すればさすがにACなんだけど、自分できっちり考えたいところだった。

C - Welcome to AtCoder

こっち系のCかあ。複雑で怖いし時間がかかる。AC後にACしてもペナルティ付かないのは知ってたが、AC後のWAもそうなのは明示的には知らなかった。WAの回数を各問題で持っておいて、ACしたらビットマスクをかけて区別する。自分がこれを早解きするのは無理なので仕方ない。

D - Maze Master

最大で20*20なので（N=max(H, W)として）O(N^4)で行けそう。グリッド上のBFSのライブラリを取ってくる（使い慣れないので不安だが、まさに使い慣れないことによるミスが出た）。スタートとゴールを全探索すればいいが、スタートからBFSすれば全部のゴールについて最短距離がわかる（ここで最短距離がO(N^2)になることに気づく（あんま関係ないけど））。で、WAになった。壁の中からスタートしてるやん！ということで直して提出してもWA。これは声が出た。少し考えて正しいコードにしか思えないのでEへ。

EFを解いて戻ってきた。時間がないのでBFSを改めて書き直すのはきつい。頑張って考えると、スタートも未訪問マスも0としていた。スタートへ引き返す動きができてしまう！ライブラリの元コードを読んだときの違和感はこれか。未訪問は-1、それ以外は最短距離として区別していたんだ。直してAC。ここで全完できたのは大きい（Dを通せてなかったらlowestを更新して精神がもっとまずいことになってた）。

E - Max-Min Sums

最大と最小の差。ということは、Aをソートして選ぶ区間を固定すればよさそう。幅Wの区間なら、端は選ぶとしてW-2個からK-2個を選ぶということになる（区間同士で重複はない）。これだとO(N^2)なのでもう少し考えるが、なかなか難しそう。ということで、両端ではなく片方だけでいいのではないかということに思い至る。これは天才。最大値の寄与と最小値の寄与は別々に計算できるのだ。Aを昇順ソートして、最大値としてありえるのはA[K-1]からA[N-1]まで（0-indexed）。端を除いてi個からK-1個を選んでA[i]を掛ければいい。最小値も同様だが、Aをstd::reverseすればなんと全く同じコードでいい（こういうのに気づいた瞬間が楽しいよね）。最大値のから最小値のを引けば答え。

F - Enclose All

最終的に、どれか3点の外接円になっているはず。ということでN点から3点選ぶのを全通り試して外接円の半径の最大が答えだと考える。しかし、サンプルを見てN=2のケースもあると気づく。これは例外処理して、しかしサンプル3は通らない。なるほど、ある3点について外接円がそれらを含む最小の円だとは限らないのか（一つの角が180度近いと外接円がクソでかくなる）（今気づいたが答えがどれか3点の外接円になってないケース普通にあるな）。その3点を含む最小の円は、その三角形の最も長い辺を直径とするものだ。さて、3点を含む最小の円が外接円になるかどうかはどう判定する？辺の長さが直径になるときその辺の向かい側にある角は90度なので、90度を超えるかでいいか。それも、一つでも90度を超える角があったらダメだ。ここで、3点を順番も区別して全探索する方針に切り替える。3点が一直線上にある場合によりバグりやすくするため。バグが隠蔽されるコードは怖い。できればサンプルでバグってくれと。あとは書いていく。サンプルにも助けられて一発AC。

外接円の半径の求め方はググった。ここは「ごめんあとで勉強するから今時間ないから」と言って公式を信用した。こういうのあまり好きじゃないけど、コンテスト中は本当に時間がないので仕方ない（まともに考えてたら1時間くらい吹っ飛ぶ）（もちろんこの問題で使えるくらいの理解は必要）。角度は内積で求めるのが普通だと思ったけど、余裕がないので思考停止atan2した。

この解法の正当性を考える（解いてる当時はちゃんと考えてるつもりだったがやや怪しかった）。最小の円が3点以上と接しているなら、その3点の外接円になっている。ここで、90度を超える角がない3点を選べる保証はあるか？いやなんもわかってなかったな。確かに、選べなかったら円をより小さくできそうだし小さくできないようにばらしたら選べそうだしな。でも証明できない。じゃあ、最小の円が、90度を超える角がない3点と接している場合で考えればいいか。そのときは、そういう3点の外接円は探索されるし、より大きい外接円を作る3点も存在しない（存在したら、その3点を含む最小の円が全体を含む最小の円より大きくなってしまう）。また、この最小の円の直径を超える辺がないのは明らか（全部の点を含む円なので）。ということで、この場合は正しく求まる。そうでない場合は、いや眠くなってきたので略（ダメ）。

第6回 ドワンゴからの挑戦状 予選

1完。コンテストとしてはまあ楽しかったが、ratedコンテストとしてはつまらなかった。お前は対象外だよと言われているようでかなしい。

A - Falling Asleep

今日は問題文がすぐに表示されて快適。

ABCのBみたいな問題だ。Xが最後に与えられるのがいやらしい。難易度のわりに時間をかけた気もするが、ちゃんと問題文を読むためには必要な時間。

B - Fusing Slimes

色々考えてみたが何もできなかった。N=4とかを手で実験しても法則が見えない。かなり不自然な設定に見える（本当に不自然だと言いたいわけではなく、そのくらいわかってないということ）。計算量無視で1小さい問題に帰着させても一番左を動かすときだけ挙動が違うじゃん。合体することで減らせるコストとか、ある区間を何体のスライムが通るかとか考えたけど、まとめて計算できる気がしない。バラバラだ。

C問題と交互に考えていた。全くできる気がしないうえに考えづらく、最後のほうはずっとCをやっていた。

C - Cookie Distribution

何が独立で何が独立でないか。まあ一人の子供がもらうクッキーの数、0からKまでの確率は求まるよね（K*2^K）。でも合計はΣaで一定なので子供同士は独立じゃない。もう全部バラバラに20^1000通りの掛け算の期待値を、と思ったけど1日目からi個選ばれる確率とかは計算できても、1日目が選ばれる個数を固定しちゃったら他の日と独立じゃないんだよなあ。

ABC150

5完。普通に問題の不備でunrated。かなしい。CDFあたり面白かったのでそれはよかったけど。最初問題が表示されなかったのは金曜開催によるものというのがまた（面白いと言ってはあれだが）。

A - 500 Yen Coins

自分の場合は、2分くらいで問題を見ることができて、最初の提出は失敗した。

k * 500 >= x。いい感じの難易度。

B - Count ABC

これも好き。全探索ではあるけど探索範囲でちょっと悩ませてくれる（自分は0で埋めた長い配列用意してN回調べた）。

C - Count Order

O(N!*N)が通るのでそのまま書く。B問題で使ったのでまたmemcmpしたが、比較しやすいよう入力をcharで受け取ったのが原因ではまった。入力を数値として受け取ってほしいのに文字で受け取ってる（charなのでそれはそう）。このミスは経験がある（繰り返すのほんとかなしいね）。next_permutationでN!回のループを回し、何回目で一致したかを返す関数を作って引き算する。

D - Semi Common Multiple

「公倍数を理解していますか？」と言われているようで困ったなあと思いながら色々試す。a_iの半分の1倍, 3倍, 5倍...が使える。奇数と偶数の「半公倍数」を考えてみると、奇数のほうを偶数倍しないとダメなことがわかる。もう少し考えると、因数として持ってる2の個数が違ったらダメそうだと気づく。そうでないとき、a_i/2たちの公倍数が最小の「半公倍数」。公倍数を求めていって、オーバーフローしないようにMを超えたら0を出力して終了する。（最小公倍数をrとして）最後、単にm / rを出力してサンプルが合わなかったが、奇数倍だけなので(m + r) / (r * 2)だった（この演算は32bit整数の範囲でできる）。

E - Change a Little Bit

Sは全部0として最後に2^Nを掛ければよさそうだし、f(S, S)=0と定義してもよさそうだし。ひねりの部分は拍子抜けするくらい楽。さて、Dはだんだん減っていくので、貪欲に小さいC_iから使っていくのがいい。Cをソートして、2^(N-1)回現れる各C_iの寄与を足していけばいい。例えば自分より大きいものが3個あったら、自分も含めて残り4個の状態で操作するのでD=4となる。4番目に大きいC_iから見ると、Tがどんな列かによって自分より大きいのが0個だったり1個だったり2個だったり3個だったりする。これは二項分布で対称なので期待値は1.5個。0.5の倍数を扱うために2倍してn - 1 - i + 2（2倍するタイミングがずれてサンプル合わないなーやってた）。最後に2^(N+(N-1)-1)を掛けて終わり。

F - Xor Shift

kはN通り、xはkが決まれば決まる。つまり、O(N^2)でよければ簡単。高速化を考える。全体にxorをかけても変わらないものとは？入力例3を2進法で書いてみるとぼんやりと法則が見える。周期のようなものがある？周期を全探索できたりする？この辺、計算量をしっかり計算していかないと感覚が利かない。そもそも周期があるものだけでいいのかというのはあるが、aとbに同じ周期があることがわかったとして位置合わせをどう高速にやるかというところ。「意外と愚直が通るのか？」「いや無理やろ」ほんと計算量が難しい。約数の個数とかその逆数の和とか。

年末恒例、アニメBEST3

「1位のキャラはこれ、2位のキャラはこれ」みたいな形式が時代に合わなくなってきたことを感じている（BEST3の候補が少なく、好きな要素が細かく分かれていたりする）。とはいえ当面（1年とか）この形式をやめるつもりはないし、そういった歪みが表現されることにも意義があると思う。

そもそも記憶力がゴミなので好きなものでも思い出すのに苦労する（あるいは思い出せずに終わる）。今年は、春クールに「川柳少女」しか見てなかったけど他の時期はけっこうたくさん見てた。ぷよぷよもやり続けながら、アニメの時間を侵食するほどではなくなった。アニメとは気楽な付き合いをしている気がする。もう時代に追い越されて久しい。新しいものを観察するのは楽しい。

作品

1. 私に天使が舞い降りた！
2. まちカドまぞく
3. （該当なし）

完全にこの2強。かなり悩んだが、好きな作品や優れた作品はあれど3位に入るような飛び抜けて好きなものは見つからなかった。

説明不要と思うことこそ説明せよ（よりもいの日向に影響を受けた名言（？））。ということで書くか。わたてんは当時すごい回数見てた。最近あったニコ生一挙放送でも見たし。いや説明できないな。まちカドまぞくは「まドまド」って略したくなる。作品名とかの（連続するとは限らない）部分列でないような略称がマイブーム。いやもうまさかの桜井弘明。俺以外にも受ける桜井がまだあったんだね。シャミ子と桃の関係が途中曖昧なまま描き進められるのが好き（わかる人にはミエミエなんだろうけど自分はなかなかわからんので）。「すっぱいミカンにご用心」とかこういうのがサブタイトルに出てくるの最近ないよね。果物の桃の黄色い（白い）部分の色が桃の頭や服に使われてるのかわいくて好き。

サブタイトル

1. 私に天使が舞い降りた！ #8（アバン）
2. かぐや様は告らせたい #8（かぐや様は呼ばせたい）
3. えんどろ～！ #11（ファイナルデッドエンド～！）

わたてん8話は服を買いに行かされる話だが、その冒頭シーン（OP前）が共感しかない。子供っぽくふくれるみやこも「自分のために生きなさい」と言うお母さんも「ねー」のひなたも。家を出て、ひなたが一緒に来てくれるのは嬉しかったなあ。

かぐやが白銀の妹と会う。そこからの妄想が素晴らしく踏み込んだ描写。自分がその立場だったら間違いなくそう妄想するというものを描いてくれている。藤原さんに対する態度もすごく共感する。

えんどろ11話は「そっちが思い出すんかいｗ」という伝説のシーンを有する。なんか今回3つとも一部のシーンがよかったという形だよね。形式が合わない。1話全体がよかったという意味ではまあこの中だとえんどろかな。

キャラ

1. みゃー姉（私に天使が舞い降りた！）
2. ヤマイ（女子高生の無駄づかい）
3. 桂木眞己（星合の空）

これは憧れの人だよ（松本目線）。

ヤマイはなんか腕のラインとかがぷにっとしててかわいい。声も見た目もかっこいい。中二病のレベルが高い（学業や人間関係で動揺しても世界観を保っている）（この美のいまりちゃんを思い出す）。いやかっこよくてかわいいの最高か。

眞己はかわいくてハイスペック。女装するのは、かわいいのがわかっているので作り手のあざとさを感じたが。EDで柊真より上にクレジットされてるの長らく気づかなかった。

次点は「川柳少女」のタオ。3位は候補が多くてかなり迷った。

歌

1. プリパラ OP1-1 Make it!
2. ソウナンですか？ ED
3. まちカドまぞく OP

「Make it! ドキドキするとき無敵でしょ」この韻を踏む気持ちよさ！この部分はアニメも気持ちいい。こんなにいいOPがあったなんて。（2014年のアニメだけど一挙放送で今年知ったので）

「生きる」いい曲。あまり繊細な感じのするアニメではなかったけど、EDによさが凝縮されている。

まちカドまぞくは、OPを初めて聴いたときに「これはただことじゃない」と思った。OPアニメのおわり、左右に花の赤と青が配置されているのがとてもよい。

声優

1. 河野ひより
2. 木野日菜
3. 小原好美

河野ひよりは、同クールのぴりからこちゃん・小野寺和紗・鈴森明日香で声の幅を見せつけられた。高音成分が気持ちいい。なんとデスマ（去年）のポチもそうだった。

木野日菜はわたてんで松本の妹。たまに見る名前だが、かわいい脇役をやってることが多くてかわいい。いつもかわいいので安心感がある。

小原好美、ククリのイメージから藤原書記で一気に広くなった。そしてシャミ子という完璧な着地で今年を終える。