秋アニメ終わり

「ライフル・イズ・ビューティフル」の無料配信が1/26くらいに始まって、それを見てようやく秋クールが終わった。他も、最終回が1月になってたり、そもそも最終回かどうかわかりにくかったりで、終わりがはっきりしないイメージだった。ていうかもう1か月くらい経ってる。はるかな過去の話に感じる。

本好きの下剋上 司書になるためには手段を選んでいられません

こういうとこで井口は信頼できるよなー。ていうか異世界転生なんだな。元のマインは消えて家族との関係はどうなるのかと思ったが、さすがにこれは（記憶は受け継いでるし）精神も幼い部分ができてるよね？わからんけど。わりと「（元の）マインでもある」状態だともとれる描き方だと思ってて、こういう曖昧（シャレではない）さは好き。

初回は、周囲が優しい人ばかりで怖かった。本を触らせてくれなかったとき安堵した。本人は病弱でつらいだろうけど、見てる側からすると何着てもかわいいのは羨ましい。オットーさんとの対比で怖かったベンノさんもいつの間にかなじんでくるじゃん。色々な人がいるけど、基本的に余裕があって、そういう世界だからつらいことがあっても考えて進むことができる。

（追記）OP歌えなさすぎワロタ。聴くぶんには気持ちいいんだけど。

星合の空

きっつい内容。出てくるのみんな超人的中学生だからなんとか見れる。ダメージを受けながらアニメみるの意味わからんとも思ってたけどね、面白いからね。ソフトテニスで腰を落とし脚を伸ばして打つのがかっこいい。雨野樹が姉と一緒に帰るシーンが好き。みつえさんの位置も、よさがだんだんわかってくる。行き違いがあって、その後ストーリー上のフォローが何もない、みたいなのとても好き。大きな実力差があっても実は普通に一発は入るというのぷよぷよっぽい。柊真の声微妙だと思ってたんだけど川柳少女の毒島エイジと同じ声かい！

オリジナルアニメなの今知った。へー。しかも「24話構成のまま12話まで作」ったのか！意図してあの第12話を作れるのすごすぎる。いいね。「コメットさん」もそうあってほしかった。

俺を好きなのはお前だけかよ

俺にとっては難しい内容。しかし一言でベッタリとネタバレできてしまうタイプでもありそうなので、ニコニコのコメントは絶対見ないようにしていた。よくわからないまま見てたけど（公式サイトで相関図が各話に対して（！）用意されていて参考になった）、難しいから面白い。特に前半の、お約束をわざと外すけど展開は典型というのが、わかりやすく楽しい。後半は、「パンジーとの関係それでいいの！？」と思っていた（曖昧な関係でキープされるのパンジーの性格だと無理だよね）。

タイトル詐欺は、まあいいんだけど、問題は内容で、終盤は微妙だった。ホースに対して、パンジーをあすなろと一緒に帰らせるシーンはあったのに、それ以降流されるままになってしまった。まさに、いつものジョーロに戻ってほしい状態だった。

最終回付近で、ふと「だからジョーロか！みんな花だから」「サンちゃん！！」と気づいた。やば。まさにそういう内容だったね。俺は新聞部がかわいいと思う。ええと5話だっけ。その最後の屋上のシーンがとてもよかった。次の話を見たうえで、あすなろだと思う。

（追記）戸松をこの位置に配するの素晴らしい。

旗揚！けものみち

言われてみれば、このすばだ。いや配色まで同じなのやば。女キャラがさっぱりしてるのがいいんだよね。シグレとの距離感な。源蔵がかっこいいのもいい。花子カーミラ過去回の無表情花子雰囲気出てる。最近のアニメにしてはキャラデザが地味なのがよい。そんな中でたまに出てくる姫様がほんとかわいい。

慎重勇者～この勇者が俺ＴＵＥＥＥくせに慎重すぎる～

出オチのような第1話からのそれなりに面白い1クールを作る技術、最近見かけるようになった。ちゃんと慎重さが役に立ってる描写が上手い。リスタのギャグシーン元がクッソかわいいから映えるんだよな。まあ一番かわいいのはエルルだけど。ゆみりもよかった。最終回付近で明かされる色々はけっこう涙腺にきた。

ライフル・イズ・ビューティフル

思ったよりよかった。キャラデザに癖があってどうかなと思ってたが。同学年の4人組は珍しい気がするけどキャラ配置がいい。最終回のひかり、AtCoderで黄色になった次のAGCの俺だった。先生やばくて好き。

ぬるぺた

