ABC267

ACDEの4完。Bが本当に嫌いなので飛ばした。Fがわからないのは頭が残念。

A - Saturday

これいちいちクオートするのが面倒というか人間のする仕事じゃないんよな。変換するツールを用意しておくべきか。ただまあこれは出題するほうが悪い気もするのでわざわざ用意するのもしゃく。必要なツールならいくらでも時間かけて用意するんだけど（それも楽しいプログラミングなので）。

で、stringの配列にしたら何番目と一致するか検出して出力。ついつい、Mondayのインデックスが1だと思い込んでしまったが当然サンプルは合わない。SundayがないのでMondayのインデックスは0だった。2分は切りたかったなあ。

B - Split?

ピンの配置を手入力する必要がある。人間がしていい仕事ではない。「ピンが全て倒れている列が存在する」の実装が重すぎる。10分くらいしたところで、コンテスト中にやっていい時間の使い方じゃないと気づき、飛ばした。

実は、「立っているピンが 1 本以上存在する」の否定が「ピンが全て倒れている」だった。このことに気づけなかったのが敗因。だから、レーティングが下がることに文句はない。ただ、このB問題のせいで100分中10分を浪費し、そのうえ最悪な気分でC以降をやることになった（普通なら楽しく解いてるはず）。本当にこのB問題が嫌いだ。

（追記）B問題をupsolveって面白いな（？）。「一つでも立っている」を前計算しておき、3重ループ。思ったよりは短く書ける。

C - Index × A(Continuous ver.)

難しそうだが、長さMの連続部分列はO(N)個しかなくてしかも差分計算できるので解けた。最初（A_1からA_Mまで）のを計算したら、それを仮の答えとして最大値を更新していく（答えは負になりうるので初期値の設定が面倒だったがこれで解決するしこの後の更新回数もN-M回なのでfor文が書きやすい）。その区間の累積和を引いて次のM*A_iを足す。累積和もA_iを足してA_(i-M)を引くことで更新していく。

D - Index × A(Not Continuous ver.)

Cとの関係に気づくのけっこう時間かかった。こっちのが難しいのかーと思いながらソートしたが、ソートしてはいけなかった（順番が関係ある）。DPですね。最初のi個からk個を選んだときの最大でまとめることができる。DPテーブルは全部-INFで初期化しておいて、0個から0個を選んだところだけ0にする。わざわざDPテーブルを初期化したのは配るDPにするため。遷移の図を描くとわかるけど、これは配る形をしている（実装が楽）。k個からk+1個に増えるときはA_i*(k+1)を足す。特に定数倍高速化はせずDPテーブルを三角形に全部埋めてdp[n][m]を出力。

E - Erasing Vertices 2

「辺で直接結ばれて」を見て「直接辺で結ばれて」ではないから「辺で結ばれて」だなと誤読して、どっちだろうと思いながら何回もサンプル含め読んでいたら「直接」を見つけた。正しい読みがわかっても、不自然な設定に思えて捉えにくかった。操作全体のコストもわかりにくい。和で計算しないコストってあるのか？

まず二分探索を思いつく。実行時間制限も4秒だしlogを2つ付けて大丈夫。コストの最大値がXでできるか判定するのは、X以下のを操作してしまっていいのでpriority_queueで小さい順にってところで二分探索いらないじゃんと気づく。改めて正当性を考えると、答えは今できる操作のどれか以上になるし操作をすることで他の頂点に対する操作のコストは悪化しない。よって最もコストが小さい操作をしてしまってよい。証明できたので実装。まず全部の頂点のコストを計算して頂点番号とともにpriority_queueへ入れる。頂点iを削除するときは隣の頂点のコストからA_iを引いてpriority_queueに入れなおす。ダイクストラ法みたいだ。削除済みかのフラグも持ち、削除済みだったらcontinue。現在のコストを持つためのvectorも用意する。頂点iを削除するためのコストも計算していたが、これは単にpriority_queueに入れたコストを使えばよかった（一致するはず）。提出してWA。

考察と実装を全部見直してどこも間違っているとは思えないのでFへ（8分程度使った）。わりとFに集中できた。残り時間が少なくなりFを通す見込みがなくなって戻ってきたが、N回操作してるつもりがcontinueしたのも回数に含めてた。今度はAC。提出時刻は遅くなったが、Fを考える時間はそれほどロスしていないのでよし。

解説見たけど、これ二分探索できる人なら二分探索しないだろ。ただ、X以下かで分ければいいのでpriority_queueが不要となりlogは1つで済むんだな。これは気づかなかった。

二分探索の上限を考えているときに思ったけど、答えはどこまで大きいのが構成可能なんだろうね（けっこう小さい気がしてた）。スターグラフだと端からやれば小さいし、完全グラフはNが小さくなる。

F - Exactly K Steps

解きたくなる見た目をしている。DFSしながらスタックで履歴を持ってとか考えてたけど、祖先や子孫はいいとしてそれ以外がきついんだよね。1個でもあればいいので子孫が深い順に探索して一番深いやつだけは2番目を相手にしてとかを探ってたけど枝分かれが多くて厳しい。ただ、めっちゃ深いやつは少ないので可能性はありそう（解ける問題ではありそう）な気はしていた。

