01/16(月)

午後4時起床。30分近くかけて布団から這い出てインターン先の定例会・勉強会に参加した。

先週の進捗は、金曜日の1on1でこの1週間何をするか決まったということのみ。まだ手を付けていない。簡単な修正なので、今週金曜日にある次の1on1までに終わらせることを期待されている。それくらいはさすがに達成したいものだ。

勉強会はKaggleの参加記だった。最近終了したコンペでめちゃくちゃ良い順位を達成されたらしい。機械学習は使わなかったとのこと。そして、機械学習を使わない解法が強いコンペだということが、順位表の上にいるチームの顔ぶれから分かりやすかったということが語られていた。競プロで順位表から得られる情報といえば問題の難易度がメインで、誰それが解いているから解法は○○だという推論は当てにならないと感じている。このあたりKaggleと結構違うのかも、と面白く思っていた。

とても好きな音MADが流れてきた。「テイキョウ・ヘイセィ・ダイガク」と言えば超有名な音MADだが、それとは別の人が勝手に裏バージョンを名乗って投稿している。正直ただの二番煎じだろうと思いながら見たらかなり完成度が高くてびっくりした。テンプレをなぞるだけではなく独自性もしっかりあって、しかも滑っておらずちゃんと面白い。このくらいネタが盛りだくさんのほうが好みだから、正直本家より好きかもしれない。

www.nicovideo.jp

先週の週記を書いていた。午後9時過ぎに投稿。いつものように校閲できていない。火曜日のセミナー準備のため月曜日に時間が取れないのがかなり厳しい。火曜日夜以降だと気持ちが離れてしまっている。

Amazonでパスタやパックご飯を購入した。少し前にお酒を買った時もそうだったが今日もAmazonポイントが使えず、なぜだろうと調べたところ、どうやらAmazonギフト券との併用ができないらしい。ほぼ確実に、自分のギフト券残高がなくなるより今のAmazonポイントが無くなるほうが早いだろう。今はほんの数百円程度なので諦めも付く。

セミナー準備を始めた。先週以下のようなことを言っていたが、今日に至るまで結局何もわかっていない。深夜までもう一度粘ってみるもどうにもならなかった。

昨日完成させるのを諦めた証明二つについては、片方は議論しているうちに思いつくことができたが、もう片方は何もわからず。自分で考えるのも苦しいためネットで誰かに尋ねたいところだ。
週記（2023/01/09-2023/01/15） - kotatsugameの日記

とりあえず助けを求めるツイートをして、明日のセミナーはここを飛ばして先の話を始めてしまおうかなと考えていたら、maspyさんからリプライを頂けた。そこにあった資料や方針を確認し、確かに行けそう！という気持ちに。ということでこれを発表することにしたのはいいのだが、その時間から読解して発表できる形に持っていくのに苦労し、午前5時までかけて何とか完成させた。

方針として、サイクル C、点 p に対して

f(p) = p から右方向に無限に進んだときに C を交わる回数

とて、f(p) の偶奇で内外を特徴づけることを目指します（競プロでもあるやつ）。

微小な回転により線分と辺が重なるなどが起きないとしてよくて、ぴったり頂点を通るところは適切に定義します。
— maspy (@maspy_stars) 2023年1月16日

ゴミを出して午前6時前就寝。布団に入ってから完成したと思ったセミナー準備の穴に思い至り、修正を考えながら寝入った。

01/17(火)

午前9時半起床。大学に向かい、購買でパンを買ってから教室に行った。購買が開店するのはセミナー開始と同じ午前10時なので、今日も微妙に遅刻ということ。

午前中は同級生の発表。今日はη-変換に関する定理を二つ示していた。証明はラムダ式の構成を見て丁寧に行う必要があり、大変そうだった。

午後0時半に終了し、購買で昼食を買って、食べている間に博士課程の方のセミナーが始まった。先週資料による定義の食い違いを発見したが、これは博士課程の方が本を誤読していただけのようだ。しかしそれ以外の部分も複雑で解釈に疑問が残る。定義がどう使われるかは別の論文を読む必要があるらしく、今日は解決されなかった。次回以降で解決されるのかもわからない。

