ABC209

プロコン

5完。レーティング更新対象でないということで緊張感がなく事前にトイレにギリギリ行かない状態だったが、やはり緊張はしていて直前になってしたくなった（無理にでも出しとくべきだった）。ABを通し、CDを頭に入れてトイレに行った。といっても、Dは読み終わったときには解けていたので考える対象はCのみ。やや難しいとはいえ小考で解けてしまい少しだけ時間を無駄にした。

A - Counting

ABCのAなのに A <= B という条件がない！？と思ったけどサンプルに A > B のケースあった。0とのmaxをとる。

B - Can you buy them all?

シミュレーションする。値引き額は i % 2 でいい。

C - Not Equal

最初は難しく感じる。ていうか前もやったことある問題だと思うんだけど、思い出せないのだ。左から決めていくと、C_iより大きい数を選んだかどうかの場合分けが発生するのでヤバい。

思いつけば簡単。ソートしても答えは同じ（ソートしていない状態で、小さいものから決めていくのと同じ）なので、ソートして小さいほうから決めていく。0とのmaxとる必要あるかなあと10秒くらい考えて自信が持てなかったのでmaxとった。単調非減少の整数列だから、使用済みの個数を引いても前の数と比べて高々1しか減らず、0を飛ばしてマイナスに行くことはないよね。

D - Collision

LCAやるだけなので貼った。あとで順位表を見ているときに気づいたが、距離の偶奇はDFSして深さを持つだけでいい。特に、LCAから根までを往復する距離は常に偶数なので、LCAを求めている意味が全くないという点が悔しい。

E - Shiritori

少し前にどうぶつしょうぎの後退解析を考えてて、（計算時間の節約を考えると）難しいなあと思っていたのだけど、こんな計算量でできるんだね（コンピュータ将棋開発してて知らなかったのかよという話もある）。これが可能であるということが問題からわかるので、解けなくても嬉しさがあるし、通せた（証明したわけではないので解けたという表現でない）のでなお嬉しい。

後退解析をする。負けのノードへ辺が出ているノードは勝ち、勝ちのノードへしか辺が出ていないノードは負け。グラフの有向辺の向きを逆にして持つ。逆にしたグラフで入次数が0のものは負けで確定。それらをキューに入れて処理していく。キューから取り出したノードが負けなら辺を辿って隣のノードは勝ち。取り出したノードが勝ちなら隣のノードのカウントを++して入次数と同じになったら負け確定。勝ち負けが確定したらキューに入れる。キューが空になって確定していないノードは引き分け。各ノードがキューに入るのは高々1回なので、グラフの辺も高々1回辿るだけでよくて高速。

前置++に書き換えたとき元のを消し忘れて1WA。グラフに落とすまでもけっこう混乱した。(26*2)^3個の頂点とN個の有向辺があるというだけの話なんだけど、それがなかなかわからない。グラフに落とせたらどうぶつしょうぎと同じ状況になるので後退解析となる。引き分け（千日手）の扱い、どうぶつしょうぎのほうでもしっかり考えてなかったなと気づかされた。

F - Deforestation

全然わからなかった。考えたことは、最初 1 2 2 2 1 みたいな重みを持ってて、選ぶとそれ掛けるH_iのスコアがもらえて隣から1引くというゲームのスコア最大化。あと、いい感じのポテンシャルがないかと思ったけど何も思いつかず、仮に貪欲に取るみたいな感じだとしたらDAGの入力辺がないものだけ取れるとして何通りの取り方があるかとかこれも解ける気がしなかった。最近は少なくなったけど、たまに「座ってるだけ」になるね。

春アニメ終わり

アニメ

毎回感想書いてたし6月は他のアニメも見てたし疲れた。今はのんびり過ごしている。

3位までが全く決められなかったので、文章量が多い順に並べた。これも難しくて、好きな作品には短いコメントしかできなかったりもするからなあ。まあ今回はこれで。

