週記(2022/04/11-2022/04/17)

04/11(月)

先週の週記を投稿した後の話。

学生証を手に入れたので、NHKの家族割引を申し込む用意が整った。書類を記入して、学生証のコピーとともに封筒に入れた。大変不快な思いをしながら作業していた。受信機器の設置日なんか知らんて。携帯買った日でも書けというのか。適当に調べた感じ、慣例的に空欄でも受理してくれているという記述をネットで見つけたので、空欄にしておいた。

現在支払っているNHKの受信料は、学生ということで家族割引が適用されている。次の4月からそれが終了してしまうというハガキが来たので、続けて適用してもらうための手続きが必要となった。

週記(2022/02/28-2022/03/06) - kotatsugameの日記

外出。気温は24℃らしい。いつの間にか通る道の脇の桜が満開を迎えており、目を楽しませるものだった。ポストに寄って書類を出し、学食に向かった。サラダにドレッシングがかかっていないと思ったら、今日から自分でかけるようになったらしい。およそ2年ぶりにドレッシングと給水機が復活しており、大変感慨深くなった。

帰宅し即座に就寝。正午だった。

午後4時半、目覚ましで起床。これはインターン先の定例会が始まる時刻である。布団から飛び起きてオンライン会議に接続した。

先週の進捗は火曜日に書いたコードのみ。いろいろ考えながら書いたので、その考えていることを含めて進捗報告のスライドを作成した。特に何事もなく勉強会まで終了。

勉強会で関数型言語の話がチラッと出てきたので、参照透過性について少し調べて、出てきた記事を読んでいた。非常に興味深い話だった。

www.timedia.co.jp

明らかに副作用を持つ入出力関数は、本当に参照透過性を満たしているのか?という疑問がある。これに対する回答は、「実はそれらのIOアクションはすべて一つの引数をとる関数の形をしていて、その引数が都度変わるので、そもそも全てが以前と同じな状態で評価されることがない」となるようだ。聞くだけならただのとんちであるが、もう一つ意味があるように思った。IOアクションの引数は何かというと、直前に実行されるべきIOアクションの戻り値(の一部)なのである。これによって、すべてのIOアクションが望む順番で実行されるということが保証される。

午後8時、外出。ゲーセンに行く。昼間はそれなりに暑かったが、夜になってちょうどいい気温に下がってきた。一年にほんの少ししかない、非常に快適な時期。

到着してから閉店まで2時間半ほどしかなかった。成果は理論値が1譜面だけ。グッズキャンペーンのポイントは15クレ分増えて、107ポイントになった。

油そばを食べて帰宅。帰り道、西公園(という名前の公園らしいことを調べて知った)の横を通った。いつも夜はスケボーのガラガラという音が非常にうるさいのだが、今日はそれに加えて人の声もかなり聞こえてきて、ただでさえ大きい物音に加えて深夜まで大声で騒ぐのはさすがに迷惑じゃないかという気持ちになった。

少しコードゴルフをした。ABC247-BがAWKで縮められていて、何かと思ったら嘘解法があったらしい。性と名をすべて混ぜてuniqueを取ったときの要素数2N-2以下ならばNo。こういうのはRakuで書いたほうが明らかに短くなるので、そうして取り返した。さらに、uniqueを取った時の要素数2N-2個ということは重複した要素が2個以上あったということなので、そちらで判定するようにして-1B。重複する要素を抜き出すメソッドは、存在こそするものの名前がrepeatedと少し長めであり、コードゴルフで効いたのはこれが初めて。

思い立ってインターンのコーディングを少し進めた。明日は久しぶりの1on1なので、それに向けて進捗を追加する。データをテキストファイルで取りまわすことにしていて、CSVファイルの形式にしようかと思っていたのだが、JavaCSVファイルを読み書きするライブラリが外部のものに頼るしかないようだった。それで、ライブラリを使わずにコーディングしている。自分で書き出したデータを自分で読み込むので、特定の形式にだけ対応できていればよい。読み込み部分を完成させて、さて本題に入るぞと意気込んでコードの形を考えていたら、眠くてうっかり意識を飛ばしてしまったので、切り上げた。1時間程度だった。

シャワーを浴びたら少し目が覚めたので、YouTubeを見たりゴルフしたりしていた。午前5時半ごろ布団に入り、少しだけカクヨムを読んで午前6時過ぎ就寝。

04/12(火)

午後0時半起床。

午後1時から1時間、1on1を行った。書いたコードの設計を説明するとメンターさんが文章にまとめてくださり、さらに何種類か別の方針を示してくださった。今の設計は、まずやりたいことがあって、それらが可能な範囲で最初に思い付いた形をコードに起こしているので、そうやって別の方針があるということすら考えていなかった。まあ、とりあえず今のところは、別方針と比較しても現在の実装が良いと思っている。今日はメンターさんが大忙しの日らしかったので、きっちり1時間で終了した。

Twitterをしていたら午後3時を回ってしまった。今日も外出しようとしていた。準備して、午後3時半ごろ出発。原付に乗ってクリーニング屋に行き、預けていたスーツ一式を受け取ってきた。そのまま学食に寄るもまだ夜の部が始まっていなかったので、購買でミールカードを使い切って、一旦帰宅。