本に書いてあるものと論文に書いてあるもので定義に食い違いがあっておかしいということを発見し、指摘した。来週に持ち越し。
週記（2023/01/09-2023/01/15） - kotatsugameの日記

午後2時過ぎに終了。少し休憩して半から自分のセミナーとなった。昨日寝る直前に発見したミス以外の部分は問題なく発表できたはず。ミスは結局修正できていないので、今日は諦める気満々だったが、なんだかんだ先生と同級生は1時間くらい考えていた。自分は早々に諦めてmaspyさんにリプライを送っていた。結局解決せず、午後5時過ぎ終了。

すいません、「左から順にPi……」のくだりで詰まりました。3つのregionのどれかが非有界であることを示したりしたいのですがどうにもなりません。何か手はないでしょうか
— こたつがめ (@kotatsugame_t) 2023年1月17日

学食で食事して帰宅。自分が入店したすぐ後5限終了の時刻になり、レジ待ちの列が学食の外まで伸びていた。

疲れ果てて帰宅し、かなり長い間YouTubeを見たりTLを見たりしてボーっと過ごしていた。この後は何をしようかなと考えて、ふと思い立ってICPCの参加記を完成させにかかった。ほとんどの部分は年明け最初の週に完成していて、あとはまとめっぽい部分を書くのと文章の手直しをするだけ。相変わらず時たまYouTubeを見ながらの作業だったため結構時間がかかり、投稿は午前2時になった。

kotatsugame.hatenablog.com

今回は5年間の振り返り記事も同時投稿。といっても大会の成績と参加記をまとめただけで特に何か文章を書いたわけではない。本当は書こうとしたのだが、そういうのは横浜の参加記のほうにまとめて、振り返り記事は単なるまとめページの意味合いでできる限りシンプルにしておいた。

食事してからまたYouTubeに戻り、しばらくして布団へ。なろうを読んでいたら寝落ちした。午前4時くらいだった。

01/18(水)

午後1時から2時までは起きていた形跡がある。なろうを読んでいた。

午後6時起床。布団でしばらくスマホを触ってから起き上がった。

今日は生命情報システム科学のレポート提出期限。相変わらずClassroomの課題には期限が設定されていないが、講義スライドにそう書いてあった。まったく非道なことをする教員である。

今回の課題は与えられた二つのデータを観察し比較して考えを述べよというもの。扱うデータはFASTQ形式で与えられており、この形式は単純なのでライブラリに頼らずとも自分で簡単にデータ読み込みの実装ができる。比較にプログラムを使ったならそれも提出せよと言われていたので、せっかくならとColaboratoryでレポートを書いた。

特に何事もなく午後10時くらいに完成。Classroomの課題提出画面でGoogleドライブからColaboratoryのファイルを直接提出すると、そのファイルのオーナーが自分から教員に切り替わるようだ。つまり提出したものを後からこっそり修正することができなくなるわけで、連携が実にうまくできている。

ラノベを読み始めた。日付が変わるくらいに「迷子になっていた幼女を助けたら、お隣に住む美少女留学生が家に遊びに来るようになった件について」3巻を読了。前半の運動会のシーンは主人公がこれでもかというくらい活躍していて、目立っていて、最高だった。その後のデートシーン二つもいい感じ。ストーリーとしてはいよいよ主人公の過去が明かされてかなり辛いが、好みのシーンが多かったため全体としてみれば良かったという感想になる。

来週は集中講義のためセミナーができない。そのしわ寄せが今週に来て、なんと明日もセミナーが行われる。朝方までそれの準備をしていた。昼からスタートで5限前に終わるため、時間が普段より短くなる。よって量も控えめでよいとのことで、昨日maspyさんに送ったリプライに頂いた返信をまとめた後、もう一つ補題を扱うだけで終えた。とはいえ今日も午前5時くらいまでかかっている。

