07/19(月)

午後3時くらいに目を覚ます。TLにチュウニズムのアップデート情報が流れてきた。8/5の更新で、CRYSTALのマップ全部とイロドリミドリのマップが1つ消えるらしい。CRYSTALはラスボスのマップが残っていて、イロドリミドリのマップは手つかずなので、都合1500マスくらい走る必要がありそうだ。非常にまずい。

先週のARC123Cについて、実は操作回数は最大でも5回らしい。かなりびっくり。僕は60回で見積もって、これだとちょうどlong longに詰め込めるから簡単で、うまい問題だな～と思っていたのだが……。

TLを眺めたりYouTubeアプリで動画を見たりした後、また寝た。次に起きたのは午後9時だった。

昨日投稿した色変記事にかなりアクセスされているようで、今日だけですでに700回くらいアクセスされている。これで週記も投稿できていれば、合わせて1日で1000回アクセスくらい達成できたのかもしれないが、書きあがっていないものはしょうがない。しばらくTwitterでエゴサーチなどした後、溜めていた分を書き始めた。

AtCoderのコンテストについて書く段になり、本当は当時の順位表など参照したかったのだが、ちょうどAtCoderのメンテナンスが始まっており、見られなかった。仕方なくTwitterや録画していた画面キャプチャから情報を補完して書いた。

午前4時くらいになってようやく書きあがり、投稿。先週も20000文字を超えてしまった。確か初期の週記は10000文字に満たないくらいだったから、1年で文章量が2倍になってしまったということ。一応人に見てもらうことを前提に書いているのだから、無理なく見てもらえるような分量にしなければならないのだが、解いた問題のコメントだったり、こういうその時考えていたことをネチネチ書いていたらどうしても増えてしまう。

午前5時を待たず、AtCoderのメンテナンスが終了した。ACLのアップデートが本題だったようだ。このアップデートによって使えなくなったゴルフテクが存在する。

【ACLアップデートのお知らせ】
AtCoder Libraryをv1.4にアップデートしましたhttps://t.co/IFWMzsQbv5 https://t.co/HTTBaqz1jj
— AtCoder (@atcoder) 2021年7月19日

ACLのデータ構造の宣言について、コンストラクタ呼び出しがあたかもint型かのように代入で行えることを知った。
週記（2021/07/05-2021/07/11） - kotatsugameの日記

以前のバージョンでは、ACLで定義される構造体のコンストラクタにはexplict指定がなかった。それで、int型を代入することで暗黙的な型変換のためにコンストラクタが呼び出されていた。バージョンアップでexplict指定がなされたため、そのようなコンストラクタ呼び出しをするコードはCEになるようになった。つい最近知ったゴルフテクだし、実際に使われたものとしても、探した中では以下の5月初めに提出されたコードが最古だから、かなり寿命が短かったテクである。

atcoder.jp

朝方、色変記事に追記する作業をしていた。ありがたくも寝ている間にまた質問がたくさん寄せられたので、それらへの回答を追加した。

実は7/20が提出期限の期末レポートがある。僕の感覚としては月曜日だから7/19なのに、実際はあと14時間もないというバグ。数理統計学のレポートで、自分の関心と数理統計学との関連で自由に論じよ、という課題。書くことは一応ぼんやりと考えていた。コンピュータで正規分布に従う乱数を生成する方法だ。僕が知っている疑似乱数生成の方法は、どれもある区間の整数を一様分布に従って生成することしかできない。よく考えると、浮動小数点数もbit列なのだから、整数を生成するのとfloatやdoubleを生成するのに大した違いはないかもしれないが、どちらも一様分布であることに変わりはない。

GCCのヘッダファイルを覗いたところ、std::normal_distributionの実際の実装は、手元のGCCでもGitHubのミラーでもbits/random.tccにあった。実際のところ、そんなことしなくてもcpprefjpに「マルサグリア法を使う」と書いてあったのだが、念のため確認した。

gcc/random.tcc at 16e2427f50c208dfe07d07f18009969502c25dc8 · gcc-mirror/gcc · GitHub

std::generate_canonicalという、整数を生成する乱数生成器を受け取って $[0,1)$ の浮動小数点数を返す関数が使用されている。これも興味深い。実装を読んだところ、2進数の桁数を指定すると、それを下位桁から埋めるように整数を生成してはめ込んでいくようなアルゴリズムらしいが、ここまで行くともはや数理統計学とは何の関係もないし、割愛した。