ゲーセンに行くつもりだったのに、TLの話題に乗っかってツイートしていたら午後5時になってしまった。会社のSlackなどにおけるtimesチャンネルについての話。別に可否について議論していたわけではなく、人それぞれの使い方についてのツイートが多かった。僕もインターン先で用意してもらっていて、Twitterと同じ……とまではいかないが、メモとしてそこそこ気安く書き込んでいる。しかし最初は、わざわざ自分のために用意された場所なんだから何か書き込んだほうがいいだろうという義務感を元に使用していた気がする。そういう風に、自分がいわば「主人公」である場所であるというのが、今感じている気安さの正体だと考えた。

いい加減切り上げて出発。そういえば、昨日の真夜中に西公園から大声が聞こえてきたのは、今が花見の最盛期だかららしい。試しにちょっと寄ってみて、写真を撮った。

f:id:kotatsugame:20220413055516j:plain
西公園の桜

イオンの地下のフードコートで食事している最中、chokudaiさんからリプライが来た。今日の午後8時からのあーだこーだーにゲストとして来られないかとのこと。直前に連絡することになってしまったからか、今日ではなく再来週でも大丈夫だと言って頂いた。今日は思いっきりゲーセンで遊ぶつもりなので、お言葉に甘えてパスさせてもらった。というわけで、僕が登場するあーだこーだーは再来週の火曜日、04/26になりそうだ。それまでに少しアーカイブを見てどんな感じか把握しておきたい。

chokudaiさんからリプライが届いていた。僕をあーだこーだーのゲストとして呼んでほしいという希望が来たらしい。chokudaiさんもリプライしてくるぐらいだから乗り気なのだろう。僕ももちろん悪い気はしないため可能であるとの返事をした。結構すぐになりそう。

週記(2022/03/28-2022/04/03) - kotatsugameの日記

ゲーセン。午後6時前から閉店まで遊んだ。グッズキャンペーンのポイントは29クレ分増えて136ポイント、何とか目標の120ポイントを溜めることができた。今日はひたすら低難易度の譜面の理論値埋めをして、Lv.11で2譜面、Lv.11+で8譜面、Lv.12+で1譜面の合計11譜面出せた。かなり調子が良かった。12+の理論値のツイートだけ貼っておこう。

最後のクレでは3連続でIMPACTをプレイした。1トラック目で6-1-0などという信じられないスコアが出たので、何とかAJを捻り出したいと思っての選曲。2トラック目は11-0-1。

祈るように3トラック目をプレイし、最後の最後までAJで通ったのに、ラストの黄タップトリルが抜けてさすがに変な声が出た。3244ノーツの譜面で3241コンボってなんだよ。精度もどんどん悪くなっていて厳しい。

立ち食いそば屋で食事して帰宅。帰り道でも西公園の桜を撮ってきた。屋台こそ閉まっているもののまだ花見客がいた。これが昨日のうるさかった声の真相か。

f:id:kotatsugame:20220413061038j:plain
西公園の桜(夜)

日付が変わったあたりで帰宅。YouTubeで今日行われたチュウニズム公式の生放送を飛ばし飛ばし視聴した。

atgolferのコードが置いてあるGitHubリポジトリの管理者が僕になったので、Twitterのatgolferアカウントのbioを修正した。kotatsugameというユーザ名が長すぎて、GitHubリンクが省略されて表示されてしまう。しかもその状態で再度bioを変更→保存すると、省略された部分を示す「…」がURLの一部になってしまうようで、リンクが切れる。大変面倒であった。その更新ついでに、botであることを示すラベルの設定もした。

GitHub - kotatsugame/atgolfer

朝まで日記を書いていた。コードゴルフのことを書くために提出を確認しているときに、bashコマンドfmt -1というのを知った。幅1を指定してフォーマットすることで、空白区切りだったり改行区切りだったりする入力を、改行区切りに統一できるらしい。これはtr ' ' '\n'の完全上位互換である。空白区切りを改行区切りに直すというのは至る所で必要になる処理で、他にもdc -e?ffactorによる方法が存在し、前者もまた順番こそ変わるものの1B縮む。factorは行の後ろに大量のゴミがつく、dcは遅い、と汎用的な短い書き方がなく、これまで大変だったのだ。革命的。しかし探し方が悪いのかあまり効くコードが見つからなかった。

atcoder.jp

ECR126Fを通した。当日のTLで解法を知ってしまっていた。コストの変化の種類数が少ないことではなく、変化が単調であることに注目すべきだったらしい。「変化がd\le -1)以下だった場合に使う」と決めると、区間ごとに二分探索することで変化を全通り生成せずともどれだけテレポーターを追加するか計算できる。あとはdも二分探索すればよい。最後に増やしすぎたテレポーターを減らすときは、1つ減らすごとにちょうど-dだけコストが増えると考えられる。二分探索の条件から、コストの変化がd-1以下のものを解消する前に総コストがギリギリになるからだ。

https://codeforces.com/contest/1661/submission/153499691

布団に入って2時間半ほどカクヨムを読み、午前10時半就寝。

04/13(水)