スーパーカブ

初回はクオリティに圧倒された。そもそもスーパーカブというタイトルが良すぎる。この言葉を選べるのが強い。

小熊さんの性格が、かなり芯があるというか、いや、こうやって安易に言葉にしないほうがいいよな、なんか今はカブがメインでその線上に礼子もいて深い関係になっていて（ここ必要以上に描かないのいいよね（描かれたらそれはそれで良いと言いそうだけど））、それが視聴者からはわかんない異常な世界で、いまいち作品に乗り切れないところがあった。カブと出会い、礼子と出会い、それによって変わったものなのかどうかはわからない。もちろん確実に変わってはいるだろうけど、あの異常性のどのくらいが最初から小熊さんの中にあったのか。

SSSS.DYNAZENON

「SSSS.GRIDMAN」がよかったから見てみるかという感じだったと思うけど、期待より良かった。世界観を保って新しい話をしている。やはりTRIGGERのアニメはクオリティが高い。OP/EDも、ただ曲がいいとか動きがいいとかだけでなく、本編の内容への寄与が素晴らしい。そんなに自分と合うわけではないので途中退屈なところも多かったけどね。見てよかった。

スライム倒して300年、知らないうちにレベルMAXになってました

かわいいキャラばかりこんなに増やして区別付くんかと心配していたが杞憂だった。全員必要なキャラになっててすごい。魔女の帽子が地味にクソデカなの好き。作品を象徴するOPを作れたのがすごい。

究極進化したフルダイブRPGが現実よりもクソゲーだったら

何が面白いか説明できない系アニメ。「嫌いじゃない」という表現になってしまうけど、実際わりと好きな作品だった。2期があってもなくてもいい感じの。アリシアに関しては中途半端になってしまったのが心残り。妹は中途半端までも行かなかった。

シャドーハウス

なんだかんだエミリコだったなあ。強かった。内容は完全に "not for me" というやつ。

結城友奈は勇者である ちゅるっと！

特になし。

その他

シャドーハウス13話。こういう展開だとOP冒頭のエミリコが救いになる。ルウがかわいい。話が難解すぎる。コーヒーのことを知った上で普通に暮らし始めるのなんなん。（ニコニコ動画のコメントを見て）あー「振り」かあ。

恋アス1話。改めて見るといの先輩がこのころからいの先輩してたんだなあと。みらとあおの関係はめちゃくちゃよい。

ABC208

プロコン

面白かった。めちゃくちゃいいABCだな。Eは桁DP部分が嫌い。

A - Rolling Dice

範囲内は全部作れる。

B - Factorial Yen Coin

かなり難しい見た目。C問題風。硬貨の額面が変わってるけど、どの2種類の硬貨を選んでも倍数の関係になっているのがポイント。普通に大きいものから使っていけばいい。なんか提出時には深く考えてなかったけど1種類の硬貨の最大使用枚数は10未満だ（倍率が2倍から10倍までなので）。10!円のが何枚使うかわからなかったのでwhileで適当に回した。

C - Fair Candy Distribution

これ好き。ここまで簡単でそこそこ楽しいじゃん、ほんと好き。floor(N/K)をまず配る。aをコピーしてソートしてN%K番目の値を使い、a_iがそれより小さかったら1枚渡す（渡す回数は0回からN-1回）。

D - Shortest Path Queries 2

これはちょっと面食らう。どんな方法で計算すればいいか色々考える。当然ワーシャルフロイドも浮かぶが、ライブラリのコードを見るとなんかこの問題に使えそうな形をしている（笑）。とりあえずサンプル合わしてから考えたけど、考えれば考えるほどこの問題文とこのコードは同じ意味だ（「s,t および番号が k 以下の都市のみ」を使っている）。よくはわかってないけど提出してAC。ド典型なのに面白くて、ワーシャルフロイド法の使い方ではなく中身を教えてくれる教育的な問題だ。これがABCか。