シンエイ動画。目がそれっぽい？体の部分がめちゃくちゃ好みで、特にぬるのスカートが素晴らしい。物語が動いても姉妹の関係は変わらなくて、良い。Steamで体験版やった。

超人高校生たちは異世界でも余裕で生き抜くようです！

OPの軽々しい明るさ、これを意図的に作れるのほんとすげえ。後半、余裕がなくてタイトル詐欺だった。他はまあ、コメ付きで見てるぶんにはそこまで気にならない。忍がかわいい。

兄に付ける薬はない！3

ちょっと暴れすぎなきらいはあるが、3期だし違うものを出してくるのは良い。

放課後さいころ倶楽部

7話で区切りが付いてしまい、8話の新キャラを見て興味を失っていることに気づいた。新キャラが出たタイミングで切るのがよくなかった経験がある気がして8話だけは見ることにした。ドブルのカードを構成できる条件を頑張って考えていたが結局わからず、ググったらわりとガチ数学なやつだった。

2話を見てから綾が異常にかわいくなった。まあ、ゲームの説明部分が、さすがにきつかった。意図的にああしてるのはわかるけど、心理戦じゃなくてルールが知りたいので。

ABC153

ABC148と同じ。問題が（青までratedのコンテストとしては）簡単すぎる。全部誰かがMonsterと戦う問題になっていて楽しいセットなのに、全完でレーティングが落ちるんじゃratedコンテストとしては納得できない。2ペナ出してしまったのは反省点。反省点があるのがせめてもの救い。

A - Serval vs Monster

切り上げ。Fの伏線になっていたのがよかった。

B - Common Raccoon vs Monster

最初、貪欲かと思ってしまったが、ABCのBでソートは使わないよね。単に、和がH以上になるかという問題だった。HからAを引いていって0以下になるか判定する実装にした。

C - Fennec vs Monster

必殺技は体力が大きいモンスターに使うほうが得。昇順ソートして、必殺技を使わなかったN-K体のモンスターの体力の和を求めればいい。

D - Caracal vs Monster

「モンスターの体力が X>1 なら」というのが意味わからん。まあ「モンスターの体力が X で、X>1 なら」ということだよね。最小値とあるけど、選択の余地はないのでどんどん半分にしていくだけ。H>=1であり、いつか1になるので、そこを条件にしてループ。1回分裂させる毎に攻撃回数は倍になる。一斉攻撃していけばモンスターの数は常に2冪なのでシミュレーションしていけばいい。あ、ひょっとしてもっと簡単に解けるか。

E - Crested Ibis vs Monster

ナップサックやんけと思ったけど、同じ魔法は何回でも使える。これは、in-placeな更新でループ方向を順方向にすればいいのでむしろ実装は簡単になる（ということを必死で考える/思い出す）（思い出してもちゃんと考えて確認しないといけないから時間がかかる）。さて、過剰にダメージを与えてもいいのがちょっと厄介だ。えーと、A_iまではB_iでできるみたいなのを加えればよさそう。提出してREで「エッ」と声が出た。REだったので原因はすぐ浮かんだ。A_iがHより大きいことがあるのだ。直してAC。

ナップサックの簡単なDPくらいならさすがにすぐ書けるが、やはり苦手分野なのでね。本当はこういうの無限に時間が欲しい（ナップサックとの違いとか別の値でDPするとか納得するまで考えたい）。ただ、青コーダーなら時間をかけずに解ける問題だということもわかるので、頑張って短時間で解いた。まあ実力通りの1ペナ。

F - Silver Fox vs Monster

えらく簡単そう。左から貪欲でいい。なぜなら、攻撃する順番は結果に関係ないし、一番左のモンスターに攻撃するときは爆弾の攻撃範囲の左端にして損しない。攻撃範囲はD*2+1（半開区間）。Xでソートしておけばstd::lower_boundでいくつ先のモンスターまで攻撃できるかわかる。で、ここまで来て範囲加算が必要なことに気づく。何か牛刀を使わない解法もありそうだと思ったが、すぐに思いつかないので遅延セグ木を貼った。AtCoderでセグメント木を使うの5億年ぶりでドキドキだった（困るなあと思っていたｗ）。1個だけWAを出してしまい、32bit符号付き整数ギリギリまで使ってるD（をD*2+1に置き換えたもの）に注目すると、同じく32bitのp[i].xに足して二分探索のターゲットとして使ってしまっていた。オーバーフローしないように64bitで計算してmax(X)より大きい2^30とminを取り提出、AC。問題は簡単だと思っていたら、自分が使った道具に圧されて注意力を欠いてしまった。

ABC152