午後5時起床。パンを食べて即座にCFのICPCミラーに出た。5時間コンテスト、ソロ。

Dashboard - 2021-2022 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) - Codeforces

最初AとBを読んで解けんなあと言っていた。別の問題にぽつぽつsolvedが出てきたので、以降はそれに従って解いた。

まずC。こういう3点を連結にする道を作るには、どこか合流する1点を決め打って、そこから3点にそれぞれ最短経路で行くのが良い。今回もその方針で考えてみると、合流する1点としてはX座標とY座標それぞれ3点の中央値となるような点にするのが最適に見える。出したら通った。後からTLを見て気づいたことだが、これで総距離が\max x-\min x+\max y-\min yとなり、明らかに最小。Dは後ろから見るだけ。

Lはちょっと悩んだ。終点が決まっていれば流量2を流せるかチェックする蟻本のやつに落ちるが、今は関係ない。最初無向グラフだと思っていて、dfs木を取って後退辺を探せばよいかなと思っていた。実際は有向グラフ。次に、適当にBFSして、初めて同じ頂点に2回たどり着いた瞬間2通りの経路が得られたと判定することにした。これはサンプル2で落ちて、途中から分岐するタイプの経路に対応できない。ここで閃いて、始点の次の頂点がどこだったか覚えておくようにした。これが同じだったら、後から来たほうは無視してよい。違った場合にやっと2通りの経路を復元する。これで通った。なかなか面白い。無視してよいことを正確に説明するのはちょっと難しい。無視が起こった頂点の先で初めてぶつかるような経路は、それ以前の両方の経路と一切ぶつからないから、という理由になるだろうか。

Jは頂点を好き勝手並べ替えてよいと誤読していた。実は元の順番を保っている必要があるらしい。そこで、区間内のどの頂点をその部分木の根にするか決める区間dpで解いた。部分木の外に行くようなコストの和を2次元累積和で求めることで、辺ごとにそこを通る必要があるペアのコストの和を足していける。

Fは難しかった。偶数番目に何を置くかを後ろから決めつつ、余ったブロックを間のどこに配置するか掛けながらdp遷移を行う。dpの添え字は、ブロックが置けるにも関わらずまだ置かれていない位置の個数とした。n番目のブロックは一意に定まるので、最初にそれを配置して、あとは(n-2,n-1)(n-4,n-3)とペアにして考えていく。ブロックの出現回数を番号の降順に見て、位置n-4にブロックを配置したら次のループから位置n-3が使えるようになる、という具合。ただこう分けると、位置1を使えるタイミングがよくわからなくなる。しばらく考えて、これまで見たブロックの数と今の空きスペースを足しnと比較することで、直前に位置2にブロックが置かれたか否かが判定できると分かった。

Iはすんなり行った。角を2か所聞くことで、r_1+r_2c_1+c_2がわかる。また、r_1\le r_2とした場合に(r_1,r_2)を定められるような辺上の位置があるようなので、全探索で探して聞いた。(c_1,c_2)についても同様にして、これで、4回のクエリでrの候補2つ、cの候補2つが決定できる。組み合わせ4通りに対しここから3手しか使えないが、実は十分で、最初に試したものが成功するか失敗するかで一意に定まる。

Eはsolvedが少なく怯んでいたが、考えてみるとすんなり行った。まず、区間幅の最小値を最大化してよい。これが最大でないような解は、そのとき幅が最短の区間を必ず伸ばすことができる。伸ばすことができない場合は家の位置がギリギリということになって、区間幅の最小値の最大値を達成できなくなるから。ということで最初に二分探索でこの値を求めると、あとはもう一回二分探索して区間幅の最大値の最小値を求めることで答えが出る。復元も二分探索のチェックを逆にやる感じでできる。ペナが出て絶望するも、単純なミスを直したら通ってハッピー。

ここで崖に突き当たった。残りの問題はどれもsolvedが1とか2の問題しかなく、困る。とりあえず全部眺めて、一番筋力で解決できそうだったGに挑戦した。まず、水面上に出ている三角形の面積は、三角形全体の面積を求め、Z座標から出せる高さの比率を相似比として、その2乗倍することで出せる。言い換えれば、面積はZ座標の2次式で表せる(正確には、この2次式はZ座標の範囲によって最大3回変化する)。これがおそらくメインの考察で、あとは水面が下がっていく過程をシミュレートし、連結になった面をUFでつないで、連結成分ごとに面積の式を足していけばよい。隣接する面が連結になるタイミングは、共有している辺の端点の片方が水面上に出た瞬間である。実装して投げるとWAで絶望したが、念のためdoubleをlong doubleに投げたら通ってひっくり返った。全体3チーム目のAC。横着して3次元座標と2次式を同じ構造体で表したりしている。

残り時間はHを考えていて、サンプルも合わせられず終了。8完9位、ソロでは3位。

atgolferの更新を眺めていたら、C++コードゴルフに新手が出ていた。ACLmodintを出力する際には、printfに変数を直接渡せばよいらしい。確かに、modintのメモリ上の位置と内部で持っている整数の位置は全く同じだから、納得できないこともない。型検査で弾かれないのは、コンパイル時にフォーマット文字列の解析をしていないからか。cout<<x.val()printf("%d",x)よりも短いが、これがstd::cout<<x.val()になると縮むようになる。