まだ睡眠時間に余裕がある。ハーメルンやラノベを読んでいた。

今日のハーメルンは新作でも更新分でもなく、読み返し。主人公の設定もキャラも非常に好みで、この先の展開が楽しみで楽しみで仕方ない。U7のライブはおそらく行われるだろうが、どのように描写されるのだろうか。自分で妄想してニヤニヤしたりもしている。それくらい好きな作品だ。

syosetu.org

午前7時半就寝。

01/19(木)

正午過ぎ起床。大学に向かい学食で昼食を摂り、午後1時からセミナー。

前半は同級生の発表。今日は公理系をいくつか用意して何かする話。内容的にはそれなりに長くかかりそうだったが、ちょっと詰まったところで先生が切って90分ちょっとになった。

後半は自分の発表、の前に、同級生に火曜日の議論の穴を埋めるアイディアがあるらしいのでそれを聞いた。なんと見事に解決していた。一昨日maspyさんから教えて頂いた方法と異なったので、一応そちらも発表した。昨日準備した補題について少し触れて、こちらも90分くらいで終了。

購買でラノベを購入してから5限のTAへ。今日の発表は多次元空間における「球」の表面積や体積を求める話だった。この話題に関しては実は高校生の頃に調べていたことがあるので、自分にとってかなり懐かしいもの。当時は適当な座標軸に沿って切ることで一つ下の次元における球の表面積・体積に帰着して求めていたはず。今日はそうではなく、謎の等式から無理やり表面積の式を出し、それを積分して求めていた。

謎の等式について少し解説。 $n$ 次元の点 $x=(x_1,\dots,x_n)$ について $|x|=\sqrt{x_1^2+\dots+x_n^2}$ とし、値 $\exp(-|x|^2)$ を考えて空間全体で積分する。遠くに行くほど値が急激に小さくなるので、この積分値は有限。というか具体的には $\left(\int_{-\infty}^{\infty}\exp(-x^2)dx\right)^n=\Gamma(1/2)^n$ となる。

一方、 $|x|$ が同じ $x$ をまとめて計算すると、 $r=|x|$ で積分するとして $\int_0^{\infty}\exp(-r^2)S_nr^{n-1}dr$ となる。ここで $S_n$ とは単位半径の $n$ 次元球の表面積で、 $r^{n-1}$ 倍することで半径 $r$ の時の式になる。 $S_n$ は定数なので外に出せて、残りはこれまたガンマ関数で表すことができ、先ほどの式と比較することで $S_n$ が出るようだ。

なかなか難しかったが発表はかなりしっかりしていたように思う。板書の字もきれいで良かった。

学食で食事して帰宅。今日も疲れ果てておりTLやYouTubeで時間を無為に過ごした。2時間ほど経ってから2月のラノベ新刊チェックと注文の作業を行った。今回は26冊。嬉しい新刊情報を二つばかり記録しておく。

一つ目は「Vのガワの裏ガワ」2巻。1巻が出たのが11月だったから、たった3か月で新刊が出たということ。無事続刊してくれたことも嬉しいし、それがこんなに早く読めるというのはもっと嬉しい。

mfbunkoj.jp

二つ目は「世界で一番『可愛い』雨宮さん、二番目は俺。」。結構前にアイドルとかモデル、芸能人というキーワードでなろうを漁っていた時に読んだ作品で、結構好みだったという記憶がある。最後の更新から1年以上経過してほぼ忘れ去っていたところ、いきなり書籍化を知らされてびっくりした。

gcnovels.jp

その後日付が変わるまでゼミの後始末みたいなことをしていた。今日聞いた同級生のアイディアをちゃんと証明にまとめるという作業。紙に書き、スキャンして先生に送った。

ABC285-Exを解いた。形式的べき級数で表されている部分が重複組み合わせを使った和の形になって、一向に閉じた状態にできなかったため、解説を開いて結構読んでしまった。

Submission #38159986 - AtCoder Beginner Contest 285

