AGC054

プロコン

あのいかつい配点から、まさかの3完早解き回。最近のAtCoderは崖を作るのが上手すぎる。

最近ずっとそうだったように調子はあまりよくなかった（ABCや典型90の復習でもあまり頭が回らなかった）が、昼寝は少しだけだけどできたし、ぷよぷよ観戦をかなり早めに切り上げのんびりトイレに行ったりして直前の時間を過ごした。ラムネも用意してコンテスト中にたくさん食べた。昨日の反省を生かし、クーラーを付けっぱなしにした（コンテスト中は体が熱くなり体感温度も上がる）。スピードは出なかったが、順当な思考を重ねることはできて、それがはまる得意セットだった。

A - Remove Substrings

両端の文字が異なるときは1回。そうでないときを考える。両端の文字が同じなのでそれと異なる文字を探す。1個では無理。もちろん0個でも不可能。2個あって隣接しているときは2回で可能（1回では無理）。他はどうも不可能っぽい。最後の1回は両端が異なる文字になるので、ラス前の操作をして消した隣に元の文字列の両端と違う文字がないといけない（これも、最終的に元の両端の文字が残っている証明も要るから厳密じゃないんだけど、まあそれができるなら全部消せてるはずなんで）。正しそう。すっきりとした証明が見えないのだけど、順位表を見てもみんなペナを出さずに瞬殺しているので、まあ正しそう。ということで提出。

B - Greedy Division

とりあえずBCを交互に考えるが、問題文の読みやすさと解いている人の多さからBに集中した。

状況は単純だが何をしたらいいかわからない。例えば「最初のK個を使ったときの通り数」とかでまとめることができない。順番がバラバラで数えられる見た目をしていない。W_i が小さいので、何個か選んで合計をいくつにするのが何通りというのは求まる（その合計が 2^N になる）。とりあえずこのDPを書く（やや手間取る（やっぱこの典型DP慣れたとはいえ苦手で頭の働きが悪いと苦しい））。で、半々に分ける具体的な方法を一つ提示されたとき、それを達成する順列がどんなものかを考えた。高橋君が取るものと青木君が取るものを上下に並べ、横幅が合計の半分という図を描く。最初のころ「最後に大きいの来たらピッタリにならないなー」とか考えてたけど、これよく見ると半々に分かれてさえいればこの図に対して順列が一意に定まる。どんな並びでも達成できるし、1通りしかない（合計が少ない順に番号を振っていくだけ（合計が等しいときは高橋君が取る））。ここで足りない情報は、半分を何個で達成したかだ。これも含めてDPする。100^4なのでまあなんとか間に合う。実装が重くなっていたこともあり、DPテーブルは3次元から2次元に変更。ここでもけっこう手間取る。個数を降順に更新すれば上書きしていける。結果的には、3重forの中で1回足し算してるだけの単純なコードに。検算のため合計が 2^N になるか確かめるコードを書いたりした。あとは階乗を前計算しておいて計算。K個で半分になるそれぞれについてそれを高橋君が取ることにすると K!*(N-K)! 通りちょうどの等しくなる順列が生成できる。K=N-K の場合や、半分を選んだら選ばれなかったものも半分になることによるダブりを心配してやや混乱したが、まあ素直に足していけばよかったと気づきサンプルも合った。

C - Roughly Sorted

（Bと比べて）問題文の読解が難しいCのほうが、頑張れば解けそうな安心感がある。

最小の操作回数ということは、直前は条件を満たしていなかったということ。転倒数（と呼ぶことにする）がK未満のものしかなかったら直前の状態がないので操作回数0の1通りのみ（後で気づいたがこの場合分けは要らなかったっぽい）。本題は転倒数がちょうどKのiがいくつかある場合。最後の操作はK+1をKにするもの。操作を逆にやっていくことを考えて、どんな操作が許されるか。関係ないやつは動かせない。一つだけならどんどん後ろへ持っていく操作になりそう（いつでもやめられる）。転倒数って、その数の左だけ見ればわかるけど、自分より小さいものが右にあればそっちへの寄与もあるわけで、混乱した。ちょうどKのものが複数あるとき、追い越すことはできる。どう考えていたか覚えてないけど、みんな「ちょうどK」だから、左にあるものほど小さい。図で見ると単純な場合の数に見えて、でもどうやるかすぐにはわからないという状態だったが、落ち着いて考えると右から順に決めていけば何回上へ移動するか掛け算していくだけだ。追い越せることに気づいたのが大きい。Nが小さく、楽な実装で済んで助かった。