明日は山に登ってセミナーをする。指導教員に今セメスターの一週間の予定を教える必要がありそうなので、履修科目を決めなければならない。院生は必要な単位数こそ少ないものの、頑張って1年生のうちにあらかた取っておくのが普通らしい。数学専攻向けの講義には目ぼしいものがなかったので、別のところに目を向けた。「学際高等研究教育院」という支援機関みたいなものがあって、指定科目から6単位以上取得するという条件を満たした学生から選抜して奨学金を与えるシステムらしいのだが、この指定科目には様々な研究科の講義が含まれており、受講するだけなら誰でもできるようだ。ここからいくつか選ぶことにした。

2つほど気になる講義を見つけたが、片方はシラバスにClassroomのコードが書かれておらず、諦めた。とりあえずもう片方を履修登録して、Classroomにも入っておく。と、すでに期限が過ぎた課題を見つけた。今週分のようだ。遅れると1日ごとに点数が引かれていくシステムだったので、慌てて提出しておいた。

海外の人から競プロのコーチをしてくれとDMが来た。……これだけだとよくある話なので、なぜ日記に書くに至ったかの背景を説明しよう。まず、日記にもツイートにもほぼ書いてこなかったが、この人とは昨年の7月からDMでやり取りをしていた。向こうが競プロの問題に関する質問をして、僕が答えるというもの。CFでもメッセージに質問が来たら答えるようにしているので、同様の対応。ただし向こうは僕のパーソナリティにも興味があったらしくて、急に年齢を聞いたりしてきたので、競プロの問題に関する質問以外はDMをしてくるなと言っておいた。こちらは質問自体に興味があるのであって、質問者には興味がないのだ。

「競プロのコーチになってくれないか?」というメッセージは、この制限を逸脱している。実は以前にも何度か同様のメッセージが来ていて、最初は「AtCoder ProblemsのRecommendationを解け」と真っ当なアドバイスをしたのだが、レートが伸び悩んでいるとかいう理由で繰り返しやって来るので、だんだん断りの口調も強くなっていった。今日は「二度とそのようなメッセージを送ってくるな」と返した。すると、「コーチの意味について勘違いしているのではないか」と返ってきた。向こうはこれが競プロの問題に関する質問だと思っているらしい。

ここで僕も自分の基準がどこにあるのか再確認した。つまるところ、主体的に相手に何かを与えるつもりがないのだ。「あなたに質問の答え以外を与えることはない」と言ってみると、今度は「なぜ怒っているのか」ときた。決まっている。この人が何度も何度も何度も何度も質問以外のメッセージを送ってきたからだ。今になって、適当なタイミングでブロックしておけばよかったと後悔している。

さらに少しやり取りして、何とか僕がその人の競プロ能力だったり精進に興味がないことをわかってもらえた。するとまだ「自分がもっと強くなったら興味を持ってくれるだろう」ととぼけたことを言っている。そういうことじゃないんだよな。この人がもっと強くなったら、僕が答えられるような質問はなくなって、それで関係は終わりである。また急に「自分はbotではない」とも言いだしたので、「自分にとっては質問を送ってくるbotと何も変わらない」と返したら、もう会話を続けたくなくなったと言い残して、今度こそ関係が切れた。

以上のことは、僕がこの人とのDMを振り返ってまとめた所感であり、DMという性質上この文章を読んでいる人にはほかの情報源がないので、一方的に印象を貶めることになるのかもしれない。まあ日記ってそういうものか。嫌いなものは、嫌いだ。もうちょっと毒を吐きたい。レートが伸びないからって急にメンヘラみたいなメッセージを送ってくるな。それは個人のモチベーションの問題に還元されて、本当に全然全く完璧に興味がない。

そもそも、別にこの人に限らず僕がコーチをすることはない。本来競プロというものは一人でプレイするゲームだと思っていて、知の高速道路が急速に整備されている現在、一人ですら強くなれない人間が僕に師事したところで何も変わらないはずだし、何も変わらないべきであるとすら信じている。また、僕の競プロ人生においては「精進しているならば強くなっている」が常に真だったので、それなりに多く問題を解いているようだったこの人のレートが伸びないのは、僕にとっては全く意味が分からないため、どう頑張ってもまともなアドバイスは出ない。

もう朝。明日のセミナーで発表する内容の準備を始めた。先週も書いたようにSWAGと、その前振りとして適切かは微妙だが累積和について話そうと思う。紙に喋る内容をまとめておいた。一応、実装例も用意しておく。先週は純粋関数型言語が話題に出ていたので、HaskellでSWAGを実装することにした。TLEが出て絶望するも、入出力高速化で通ってくれた。

#753694 (Haskell) No.1036 Make One With GCD 2 - yukicoder

セミナーを行うことになった。自分が取り組んだことをちょっと準備して説明する。院試の面接のときに取り上げようとしたSliding Window Aggregationについて話そうと思っている。

週記(2022/04/04-2022/04/10) - kotatsugameの日記