マルサグリア法の細かい話を書こうとしたが、眠くて頭が働いていないのか、理論的な話が全然分からない。いったん寝て、また明日レポートを仕上げることにした。午前2時就寝。

07/20(火)

午後8時起床。レポートの続きをする。

マルサグリア法は、 $0\lt x^2+y^2\lt 1$ を満たすような $-1\lt x,y\lt 1$ を生成したとき、 $X=x\sqrt{\frac{-2\log(x^2+y^2)}{x^2+y^2}}$ と $Y=y\sqrt{\frac{-2\log(x^2+y^2)}{x^2+y^2}}$ がそれぞれ標準正規分布に従うというアルゴリズムである。これを理論的に示すには、講義ではやっていないはずだが、この記事にある感じの計算をすればよさそう。

2次元確率分布の変数変換（計算してPythonで確認）

$x=\frac{X{\rm exp}\left(-\frac{X^2+Y^2}4\right)}{\sqrt{X^2+Y^2}}$ 、 $y=\frac{Y{\rm exp}\left(-\frac{X^2+Y^2}4\right)}{\sqrt{X^2+Y^2}}$ となる。かなりゴツい形をしているが、実際にこれでヤコビアンを計算してみると、いい感じに $\sqrt{X^2+Y^2}$ が消えてくれて $-\frac 1 2 e^{-\frac{X^2+Y^2}2}$ となった。

絶対値を取って $X$ と $Y$ に分離すると、 $X$ に対しては $\frac 1{\sqrt 2}e^{-\frac{X^2}2}$ というような形になる。これはかなり標準正規分布に近いが、微妙に違う。 $\frac 1{\sqrt\pi}$ の違いは、おそらく $0\lt x^2+y^2\lt 1$ という条件を考慮していないことによるものだろう。では実際はどのように計算すればよいのか、とWikipediaを読んだところ、実はボックス=ミュラー法という別のアルゴリズムを高速化したものだったということを知った。そちらを経由して示すべきだったということか。

しかしもうレポートを書くのが面倒になってきたので、計算したら合わなかったということを書いて終わらせることにした。最後に、疑似乱数の話ばかりしていたので、真の乱数である/dev/randomにちょっと触れて終わった。環境ノイズを収集して真の乱数を得るという話は面白くて好きであるが、中身は全然知らない。

しばらくコードゴルフをした後、日付が変わってからTCB38に出た。ちょうどこの時間からだった。いつものように、この週記が公開される前にイベントが終了しているため、結果を書いておく。

https://techful-programming.com/user/event/2189

今回も理論値を達成することができたが、序盤かなり失速してしまった。数え上げというテーマからもわかる（？）ように、どうせmodintをしこたま使うので、最初から貼りっぱなしでやっておけばよかった。1問、modpowを自前で実装してしまったのもかなりのタイムロスだろう。

4問目まではよい。5問目がmodpowを実装してしまった問題。制約が10⁹と思ったより大きくてびっくりした。 $N=K$ というコーナーケースもある。6問目はlong longで管理すれば十分収まる制約だが、そのことを確認するのに慎重になってしまい、結構時間を使った。 $19!\approx 10^{17}$ のようだ。7問目は余事象。8問目はちょっと面白かった。先頭からの累積和として出現した値を管理するbitDPになる。数列の長さは高々10。9問目はケイリーの公式を知っていれば一瞬だが、知らずに解けるものなのだろうか。10問目は木DP。畳み込みが出てくるが、2乗の木DPなので愚直に計算しても間に合う。というか、そこで畳み込みを使ったところで計算量的には良くならなそう。

今日も色変記事に質問と回答を追記した。もう新しく来る質問の数が少なくなったので、そろそろGoogleフォームを閉じるつもりだ。

朝方、院試ゼミの準備としてまた問題を解いていた。今回も2問担当するので、まずこれを解く。1問目は位相の問題で、嬉しいことに瞬殺できた。逆に2問目が全然わからない。しょうがないので頭の中で寝かせておくことにした。

日記を書いて寝ようとしたら、第7回PAST-Mのコードゴルフで更新が流れてきた。解いていない問題だったが、微妙にコードが目に入ってしまい、なんとなく使うアルゴリズムがわかってしまった。考えてみたら、案の定フローに帰着できた。コードゴルフについては、もうどこも縮まないかと思われたが、ふとnetworkxでNoneを頂点に使うことを思いつく。