DEF

不可能そうな見た目のBCに対し、Dはわりと簡単そうに見える。EFは何言ってるかわからない感じだが、まあ問題文の表面的な意味はわかる。AGCでコンテスト中に全部の問題読む展開珍しいな（読めること自体はいいことだ）。やや「座っているだけ」になってしまった。Eはまさかの門松列か！？Dについては、'o'はわりと自由に動けて、'x'が高さ1を要求する、括弧だけなら転倒数みたいに行ける？どうも'x'の扱いが難しいということそう。この見た目でtouristさえ通していないというのがヤバすぎる。

ABC207

プロコン

4完。ゴミ。

A - Repression

総和から最小値を引く。瞬殺できて嬉しい。

B - Hydrate

異常に難しい。不等式を解いてKの最小値を求める。C*D-B が正なら割って切り上げればいい。そうでないときは、そもそも最初のA個がなくてもD倍より多くなっているので-1を出力。

C - Many Segments

ハチャメチャに難しい。最初、共通部分を持つならばその共通部分は整数を含むと思ってしまいサンプルが合わず。そこで、入力を2倍して受け取ることで対応。AC。問題が難しすぎて何も考えてない。[l, r) の半開区間を基準として実装したが、これは一番左に寄ってるんだね。知らなかった。さすがに0.5の倍数は含むだろうと2倍にした。2区間の共通部分があるかどうかは、まず l の昇順になるようスワップしてから2番目の l と1番目の r を比較する。

D - Congruence Points

まず雑な解法として考えたのが、2点間の距離の集合を比較するもの（今考えると鏡にうつしたの判定できない）。三角形も考えるが、合同でも鏡にうつしたのはダメなので厳しそう。あとはSとTから1点ずつ固定し、それが対応する点であると仮定して他の点を偏角ソートし偏角と距離が一致するか調べる。さすがに想定ではなさそうと思い他の問題をやる。

他の問題があまりにも解けないので戻ってきて、結局偏角ソートをした。やってることは単純なのに、正確に書くのが難しい。つまらないことに時間を吸われて嫌な気持ちになる。まず、S側の点は一つに固定していい。T側でN通り試す。座標の値が小さいので偏角ソートは厳密にできる。引き算をしたら0以上2π未満に正規化。角度が同じものは距離でソート。これで、ぐるっと正規化された状態でソートできた。あとはN通り開始位置を試して完全一致判定するだけ。0番は基準点なので周期が N-1 であることに気づかず1WA。これは仕方ない。この方針はそのくらいきつい。

（解説を見て）重心は当然思いついていたが、N倍するだけで整数になるの気づかなかった（やれば気づくだろうけど方針をたくさん出して切り捨てる段階だとこうなる）。その後回転をN通り試すのも言われてみれば。差だけ見るやつもいいなあ。

E - Mod i

DPを考えていたが、どうしても3乗から落ちなかった。

F - Tree Patrolling

任意modのFFTでクソ重いlogを付けるのが3秒とはいえ想定ではないだろうと思いそちらへは行かなかった。

春アニメ第11話

アニメ

アニメは面白いが、精神状態はいまいち。

SSSS.DYNAZENON

凄い回だった。もちろん好みで言えば好きなのは最初の5分くらい。あの手の形をカニのまねという文脈で使うのよい。次々に場面が切り替わる。赤ぶち眼鏡の友達が久しぶりに出てきたけど、この二人が出会ってこの位置に収まってるのめちゃくちゃ良いな。ちせの似合わない制服は、「夜桜四重奏」のアオを思い出した（年齢的には制服を着ているはずだが、違う世界にいることが視聴者にも染み込んでいる）。寂しそうにしているのが効く。