午前7時になって一部のゲーセンが開店し、チュウニズムのバージョンアップ情報が流れてきた。いつもの定数変動で、今回はLv.14+からLv.15への昇格が2譜面。「Contrapasso -inferno-」と「otorii INNOVATED -[i]3-」。このうち前者はSSS達成していたため、この昇格でLv.15の初SSSが出たことになる。これまでは、自分がLv.15でSSS出せるとは思えず腰が引けていた部分があるため、これをきっかけに他の譜面でも戦えるよう頑張りたい。

布団に入って少しハーメルンを読み、午前9時就寝。

04/14(木)

正午あたりに起床。寝坊が怖くて二度寝できず、2時間ほど布団でグダグダしていた。

起き上がって、もうちょっと履修を考えてみた。昨日からさらに2つ増やして、学際高等研究教育院の指定科目からは3つの講義を受講することに決めた。履修のためには教務課に書類を提出する必要がある。そんなことをしていると結構ギリギリの時間になったので、山に登る。雨が降っているので地下鉄を使いたかったが、それだと間に合わないかもと思ったので、カッパを着て原付を出した。

何とかちょっと前に到着するも、コンビニでパンを買い込んだり教務課で履修申請の書類を貰ったりしていたら予定の時刻になってしまった。ここで同じ担当教員についた人から連絡が来て、先生が研究室にいないことを教えてもらった。とりあえず合流してどうするか考える。僕は食事がまだだったので、買ってきたパンを食べながらしばらく履修について話していた。食べ終わったあたりで先生から、時間を間違えているのではないかとメールが来ていたのに気づく。どうやら集合場所が研究室ではないようだ。では、どこか。

先ほどのメールには肝心の場所が書かれていなかった。これについては確か、事前に先生がメールを送ってくださることになっていたはずで、それがなかったので今回は僕らのミスではないはず。仕方ないので探し歩くことにして、とりあえず1階下の教室を覗くとすぐ見つかった。僕らのミスでないと思っているとは言え、謝り倒しながら入室。留学生の方もいて突然英会話が始まり、聞き取りに失敗しまくって大変だった。

セミナー。僕の発表は、1時間の予定だったところを20分くらいオーバーしてしまった。SWAGの導入もStackからQueueを作る手順を元にして話そうと思っていたのに、焦って天下り的に与えようとしたせいでかなり不自然な説明になってしまった気がする。しかしその分、前半のアルゴリズム・考察の説明は手厚くできたつもりなので、そこは満足している。もう一人の発表も、記号の定義などを念入りにやってもらった結果終盤時間が足りなくなっていたが、そちらはバッサリ見切りをつけることで見事時間内に収めていて上手かった。また、発表と発表の間に休憩時間を取ってもらい、その間に履修申請の書類を記入し、走って教務課に行って提出した。

学食で食事し、午後8時前に帰宅。パソコンの前に座ってみるも凄まじい眠気に襲われ、たまらず布団に移動して寝落ちした。午後8時半から午前0時まで寝ていた。

起きてからしばらく、もう一度寝ようか迷いながら布団でスマホを弄っていた。TLにめちゃくちゃバズっているツイートが流れてきた。投稿から1時間も経っていないのに、すでに4万いいねくらいついている。実際に信じられないくらい面白かったので貼っておこう。

セミナーで先生から貰ってきた問題が非常に競プロチックで面白そうだったので、しばらく考えていた。小さいケースだけでも解けないかという話だったので、それに狙いを絞って考えてみると、無事解決できた。あまり具体的なことは言わないほうが安全だろう。答えが綺麗な形になったので、何か特別な解釈があるのかと思ったけれど、僕の採ったアプローチでは特にそれらしいものは見えてこなかった。

水曜日のコンテストのeditorialが出ていたので、K問題を解説ACした。冷静になるとコンテスト中はこの問題をほとんど考えていなかったので、精進としての効果は薄そう。頂点を3種類に分割して最小カットみたいなものを求めたいとき、頂点を倍加して適当に割り当てることでうまく重みを対応付けられるらしい。こういう方法があると知れただけでも良かったか。ただ、そうやって2000頂点4000辺くらいのグラフを作って最大流を流した時、高速に動作する正当性がよくわからない。出したら15msで通ってはいる。

https://codeforces.com/contest/1666/submission/153673254

すでに朝になっている。途中にゴミ出しやコードゴルフを挟みつつ、寝るまでカクヨムを読んでいた。午前10時半就寝。

04/15(金)

午後11時起床。たっぷり寝られた。このままもう一度寝て金曜日をスキップするか迷いながらゴロゴロし続け、午前2時にようやく起き上がった。

履修が確定したので、今週分として出ていた課題を片付ける。ゲーム理論の講義を取ったのだが、これは教科書が指定されていて、来週からその演習問題が課題として出るようだ。今のうちに手に入れておく必要がある。その本を生協で注文するついでに、新刊のラノベもチェックした。4月下旬から1月分ほどの新刊をチェックして、20冊予約した。ところで4月買った本は全然読めておらず非常にまずい。代わりにカクヨムに全てを吸い取られている。カクヨムは今月読んだ文字数を勝手にカウントしてくれるようで、見るとすでに200万文字を突破していた。

午前5時過ぎからTCB46に参加した。-167pt。例によって今週日曜日終了なので、ここに各問題の感想を書く。

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