networkxの頂点にはたいがい何でも使える、というのは知っていた。これまでは別の関数を使ったり、あるいはグラフそのものを使ったりしていたが、これらはどれも1Bかかってしまう。一方Noneは4Bだが、グラフにadd_edgeしたりadd_nodeしたりするとその返り値がNoneになるので、そのまま使うことで-1Bどころか、セミコロンを省けるのでさらに-1Bできる。これを利用して縮め、ほかに適用できる問題がいくつかあったので、それらも縮めておいた。

atcoder.jp

MultiDiGraphを使う問題では、add_edgeするとNoneではなく辺に割り振られたkeyが返ってくるようで、そこだけちょっと変える必要があった。結局これもadd_nodeが必要なNoneの個数分用意できたので、それらを使って思った通りに縮めることができた。

午前9時就寝。

07/21(水)

午後4時起床。昨日寝る前にゴルフした問題から1問縮められていたので、縮め返した。

夜、ホスフィンからリプライが来て、一緒に夕食を食べてゲーセンに行くことになった。午後7時くらいに外出。僕の自転車を止める場所を見繕いながらどこで食事するか相談していたところ、ホスフィンはイオン近くの道路の下にある駐輪場の話をしているのに、僕はイオンの地下にある食事処の話をしていると勘違いするというすれ違いが起きた。イオンの地下にも食べ物屋さんはあるということなので行ってみたらフードコートだったが、かまわずそこで夕食を食べた。

はなまるうどんの大を注文。実ははなまるうどんを食べるのは初めて。信じられないくらい多くてびっくりしていたが、実は丸亀製麺の大よりはなまるうどんの中のほうが多いらしい。なんとなく聞いたことがあるかもしれない。後悔しつつうどんだけはなんとか完食したが、取ってきたいなり寿司はホスフィンに食べてもらった。

午後8時過ぎからゲーセン。今日も閉店までプレイしていたが、入店時間が遅かったのでプレイ時間としては3時間くらい。ずっとマッチングしていたのであまり進捗はないが、チュウニズムのアップデートで削除される曲関係の、8/5から新規取得ができなくなってしまう称号を集めていた。

ラスト3クレくらい使ってMIRACLE RASHの1速フルコンに粘着、見事達成できた。ギリギリまで下げたフィールドウォールがかなり便利で、格段に見切りやすくなった。フルコン目的なので適当に擦っていれば取れるだろうと思っていたが、全然そんなことはない。エアーのタイミングも怖いし、そうでなくてもいたるところでミスが出る。結局普通にプレイした。

MIRACLE RASH 1速フルコン
フィールドウォール便利〜〜 pic.twitter.com/wT8eioqTZ1
— こたつがめ (@kotatsugame_t) 2021年7月21日

マックに寄ってポテトを食べる。明日はホスフィンとたいぺーと3人で家飲みをするつもりなので、ドンキでお酒を買って帰宅した。

あーだこーだーで重大な発表があったらしいということはゲーセンにいる間から気付いていたが、公式のツイートを見て詳しい内容を知った。ABCが8問体制とはびっくりである。

【お知らせ】
ABCが7/31から8問体制に変更になります。
F問題の供給が多く、EやDが圧迫されている問題を解消する目的です。
600点の枠が1問増加し、それに伴って、400,500点レベルの問題が比較的簡単なものだけになり、さらに400点問題の枠が1問増え、400と500に配分される、といった形になります。
— AtCoder (@atcoder) 2021年7月21日

TLに小林賢太郎さんの過去のコントについての記事が流れてきたので、読んだ。これヤバいやつじゃないか？僕の抱いているラーメンズ・小林賢太郎さんのイメージとはそぐわないが、公演メインの活動に移る前、テレビでコントを披露していた時代のラーメンズのことはよく知らないので、実際そういうコントがあったのだろう。燃えそう。

今日開かれていたyukicoder 305を解く。

yukicoder contest 305 - yukicoder

Aはよくわからないが、貪欲に操作してよさそう。投げたら通った。Bは、存在しない素因数を掛けるか、どこかの素因数を1つ選んでいくつか掛け、約数の個数がちょうど2倍になるようにするかしかないと思っていたが、違った。素因数をいくつか選ぶ場合がある。しかし、存在しない素因数を掛けることで必ず条件を満たせるので、探す範囲は50倍くらいまでで十分。約数の個数を数えるのが難しそうだが、新たに掛けた数に含まれる素因数のぶんしか関係しないので、十分速く計算できる。