朝方までインターンの作業をしていた。久しぶりに触ったら依存ライブラリのアップデートか何かがあって、ちゃんと動く状態にするまで結構時間がかかってしまった。それさえできれば今日実装するものは簡単……と思っていたら、ライブラリの仕様にない内部の変数を触っていた部分でうまく動かないケースがあって困ってしまった。そのライブラリのコードを読んで何とか修正したが、結局仕様にない使い方をしているままのため、これもいずれ動かなくなるのだろう。

外から触られることを想定されていなさそうな_cellという変数を直接見ることになった。
週記（2023/01/09-2023/01/15） - kotatsugameの日記

1時間程度日記を書き、午前7時就寝。

01/20(金)

午後2時ちょっと前に起床。すぐ1on1が始まった。

自分からの進捗報告は昨日書いたコードの説明。特に問題なさそうでこれはすんなり終わった。ツールの下調べというタスクも振られていたので、残り時間はそれについて話していた。実はこのツールが要求するライブラリのバージョンと他のライブラリのバージョンが合わず、昨日もかなり苦労していた。結局どうやっても合わなさそうだと分かったが、合わないままでも動いたのでまあいいだろうということに。

終わってから大学に向かった。購買でラノベを買うだけのつもりだったが床屋が空いているのを見て思わず入店。散髪し、学食で夕食を摂って帰宅した。サークルはサボってしまった。

古典部シリーズの愛蔵版第1弾をAmazonで注文した。すっかり忘れているうちにリアル書店での予約は締め切られてしまったらしい。何はともあれ買えてよかった。Amazonギフト券を使えるのも嬉しい。

地元で買えるとそのまま実家に安置できるので嬉しいが、タイミングが合わなければ仙台の本屋で予約することになるだろう。限定生産とあるのでちゃんと予約を忘れないようにしたい。
週記（2022/12/12-2022/12/18） - kotatsugameの日記

しばらくラノベを読んで、午後9時からSRM844に出た。出場した赤以上23名のうち12名までもがRoom1に割り振られていた。

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19550

Easyはdp。状態と遷移を掛けると10⁸になってちょっと怖い。注意点としてcakesは昇順に使う必要がある。これをしないとサンプルで落ちるのは非常に優しかった。

Medは難しかった。 $A\times B\times C$ の直方体の表面積は $2(AB+BC+CA)$ なので、あらかじめ $N=\lfloor{\rm paperArea}/2\rfloor$ としておく。 $AB+BC+CA\le N$ が条件なので、 $A$ を最大化する場合整数という条件を無視すれば $A=B=C=\sqrt{N/3}$ となる。よって $1\le A\le\sqrt{N/3}$ がわかる。これくらいなら全探索可能。

ここからなかなか先に進めなかった。 $AB+BC+CA=(B+A)(C+A)-A^2\le N$ となるので $B+A=\left\lfloor\sqrt{N+A^2}\right\rfloor$ とするのがよいかとも考えたが、サンプルが合わない。しかし $B$ の範囲は $A\le B\le\sqrt{N+A^2}-A$ と分かった。この時 $C$ は単に最大値を取ればよいので、 $C=\left\lfloor\frac{N+A^2}{A+B}\right\rfloor-A=\left\lfloor\frac{N-AB}{A+B}\right\rfloor$ 。

このような $B$ と $C$ に対して $ABC$ を最大化するのが目標である。 $C$ が整数という条件を忘れ、 $B\times\frac{N-AB}{A+B}$ が $B$ に対してどういうグラフになるか微分して計算してみると、 $B\lt\sqrt{N+A^2}-A$ なら微分係数が負になることが分かった。つまり先に求めた $B$ の範囲に対しては $B$ が大きくなるごとに単調増加する。

よって $B$ を降順に探索し現在の解を更新しなくなれば打ち切るという枝刈りが思いつく。解の初期値を $\left\lfloor\sqrt{N/3}\right\rfloor^3$ にしておけば十分高速そう。注意点として、 $ABC=AB\times\left\lfloor\frac{N-AB}{A+B}\right\rfloor$ ではなくあくまで $AB\times\frac{N-AB}{A+B}$ と解を比較しなければならないことに注意。オーバーフローが怖いのでfloorやceilを取って緩めに判定した。