4問目から難しい。初手がすぐに出ず、しばらく適当な値を入れて計算するという謎の作業をしていた。解法は、期待値をpqを用いて表し、qを変化させても期待値が変わらないようなpと、pを変化させても期待値が変わらないようなqをそれぞれ求めるというもの。問題文によれば求めるpqはそのような性質を持つらしいが、あまり正当性がわからなかった。ゲームといいつつ2人が同時に行動している感じだから単純に最大・最小を考えることはできなくて、期待値が均衡する点はこのように求めなければならないのかもしれない。さらに、そのようなpqが一意に定まるのは式の形からわかる。この問題は14分かかって-8pt。

6問目もかなり神経を使った。まず作れる個数が\lceil N/M\rceilになって、この値が1なら余りを取る操作は行わない。2以上なら最初に1回だけ余りを取る操作を行い、1\dots(N\bmod M)\lceil N/M\rceil個存在するようになるので、Kに一番近いものをずらして合わせる。ただしN\bmod M0の場合は0\dots M-1がすべて\lceil N/M\rceil個存在するようになる。11分かかったが何とか減点なしに。

7問目は大変だった。p+n\le Nに対して\binom{N}{p+n}\binom{p+n}{p}\binom{U-1}{p-1}\binom{D-1}{n-1}を足し合わせることになる。ただし\binom{-1}{-1}=1とする。適当にバラすと畳み込める形になるので解けた!と早とちりするも、残念ながら\bmod 10^9+7なのでそう簡単にはいかない。convolution_llでもオーバーフローするようだ。そこで、自分のライブラリから任意mod NTTを引っ張り出してきた。modを変えて3回NTTを行い、garnerで復元するやつ。ACLも多分同じようなことをしているはずだが、64bitどころか3つのmodの積未満までは正確に復元できる。その上限は64bitより大きく、今回のように最大(10^9+7-1)^2\times 10^5なら十分。しかしこれで手元では合ったのに、TCBのページでテストすると落ちた。次に書くように、これは僕のライブラリの設計と運用が絶妙に噛み合ったとんでもないバグだった。修正も含めて28分かかり、-14pt。

自作のcombinationクラスは、階乗とその逆元を前計算することで、組み合わせの記号3種類と階乗そのものを定数時間で計算してくれる。この定数時間とはならし定数時間であり、vectorのように大きな引数が来たら倍々で前計算の列を伸ばしていくことで、事前に前計算する最大値を指定しなくても動くようになっている。ここで階乗の逆元は関数の形で提供していないため、ほしい場合は内部のvectorに自分でアクセスして拾ってきていた。今回もそうしていたのだが、すぐ近くで組み合わせの関数も呼び出し、掛け合わせるようなコードを書いていたのがバグの原因。組み合わせの関数内で前計算の列が伸びたとき、式の評価順によってはアクセスしていたvectorが別の位置に移動されてしまい、メモリに残された変な値を読んでしまうことがあるようだ。これを受けて、ライブラリに階乗の逆元を返す関数を実装した。

8問目はよくわからない。そもそもこのゲームが終了することすらすぐには分からなかった。冷静になると、2人が操作するごとに(X-Y)\bmod N1減らせるので、そう。これが分かったので、最初8手程度を全探索して細かい場合分けを無視し、残りを(X-Y)\bmod Nとするコードを書いた。しかしサンプルで落ちる。どうやらNが奇数の場合、FULくんは\lfloor N/2\rfloorの移動を2回行うことによってY\leftarrow Y-1ができ、これが効いてくるようだ。必死にそれっぽい式を書いたり適当に実験したりして何とかサンプルを合わせ提出するも、1ケース落ちてしまった。もうちょっと考えてより複雑な式を書いたりしたのだが、WAが取れない。

最終的にすべての0\le d\lt Nに対して(X,Y)=(0,d)の場合の答えを求めてくれるような実験コードを書き、そこからエスパーして求めた。Nが偶数である場合は1種類、Nが奇数の場合はN\bmod 3で3種類に分岐するようだ。答えの最大値が\lfloor N/3\rfloorになっていたので、N\bmod 3に注目する発想はすぐ出た。最初からこうしておけば……。3時間弱と3ペナで-66pt。

9問目は最初O(N^3)のコードを書いて高速化しようとしていた。そのままだと11secで、グラフ系の問題はベクトル化も効きづらいため絶望的。しばらくして諦め、ようやく真面目に考え始めた。FULくんは常にTechちゃんに近づくように移動するべきである。よって、2人がいる頂点の組(u,v)と、そこから2人それぞれの移動を1手ずつシミュレートした遷移先の組は、Techちゃんの移動の種類数に等しくなって全体でO(N^2)個しか存在しない。その移動を有向辺として作ったグラフはO(N^2)頂点O(N^2)辺であり、しかもゲームが常に終了するのでDAGとなり、トポロジカルソートの逆順で期待値が求まる。実装時はvからuに1歩進んだ頂点をO(\log N)かけて求めてしまったので4secくらいかかっているが、一発で通った。最初の迷走が高くついて40分強、-23pt。