Cは疲れた頭には非常に辛い。頂点 $1$ と頂点 $N$ から同じ回数だけ辺を辿り、最後に辿った辺のラベルを記録しておく。このラベルが異なるような辿り方を見つけたら、その間を適当に繋げば回分ではなくなる。3回くらいbfs→親を辿ってパスを復元、をする必要があって、変数名など気を使う必要があった。

今日ホスフィンと相談してきたので、それを参考に院試の問題に再挑戦する。小問が2つあって、1つ目は別の定理の証明を参考にすれば解けるんじゃないかという話だったのだが、それを調べようとしたら今解いている問題と全く同じ命題の証明が目に入ってしまった。背理法というワードが見えて、ちょっと考えてみると一瞬で解けた。

2つ目は解けない。1つ目を参考にするのだと思って、久しぶりに「点列による連続性の定義」とか「点列コンパクト」などを調べてみて、ちょっとばかり進んだかなと思ったが、ある所からパッタリ先が見えなくなった。問題を整理してみると、良さそうな定義などいろいろ生えてきていたものの、本質が一切変わっていないことに気づいて絶望。今日は諦めることにした。

寝る前に恐る恐るTwitterのトレンドを見ると、小林賢太郎さんが炎上していた。小学生のころからずっと好きだった人が批判されているのを見るのは本当につらい。問題のコントでは、ホロコーストは否定的な文脈で出ているが、コントによる「いじり」であるかと言われると、該当しないとは言えないだろう。もはや何を言っても炎上は収まらないように思われる。これからどうなってしまうのだろうか。YouTubeに公式で上がっているコント動画たちも消えてしまったりするのだろうか。

かなり落ち込みながら午前7時半就寝。

07/22(木)

午後1時起床。即座にゼミのZoomに入る。

Twitterのトレンドを確認すると、僕が寝ている間に小林賢太郎さんがオリンピック開会式のディレクターを解任されていた。昨日の今日であるから、信じられないほどの速さである。小林賢太郎さんのコメントも出ていたので、読んだ。オリンピックに携わる以上このような問題があってはならないだろうと、考えればわかるが、感情としては非常に悲しい……。

昨日のyukicoder Dを解いた。小さい盤面で実験すると、2進数表現と見て3で割ったあまりがGrundy数になるようだったので、実装してみたら通った。解説はbitの引き算で考えていてなるほどという感じ。

院試の受験票が速達で届いた。出願に成功したようだ。オンラインで試験することになった場合のため、家の環境に関するアンケートに答える必要があるようだったので、答えておいた。アンケート回答の締め切りが結構早くて焦る。

ゼミが終わってからホスフィンとたいぺーが家に来た。大学病院のほうまで出向いて食事をする。最初は焼き鳥屋さんに行くつもりだったが、2店見つかったうち片方は満員、もう片方は休みだったので、ラーメン屋に行くことになった。学生は麺増し無料だったのでお願いしたのがちょっと多かったが、おいしかった。

午後7時くらいに帰宅して飲み始める。

OK！ pic.twitter.com/KBhe63DaVJ
— こたつがめ (@kotatsugame_t) 2021年7月22日

最初はホスフィンがハマっているという大喜利を3人で行っていた。ホスフィンがお題を考えてきてくれたので、小分けにしてGoogleフォームを作り、匿名で回答を投稿、みんなで確認するという形。大喜利はほとんど考えたことがないのでなかなか難しかったが、そこそこ良さげな回答が出てきて面白かった。自分と違う着眼点で答えているものは興味深い。

途中参考資料として動画を再生しようとしていたが、ノーパソから音が出ない（スピーカーがダミー出力しか選択できない）ことが発覚。ちょっと格闘してみたが直らなかったので、結局スマホで再生した。

途中、最近の睡眠不足が祟って少しだけ眠ってしまった。その間にノーパソのTwitterから勝手にツイートされており、涙。yukicoderが開催されていたので問題を見たが、全然頭が働かない。1問目は入力をそのまま出力すればよいように感じられるが、証明が付けられない。最短コードを見るとbashだったので、おそらくddだろうなと思い、それ以上はさすがに縮まないのでわざわざ提出する必要もない。

日付が変わったあたりで大喜利を終え、回答をTLに流した。

こたつがめ、ホスフィン、たいぺーで大喜利やったので、回答をツイートします。
— こたつがめ (@kotatsugame_t) 2021年7月22日