上条さんは覚えてない。怪獣優生思想の服、あれを着ていても（以前暦に記憶されていたくらいで）街中で不審者扱いされない世界というのがいいよね。そしてかっこいい。怪獣パート、ちせが電車から見てるとことか、日常に怪獣が現れて非日常になった表現がすごい。EDもちょっとびっくりするくらいいい曲になっている。

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

OP久しぶりに見た気がする。先週のウサ耳さんが見えるようになった！本編はアズサが小さくなるけどどうせなら髪型も変えてほしかったな。ただ、時折見せる子供っぽい表情がとてもかわいい。ここに来て平常回に戻ってくれるの嬉しいね。

スーパーカブ

「お礼ならカブに言って」は中二病が過ぎるけど、ないないの女の子がこんな尊大な態度でいられるというのはほんとにいいことだ。まあ中二病を馬鹿にするのはただの嫉妬だからな。

久しぶりに色づいた気がする。椎ちゃんと一緒にいると、小熊さんの体がめっちゃデカく見える。予告の効果音が良い。

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

このゲーム面白いところもあるじゃん。ただ、アニメのほうは作画が悪くその面白さを出し切れなかった。展開が雑な気はするがミザリサとアリシアがいるのはよい。本編ともはや関係が感じられなくなったEDも楽しみの一つになっている。

シャドーハウス

こういうの、7話くらいのタイミングでやればよかったのに。まあニコニコで見ても共感できないコメントが多いから、自分に合ってない作品というだけなんだろうけど。原作は未完だが、1クールのアニメに合わせて原作の使われなかった話を持ってくるというのはめちゃくちゃ良い。

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

いい日常回。

春アニメ第10話

アニメ

最近難しいこと考えらんないし睡眠もヘタクソになっている。まあ他は悪くないかな。アニメたくさん見てるしプログラミングもできる。

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

最高のフラットルテ回。始まった瞬間作画が良かった。やっぱ作画だよなあ。ククの耳が4つあるのが非常に好み。

SSSS.DYNAZENON

作画が一部独特。人が消えるやべー展開。ただ消えるだけという消え方をわかりやすく見せるのも上手い。過去の様子は断片的でわかりにくいが、面白い。戦闘シーンに入り、この展開からバンク使うのなんか可笑しい。

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

ヒロイン全員出てくるとやっぱいいな。特に面白いというわけではないが、いい空間だ。アリシアがどういう状態なのか忘れたけど戦闘がかっこいい。

スーパーカブ

雪の中を走った先で得るものがチェーンなのやばすぎん？車が通って雪が減っている車道が滑りそうで怖い。小熊に何回か電話がかかってくるのが効果的な演出。

シャドーハウス

こういう展開だとエミリコの声いいな。あと、声が釘宮のキャラの見た目がやはりよかった。

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

わかりやすくていい話だ。

その他


このツイートを見てウマ娘1期の第3話だけ。ウンスっていい呼び方。なんか主人公サイドから見るとあれじゃん。展開自体は（最初にツイートを見たのもあって）わかりきっていたが、セイウンスカイが予想外にキャラクターとして強くなってしまった。

あんハピ♪、12話まで。OPのツインテールは10話になって振り向く！こんなタイミングなのか。そしてEDのクレジットでまたびっくり。チモシーの声はあの子が作っているっぽい。先生だと思ってたら制服着てる。ラップもチモシーが何だったのかもわからないままだなあ（クールの境目に合わせて変に展開をいじるよりはいいか）。アニメ公式サイトがanne-happy.comなのよね。はなこの胸のサイズが大きくなってたけど保たれてほしいのって大きさよりか形なのでまあ許容。全体としては、声がいまいち合わなかった。当時切った理由と同じかも。チモシーは当時よりだいぶ好きになった。楽しみ方があんまりフォワードっぽくない。

ふらいんぐうぃっち。7話まで。こういうの久しぶりに見る。最近はもうストーリーが進んで面白いアニメしか見てなかったから。あんハピもそうだけど、謎が明らかになる部分にばかり注目して日常パートを楽しもうとしない。「のんのんびより」みたいないわゆる日常系でも、新キャラが登場して仲良くなる過程みたいな、やっぱりそういうストーリーが楽しみの軸になるんだよね。千夏がかわいい。こんなにゆっくりテンポなアニメで赤尾でこなの意外。