10問目は面白かった。よくある、端で跳ね返る代わりにそのまま突き抜けて反転した長方形に突入すると考えるやつに見える。ただし跳ね返り方が特殊。まず、角に当たるまで縦・横の壁を何回通過するか求めた。これは回数を変数にして時刻の等式を立て、拡張ユークリッドの互除法で解けばよい。そのあと、跳ね返り方について考える。奇数回目の跳ね返りの度に長方形が反転するので、縦横それぞれの跳ね返り方について、それが奇数回目の跳ね返りであるものの個数を求めたい。反転回数を求めたいのだから個数の偶奇さえ分かればよいので、何回目の跳ね返りかの和を求めることにする。

最後以外同時に跳ね返ることがないため、各跳ね返りについて、それより前に起こった跳ね返りの回数が求まれば良い。X軸方向でk回目の跳ね返りは、X軸方向にkHだけ進んだとき、つまり時刻\frac{kH-S_x}{a_0}に起こる。このように各跳ね返りの時刻の式がわかるため、それより前にY軸方向で何度跳ね返ったかを時刻を比較することで求めることができる。具体的にはkの1次式を定数で切り捨て除算した形になるので、すべてについての和を求めるのにfloor_sumが使える。さらに同じX軸方向の跳ね返りを考慮に入れることで、求めたかった和が手に入る。1時間強かかり、さらにうっかりミスで1ペナつけて-56pt。ペナではassertによるREが出て、再現するケースも小さい範囲のランダム生成で見つかったので、それの解消を目標にデバッグすればよくかなりやりやすかった。assertの威力を体感。

終わって午前11時半。そこから食事して、TCBについてのみ日記を書き、就寝したのが午後1時半だった。

04/16(土)

午後5時くらいに、今度こそ今年度初の冷凍弁当を受け取った。また寝て、午後8時起床。シャワーを浴びたり食事したりして、午後9時からABC248に出た。

UNIQUE VISION Programming Contest 2022(AtCoder Beginner Contest 248) - AtCoder

Aは桁和を見ると短く書ける問題。Rubyで文字列のsumメソッドを使い、サンプルで定数を合わせて提出した。Bは短く書けそうで書けない問題。とりあえずC++で書いておこうと思ったらオーバーフローで1WAしてしまい、ひっくり返った。ここからもずっとC++。Cはdp。この位置にdpが置かれるのは驚き。ただ、確かにそれだけ簡単な問題である。Dは要素ごとにインデックスを集めて二分探索。

EはK=1の場合を処理した後、まずあり得る傾きを全列挙した。その後、傾きで点の位置ベクトルを正規化し、重複する個数を数えてK個以上あれば答えに加える。正規化は「割った余りを取る」操作に近い。典型操作の組み合わせなのでほとんど何も考えずに書いていたのだが、提出すると1400msくらいかかってしまった。よく見るとO(N^3\log N)で、想定解じゃなかったんだなあと思った。

Fもdp。縦2つの頂点が連結かどうかと、そこから辺が伸びているかをそれぞれ考えてみると、必要な状態を4つに絞り込むことができる。それらの間の遷移もいちいち手で求めて、コードに写した。任意modだが、何となくACLを使わず遷移ごとに手でmodを取ることにした。ただN\le 3000O(N^2)に定数倍がちょっとつくのが怖いと思って、%演算子を使うのではなくmodの値以上になったら引き算するような形で書いていたら、実装にかなり時間がかかってしまった。この日記を書いているときに出しなおしてみたら、別に普通に余りを取っても十分間に合うようだった。

Gはちょっと難しい。約数包除をしたいなと思った。すると、すべての1\le d\le 10^5に対して、d\mid A_iなる頂点iだけを考えた上で全パスの頂点数の和を求める必要がある。逆に頂点id\mid A_iである場合しか考えなくてよいので、全体でO(N\sqrt{\max A_i})個の頂点を見ることになる。約数の個数なので実際はもっと少ない。ここでTLが8secであることに気づき、実装を決意。各dに対して考えるべき頂点をvectorに持ち、先頭から舐めつつ木dpをする。グラフを毎回構築せずとも、uに到達したら隣接する各頂点vに対しd\mid A_vを満たすか判定しても良い。この判定回数が十分少ないことは、辺に注目して、一方からもう一方を見る回数を考えればわかる。パスの長さではなく頂点数を考える必要があるため木dpもちょっと難しかった。最後に包除原理……ではなく、いわゆる除原理を行うことで\gcdを固定したときの全パスの頂点数の和が出る。固定した\gcdを掛ければ答えに。

Exがちっとも分からず、残り時間はコードゴルフをしていた。7完1ペナで28位。Eは2点固定した後、傾きを求めるのではなく直接その直線に乗る点を数えればよかったらしい。

コードゴルフ。A問題は、桁和\bmod 9を求めてしまうと09が判別できない。ただし、dcでは読み込みの基数を変えられるので、10進法から外れることでまたいろいろできる。試行錯誤して、13進法で桁和\bmod 12を求め、9からその値を引くことで答えが出せることを発見した。ただし全く同じコードがコンテスト開始10分程度で提出されており、敗北。Bもdcで書いてみたが、朝になって見覚えのあるテクで縮められ残念。衰え。Cは普通にRubyで書いた後Vimに直したものが最短になっている。DもRubyで二分探索。インデックスのリストはgroup_byで見つけることにしていて、そこの改善で結構争っていた。以降は手付かず。