相変わらずノーパソから音が出ないのでもうちょっと格闘してみたものの、諦めてスピーカーをつないだ。以降、YouTubeやニコニコ動画でお互いの好きな動画を紹介しあっていた。午前1時半くらいにお酒がなくなってしまったが、その後もお茶などを飲みながら延々と動画を再生していた。感電MADとか、カロリーメイトのCMに使われたorangestarの新曲とか、ゆっくり実況とか。

僕はラーメンズのコントを1本再生した。公式チャンネルは最初から動画のコメント機能がオフになっているので、今の状況下でも安心して見ることができる。でも相変わらず初見の人にどれをおすすめするべきかがわからない。今の動画を紹介しあう流れなら短めのものがよいだろうと思って、今日も「受験」を選んだ。大体1年くらい前も同様の悩みを得て、この日は「受験」以外にもいくつか見せている。

あとは動画投稿サイトで各々の好きな動画を布教しあっていた。僕はラーメンズが好きなので、コントをいくつか見せようと思ったのだけれど、これといって心に決めていたものがなかったので、かなり迷ってしまった。
週記（2020/09/21-2020/09/27） - kotatsugameの日記

www.youtube.com

朝方、今度はたいぺーが布団で寝てしまったので、ホスフィンと喋っていた。大学生協で弁当を注文するのを忘れていたので注文し、その時にautocompleteが暴発するのを見せたり、相変わらず解けない院試の問題について相談したり。

午前5時半くらいにホスフィンが帰り、床で寝る体勢だったはずのたいぺーも復活して帰った。少し部屋を整えた後、布団に入ってラノベを読み、午前8時半に就寝。

07/23(金)

午後3時起床。即座に院試ゼミのzoomに入る。昨日まで考えていない問題が結局解けていないし、考えたことだけ発表するにしても解答を書いていない。ほかの問題の解答もスキャンしていないので、人の発表を聞きつつ済ませた。

オリンピック開会式についての続報が流れてきた。内容を精査した結果、問題がないものとしてこのまま行うそうだ。これはつまり、小林賢太郎さんの手になる演出が見られるということだろう。クレジット表記から彼の名前が消えてしまうことは悲しいが、彼の作品が世に出るのは嬉しい。しかしどちらにせよ、すでに引退し、さらにこのような事態になった以上、もう彼は表舞台には出ないのだろう……。

ゼミは良かった。僕が解けなかった問題は特別難しいらしく、大体みんな解けておらず黒い安心感を得た。一人の昔の解答を共有してもらい、みんなで読んだ。かなりうまい。僕は収束先の具体的な形が得られず困っていたが、背理法を使うことにすると収束先をそのまま文字で扱って矛盾を導けている。

ゼミが終わってからサークルの解説会の準備をした。ABC210。最初はF問題を扱おうとしていたが、準備時間が1時間しかなかったのでE問題に変更。今日はほかにD問題を解説してくれる人と2人で発表した。先週書いたGoogle Meetのリンクを固定する話は、今日からやってみた。リンクの生成自体はいつもと同じで、それをSlackのチャンネルにピン留めしておいた。

来週の解説会からは固定されたリンクで活動できるように準備しておきたい。
週記（2021/07/12-2021/07/18） - kotatsugameの日記

yukicoder 306に出た。3完。

yukicoder contest 306 - yukicoder

Aは正三角形を作ればよい。2等辺三角形3個に分解して面積を求めると簡単。Bはちょっと難しい。長さについてのヒストグラムで各色の棒を管理する。赤色の棒の長さを決め打つと、他2色で使ってよい棒の本数がわかり、前計算によって2色の棒の組であって使っていけないもの（長さの和が赤色の棒以下になる）の数もわかる。青色や緑色で赤色の棒より長い棒を使おうとすると、2色の棒の長さの和が赤色の棒より大きくなるため、この前計算は最初に全部やっておいても問題ない。コンテスト当時の僕は赤色の棒の長さを決め打つループの中でインクリメンタルに計算する必要があると思い込み、実装がちょっと面倒になっていた。

Cはたくさんの三角形で平面を敷き詰め、反射を直進に読み替えるテク。僕がこのテクを初めて知ったのは、確か高2の時に出た数学甲子園2016だったはずだ。数学甲子園の本選では毎年、与えられたお題に沿って各チームが数学の問題を作り、出来の良いものは前に出て発表することになる。この年に作られた問題の中に、反射を直進に読み替えるテクを使う問題があった。YouTubeで当時の動画を探してみたら、写っていた。以下のリンクを踏むと該当の箇所に飛ぶ。スクリーンにそれらしき図が映っているのが見える。