計算量はわからないが乱数で試したところ十分高速だったため提出。この時点で20位ちょっととかなり低い順位だった。Hardには10分しか残せずそのまま終了。

チャレンジは自分は何もしなかったが、Medがボコスカ落ちていてびっくりした。さらにシステスでも大量に落ち、無事2完した自分の順位は8位まで上がった。レートは2894→2897(+3)でギリギリ耐え。赤が大量にいたRoom1はチャレンジで全部落とされ切ったようで、システス落ちが一人もいなかったのですごいなあという気持ちになった。

夜中はラノベを読んでいた。「完璧な俺の青春ラブコメ」を読了。非常に面白かった。主人公は顔も良く、勉強も運動もできて、おまけにコミュニケーション能力も高い。まさに完璧と言う他ない設定でかなり好みである。ストーリーについても、初めの方はいかにも不穏そうな空気を醸し出していたのに、恐怖していたドロドロした展開は最後までなく、純粋に楽しい気持ちで読むことができた。総じて最高。

朝まで日記を書いて午前9時前に布団に入った。ちょっとなろうを読もうとして、すぐ寝落ちしたらしい。

01/21(土)

午後3時頃に生協の弁当を受け取って、またすぐ寝た。午後6時半起床。布団でずっとなろうを読んでいて、午後8時を過ぎてようやく布団から脱出した。

昨日読んだラノベは本当に好きだったので読了ツイートに感想を書いていたが、それがアキバBlogで引用されたらしい。FFの方がツイートしていて見つけた。結構嬉しい。

「完璧な俺の青春ラブコメ」読んだ！非常に良かった、主人公が完璧すぎて最高！話も重そうな始まりだったのにドロドロしていなくて、最後までずっといい気分で読めた！
— こたつがめ (@kotatsugame_t) 2023年1月20日

blog.livedoor.jp

食事して少し日記を書き、午後9時からABC286に出た。

UL Systems Programming Contest 2023(AtCoder Beginner Contest 286) - AtCoder

Aから面倒。変なことはせず素直にC++で実装したのに、区間の始点や長さを間違えまくって合わせるのに少し手間取った。Bはsedで一発。Cは文字の置換より先にrotate操作を全部行うとしてよく、その回数を全探索。

Dは個数制限ナップザック問題なので、何も考えず $B$ を2べきに分解して解いた。あとから単に $B$ 回遷移しても間に合うことに気づいた。

Eは問題文にある通りの値のペアを距離と見てワーシャルフロイド。辺の重みとしてそれが向かう先の都市で売られているお土産の価値も含めた。経路の始点については出力時に加える。

Fはfunctional graphにおいて各頂点から $N$ ステップ移動した後の頂点の情報から $N$ を復元する問題。グラフとしてはループの集まりしか考えなくてよく、このとき $N$ をループの長さで割った余りがいくらかという情報が得られる。ループの長さを互いに素にして、中国剰余定理で復元すれば良い。

難しいポイントは $N\le 10^9$ かつグラフの頂点数が110以下というところ。単に素数を並べるだけでは29まで使う必要があり、足りない。2²などべき乗を使えば良いのでは、と思いついて適当に全探索すると $2^2\times 3^2\times 5\times 7\times 11\times 13\times 17\times 19\times 23$ が見つかった。調べた範囲ではこれが唯一の解だった。

Gはちょっと面白い。歩道をマルチグラフと見ると、使った辺が全て連結で、次数が奇数の頂点が0個または2個しかない。そのように辺を選べればよい。ここで、 $S$ に含まれない辺をすべて2回通ることを考える。すると $G$ が連結という条件から自動的に使った辺も全て連結になる。あとは次数に関する条件を満たせればよい。