E - Digit Products

なんでKが小さいんだろうと思って見ていたが、なるほどDFSを書いて調べてみると桁の積としてありえる10^9以下の値は5195通りしかない。あとは桁DPみたいにする。具体的には、[1, 9], [10, 99], [100, 123] のように分けてそれぞれ数える。しかし実装が難しく、unordered_mapを使うか二分探索で5195通りのインデックスを求めるかで迷い、後者を選ぶも残り10分を切ってKを超えてから0を掛けて0になるケースの見落としに気づき死亡。せっかく面白いセットだったのに、この実装がコンテスト時間の大半を占めており非常に残念な感じに。桁DP的なやつの面白さがわからない（いつもの分け方でできるし実装が面倒だし面白くないと思う）。

（追記）


F - Cumulative Sum

手で少し計算してみてM=1でさえ（K乗の和になって）普通には解けないことに気づく。少し考えて、最低限のヤバさは感じたとしてEに専念した（Eから戻ってくることはなかった（そ、そんな））。

春アニメ第12話

アニメ

SSSS.DYNAZENON

未来を勝ち取るための戦いだったか。どちらが正しいか、どちらかが否定されるべきものなのかどうかはわからないが、ガウマさんがそれを選んだことは感情移入する基準になる（ガウマさんがこれまでの1クールでそういうキャラになっているのがすごい）。蓬もそれを選びとることができた。たしかに、かけがえのない不自由を選び続けるのは生きてるって感じするね（あまり子供っぽくない気はする）。ちせと暦が（これだけ状況変わっても）ずっと仲いいの妬けるなあ。しれっと「蓬」呼びなのいいシーンで、これが自然になるような流れがここ数話でできていた。

うわあ最後のカットで締まる。たった数秒でこんなにもきれいに終われる。

スーパーカブ

少し前から気づいていたけど、OPの冒頭が夏秋冬春なのはこの1クールを表している。最後に桜が見られる作品は良い。OPとEDもある。あるあるのアニメは良い。小熊さんのキャラが今回で決まった。ほんといいキャラになった。色づいたことに気づかなかった。ごく自然にあの状態。クオリティが高い。

スライム倒して300年、知らないうちにレベルMAXになってました

最後らしい豪華さを出しつつ、話はいつも通り。なんだこれすごいな。フラットルテかわいい。ロザリーなんで黄色なんだろ。

究極進化したフルダイブRPGが現実よりもクソゲーだったら

どう区切るんだと思っていたが、これはきれいに終わった。まあそんなに面白くはなかったけど、毎週ニコニコ動画で見るこの時間は嫌いじゃなかったよ。アリシアが好きだった。

シャドーハウス

オッ、なんか進みが遅いと思ったら今回では終わらないのか。相変わらず内容はわからない。ルールのわからないゲームを見ている感じ。エミリコが強い。バービーの声がいい。

結城友奈は勇者である ちゅるっと！

とりあえず締めた。キャラ多いなー。

その他

ふらいんぐうぃっち。8話から12話まで。いい感じに日常になってきた。OPのキャラも大体わかるようになってきたし、周りが充実したうえで真琴と千夏がキャラとして強くて。セーラー服井口は「さんかれあ」を思い出す。11話は空飛ぶくじらだが、これも日常回になってしまう。なじみ方がすごい（魔女っぽいことをするかどうかが関係ない）。みんなでしゃべりながらホットケーキ食べてるだけの話。ほんと後半になって化けた。10話と11話が好き。OPが目立つアニメでの最終的に地味なEDが好きになるやつ。キャラデザが丸いのが思い切ってる。姉ちゃんもいつもニコニコしてる。

鋼の錬金術師（2003年の）5話まで。初期の話だからか本当に背が低い。アルがかわいい。OPもEDもかっこいいし、本編もわりと自分に合う面白さ（微妙に古くて安心する）。ロイ・マスタングもかっこよくて好き。