数学甲子園2016 ダイジェスト - YouTube

探している途中、動画の中に僕の後ろ姿が映りこんでいるのを発見し、懐かしい気持ちになった。のちに競プロ関係で知り合ったり認識した人も数人出場しており、こんなところでニアミスしていたんだなあと思った。

4問目は難しい。考えながら椅子で寝てしまったため、布団に移動。すぐさま寝ようと思ったが、なぜか微妙に目が冴えてきたので、ラノベを2冊読んだ。

1冊目は「サベージファングお嬢様」。数日かけて少しずつ読んだ。面白かった。いい感じの無双系。赤石赫々さんのラノベは読んだ限りどれも主人公の1人称視点で、特に主人公の設定上言葉遣いが普通とはちょっと異なる場合、地の文もそれに合わせた口調になるので、結構特徴的。このラノベでも、主人公は前世が傭兵ということで粗暴な男っぽい口調で、それが地の文に反映されていた。

2冊目は「ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました」4巻。相変わらずキャラクターの名前をほとんど覚えていない。今回も無双してハーレム作っていたなあという感じ。

さらになろうを読んで、午前5時半就寝。

07/24(土)

午後3時くらいに目覚ましで起きる。生協の弁当を待つ。チャイムが鳴ったので出たら、母から送られてきた荷物だった。夏用のシーツ。

布団に戻って弁当を待ちながら寝ていたが、午後6時半くらいにハッと目覚めた。すわ寝過ごしたかと思ってインターホンを確認するも、宅配便以降の来客はなさそう。そこでふと思い当たった。今日は休日なので、生協の弁当配達は休みであった。もうちょっとぐっすり眠れたのに、と後悔。

色変記事の更新をする。数日ぶりで、いくらか質問が溜まっていた。じっくり悩んで回答していたら、ABCの時間になってしまったので、記事の更新ページをそのままにして出た。

AtCoder Beginner Contest 211 - AtCoder

全完8位。BCでWAを出していてやる気あるのかという感じ。

A問題は $\frac{A+2B}3$ 。dcで書く。Bは入力を全部読み、Perlの正規表現で4つそれぞれ含んでいるかチェックした。単語の末尾を/$/としていたが、文字列はまだ続く可能性があるので、/\n/である必要があった。1WA。Cは典型90問008でほぼ既出なので、そこから最短コードをコピペしてきて提出。典型90問のほうは微妙なテストケースハック（'r'が出現しない文字列は入力されない）がなされており、これで1WA。

Dはやるだけ。Eは結構考え込んだが、最終的にはBFSをした。サンプル3を見ると状態数が十分少ないことがわかる。Fは面倒そうに見えたが、よく考えると区間add・点取得で多角形の内部にいるか外部にいるかが判別できる。これはすべての多角形について同時に行えるので、解けた。多角形の点がどちら周りで与えられるか固定されていなかったので、x座標最小の点とその次の点を見て適当に反転したりした。

C問題が典型90問とほとんど被っていたのが話題になっていた。僕は、これはあまりよくないことだと思っている。典型90問を解いた人が得するというのは、典型的なテクニックを学べるという意味であるべきで、まったく同じ問題が出るという意味ではないはず。これに関し、Twitterでこういう↓意見を見た。このことで解けなかった人が不利益を被っているかというとあまりそうでもなく、典型90問がなくてももともと同じくらい解かれただろう、という感じか？これも納得はできる。が、やはり被った問題が最近過ぎるのも問題だろう。

典型90と同じ問題だから典型90やってない人に不利だってキレてる人、これは典型90関係なくド・典型なので writer のせいじゃなくてただの実力不足です
— yuto (@yuto1115_cp) 2021年7月24日

コードゴルフをする。Aはこれでよい。Bは制約をよく読んでいなかったが、入力される文字列は4つで固定らしい。ソートして全体をマッチさせる正規表現を作り、両端を削るテストケースハックを行っていたが、入力に被りがあるかどうかを見るほうが短い。Vimの:sor uに取られて終わりかと思ったが、実はテストケースには4つ全部違う文字列の場合と2つが同じ文字列の場合しか含まれていないらしく、*をうまいこと使うと縮んでくれた。*dd*dd*で2行消し、残り2行の状態になるが、3つの*のどれかでマッチした場合は下の行、マッチしなかった場合は上の行にカーソルがあるので、それで場合分けできる。

