【バチャ】CODE-FESTIVAL-2016-QUALB

4完。時間をオーバーしたものの自力で全問通せたのは嬉しい。やっぱこのころ（というか現行のレーティング制度が始まってからの2年間くらい）の問題面白いよな。

A - Signboard

コピペした"CODEFESTIVAL2016"と1文字ずつ比較。

B - Qualification simulator

これは珍しくリアルタイムで参加したほうが有利な問題だ。海外の学生も予選を通過できる。問題文の通りにやるだけだが、条件が見た目より多い分量でかなり大変だった。

C - Gr-idian MST

家と家の間の道路ってさあ、家と家を結ぶ線分に垂直なものを想像しちゃうじゃん。まあ問題文やサンプルをよく読むと気づく。問題名の通り最小全域木の問題だ。小さい例を作りクラスカル法で図を描いてみる。盾に並んだ横線は全部同じコストだからまとめてやってしまっていい。縦と横に分けて、反対側でやった回数ぶん（連結になっていたら線を引かないので）線を引く回数が減るっぽいことに気づく。証明はできないが色々試してそれっぽいので実装に入る。実装は軽いけど、書く前は全貌が想像できなかった。そういう実装は勉強になってる気がして好き。

D - Greedy customers

ストーリーがつかみにくい。要するに、棒がN本並んでて水平に弾を発射して当たったらその場所より下が消滅して落ちる、弾の位置は整数のみで棒を消滅させてはいけない、みたいな状況。できるだけ多く弾を当てたいので、低い場所に当てたい。手前から順に当てていくことを考えると、それよりいい方法は存在しないように思える。証明はわからないけど。そうだと仮定して実装する。最初の棒は1ずつ削って高さ1にできる。次の棒が高さ2以下だと何もできない。3以上のときは2ずつ削っていけるし、最後の1発（次どこを撃っても高さ2以下になるとき）で上から1の位置を撃てば高さ1にできる（低いほうがのちの選択肢が増えて得）。境界をきっちりするのが大変だが、自分より左の棒の現在の最大の高さ+2を残して何回撃てるか割り算で求めて次の1回で高さ1にすればいい。

なんとなくで問題をACしていくの、AtCoderを始めて半年とかの自分がそうだったと思う。証明を心がけたり、未証明でやっていることを自覚したりが、そのころと比べればできるようになった。この点では本当にAtCoderをやっていてよかったと思う。

（解説を見て）『そしてこの連結操作は、「これ以降 x 座標 i と i + 1 を同一視する」という操作です』なるほどなあ。何か超頂点を持って連結を管理とかはちょっと思ったけど、そういう捉え方。ちょっと抽象的になると自分が持ってない概念になって、そうなると「図を見てなんとなく」を言語化できない。

E - Lexicographical disorder

1100点だけど1時間以上残ってるので解けないまでも自分のやれるところまでやる時間としては十分。どの文字が大きいかが毎回変わるのはきつい。しかし、トライ木を思いついた。全部の枝を見て現在の文字より小さいものの個数を足していけば何番目かわかる。経路上に他の文字列がある場合がややこしいが、枝に進んだあとそこで終わる文字列があれば1を足すようにすればいい。提出してTLE。

まだ30分以上あるのでデバッグの時間としては十分。同じ文字列に対して大量のクエリが来ることもありえるので、当然のTLEだった。そこで、クエリを先読みして同じ文字列に対するクエリをまとめて処理する。書き始めて気づくが、トライ木を辿るときにそのまとめた個数ぶんの時間を毎回かけることはできない。ただ、文字の順番は26!通りもある。まとめて処理はできないように思える。文字と文字の比較は26^2通りしかないのでそこでどうにかならないか。あるいは、注目する文字を固定しその文字の枝の寄与だけを計算するとか。上手く行きそうに思ってやっぱ全然ダメを繰り返す。時間がないので変数名がごっちゃごちゃになった（これは反省点）。最後に、寄与を26^2通りに分けて計算しておくことを思いつく。26^2が掛かるのがQに対してで済んでいるので、計算量もそんなに重くならない。経路上の文字列の個数は共通。文字の順番を表す各pに対して、c0がc1より小さいならこれを足すという値が求まる。