午後11時半からCodeChef、April Lunchtime 2022 div.1に出た。

https://www.codechef.com/LTIME107A

GCD_LCMは簡単。とりあえず、直感的にn素数で操作するとしてよさそう。その方針で考えると、X素因数分解したうちのp^eの項について、e\leftarrow \min( (e\bmod c),c-(e\bmod c))とすることができるとわかる。ここまで操作が把握できれば、n合成数として操作しても特に状況に変わりはないことが言える。

CONSTMEXはちょっと面倒。P_L\lt P_Rと固定して変化を観察してみる。元々MEXがP_L未満の部分列はどうでもよい。MEXがちょうどP_Lになる部分列が存在するなら、P[L+1\dots N]はその一例になっているはずで、とりあえずこの部分列のMEXはP_L未満である必要がある。次に、MEXがP_Lより大きかった部分列からP_Lが消えることがあるかどうか。これは部分列P[1\dots R-1]をチェックすれば十分。この部分列のMEXもP_L未満である必要がある。逆に、以上の2条件を満たせば交換可能であるとわかる。よって、まず両端からのMEXの列を求め、P_Lの昇順にカウントすることにした。Rの条件はL\lt RL\gt Rに分けて考える。BITを持って、条件を満たすようなRの位置に加算しておくことで、区間和でカウントできる。実装はちょっと大変だった。

MODCIRCはすんなり。とりあえずAはソートされているものとする。基本的にB=Aとするのが良さそう。なので、逆に\max A=A_Nから\min A=A_1までをどのように繋げるか考えればよいという話になる。残った要素は昇順に並べれば全部丸々使えるので、そこから引いてA_NA_1を繋げる一部にするときのコストを定める。つまり、iの次にjを置くコストが-A_i+(A_i\bmod A_j)となる。で、コンテスト中の僕はこの次にj\rightarrow kとするのではなく、いったんj\lt j'なるj'を挟むケースがあるのではないかと思っていた。まあ区間MINから遷移すれば対応できるかなと思いつつ、実装時にはそれをすっかり忘れてしまっていた。サンプルが合って提出直後に気づくも時すでに遅しで、しかしそのまま通った。冷静に考えれば、(-A_j+(A_j\bmod A_k))-(-A_{j'}+(A_{j'}\bmod A_k))=(A_{j'}-A_j)-( (A_{j'}\bmod A_k)-(A_j\bmod A_k))であり、(A_{j'}\bmod A_k)-(A_j\bmod A_k)\le ( (A_{j'}-A_j)\bmod A_k)\le A_{j'}-A_jとなるため、j'を挟むような遷移は得しない。

PALANDはヤバい。貰う遷移の区間dpを考えた。「あるbitが立っていない、最も近い要素」を左右で求めておくことで、bitwise ANDとして候補に挙がる高々30種類を効率的に列挙できて、さらにそれぞれについて貰ってくるべきdpの範囲もわかる。ただしその範囲は2次元の領域になっている。これを2次元BITでゴリ押してみた。O(N^2(\log N)^2\log \max A)。1回目の提出は当然TLE。手元で適当なケース(2のべき乗引く1しかない)を試すと3.5secだったので、区間が潰れているときは即座に0を返すという高速化を入れた。すると今度はWAになった。さてランダムケースでチェックするか……と思いつつ実装を進めていたら、modの値を勘違いしていたことに気づいた。修正して投げなおすとAC。1.5sec。

最後の問題は全然わからなかったため、ラスト30分はハーメルンを読んでいた。4完13位で2640→2654(+14)。途中何回か順位表を確認していたのだが、一時1ページ目の25人中15人が日本人でさすがに面白かった。

PALANDの想定解はさすがにこんなわけがなくて、遷移順を工夫することで2次元累積和を求めながら更新できるということだったらしい。また僕のコードがTLEするケースもTLに流れてきた。以下のコードで生成した入力だと手元で4.15sec。もうダメダメ。

ノクターンノベルズから1作読了。およそ一年ほど前にいろいろ読み漁っていた時の残骸がスマホのブラウザのタブに延々残り続けていて、そのうちの一つを消化したという形。今の好みではない。

https://novel18.syosetu.com/n7278ce/

日曜日は久しぶりにOpenCupもAtCoderもないので生活リズムを気にしなくてもよい。朝から昼までずっと溜めていた日記を書いていた。めちゃくちゃ集中が切れて、終盤は大部分の時間でYouTubeを見ていたようだ。午後3時までかけて水・木・金しか書けなかった。午前10時くらいにABC248に提出するとめちゃくちゃジャッジが詰まっていて、何かと思って全体の提出を見ると、Ex問題に延々無限ループを投げ続けているアカウントがあった。すぐにBANされて、朝からお疲れ様ですという気持ちになった。

布団に入り、1時間ほどカクヨムを読んで午後4時半就寝。

04/17(日)

消えた。土曜日以降の日記は月曜日の朝に書き上げて投稿した。