atcoder.jp

Cも典型90問そのままのコードが現状最短。Dは適当にRubyで縮めた。EFは手つかず。

午前1時からSRM810に出た。コンテスト開始直前に次のような内容のメッセージが表示され、かなり不穏だった。

div.1の人々へ：今日のHardはとっつきやすいけど実装がクソ重いので750点になっています。この点数は実装の重さによって付けられました。
↑あってる？
— こたつがめ (@kotatsugame_t) 2021年7月24日

TopCoder Statistics - Match Overview

EMの2完と2Chalで14位、レートは2535→2575(+40)でhighest。これで今現在、AC、CF、TCの3サイトでレートの最高値を記録している。

Easyは難しい。 ${\rm clamp}\left(2\left\lfloor \frac{raceTime-1}{observationTime}\right\rfloor,1,observerCount\right)\times observationDistance$ になる。最初は全部同じくらいずらすことを考えていたが、反例を見つけたので考え直した。2人の観測者をペアにして扱うと、 $observationTime+eps$ で $2\times observationDistance$ 進むことができる。

Easyに40分くらいかけたので真っ青になりながらMedを開いたら、既出でびっくりした。これ↓のメイン部分の問題になる。当時は計算量的によくわからない解法で通したが、その後改めて解説を読んで通してあったので、それを引っ張ってきた。ACLの遅延セグメント木はTopCoderではコンパイルエラーになるだろうと思ったので、自分の遅延セグメント木を持ち出し、ラムダ式をfunctionで受け取っている部分を関数に直したりしていたが、この作業は結構時間がかかった。幸いバグなく動いた。

atcoder.jp

Easyはサンプルがめちゃくちゃ弱いので、沢山落ちるだろうと思ってチャレンジフェーズもきちんと参加した。最初にノールック爆撃が行われていたようだが、幸い僕が開いた提出にはチャレンジされず、じっくり考えた結果落とすことができた。他に同じケースで落とせる提出を2つ見つけたが、片方は入念にチェックしている間に取られてしまった。合計で2Chal。部屋のEasyの提出13件の提出のうち、生き残ったのは5件だけだった。いろいろな解法があったが、上に書いた解以外はすべて落ちてしまったようだ。

色変記事の続きを書き上げて投稿。質問を受け付けるのは日曜日いっぱいにするつもりだ。

IOLの結果が出たらしい。今年は金賞が2人同時に出たということで、日本の言語学オリンピックもレベルが高くなったなあという感想。僕が出場したころは競技人口が少なかったため、なんとなくで国際大会に進めることになり現実感が湧かず、まともに努力できなかったどころか大会中も結構不真面目だった。今になっても後悔している。

第18回国際言語学オリンピック（IOL2021）

の表彰式が本日行われました……

日本チームにとって出場以来最高の成績です！

受賞された5名の方，おめでとうございます🎉🎉🎉 pic.twitter.com/bocbml0jaJ
— 国際言語学オリンピック日本委員会広報 (@iolingjapan) 2021年7月24日

小林賢太郎さんはオリンピック開会式の公式プログラムに寄稿していたらしいが、ディレクター解任を受けてプログラムの発売が中止になってしまった。その内容がTwitterにアップされていた。以下のツイートの文面はどうあれ、またこのような形であっても小林賢太郎さんが書いた文章を読めるのはうれしい。まあ、僕は結局開会式を見なかったわけだが……。

https://twitter.com/matsukaze1978/status/1418775167048687617

溜めていた日記をある程度書き、午前10時就寝。

07/25(日)

午後6時くらいに目を覚ました。

いい加減に冬用の布団を片付ける。布団カバーをはがし、シーツを昨日届いた夏用のものに交換し、洗濯機を回した。布団はクリーニングに出すべきらしいが、とりあえずクローゼットにしまっておく。布団を入れる袋に押し込んで、さらに天井に押し付けて無理やり棚に乗せた。毛布などがあるせいで幅が狭く、かなり苦労した。

ARC124に出た。人生初のUnrated ARC。結果は4完遅解きで、かなりひどい。

AtCoder Regular Contest 124 - AtCoder