しかしサンプルの実行で落ちる。落ちるはずがないのに落ちていて最後の数分間頑張ったが原因がわからなかった。そもそも落ちないはずのTLEコードを貼っても落ちたので、原因はトライ木の処理ではなかった。まとめて処理するときに、ソートして同じ区間を求めるやつってやっぱり複雑で、最初に-1番目の文字列に対して処理をしていた。落ちないはずなら別の場所を見る発想がほしかったね。

（解説を見て）ちょっと待って。26^2の大小関係の情報があればそれを使ってソートして元の順列が求まるがそれは26!通りあるってどういうこと。（しばらく考えて）2^(26^2)通りじゃん。それはダブってる情報もあるから26!より大きい。いや間抜けに見えるかもしれないけどこういうかつて考えたことがあるような分野でもこの勘違いがパッと正せない。難しい（けど決して届かないわけじゃない）問題でめちゃくちゃ時間がかかるのはそういうところなんだよな。高々26^2個のブール値で順列の情報を表せるということがわかってなかった（26*log(26)個くらいあればいい）。

【バチャ】CODE-FESTIVAL-2016-QUALA

コンテストがない週末なので、バーチャルコンテストをやった。AtCoder ProblemsのAGC-Likeのところに、現行のレーティング制度が始まってから自分がAtCoderを始めるまでの半年くらいの間にあった面白そうなコンテストがごっそり残っていることに最近気づいたのでそれを。内容的にAGC-Likeではないだろと思ったけど、CまでもDもかなり面白かった。Eは読んだだけ。

A - CODEFESTIVAL 2016

どういういきさつか忘れたけどこれは最近やってあった。1文字ずつ受け取って1文字ずつ出力、4文字出力したところでスペースを出力すればいい。

B - 仲良しうさぎ / Friendly Rabbits

複数の仲良しペアに所属することはありえない（自分が好きなのは1匹だけなので）。仲良しペアに所属するうさぎを数えて2で割ればいい。あるうさぎが仲良しペアに所属するかは、好きな相手が自分を好きか見ればいい。

C - 次のアルファベット / Next Letter

Kが大きいので注意しておく。貪欲に前から小さくしていけばいい。よく考えると、aに到達できないなら操作を行う意味がない。ということで、aにできるならして、できないならスルー、最後の文字になったら残った操作回数ぶんやる。

当時は深く考えてなかったけど、aにするにも26回余計に操作する手などがあって、しかし26の倍数回だけ余っても最後の文字での結果は変わらないので、やはり最小回数でaにするのが他の文字のに操作の選択肢を増やして得だ。

ここまで気持ちよく早解きできている。

D - マス目と整数 / Grid and Integers

10分強で簡単な3問を解いたら、残り2問がかなり難しそうで、残り時間の過ごし方が心配になってくる。しかし実際には、わりとすぐに、2時間を短く感じるくらい色々考えることが出てきた。

手で例を作って観察すると、どうも隣り合う行同士は、行全体に同じ数を足したら隣の行になる、みたいな関係になっているっぽい（今式変形してみると隣の行との差が隣の列と同じになってた（バチャ中にもそのうちやろうと思って忘れてた））。つまり、どの行同士、列同士もそういう関係になっているということだ。これをベースに考えていく。

「この行はこの行より3大きい」みたいな情報がたくさん与えられるので整理してくださいという部分問題を考える。UnionFindで親との差を管理しながらやるのをしばらくやっていたが、頭がこんがらがる。トイレに行って、グラフでいいじゃんと気づく。書かれている整数を行毎（列毎）に分けて、同じ行にあるものをつなげる。全部つなげると2乗になってしまうので、隣同士だけつなぐ（列同士の差を管理するにはそれで足りる）。相対的な大きさを行毎に決めていく。DFSで値を決めていきながら、全ての辺について矛盾がないか調べる（矛盾したらNoを出力）。この処理が、定義に沿ってL字に並んだ3つの整数から残りを埋める作業と比較しわりと違うような気がしてやや混乱する。