$S$ に含まれない辺たちからグラフを作ると、その連結成分の中ではある程度好き勝手できる。具体的には2頂点ずつ次数の偶奇を入れ替えられる。次数が奇数の点が奇数個あるとどうしても1個残ってしまうようだ。このチェックをすべての連結成分に対して行い、残った点の数が合計で2以下になっていればOK。そうでなければ不可能。

Exは結構簡単だった。線分 $ST$ が $C$ と交差しない場合は直線で向かえば良い。そうでない場合、 $S$ から $C$ 上の点に移動し、 $C$ 上で別の点に移動してそこから $T$ に行くということになる。真ん中の部分は多始点多終点の最短経路問題になる。グラフがループなので簡単に解けるが何も考えずdijkstraを使った。

問題は、 $S$ または $T$ から $C$ の内部を通らずに直線で辿り着ける $C$ 上の点をどう判定するかについて。1点の判定に $O(N)$ かかると思ってしばらく判定回数を減らす方向で考えていたが、そもそもの判定が $O(1)$ で行えた。 $p_i=(x_i,y_i)$ とすると、 $S$ から $p_i$ を見たとき右手に $p_{i-1}$ 、左手に $p_{i+1}$ がある場合 $S$ から $p_i$ に辿り着けないらしい。外積で判定できる。

出したら通った。1時間ちょっとでノーペナ全完、順位は9位。Fでループの長さの組を見つけるのに手こずっているが、それがなくても賞金には遠かった。Exは $S$ と $T$ を含めて凸包を取れば $C$ を経由するときの距離が簡単に出せるらしい。頭が良すぎる。

コードゴルフ。AはAWKで縮めていたがVimにボロ負け。行の範囲を指定すると、それを一気に別の行の下に挿入するmoveという命令があるらしい。これを知らないし、知っていたとしてもその周りの部分を縮めきれたとは思えない。

Bはやはりsedで速度差で勝ち。DはRuby。コンテスト中に自分で80Bのコードを書いたが、コンテスト直後に見ると同じ長さのコードがもう一つ提出されていて、そちらが3B縮み最短になっている。他は手付かず。

午後11時半からCF #845 div.2。

Dashboard - Codeforces Round 845 (Div. 2) and ByteRace 2023 - Codeforces

Aは操作で挿入される要素のparityが元の要素と変わらないため、単純に1要素削除だと思ってよい。

Bは $p$ の内部の転倒数、 ${\rm rev}(p)$ の内部の転倒数、 $p$ と ${\rm rev}(p)$ にまたがるペアによる転倒数の三つに分けて考える。前二つについては、 $p$ で転倒数に寄与するペアは ${\rm rev}(p)$ では寄与せず、逆も然り、ということで合わせて $n(n-1)/2$ になる。三つ目は明らかに $n(n-1)/2$ 。よって答えは $n(n-1)n!$ である。

Cはちょっと難しかった。smartnessを見ながら尺取り法のようなことを行う。各topicを誰が担当しているか管理し、逆に人ごとに担当するtopicの数も数えておいて、それが0になった人をチームから抜いていくという方法で行える。問題はチームに人を追加するときの処理について。

担当するtopicすべて、つまりsmartnessの約数をすべて見る必要がある。事前に $a$ の重複を取り除いておけば見る個数は十分少なくなるが、そもそも約数を列挙する部分で $O(\sqrt a)$ かかってしまう。どうしようもないので祈りながら提出したら爆速で通った。

Dはちょっと面白い。時刻 $t$ におけるある頂点の値は、そこから $t$ 段下った子に最初に割り振られた値のbitwise XORになる。そのような子が存在しなければ当然値は0。存在するとき、子から一つ選ぶと、それ以外の頂点にどんな値が割り振られていても選んだ子の値次第で0か1かが決定するから、1になる割り振り方は必ず $2^{n-1}$ 通りだとわかる。よって各頂点について値が1になり得る最大の $t$ を求めるだけになり、単なるdfsで解ける。