全完！これは気持ちいい（内容がよかった）。昨日よりはいい精神状態で臨めて立ち回りもよかった（面倒そうなDを後回しにして最後すっきりした解法を見つけた）。窓を開けて換気したりもした。

A - AC or WA

ACの場合はYesなので、n == m ? "Yes" : "No"。逆だったら、m < n ? "Yes" : "No"とするつもりだった。

B - Comparing Strings

罠がありそうで怖い見た目してるけど、先頭の数が小さいほうが辞書順で小さいので、小さいほうの数を大きいほうの数だけ出力する。

C - Low Elements

不等号の向きがややこしいな。自分も含めてるけど、含めずに（添え字が小さいほうから見ていって）「これまでで最小のもの」ってのが何個あるか。最大か最小を更新していって比較するだけだね。で、最大と最小どっちだい。「これまでで最小のものよりさらに小さい」だから最小値だ。チキンなので含める書き方にしてしまった（最小値を更新してからの比較）。

D - Handstand 2

とりあえず場合分け1桁のときは同じ数同士でつながれる。2桁以上のときは81通りあって、4桁の数なら端以外で100通りある。さて、N=3214とかだとどうするか。その100通りの途中で切られるのがきつい。桁DPの問題みたいに、3000までと3200までと3210までとって分ければいいのかな。できるかもわからんし、だいいちやりたくねえ。ということでさっさとE問題に行った。

EFを解いて帰ってきた。時間が経っているからか違う発想が出てくれた。桁数関係なくiで始まりjで終わる数をカウントすればいい。0で終わる数は数えないように気をつける（今気づいたけど0で始まる数がないからカウントしてもよかった）。あとはp[i][j] * p[j][i]を足し上げるだけ。後回しにしてきれいな解法思いついて全完。最高のムーブだった。

E - Flatten

要するに積が全部同じ数になる。まあA全部の積をA_iで割ったものをB_iにすればいいよね。あとは最大公約数で割るとかすれば最小が求まる。よーするにAの最小公倍数がmod Pで求まればいい。実際、単にmodを取らず最小公倍数を求めるだけでサンプルは通った。さて、mod Pで最大公約数が求まるか！？（そこを問われていると思って緊張が走った）

しばらく考えてたけどさすがに無理でしょ。いやなんかA_iは10^9+7の倍数じゃないから行けるかもと思っちゃった。1と10^9+8が全然違う数なわけでね。ここでようやく、Nが小さい制約になってる理由に気づく。素因数分解して最小公倍数を求めるんだ。各素因数について最大何個あったか更新していく。試し割りは10^6まですると素数だけでも間に合わなそうなので、ここは10^3までやって残ったらそれは素数ってことでいいんだけど、そうなるとそのでかい素数が何番目かわからんので（別に二分探索やmapで間に合うだろうけど）困った。ここで、A_iが小さい制約になってる理由に気づく。10^6サイズの配列を用意しちゃえばいいんだ。A_iが小さいから素数以外まで含めても余裕がある。ということで実装。最小公倍数を求めるパートがやや複雑で不安だったがなんとか一発AC。

F - Tree and Constraints

Nが小さいが、Mが20以下とほんとに小さい。2^Mができる。否定を考えると「1個でも全部白なパスがある」になる。これは包除が使えるか！？使ったことなかったけどここでわかりやすい典型で出してくれたか！実際そうだった。包除原理の実装の勉強ができて嬉しい。Nも50以下で、64以下なので辺の選び方がビットで表現できる。

つまり、まずDFSでuからvへのパスを求め、パスに使われている辺のビットを立てる。これで条件が1個の64bit整数になった。DFSは、目的地に着いたらフラグをセットして、フラグが立っていたら使った辺の辺番号のビットを立ててすぐループを抜ける（帰りがけにセットする）（他の辺を探索しない）。辺が辺番号を持つことが必要だった。ビットを立てるときシフトを忘れてサンプル合わなかったりした。次に、条件の選び方2^M通りについて、選んだ条件たちの全部白でなければならない辺の和集合をビット毎のORで求める。そこが全部白で、他は白黒どっちでもいいので2の他の辺の数乗通り。これを包除の公式通りに足していく（競プロ的だ）。popcntがけっこう重そう（N-1ビット毎回数える）だと思ったけど、実行時間制限が4秒なので安心。

サンプルでデバッグして合ったら提出。条件を64bit整数にしたものを保存するときintの配列に入れてしまっていて1WA。最近、WAを出すのが怖くて固くなっていた気がするので、軽い振る舞いを心がけていた。結果的に1ペナだけでスピード出せてたので満足。まあ、変なWAを出したらダメージあるんだろうなあとか思いながらジャッジを待ったりしてたけどｗ