行同士（列同士）を入れ替えても答えに影響しないから、関係を持った行と列たちを左上に集めて考える。すると、他の塊は上下左右に存在しない（斜め下に連なる感じになりそう）。そこでそれぞれ条件を満たせた場合、他のマスも条件を満たすように書けるか？何も関係ないマスは大きい数を入れておけば問題なさそう。左と下に塊がある場合が怖いが、あれ、どう納得したか忘れた（コピーすればいいと思ってた気がするけどそれでは不安が残るような）。

塊をatcoder::dsuで求める。行と列（合計R+C個）を、高橋君が書いた整数でつなげていく。その中の連結成分で、いくつかの行があってそれに対応する相対的な大きさの最小値を求め、列に対しても求め、そこに含まれる高橋君が書いた整数が存在するのでそれとの差を見て負の数が現れないか確認する。全ての塊についてOKならYes。結局、Yesのときのマス目全体は、100マス計算みたいになっている。負の数が現れないなら、その100マス計算の元になる相対的な大きさの値も全部非負にできる。これをそのまま使えば（現れなかった行や列は0とすれば）、全てのマスが0以上になるように構成もできる。

各ステップはそこまで難しくないはずだけど、いざやろうとすると意味不明に混乱したりする。普段認識できていない自分の理解の足りなさを見せてくれる感じで、よい。

年末恒例、アニメBEST3

2021年1月開始アニメのことを思い出すのはきつい。具体的には、順位を付けようとすると解像度がめちゃくちゃ低い。

作品

1. のんのんびより のんすとっぷ
2. ラブライブ！スーパースター!!
3. 小林さんちのメイドラゴンS

あんまり3期のアニメとか入れたくないんだけど、のんのんびよりは仕方ないね。自分の好きなアニメを選ぶのだけど、面白さだけでなく波長が合うものを選ぶようにした。

初めてのラブライブ。なんか最初はキャラデザが好みじゃなかったらしいけど、それを意外に思うくらいには慣れている。

このクオリティのメイドラをいきなり出してくる。OPもしっかり新しくなってる。「Come on!」のところからの、広い場所に「抜けた」感覚が気持ちいい。

サブタイトル

1. 無職転生 ～異世界行ったら本気だす～ #20（妹侍女の生まれた日）
2. スーパーカブ #1（初回）
3. 小林さんちのメイドラゴン #13（1期最終回）

無職転生はずっとクオリティ高かったけど、その中でもアニメとして正統派の強さで圧倒してくれた回。

スーパーカブの初回は説明不要でしょ。説明不要という言葉を使ったら説明しないといけないしばりがあるんだよな。いやでも難しいよ。今はスーパーカブ以後なので、スーパーカブという言葉でスーパーカブ1話が説明できてしまう。説明が必要というからには、スーパーカブ以前の世界でも通じるような表現が求められるはず。まあ無料なので見てください → https://www.nicovideo.jp/watch/so38571104

「1期の」最終回。2期が始まった辺りで途中まで見てて、2期が終わってからてきとうに最後まで見た。この回あまりにもよくてびっくりしちゃった。シリアスな中にも思わず笑ってしまうシーンがあったり。もちろん当時見てる（だから一応BEST3の対象外ではある（新しい驚きがあったのでいいでしょう（ルールを目安としてゆるくやっていきましょう）））はずなんだけど、めちゃくちゃよくてやばかった。

キャラ

1. 空魚（裏世界ピクニック）
2. かのん（ラブライブ！スーパースター!!）
3. トール（小林さんちのメイドラゴンS）

読み（というか、かな表記）は「そらを」らしいけど、脳内ではソラオと呼んでいた。俺はパーカーが好き。そういえば何年か着てたパーカーがボロボロになってしまい今パーカーを持ってないんだけど買うかあ（どこで）。

澁谷かのん。なんでかわからんけど、何やってもかわいい。歌が好き*1で、あの5人の中にあって飛び抜けた才能を感じさせる。例えば、好きな食べ物並べた歌がよかった。キャラとしてめちゃくちゃ強くて、その点で好きなタイプのキャラ。

トールは、2期が始まったときにどんなキャラだったかよく思い出せなかった（トールだけ）。ある意味で特別なキャラだったということだと思う。2期が始まると、ほんとにいいキャラでどんどん好きになっていった。