いや直径は全く思いつかなかった。深い順に探索とか、雰囲気はそうだったのに。本当に頭が固い。

（追記）よくわからんけど直径となる2頂点のどちらかがどの頂点から見ても最遠の一つになっていそう。各頂点にクエリのvectorを持たせ、祖先たちをスタックで管理するDFSをしながら処理していく。それを直径の端2頂点からそれぞれやる。答えは-1で初期化しておき見つけたら上書きしていけばいい。

Gは読んだだけ。

調子が悪い

先週から新しいパソコンを使っている。そのことで苦しんでいる気がする（具体的な理由は自分でもよくわからない）。

プロセカは、淡々とライボ消費（先週からブログを書こうとしているが進まない）。アニメは、楽しみではないけど見れば楽しめる。ぷよぷよは普通にやる。ぷよ配信はけっこう見てる。

競プロは、コンテスト中はいつも通り。復習というか解けなかった問題を考える気がない、解説を理解する頭もないという感じで、普段ならupsolveしていたはずの問題が溜まっている。

パソコンの箱をまだ片付けていない。やる気がない。やる気が出るときがない。何も面白いことはできない。時間がびゅんびゅん過ぎる。この記事も書き始めから1日半くらい経ってる。

苦しかったりやることがなかったりすると、早寝になる。普段と比べれば寝付けなくてもいいやって気持ちになりやすい。いつもより寝付きはいい気がする。朝は、こんな世界に起きてもしょうがないという気持ちになるので、布団でうじうじしがち。

ABC266

6完。内容的には自分なりに満足という感じだが、レーティング1900を割ってしまった。

A - Middle Letter

いいA問題だ。長さを2で割れば中央のインデックスが得られる。

B - Modulo Number

x以下の最もxに近いmの倍数を返す関数を持っているのでそれを貼る。探すのに時間食ってしまった。直接求まるわけではないので、まあNから引けばいいんだけど、そこも少し時間使った。これも自分にとっては（実装軽くて）いい問題（適正レベルの人に対してはやや難しいか？）。

C - Convex Quadrilateral

各頂点について、どっちに曲がっているか調べる。注目している頂点から見た隣の頂点の位置を表すベクトルの外積をとり、とりあえずサンプルで符号を見てそれに合わせて判定を書く。一つでも逆の符号があったらダメ（制約で0がないことは保証されている）。これもわりと軽めだったのでよかった。ただ、C問題としてはかなり高度。

D - Snuke Panic (1D)

全然わからない。ということはDPだ。実際DPできた。整数時刻に整数座標にいるとしていいか証明できなかったが、コンテスト中はいくつかの例を考えて済ました。穴から出てくる時刻だけ考えて、前の時刻と今の時刻の差で移動距離の上限がわかる。25通りの遷移を全部やる。可能な移動元の最大に、もしちょうど出てくる場所にいるならその大きさを足す。長さ5のDPテーブルを2つ使うだけの省メモリ。

解説見て気づいたけどT_Nが10^5以下なの完全に忘れてた（ちゃんと読んで認識していたけど見つけたのが10^9でも解ける方針だったから「都合よく」忘れてしまった）。

E - Throwing the Die

後ろから。最初は3.5で、次はそれ未満の出目なら続ける。6通りの出目の期待値の平均をとればよくて、それをN回回す。かんたん。

F - Well-defined Path Queries on a Namori

なもりグラフは、ループにひげ（木）が0個以上付いてるやつ。まず閉路検出。無向グラフなので、DFSで祖先に当たったらそこがループ（祖先でない訪問済みの頂点に当たることはない）。祖先の頂点番号を記録しておき、そこに戻るまで親に印を付けていく。これで閉路に含まれる頂点を列挙できた。次に、パスが一意になるかを場合分けして考える。どちらも閉路に含まれているなら2通りある。片方だけ含まれている場合は、閉路の中を移動するかどうかで違いそう。どちらも含まれないなら1通りかと思いきや、閉路の中を通過するやつは2通りある（かすっただけでは1通り）。2通りを超えてありえるかは知らんけどそこは関係ない。閉路に含まれる頂点を2個以上通ったらそこを閉路の反対側に置き換えることで別のパスになる。そうでないなら、0個は明らかに無理だし1個も無理そう。未証明だが実装に入る。

DFS木で考えて、セグ木でLCAを求める。まず閉路に含まれる頂点を求め、それを使って自分を含めた祖先たちに閉路に含まれる頂点が何個あるかもう1回DFSで求める。クエリに対しては、LCAを求めて引き算とかすればDFS木上のパスに含まれる個数がわかる。それが2未満ならYes。が、全然サンプルが合わない。プログラムが落ちることもある。なもりグラフを木のように扱うのが思ったより厄介。まず閉路検出のDFSでループに反対側から入るのを抑制していなかった。その後のDFSも、単にループ検出したときの辺を使用不能にするだけでいいのに迷走していた。それでも合わない。なんと、自分の以前の提出からコピーしてきたら、lcaという名前の関数がLCAの頂点番号ではなくパスの長さを返していた。これは反省せざるをえない。まあLCAって苦手なんだよな。