キーエンス プログラミング コンテスト 2020

久しぶりに熱測って37.2。上がりすぎ。上がったぶん空回りしただけ。またlowestを更新した。まだまだ下がる余地があるんだなあ。

A - Painting

min((n + h - 1) / h, (n + w - 1) / w)。もう少し短く書けないかなあと思いながら出した。（解説放送を聞いて）Fのパロディかあ。

B - Robot Arms

めちゃくちゃ難しい。区間を右端が左にある順に見ていく、というのはよくあるので思いついたが、それをどう利用するれば100%正しいと言える解法になるのか考えるのに時間がかかった。えーと、一番左の右端が占める場所で1個しか生き残れないのだけど、一番左のを選んでデメリットがない。その場所の左側を考えると既に被ってるやつしかいない（デメリットがない）し、右側は明らか（メリットしかない）。ということで左から貪欲に取っていく。生き残ったやつの右端の場所を更新していって、左端がそこにかかるやつを落としていく。右端でソートしてあるので、現在見ている場所より左端が左な区間は必ず被る。この解法で全部上手くいくんだけど、全部確認する必要があって難しい。

C - Subarray Sum

楽しい構築。制約を見て、KがN以下なので、N=5,K=4,S=9みたいなケースで9,9,9,8,1を思いつく。S=1だとこれができないので、1,1,1,1,4とかする。どうも、Sが大きいときも小さいときも簡単なので、その2つの解法を組み合わせれば解けそうだと思った。もう少し考えて、S,S,S,S+1,S+1とかでいいと気づく（代わりにS-1を使うとそれらの和がSになるかもしれない、S+1なら心配ない）。これができないのはS=10^9のときだけなので、場合分けしてS,S,S,1,1にする。10^9はNより十分に大きい。

終了後にジャッジをどう書くか考えていて気づいたが、ジャッジはしゃくとりで書けて、正の数しか出てこないので1つの開始地点に対し和がSになる区間は高々1つしかなく、だからK>Nのときは構成できない。なぜK<=Nなのかコンテスト中はわかってなかった。

D - Swap and Flip

解けなかった。カードiが裏になるかどうかで2^N通り探索し転倒数を数えるというところまでは行ったが、同じ数がたくさんあるときの処理がわからなかった。

最初、広義単調増加となったときの一番左と一番右のカードの数を固定することを考えた。少しして、数ではなくどのカードが来るかで考えたほうがいいと気づく。これだと何もわからなくて、しばらくして、1回の操作でカードは距離1だけ動き裏表が入れ替わる、つまりあるカードについて最終的な位置から裏表がわかると気づいた。なんか普通にDFSしてもしっかり枝刈りすれば通るのではとか思い始める。しかし計算量が全くわからないので困っていると、裏表の2通りを全探索する（2^N回）ことを思いつく。裏表は1回の操作で2回変わるので裏なカードの枚数は偶数。全カードの裏表を決めれば使う数がわかり最終的な数列がわかる！と思っていたが、なんか最終的なカード位置での裏表を考えていて、そもそも裏表を固定しなくてもその位置に来る数は高々N通りで、固定することで半分になる。で、その選ばれうるシーケンスをソートして組み合わせればいいかと思いきや、全部でN*2個ある数の中からN個しか使わないわけで、全部使わないのでは最終的な数列もわからない。難しすぎてめちゃくちゃ時間食った。残り30分くらいになってやっと、単にカードiの最終的な裏表全探索じゃんと気づく。これで、使える数が決まった。だから最終的な広義単調増加な列も一意に定まる。あとは、これが実現可能か。最初はソート前とソート後の数列を持っていたが、単にカードぐしバブルソートすればいいと気づく（Nが小さいのでNlogNもN^2も変わらん）。swapされた回数を各カードに保存しながらバブルソート。ソートが終わって裏表が合ってればそれ（全体のswap回数）が答え。合ってなくて全部違う数のときは-1。そうでないとき、同じ数の区間で追加で最小のswapをして合わせる必要があるが、ここが難しくて残り時間もわずかしかなく、書ききれなかった。ただ、ここはかなり難しく、時間があってもダメだったかもしれない。swap回数の偶奇が合わないもののうち一番左のものに注目する。これはswapする必要があるけど、だからといって他をswapする前にやってもいいのかがわからない。そもそも、もう少し考えると、カードをswapすることで一番左の合わないカードを左のカードとswapすることもありえる。偶奇は位置じゃなくてカードにかかるから、カードをswapすればまた話が変わる。一番左のものより左まで巻き込む可能性があるんじゃどうしようもない。