次点は只草ちゃんかなあ。

歌

1. ラブライブ！スーパースター!! ED
2. たとえばラストダンジョン前の村の少年が序盤の街で暮らすような物語 ED
3. SSSS.DYNAZENON ED

みんなED曲じゃん。スーパースターEDはまあ当然の1位。ラブライブのEDがどういうものなのかわかっていない状態から、ED曲はこれなのかとわかって、その時点で好きだけど、期待通りにどんどんよくなっていく。アニメーションも、1クールの最初から最後まで合っていた。

ラスダンED、これだけちょっと毛色が違うね。「迷うのもちゃんと前を見てる証」という歌詞が頭に残る。かわいい。女の子視点のかわいさなのがいい。

SSSS.DYNAZENONのEDは、作品のよさを吸収して、最終回にかけてめちゃくちゃよくなってくる。その「作品のよさ」というやつがこのアニメは凄かった。

声優

1. 内山夕実
2. 大空直美
3. （該当なし）

最近、声優に対する絶対の信頼がなくなってきた（原因はわからない）。

内山夕実は、何年か前に「えっまだ1回もBEST3に入ってないの」と気づいて、でもタイミングが全然なかった。今年はルーデウスが「ああ確かに内山夕実なら信頼できるな」という配役で文句なし。Aチャンネルのナギで知って、猪熊陽子・犬吠埼風・パックの流れ。

大空直美。調べてて気づいたけど、サターニャとラフィエルの声がジャヒー様とドゥルジじゃん。今年は弥勒さんもそうだった。みんな似た声でありながらしっかり区別された声になっている。ジャヒー様のかわいさそのままの声だった。

*1:かのんは歌が好きという意味であり、俺がかのんの歌を好きという意味ではない（いや好きだけど）

秋アニメ終わり

今年も、アニメBEST3を決める時期がやってきた。大晦日丸1日使えば決まるだろとという考えは無計画が過ぎて、RTA in Japanを見るかもしれないし、他の用事が入るかもしれない。ということでアニメの情報を整理していたら、途中でこの記事が出来上がった。

（追記）ラブライブ忘れてたー！夏アニメが日程の都合で少し延びただけだから、終わった時点で夏アニメに追記するべきだったか。これはアニメが終わってわりとすぐ書くものだしなあ。ほら～ラブライブだけ文章長くなっちゃったじゃん。短い2クールのジャヒー様と区別が付いていなかったというのもある。

無職転生 ～異世界行ったら本気だす～

ずーっとクオリティが高かった。

特に妹の見た目のかわいさが尋常でない。

ラブライブ！スーパースター!!

ラブライブシリーズは目とかがプリキュアみたいで苦手なので避けていたが、最近絵柄が自分の好みに寄ってきた気がしており、今回初めて試した（虹ヶ咲の時点でちょっと気になってた）。今思うと、子供向けっぽい柔らかい内容が好みに合っていた。キャラデザもよかった。EDが好き。

2話冒頭の歌好きだった。妹と母が引いてるのも含めて、よい。

結城友奈は勇者である -大満開の章-

最終回だけよかった。

病んでる千景の描写がよかった。

ジャヒー様はくじけない！

作画が悪いことが多かったけど、のんびり楽しめるいいアニメだった。

こころちゃんが出てくるとちょっと嬉しくなる。ED1の「明日はジャヒー」みたいなの好きなんだけど、そのまま「明日はジャヒー」という歌詞でいいだろと思う。

かぎなど

俺がちゃんとアニメ見たのリトバスだけなのでよくわからなかった。いいアニメっぽくは見える。鈴が抜群にかわいい。

吸血鬼すぐ死ぬ

後半、かわいくない絵面が増えて興味を失った。OPはよかったし、丸い絵柄のかっこいい男キャラは貴重だった。

でーじミーツガール

特に刺さるものはなかったけどよさげなアニメ。

なんか、1クールかけたことで損してないか？

ルパン三世 PART6

相当よくできているアニメだと思うが、自分の理解できない言語で書かれている。12話で一区切り。

押井守回があったり、各回尖ったことをやろうとしていたのは面白かった。いやその回が面白いとは限らないけど、1クールの構成として好き。