Aはよい。制約の $k_i\ne k_j$ が優しい。Bは上の桁から再帰するいつものやつだろうと思って実装。適当に投げたらTLEしたが、全部同じ要素になったらすぐreturnする枝刈りを入れたら通った。Cは1番目の要素の約数のペアを全探索すればよい。

Dを読んでわからなかったので順位表を見たら、かなり悪い順位でびっくり。B問題が明らかに遅い。考え直してみれば、作れる数の候補となるのは $a_1$ と $b_i$ のXORだけなので、全部試しても十分間に合うようだ。なぜ気づかなかったのだろう。悔しいので適当にRubyで縮めていた。

D問題に戻る。適当によさげなswapをすると $1\dots N$ と $N+1\dots M$ の置換に分割されるので、お互いを使ってうまいこと当てはめてみた。サンプルがあったので提出するも、当然のようにWA。これをさらに2回行った。もう全然わからないまま残り15分くらいになったあたりで、急にもともとの列をFunctional Graphとして見るアイディアが浮かんだ。とりあえずループを検出してそれぞれ $1\dots N$ と $N+1\dots M$ に含まれる要素を数えるコードを書く。片方しか含んでいないようなループの個数が重要なことはすでに分かっていたので、両方含むようなループの操作回数として手で試したループをもとにそれっぽい式をいくつか当てはめてみる。サンプルが合うものが見つかったので提出、AC。

BもDも初手が悪すぎた。特にBはそのまま突き進めてしまったのもまずかった。コードゴルフはBのRubyコードをもう少し縮めたあと、AをPerlで通したくらい。

Codeforces Global Round 15に出た。7完45位、レートは2850→2885(+35)でhighest。

Dashboard - Codeforces Global Round 15 - Codeforces

Aからちょっと悩んだが、冷静になるとソート後の文字列がわかるので、異なるインデックスを抜き出せばよい。Bもしばらく悩んでいた。勝ち抜き戦を行い、それが本当に全部に勝てるか確かめることで解ける。以下の問題と同じ。1度考えたが、求める選手の条件をよくわかっておらず棄却してしまい、再度正気に戻ってようやく解けた。

atcoder.jp

Cは円を適当に切り開き、空いている点を $N-K$ 個飛ばしで繋げばよい。これの最適性は、そのように繋いだ時すでにある辺と目いっぱい交差でき、また新たに繋いだ辺同士もすべて交差していることからわかる。交点の個数の計算はBITを用いた。Dは未証明だが、 $a_i$ の絶対値を取った後2つの異なる部分集合で和が等しいものがあればYES、なければNOとした。Eは難しい。 $k-1$ 個のブロックに分割するとか考えていたが、ブロックの幅が問題。最終的には左から貪欲に $\left\lceil\frac{n}{k-1}\right\rceil$ 個ずつペアを作り、作れた段階でブロックを区切っていった。何を示せば正当性が言えるかよくわからなかったため、 $\left\lfloor\frac{n-1}{\left\lceil\frac{n}{k-1}\right\rceil}\right\rfloor$ 個のブロックを作った後にまだペアになっていない要素が2個以上残っていることをプログラムで全通り確かめた。

Fは簡単。あるポータルにたどり着いたとき、それより前のポータルはすべてactiveになっているため、その状態でワープした後戻ってくるまでの時間は常に等しい。これは累積和やBITを用いて前から計算できる。

Gはそこそこ面白かった。 $2^N$ 通りの $01$ 列がソートされることを確かめればよい。当然 $2^N$ 通りあるが、各回の操作で新しく触れることになるインデックスの個数を計算し、そこに何個 $0$ を配置するかさえ全探索すれば、すべての状態をカバーできる。これは最大でも $5^{10}\approx 10^7$ 通りとなる。普通にシミュレートしていると通らないが、再帰関数で全探索しながらシミュレートを進めたり、情報を40bitに詰め込むことで1回の操作のシミュレートを $O(1)$ で行えるようにしたところ、爆速になった。

Dの証明とEの証明をTLで見た。Dは、 $a_i$ を数直線の点の間に張られた辺だと思うと、必ず閉路が存在することからわかる。Eは、実は上のようにブロックを区切ると、全部で $k-1$ ブロックになっているらしい。しかも作り方から、 $i$ （1-indexed）番目のブロックまででまだペアになっていない要素は高々 $i$ 回しか出現していないため、残り $k-1-i$ ブロックに $k-i$ 個以上出現することになって、必ず最後までにはペアになれる。