Eはちょっと苦労した。辺の向きを入れ替える代わりに逆辺を追加すると考えてもよい。その状態である頂点から他のすべての頂点に辿り着けるなら、通る有向パスたちは木になるように取れて、それに沿って改めて辺の向きを決定できる。

追加した逆辺込みで強連結成分分解したとき、入次数が0の成分が一つだけであるかをチェックしたい。最初に分解してあとはマージしていけば良いかと思ったら、マージで内側に飲み込まれてしまう辺を入次数にカウントし続けてしまうようで2WAした。コストで二分探索すると判定の度に真面目に分解できるためOK。

Fは分割統治。区間の最大値が固定できると、考える値は最大値と累積XOR二つのXORになって、そこから片方の端を固定するとbinary trieで最大値が求まりそう。しかしこのbinary trieには考えている区間の値だけを乗せておきたくて、少し難しい。

区間の最大値で分割すると区間の幅が抑えられないので、binary trieを構築する段階でTLEしてしまう。そこで区間の真ん中で分割することにした。ABC282-Exの解説を見ながら実装。1.8secで通った。

Editorial - HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282)

1時間17分で全完、25位。

ベッドのシーツや掛け布団がずっと春・秋用だったのを冬用に変えた。流石にもう耐えられなかった。ちなみにTwitterや日記でずっと布団という言葉を使っているが、これは自分にとって寝床一般くらいの意味合いで、実際はベッドで寝ている。

ABCの画面録画＋音声をYouTubeに投稿した。編集は一切行っていない。実況と銘打っている通りコンテスト中はあれこれ口に出しながら解いていたつもり。普段はわざわざ音声を入れないのだが、今日はたまたまその気になっていた。そういうタイミングで全完できたのも運が良かった。

www.youtube.com

朝までなろうを読んでいたが途中で放棄した。興味が薄れたのと、やらなければならないタスクが溜まっていたから。一応記録しておく。

https://ncode.syosetu.com/n7707gs/

日記を書き、さっきとは別のなろうを少し読んで午前11時就寝。タスクが溜まっているとは何だったのか。

01/22(日)

午後6時起床。そのまま布団でなろうを読んでいたら、午後7時半頃に今日の昼行われたJOIG本選の過去問が上がっているのを見つけ、飛び起きた。

JOIG 2022/2023 本選過去問 - AtCoder

Aはよい。Bはまともな性質がなさそうだが単に $O(N^2)$ でシミュレートすればよい。Cは音の強さが固定なので、家から最も近い座標を左右で求め、比較すればよい。

Dは葵が操作する行を全探索し、各列の表のコインと裏のコインの枚数を差分更新する。凛はそれを見て貪欲に操作すればよい。 $O(HW)$ 。

Eは $k$ を全探索すると左右が分割できるので、それぞれ解ければよい。実際、 $HW$ 頂点のUFを持って見ている範囲の頂点だけマージしていけば可能。

Fは解けていない。

コードゴルフ。Aは追加してから条件をチェックして削除すると書きやすい。sedで実装して満足していたらVimで縮められた。Bは真面目に数列の要素を一つずつ減らしていかなくても必要な値は計算できる。これで結構縮んだが、まだ隙があったようで取られた。CはOctave。以降は手付かず。

午後9時からARC154に出た。

AtCoder Regular Contest 154 - AtCoder

Aは $A$ をできるだけ小さくするのが最適とエスパー。桁ごとに数字を見て、 $A$ のほうが小さくなるようにswapしていけばよい。

Bは操作を分解し、最初に削除を全部行ってそれから挿入すると思ってよい。 $S$ と $T$ を構成する文字の種類・数が異なれば一致させることができない。そうでない場合、削除しなくてよいのは $S$ のsuffixであって $T$ の部分列になっているもののみだから、その長さの最大値を求める。

Cは $i=N$ で操作できるのでちょっと難しい。もしこの操作ができなければ、要素をコピーして区間を広げていくと思えるので、 $B$ から隣接する重複要素を取り除いたものが $A$ の部分列になっていることが必要十分条件になりそう。正確には要素が後ろにコピーできないので少し違う。