解説見たらとてもシンプルだった。これはなあ。力不足と言えばそうなんだけど。シンプルな解放を目指すべきなんだよな。にしてもこれを1000人解いてるのはやばいだろ。

G - Yet Another RGB Sequence

Fの実装で詰まったとき読むだけ読んだ。Fを通したあとで考えたが難しい。包除っぽいけど、指定したRG以外のRGが被ってくるのをどうしようもない。

（追記）解説見るとわりと簡単だった。ARCっぽいよな。解説見ちゃうとその通り実装するだけで勉強してる感じがしない。RとRGとBを好きに並べてそこへ（RGを作らないように）Gを入れるのが何通りあるか。Rが1個あるたびに入れる場所が1個減る。0個以上好きな個数入れていい場所がいくつあるかという意味でRを取り除いたときと同じだ。

夏アニメ第6話

話数の概念。

人生には運が絡むのでそのことに疲れた。

ラブライブ！スーパースター!! 2期 #5,6

5話。9人ってそういう数なの（他のシリーズを知らない）。2年生と1年生の差。去年の積み重ねが見えるいい描写、と言いたいところだけど薄っぺらくも見える。最後の一人がお金のためという形で近づいてきたが、どうなるか。かのんが強い。なんや次回のサブタイトル。

6話。前回の1年生だけでというやつ夏美の企画に周りが合わせて何か確かめようとしてるのかと思っていた（なにそれ）が、普通に1年生主体の練習か。これだけ間近でリエラの1年生を見ていたら、そりゃあわかってくる。かのんのお父さんが謎すぎるけど、これはスルーしていいところ（最近こういうの自信ないが）。夏美とかのんの時間。作ってる側もこれがいいシーンだってわかってるからこの演出。今回のライブはよかった。学園祭まで時間が経っているから力が付いているのも自然だし、曲調と服が合っていて好み。また次回のサブタイおかしいな。

オーバーロードIV #6,7

6話。面白い。ドワーフの心理描写が、構造はシンプルだけどきっちり描かれている。

関係ないけどEDでアルベドに対して「誰？」ってコメント付くじゃん。本編ではギャグっぽいのにEDでは違うからなのはわかるけど、んー、俺には同一人物にしか見えないんだよなあ。マジレスしすぎて変になってるけど、なんというか、あれを違うものとして認識する能力が自分には欠けているという不安を持っている。全然欲しい能力ではないけど、自分と他の人の能力（というか性格）の差分で認識できていないものがある気持ち悪さ。

7話。グラスプハートを寸前で回避するのすごすぎ。「なんで教えてくれなかったんだ」はさすがに感情がこもっているというか、かわいそう。きちんと考えて行動していて、それでも仲間の命を犠牲に生きることだけを許される状態。付いてきたドワーフがわりと平然としている。

リコリス・リコイル #8

お金を子供に配るとこよくわかんなかった。千束と真島がなんか仲良くしてるとこよかった。もう男女間の友情も百合でいいんじゃないか。たきなも今回よくて、千束と嚙み合っていないところが尊い。千束周りが不穏。

異世界おじさん #5,6

5話。樋口一葉うそだろって思ったら2004年なのでアニメのミスっぽい。換金で凍って殺意を感じてという流れ笑った。

6話。翻訳能力で精霊と話せてたというのはいい回収の仕方。かわいい魔物を逃がして襲われるの好き。ハーレム展開は無理があるだろ。まあおじさんの人生経験が特殊というのはあるだろうけど。やっぱりパーカーいいね。

異世界薬局 #5,6

5話。最後の陛下かっこい～。ずっともやもやしてた部分に一言言ってくれた。なるほど主人公サイドから出る言葉じゃないのね。上手い構成だ。好きではないけど。

6話。海のシーン、なんやねん。やっぱり妹もかわいい。ファルマが狙われている。見てる側としては何を信用していいのかわからなくなる。EDのロッテが好き。

邪神ちゃんドロップキックX #8

女の子の体がかわいい。服もかわいい。ドルフィンキックはいいタイトル改変。

ダンジョンに出会いを求めるのは間違っているだろうかIV #4,5

4話。状況が絶望的すぎる。

5話。完全に運という感じがするけど、ここで回復できたのは大きい。魔石を食って更に絶望的と思ったがベルくんが強すぎた。相変わらず作画だけはいい。

その他

ガンスリンガーガール #1-5

女の子がかわいい。「崖の上のポニョ」を見たとき、よくこんな趣味丸出しの作品を世に出せるなと思ったのを思い出した。そのくらいかわいい。そもそも少女と銃の組み合わせが良いというのはあって、「リコリコ」に関連してこの作品の名前が出されるのも頷ける。でも、かわいさの種類というかヤバさが全然違う。