$i=N$ で操作するのは $A$ をrotateするのとほぼ同じに見えた。そこで、逆に $B$ をrotateしてから先程の判定を行うことにした。rotate状態が $N$ 種類あって毎回 $O(N)$ で判定可能なので、間に合う。しかしWA。

冷静に考えると、 $B$ のどの隣接する2項も等しくなければrotateはできない。この場合はそもそも操作後の状態としてはありえないので、最初に $A=B$ であるか判定するだけでよい。逆にそういう2項がある場合はそこを使って $B$ をいくらでもrotateできるので、最初にちょっと触れた「要素を後ろにコピーできない」制限も回避できる。これで出したら通った。

Dは難しかった。質問の回答がYesだとあんまり情報がないため、なんとかしてNoを見つける必要がある。 $i=j$ とすると見つけやすいのではないかと考えた。 $k$ を固定し、 $i=j\ne k$ に対してすべて聞くことで、 $2P_i\le P_k$ なる $i$ を集めることができる。これを何回か行うと $P_k=1$ なる $k$ を見つけることができる。

今度は再帰の帰りがけに各要素の値を決定していくのかと思っていたが、実はこの時点で $P$ をソートすることができる。 $P_l\ne P_r$ という条件のもと、 $P_l\gt P_r\Leftrightarrow P_l+1\gt P_r$ となるからだ。

最初に $k$ を見つけるとき、固定する $k$ をランダムに決めることで候補が4分の1になることが期待できる。後からソートする分も合わせるとクエリが微妙に足りない気もするが、とりあえずジャッジを書いて手元で試してみることにした。

std::sortを使うと全然足りなかったが、std::stable_sort、つまりマージソートを使うことでかなりいい感じになった。数回試して通りそうだったので提出。最初の提出では1ケース落ちてしまい、実際手元のランダム順列でも落ちるケースを発見したものの、乱択だから何回か出せば通るだろうと思って全く同じコードをもう一度出したら通った。

残り1時間はEとFを半々くらいで考えていた。Eは何もわからず。Fは下の記事と同様にして $k$ 種類持っている状態から新たに1種類ゲットするまでにかかる回数の確率変数を $X_k$ とおくと、 $f_k(x)=\sum_n E[X_k^n]x^n/n!$ という指数型母関数を $k=0\dots N-1$ で掛け合わせられれば解けることまではわかった。

コンプガチャに必要な回数の期待値の計算 | 高校数学の美しい物語

4完32位。コードゴルフはAをRubyで縮めたのみ。

今日も画面録画＋音声を撮っていたので、YouTubeに投稿した。E以降はバッサリカットした。最近新しい動画が見たいですというコメントを頂いたので、昨日今日とマイクに向かって喋りながらコンテストに出てみた。しかし編集する余力はない。ゆっくり実況など夢のまた夢である。

またUnratedのコンテストしか動画にしていないのもちょっと気にしている。本当はAGCの実況を作ってみたい。しかし今の形式だと紙の上での試行錯誤が動画に反映されず、面白くなさそう。板タブで書くのは面倒だし、紙に書くと動画で見えない。やはり手元を映してみたい。

www.youtube.com

実は、コンテスト参加時の画面の録画自体はここ2年ずっと行っている。今その動画ファイルが300GB以上あってPCのSSDを圧迫しているが、しかしこれはShadowPlayでキャプチャした動画ファイルをそのまま保存しているからで、適当にエンコードしておけば6分の1くらいになることに気づき、今日はそれからずっとエンコーダーを動かして圧縮に勤しんでいた。

エンコードしているPCはCPU使用率が100%に張り付いて使いづらいので、別のPCで日記を書いていた。また結構な頻度でなろうに気を取られていた。

午前8時過ぎに布団に入る。なろうを読んでいたら午前9時頃寝落ちした。来週一週間、午後3時から6時まで集中講義である。ただ明日はオンラインになったのでこの時間までのんびり起きていた。