週記(2021/09/27-2021/10/03)

09/27(月)

先週は週記を書いてからすぐ布団に入ったが、そのあとPixiv小説をちょっと漁ってしまい、結局寝たのが午前8時半だった。

午後1時半起床。しばらく布団でウダウダした後、大学生協に行って注文していた本を受け取ってきた。

午後3時からインターンの業務を進める。先週したことをまとめて、直後に迫った定例会で報告するための資料を作っていた。載せるデータを吟味していたら思ったより時間がかかり、ギリギリになって完成。発表自体は特に問題なく済んだが、そもそもデータが足りていないのでは?という話になって、アクセス権限が足りていない可能性があることが分かった。これは困った。とりあえず明日の1on1で話し合ってどうにかする予定だが、それまではすることがない。まあ今日は週末の疲れが残っているので、することがないならないで今のうちに体を休めておく。

Kaggleの新しいコンペが始まって、これはチーム制限が5人なので、ちょうどインターン先の興味があるメンバー全員が1チームにまとまることができる。早速チームを組むことになった。以前の週記で言及したかもしれないが、一応今Optiver云々というコンペに個人で参加してはいるものの、興味が離れて最近は手付かずだった。出だしで躓いていては世話がないので、何とかこの新しいコンペで自分なりのKaggleへの取り組み方というものを見つけたい。しばらくはコンペの内容だったり公開カーネルを読んでいた。

余った時間で、Kaggleに興味がある面々が集まってチームを組もうという話になった。チームを組むということ自体に非常に興味があって、ぜひやってみたかったのだが、残念ながらコンペのチーム人数制限が3人だったので組めなかった。以前は5人だったらしい。

週記(2021/09/06-2021/09/12) - kotatsugameの日記

CodeChefの先週のコンテストまとめ記事がメールで送られてきた。div.3の優勝者の部分に自分の名前が載っていて気持ちいい。自己顕示欲が満たされていくのを感じる。

ラノベを1冊読んだ。「王様のプロポーズ」。「デート・ア・ライブ」の著者・橘公司さんとイラストレーター・つなこさんのコンビの新作で、あらすじもかなり面白そうだったので、楽しみにしていた。実際素晴らしく面白かった。まず設定が自分の最近の好みにピッタリ一致していた。「最強の能力者」も好みだし、「主人公が学園長」も好み。しかも「学園長がその学園に通う」という展開に至っては、好みに好みが掛け合わさって掛け値なく最強に見える。そういうストーリーがありなのか。まさにコペルニクス的転回と言って過言ではないだろう。

序盤はいろいろ後に続きそうな展開が盛りだくさんだったので、もう何巻か出ることを見越して、1巻は準備の巻かなと思いつつ読んでいたが、思いのほかラストで話がまとまってびっくりした。非常に満足したが、2巻以降への期待が薄れたわけではない。あとがきによれば続刊が出ることが確定しているわけではなさそうだったが、ランキングを見るに売れ行きは好調なので、きっと出てくれるだろう。

実はかなり眠くて、ラノベを読んでいる間ちょっと意識を飛ばしたりしていたが、ラストが良かったので目が覚めてきた。次に「デート・ア・ライブ マテリアル」2巻を手に取って読み始めた。著者とイラストレーターの対談を読みながらその巻を思い返して非常に感慨深くなっていた。12巻などは男主人公がピンの表紙イラストになっていて非常に好みだった。この巻が出た頃に既刊を一気に買ったことを覚えている。

そこそこで切り上げて、ABC220-Eのコードゴルフをした。この問題はPythonによるゴルフがしばらく行われていたようで、なかなか短い計算式が以下のように最短を保持していた。しばらく考えていたら自分でも再現できたので、安心。

atcoder.jp

基本的に解説と同じ方針、つまり2頂点のLCAを固定して数え上げている。LCAの深さが0\le i\lt Nであるとすると、まずi+D\lt Nであれば答えに2^D\times 2^iが足され、さらにD\gt 1であれば、0\lt k\lt Dかつi+k\lt Nかつi+D-k\lt Nなるkの個数に応じて2^{k-1}\times 2^{D-k-1}=2^{D-2}かける2^iが足される。最後に、以上で求まった組の左右を逆にしたものを考えて、答えを2倍すればよい。2倍するのも2のべき乗を求めているときに行うことにすれば、i+D\lt Nのとき2^{D+i+1}を、また上の範囲の幅に応じて2^{D+i-1}を掛ければよいことになる。D\gt 1という条件は、この式変形によって必要なくなる。2^{D-2}を計算しなくなるし、D=1のときはkが取りうる値の範囲が常に0に等しいからだ。

さて、kの範囲をより精密に考える。区間の右端としてN-iまたはDを、左端としてi+D-Nまたは0を考えるので、この2×2を計算してminを取ればよい。計算すると、区間の幅は\min(2(N-i)-D,N-i,D)-1になるようだ。k=N-iとおいて場合分けすると、k\gt Dのときは\min(2k-D,k,D)=Dであり、k\le Dのときは2k-Dとなる。ここで区間の幅は正になる必要があるため、2k-D\gt 0よりk\ge\left\lfloor\frac D 2\right\rfloor+1が必要となる。

i+D\lt Nという条件はD\lt N-i=kと書き直せるから、結局1\le k\le Nに対してk\gt Dならば2^{D+N-k+1}+2^{D+N-k-1}\times(D-1)k\le Dならば2^{D+N-k-1}\times(2k-D-1)を答えに足す、とまとめられる。前者を2^{D+N-k-1}でくくり、kの代わりにk-1を考えれば、先の提出の式が得られる。

試しにdcで計算してみたところTLEしなかったので、それで縮めることにした。毎回2のべき乗を計算するのはまずいが、kのループを降順に行うことで、ループごとに2倍するだけで計算できるようになる。掛け合わせる数の場合分けは単純なminというわけにはいかないが、何とかして、73Bの解ができた。制約にD\le 2N-2がなくてキレそう。

atcoder.jp

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

09/28(火)

昼前、腹を壊して目覚める。トイレに行った後またすぐ寝て、次に午後3時半に目覚ましで起きた。午後4時の1on1のためにかけていた目覚ましだったが、ギリギリに起きるのも怖いものだと分かった。

明後日木曜日のCHUNITHMのアプデ情報が来ていた。もう見るからにラスボスですごい。@anayama_daisuke というラスボスの曲ばかり作っている人のアカウントが昨日の夕方にそれっぽいツイートをしていたので来ること自体はわかっていたが、作曲者が5人もいるのにはびっくりした。「ep. Grandioso」というマップ名も特徴的。

今日の1on1は、昨日から特に進捗もなく、やっぱりデータ足りていないですねという話になって、権限付与が完了するまではインターンに関係ないことを済ませておくことになった。具体的には10月第一週の木曜日に迫った4年ゼミの発表準備である。

1on1が終わって、あまりに眠いので布団に戻った。しばらくスマホを弄っていたが、午後6時半くらいに本格的なお昼寝の体勢になり、そのまま日付が変わるまで寝ていた。ここで日記の日付も変えておくのがよいと考える。

09/29(水)

午前0時起床。僕が寝ている間に権限付与が完了していた。素早い対応に感謝。

@anayama_daisuke というアカウントから、ラスボス曲の譜面の一部が動画でツイートされた。数年前に混沌で初めて見たときはびっくりしたが、これも恒例行事。25秒の動画からいろいろ情報が得られる。まず譜面定数14.0以上が確定し、この時点でレート理論値が16.00を超えることが分かったらしい。一体何色の表示になるのだろうか。またノーツ数は4444で、これはつい最近出た「赤壁、大炎上!!」を抜いて最多ノーツ数である。タップスライド以外での16分割タップも当然のように配置されており、新時代という感じが強い。

CF #744 div.3が始まっていたので、1時間遅れで参加し、1時間弱で全完した。

Dashboard - Codeforces Round #744 (Div. 3) - Codeforces

Aはよい。Bは先頭から合わせる。Cは作れるチェックを全部作る。Dはよく難しい問題の部分問題として見る設定で、多いもの2つをどん欲に組にしていけばよい。特に証明したわけではないが……いいだろう。個数の最大値が小さければそれだけ自由度がある。E1は後ろから見て残りの最小の要素を先頭に、それ以外を末尾に入れる。E2も後ろから見ると、その要素が絡む転倒数が計算できるため、小さいほうに振り分ければ残りの列はそれだけで考えればよいことになって、貪欲。Fは操作でANDを取ることになる列たちに分解し、それぞれ全部0になるまでに必要な操作回数を計算する。Gはdpで、現在の終点からすでにカバーした範囲の左右までの距離で状態をまとめられる。これでも状態が3次元だが、bool値のdpになり、実際1つの次元の値は最小値さえ考えればよいことが示せるので、2次元のdpに落とせる。

ARC084-D「Small Multiple」が縮められていたので考えていたら、大幅に縮め返すことに成功した。

atcoder.jp

01BFSをするため、配列の先頭と末尾に挿入する必要があって、コード長的にも実行時間的にも重かった。これを、コスト0で遷移するループとコスト1で遷移するループをうまく分けることで解消でき、しかも短くなったというのが驚き。リストを用意して先頭から走査する。コスト0の遷移についてはリストの末尾に追記することで、同じループでそのまま走査していってくれる。コスト1の遷移は、今見ているリストを書き換えることで次回のループの時に走査してもらう。コスト自体は外側のループで管理しているため遷移の際に考える必要はなく、ゴールにたどり着いたと判定されたら外側のループを抜ければOK。

デート・ア・ライブ マテリアル」2巻を読んだ。設定の話とかは非常に興味深く読めたが、正直ゲーム特典SSなどはゲームオリジナルキャラをよく知らないため、微妙……。あとは作中時間も大幅に前後しているため、あまり出てこないキャラがいたりするが、短編集として出されているわけではないため我慢できる。ゲーム展開もしているなんてすごいことではないか。

インターンの業務に関連して、新しく使えるようになったデータを処理するコードをずっと回していたが、全然終了する気配がない。このあたりのコードの改修をデータが非常に少ない状態で行えたのは、むしろ僥倖だったのではないかという気持ちになってきた。

午前10時になったのを見て、学食に行くことを思い立つ。営業時間を確認すると午前8時から空いているようだったので勢い込んで行ってみると、午前11時半からの開店だった。実は僕が見ていた営業時間の表は、10月からのものだったのだ。仕方なく、購買で少し買い物をした後は前の広場で1時間くらいハーメルンを読んでいた。

食事して帰宅。ツイッターを見ていると、「ゴルゴ13」で知られるさいとう・たかを氏が亡くなったとのニュースが流れてきた。生前から漫画の分業体制を整えていたという話で、この先もその体制を維持してゴルゴ13の連載は続けられるらしい。

ラノベを読んでいたが、午後3時くらいに急激に眠くなり、布団に倒れこんだ。午後11時まで寝てしまった。とんでもない生活リズムになった。

起き抜けに確認したこととして、まずCF #744 div.3のHackフェーズが終了し、全完が確定していた。次に、寝落ちするときにも動かしていたスクリプトがエラー落ちしていた。実際はPythonスクリプトいくつかをシェルスクリプトでまとめていただけなので、それ以前のスクリプト(8時間かかっていた!)の出力は保存されているが、エラーの原因がスクリプト名指定ミスでげんなりしてしまった。

今日の初めのほうで縮めたARC084-Dがさらに縮んでいた。Vim部分の更新で、ある行の左と右にそれぞれコードを挿入したい場合、IAを使うとセミコロンが必要になるが、Ioだと改行がコードの区切りになってくれるという話らしい。同様の手法が適用できるコードがいくつかあったので、探して縮めていた。

atcoder.jp

ゲノコン2021のシステムテスト・表彰式が終了して提出がすべて公開されたので、AtCoderProblemsでクロールされるようにプルリクを出しておいた。ゲノコン2021のD問題は、適当な文字列を2回出力するTextと、入力の1行目を2回出力するsedコードを提出していた。Textについては空文字列を2回出力する2BでACできたが、sedはさらに短く、pのみのコード1BでACできた。どうやら、出力の先頭2行を読み込んだら残り何が出力されていてもどうでもいいらしい。

Add genocon2021 by kotatsugame · Pull Request #1066 · kenkoooo/AtCoderProblems · GitHub

起きて落ちていることを確認したスクリプトだが、改めて実行してしばらく放置していたところ、どこからかキィーみたいな音が断続的に発生するようになった。恐る恐る部屋を調べていると、パソコンから出ていることが分かった。HDDのシーク音だろうか。確かにファイル読み書きが多く発生するスクリプトなので、しばらくは我慢だろう。で、我慢していると実行が終了した。これまで扱ってきたファイルよりサイズが非常に大きいらしく、書いたコードが一部動かない。とりあえず、ファイルサイズをヒストグラムにして確認したいと思ったので、サイズをcsvファイルに出力するのはPythonで、ヒストグラムOctaveなんぞ起動してちょっと弄っていた。いい感じのグラフができて満足。

あとは、今まで長い時間をかけて作ったデータを機械学習のコードに流し込んで動かす。スクリプトを実行してみると、今度こそパソコンのファンの音がすごいことになったが、触ってみた感じ熱を持っているわけではないので、安心。ただデータが増えたのでかなり時間がかかりそう。寝ている間に終わるだろうか。

布団に移動して俺ガイルの新刊を読んでいた。途中、「知識の泉」と「混沌の欠片」という単語が出てきて、GOSICKのネタだと気づいた。あまりにも脈絡がなくてびっくり。そういう風に出てきたネタであって、気づかず通り過ぎたものがいくらでもあるんだろうなあと残念な気持ちになった。

午前5時半就寝。

09/30(木)

午前9時半起床。すでにチュウニズムのアップデートの情報がいろいろ流れてきていた。レート16.00を達成した人も現れた。レートの色は変わらないようだが、称号が虹色に光っている。非常にカッコいい。この「皇帝」という称号は、チュウニズムの現行バージョンでレート16.00を達成することが条件のようだ。わざわざ現行バージョンという制限を付けたということは、次回作からレートシステムに変更が!?……というようなことを考えていた。無論僕の実力的にはほとんど関係のない話であって、ただのランカー厨。

せっかく起きたので、SRM814に出た。全完4位、2443→2540(+97)。SRMで全完するのは初めてかもしれない探したら2年半前に全完していた。

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

Easyは前にしか進まなくてよいことを確認してやるだけだが、制約が5\times 10^5なのでスライド最小値でlogを落としておいた。Mは素因数分解して各素数の指数を見る。素因数分解100\times\sqrt{10^{12}}で、毎回やって間に合うか不安だったので、素数を前計算しておくことにした。置き換える値はALCAでよく、LCAが一致しない場合は必ず1個置き換える必要があることに注意。Medを落とした人はこれを見落としていたらしい?

Hardは2べきで作ろうとしたが難しそう。適当に1直線にマスを置いてみたところ、トリボナッチ数列が現れることに気づいた。フィボナッチ数列を適当に組み合わせると任意の正整数が作れることは有名だが、ではトリボナッチ数列では?と思って探索してみると、制約の範囲内(109以下)ではちゃんと作れることが分かったので、この方針で実装。1直線のマスの適切な位置から分岐して、残りが1本道になるようにしたい。別に3本くらい1本道を用意しておいて、そこに合流させることにした。分岐が連続すると、その間で移動ができてしまうな……と思っていたが、逆に連続した分岐はそこで1本道にまとめてよいことに思い至り、あとは右下を手作業で構築して完成。

昼頃1on1をした。昨日パソコンをぶん回した結果を報告した。データに不要な箇所が大量にあるという指摘を受けて、それを単純に削除して様子を見て、また明日の1on1で報告することになった。業務ばっかりやっているようだが学業は大丈夫か、と心配していただいた。そのあと閉店前の学食に急いで駆け込み、食事。

帰宅してラノベを読んだ。「やはり俺の青春ラブコメはまちがっている。結」1巻。年末年始の話を、由比ヶ浜結衣に着目して描きなおした感じだろうか。正直この辺り、本編で描かれたのが昔過ぎてあまり覚えていないが、覚えていなくてもエモいものはエモい。

チュウニズム14新曲の譜面動画がYouTubeに投稿されていたので視聴していた。MASTERで16分割ノーツが多用されているのは当然として、赤譜面にも16分割があってびっくりした。動画のコメントを見た感じでは振り下ろしエアーも赤譜面初らしい。

明日から新学期なので、履修計画を立てようとしたが、春先にダウンロードした資料を夏休みの間に削除してしまったらしく、新たにダウンロードしてくる羽目になった。院試に合格したので大学院の講義を先行履修することができるらしく、どんな講義があるのか調べてみたところ、4年生向けの講義と全く同じでびっくりした。つまり、同じ講義でありながら4年生向けとして履修すると学部の単位になり、大学院生向けとして先行履修すると大学院の単位になるらしい。学部の単位はもう足りているので、先行履修できないか4年ゼミの教員に聞いてみたいと思う。

午後7時過ぎからCF #745 div.1。10分こどふぉった。4完15位で2952→2998(+46)。あと2……。

Dashboard - Codeforces Round #745 (Div. 1) - Codeforces

Aから難しい。単純に4乗したくなるが不可能で、2乗で幅を決めた後、累積minなど使って高さを決定することにした。累積minの計算にも、ある行の区間内の'1'の個数を定数時間で求める必要があったりと、非常に面倒だった。

Bは非常に難しい。挿入dpでもどのように挿入するかが問題。大きい要素からどこに配置するかを決定するのが正解。今のところ最大値として何種類ありえるかをインデックスごとにカウントしておきたい。これまで配置した要素で数列はいくつかの区間に分割されるが、この区間内でカウントの値はすべて等しいから、区間の幅O(N)とカウントO(N)で状態をまとめることができる。それぞれ、区間内のgoodな要素の個数O(N)に対応して場合の数を持つ。遷移は、区間内のどの位置に要素を置くか、左右でgoodな要素がいくつあるか、でO(N^3)になる。O(N^5)で一度TLEを食らった。goodな要素はそれほど多くならないので、余計な個所を見ないようにすると通った。

Cはx_i+y_iの値が\sqrt nより大きいかどうかで処理を分ける。大きい場合はimosで愚直にカウント、以下の場合は\bmod{x_i+y_i}のテーブルを用意しておいて、そこを書き換える。imos法を使うことでlogがつかないようにした。おそらくそれを要求するためのTL 1secだろう。Dは、区間の最大値で分割して、マージに左右の列の長さの積だけかかるdpを書いたら爆速で通った。やっていることは、数列から作られるCartesian Tree上の2乗の木dpと同じらしく、このことから計算量解析ができるらしい。適当に投げてしまったが、面白い。

システスで上から4人ほど落ちて15位になり、LGMまであと2になってしまった。BとCで1ペナずつ吐いていて、どちらかがなければ14位だったのでLGMを達成していただろう。特にCのWAは、スコープ外の変数を書き換えるつもりで新しく変数を用意していたという理由だったので、非常に悔しい。処理を変えるしきい値を小さくしてデバッグするのをすっかり忘れていた。

「株では勝てる俺も、カワイイ女子高生には勝てない。」2巻を読んだ。1巻の個人的な評価は低めだったが、2巻は思いのほか面白く読めた。主人公に人間性がない描写は控えめになっていて、多少受け入れやすかった。ヒロインがディープラーニングで株価変動を予測しようとして、案の定莫大な損失を抱えてしまうという展開は、導入部分から破滅が約束されていて目も当てられなかった。それでもラストはいい感じに落ち着いたかと思ったが、急に不穏な感じの描写が挟まって心臓が休まる暇がなかった。

動画を見たりしているうちに、うっかり椅子の上で意識を飛ばしてしまった。ふと目を覚ますと、昼の1on1が終わってからずっと動かしていたスクリプトが最後の最後に「強制終了」と出て落ちていた。そういうエラーメッセージが出るような落ち方とはいったい何だったのだろうか。必要なデータは適宜ファイルに書き出してあったので、とりあえずそれを処理するコードを動かして布団に移動し、改めて寝た。午後11時半だった。

10/01(金)

午前6時半くらいに目を覚ました。その時はいい感じに眠気が残っていて、またしばらく眠れるはずだったが、うっかりスマホを手に取ってしまい全てが崩壊した。

Twitterで何かのゲームと東方がコラボしたときの霊夢が流れてきた。なかなか可愛らしい。

布団から出て、今日の夜にCFで行われるICPC WF MirrorにICPCチームで出るため、人をinviteしたりレジったりしていた。Slackに投げるとすぐ反応があったから、実は見てくれているんだなあと感動。僕が引きこもっているだけで、誘えば普通にICPC練習を連打できるのかもしれない。もしくはたまたま僕から誘ったから無理して出てくれたのか。

数時間かけて日記を書いて、読書記録もつけて、9月分の集計をツイートした。今月は結構読んだし、あまり本を買わなかったので、久しぶりに積読の数が減ったらしい。焼け石に水な気もする。

そのあとは今学期の履修登録をしていた。昨日も言及したが、改めて大学院の科目で先行履修したいものを選び、4年ゼミの指導教員にメールを出す。すると一瞬で承認してもらえたので、そのメールを証拠として含めて、改めて大学の事務方にメールを送信した。また、通常の履修登録の画面を開いて、1講時ずつ履修可能な科目を確認していく。科目名で気になったものがあれば、シラバスで内容を確認してみる、という感じ。

意識が高すぎてさらに2科目履修登録してしまった。「Pythonによるデータ科学入門」と「計算物理学」。どちらもPythonでプログラミングをする何かである。前者は、最初数回以降は対面で講義を行うというようなことが書かれており、不穏。しかし学部生活最後であることだし、講義棟まで足を運ぶのも一興か(こんなこと言っていて、どうせその日になれば行かない確率が高いが)。プログラミング関係では、探せばR言語を学ぶ講義もあったのだが、グループを作って発表しあうというようなことが書かれていてスルー。他に「インターネットを誰が守るのか」とか「批判的思考と論理的文章」という講義にも興味を惹かれたが、冷静に自己診断すれば面倒さが勝ることに気づけた。

これで今学期は講義を3つとる予定だ。それらのクラスコードを探してClassroomに登録し、ちょっと中を覗いてみた。まだ初回授業前なので、特に見るべきものはなし。

富士見ファンタジア文庫が、自社ラノベのキャラを集めて作ったクロスオーバーRPG「ファンタジア・リビルド」がある。ラノベの帯によく広告が出ていたので認識はしていたが、残念ながら今年の12月、公開から1年でサービスを終了することになったらしい。シナリオ担当もキャラも、ラノベ読みからしたら超豪華な布陣だが、ゲーム業界は厳しいものだ(プレイしていないのにどの口が言うか)。

午後になってしまったので、学食が閉まる前に急いで大学生協に行く。行きは普通に雨が降っているなあという感じだったが、ちょっと昼食を食べているうちに土砂降りになって、靴の中を濡らして帰ってきた。濡れた靴を乾かすため、わざわざ実家から送ってもらった古新聞を詰めていたら、その新聞がコロナ禍前のものであることに気づいて、ちょっと感慨深くなった。

自分は出不精なものだから、コロナ禍でも比較的影響を受けなかった人なのかもしれないが、影響がゼロというわけでは決してない。外出時にマスクが手放せなくなったとかそれ以前に、人が密集している状態に違和感を覚えるようになってしまったのだ。これはTwitterでもたまに流れてきた話で、過去の写真や動画などを見ていても、密な状態を検出して勝手に嫌な気分になってしまう。我々の認識の根幹を揺さぶってくる、そういうウイルスだったのだ。

そのとき考えていたことを時系列で並べているだけなので、話は変わるが、「ら抜き言葉」について。可能の助動詞「れる・られる」の使い分けは、付く動詞が五段活用・サ行変格活用の場合前者、それ以外は後者である。このことは高校生のころよこに教えてもらったもので、それ以来この判別に従ってらを入れたり抜いたりしている。僕が文章を書くときは、その判別でちゃんと思考が一時停止するため、週記でもら抜き言葉が出現しないようになっているはず。

眠気が強くなってきたので、午後5時の1on1まで1時間ちょっと寝ることにした。布団に入って人の週記を読んでいたら思ったより時間が経ってしまい、90分周期の睡眠が難しい状態になったが、強気のお昼寝。ちゃんと1時間時点の目覚ましで目を覚まし、しばらく布団の上で唸っていたものの、無事身を起こすことに成功した。

実は昨日の夜CFに出つつパソコンをぶん回していたので、1on1で報告すべき進捗はちゃんと用意されていた。いよいよ機械学習が本格化しそう。毎日作業を進めるのではなく、いったん時間を取って使いそうなモデルについて学び、実際にデータに適用して理解を深めることになった。

午後7時半から午後9時までまたお昼寝。今度も起床に成功して、yukicoder 316に出た。1時間で3完して午後10時からCFに出た。

yukicoder contest 316 - yukicoder

Aはよい。Bはコインの枚数を決め打って必要な操作回数の最小を考える。必要な操作回数の最小がk回だとすると、左端からkマスにはコインが置いてある必要があって、それ以降は自由なので、組み合わせで計算できる。Cはちょっと手で試した感じ0110の交換だけ考えてもよさそうな気がしたので、1がどれだけ動いたかを持ってdpしたら通った。後から解説を読んで証明を確認。操作によって、文字列の先頭から各1までの距離の和が変化しないことを使って示せるらしい。

残りは難しそうだと思ったので放置してCFに専念していたのだが、思ったより解かれていて順位がひどいことになった。ともかく、CFのICPC WF Mirror。5時間のコンテストである。

Dashboard - ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred) - Codeforces

ひどい目にあった。序盤EとHが解かれていて、Eはすでにチームメイトが取り組んでいたのでHを読んだ。Hは構文解析やるだけで15分で通ったが、以降L問題にハマり続けて4時間45分椅子を温めた。コンテストが終わってTLに流れてきたツイートを読んでもピンと来ていない。

しばらく日記を書いてから、朝方、ふとあるGitHubリポジトリのcollaborator一覧を確認したくなった。普通にGUIから見れるものだと思っていたが、認証付きAPIを叩かなければいけないらしい。調べたQiita記事ではPostmanを使って、通常の認証としてユーザ名・パスワードを入力しつつ叩いていたが、僕が試した限りではブラウザのURL欄に直打ちするのと同じく認証が必要であるとの文章しか返ってこなかった。やはりOAuthを使わなければどうしようもなさそう。公式ドキュメントを確認したいが、かなり眠気があって英語を読むのが辛いな……と感じていたら、日本語のドキュメントを見つけた。これに従ってやってみると上手くいったものの、自分が管理しているリポジトリでないとcollaborator一覧が取得できないらしく、結局ダメだった。

REST APIを使ってみる - GitHub Docs

布団に入って少しラノベを読んだ後就寝。午前7時半だった。

10/02(土)

途中何度か意識を取り戻した記憶はあるが、そのたびにまたすぐ寝直せていた。結局午後8時起床。

寝ている間にチュウニズム14新曲のAJが陥落していた。初日AJが出なかったのはバンキシャ以来だということで話題になっていた。バンキシャが追加されたのは僕がチュウニズムを初めてからで、それほど昔とは思っていなかったが、調べてみるとほとんど4年前の楽曲らしかった。

atgolferにいくつか更新が流れてきており、それらを確認しているうちに午後9時になったのでABC221に出た。G以外の7完。

AtCoder Beginner Contest 221 - AtCoder

Aはdc。プルプルしながらタイプしていたらFA+1秒だった。Bから面倒だったのでC++。Cは分割パターンさえ全探索すれば、それぞれは降順ソートするのが最適。Dは何も考えずに座圧してimosしたが、普通にソートした後カウント変数を管理するだけでも良かった。Eは「取り出した列の第2項以降が初項以上である」という条件だと勘違いしてしまった。この勘違いはサンプル4でしか落ちないので、念のため確かめてギリギリセーフ。誤読を修正するのにもいくらか時間がかかった。気づいてしまえばあとはBITで管理するものを変えるだけなので、簡単。Fは、まず適当に直径パスを取ってくる。直径パスの中心がちょうど頂点なら、そこから出ている辺の先にある頂点(十分な距離があるものだけを考える)をそれぞれ選ぶか選ばないかという話になる。2つ以上選ぶ必要があるので、ちょっとしたdpを行った。中心が辺なら、辺の両端の先にある頂点をそれぞれ選ぶ必要がある。

Gはしばらく考えていてもよくわからなかったし、そうしているうちにHのsolvedが増えてきたので、Hに移った。商で分類することをずっと考えていたが、それはO(N^2\sqrt N)になっていかにもまずそう。残り30分くらいで大幅に方針を転換した。冷静になると、Mの制限を外した問題がそのまま写像12相に存在する。玉も箱も区別せず、各箱に玉を1個以上入れるので、分割数P(n-k,k)というやつだ(ただし、コンテスト中は新しく箱を増やすときに玉を1個入れた状態で追加していたので、遷移が微妙に異なる)。全体に玉を追加したタイミングで、その後連続して箱をM+1回増やした場合の遷移先から前もって値を引いておくと、そこまで遷移していったときにうまいことvalidな状態のみを残すことができる。このことは、斜めに累積和を取りつつimos法を行っているとも理解することができるが、斜めに累積和を取るとか考えると頭を壊しがちなので、むしろ意識しないほうがうまくいくはず。

午後10時半からCFで何かのミラーコンテストがあったので、昨日と同じくICPCチームで参加した。結果はADBJGLIKHをこの順で通して9完。

Dashboard - COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred) - Codeforces

Aから読み始めたが、Aが最も簡単な問題で、本当にこれでよいのかと首を傾げながら出したらFAだった。入力が106文字とちょっと怖いところだけが不安要素か。当時は気づいていなかったが、入力文字列がすべて同じ長さであるところから偶数番目の文字だけ反転する解法の正当性が簡単にチェックできる。Dは頑張って探索する感じの問題に見えるが、制約がギャグなので全探索できる。Bはどう見ても二分探索してくださいという見た目をしていて、その方針で考えた。適当にrを決め打った時にある点を含むような円は、原点から中心までの角度がある区間の内部に収まるという条件で表せる。この区間は円の交点の計算を流用すると求まる。そもそもどうやっても内部に含められない点をケアし忘れていて2WA。Jはチームメイトが通した。

このあたりでしばらく時間が空いて、100分ほど格闘してGが通った。最初の方針が、\sum_{i,j}\sum_{k,l}\gcd(a_i,a_j)\gcd(k,l)を求めた後うまいこと引き算して(i,j)=(k,l)なる場合のみ残すという方法だったが、これは結局iを固定してj\lt lに対して和を求めるような形が出現し、gcdを分離することができなかった。方針を大きく切り替える。ある数列\{b_n\}が与えられたとき、数列の要素の約数をそれぞれカウントしておくことで、値xに対して\sum\gcd(b_n,x)を求めるのを包除原理を用いてO(d(x)^2)(ただしd(x)xの約数の個数)で行える。個数カウントではなくて適切な値を足しておけば、重み付きgcd和も求まるので、まず数列の添え字の各約数に対応させて値をvectorなどに溜め、vectorの各要素をxvectorそのものを\{b_n\}として上記の計算を実行し、得られたgcd和を重みとして再度添え字の方で重み付きgcd和を求めればよい。

これだと約数の個数の2乗が出てきて、105以下の最大の高度合成数が約数を130個近く持つため、TLEしてしまう。同じ値が出現する可能性のある場所はmapを使って結果を持っておいたり、そのmapを使っていた箇所を配列(と配列の値を書き換えたタイミングを記録する列)で置き換えたりしたが、まだ間に合わない。ここで、O(d(x)^2)の部分は、xの約数のペア(p,q)であってp\mid qなるものを考えていたので、そのペアを最初に列挙しておくことにしたら、2sec弱で通った。

しばらく時間が空いたので、順位表で人間向け問題が一目瞭然になっていた。まずLは、dp_iへの遷移元の条件がj\lt iかつa_j\lt a_iかつa_i-i\le a_j-jと書ける。ここでa_iがpairwise distinctだとすると、a_iの昇順にiを見ていけばa_i-i\le a_j-jからi-j\ge a_i-a_j\gt 0が導けるため、j\lt iという条件を考えなくてよくなる。このことはpairwise distinctでなくても(a_i,-i)の昇順にソートすることで同様のことが言えて、a_i-iをセグ木のインデックスにすれば実家dpができる。方針だけ示して、実装はチームメイトに投げた。

次にI。\max(|a_x+a_y|,|a_x-a_y|)という式を分解すると|a_x|+|a_y|になったので、ほとんどギャグみたいなもの。更新はオイラーツアーして部分木に対する区間加算で行える。更新後に重みの配列を更新しわすれて1WA。このあたりでKの考察が完了していたので、マスがぴったり重なるコーナーケースを指摘しつつ見守っていたら通った。Hも思ったより簡単で、部分文字列bを受理するオートマトン上でdpするいつものやつ。Aho-Corasickのfailure関数みたいなものを計算する必要があったが、制約が小さいので愚直にやっても間に合う。

そのあとはE問題を考えていたが、パスのコストを単純に辺の本数で定めた場合の問題すら解けず厳しい。終了間際にC問題の解法っぽいものがチームメイトから出てきたが、実装する時間がないなあとなって終わってしまった。E問題は重心分解らしい。さすがにこの段階で未履修なのはまずいか。

ABCに戻ってコードゴルフをする。A問題はコンテスト中のdcコードでよい。B問題はPerlで文字列のxorを取る解を提出していたのだが、print関数ではなくprintf関数を使っており、そこで1B短縮されていた。さすがに呆れかえった。Cは文字ごとに分解して降順ソートし、2数の小さいほうの末尾に貪欲にくっつけるとよいらしい。Vimの48B解がすでに存在しており、Perlで同じく48Bに至ったがそこからは縮まない。Vimのほうで考えて、文字ごとに分解した後各行の末尾に文字列を挿入している部分を置換コマンドで一気に行ってみたところ縮んだ。DはPerl解をちょっと縮めたところすぐ取り返された。区間の始点と終点を区別する必要があって、Perlでは文字列に空白や改行が含まれているかどうかをチェックしているが、ほかの言語で実装しようとすると新たに別のデータを持つ必要があって難しそう。

このあたりでABC-Gを通した。kyopro-friendsさんのツイートを参考にして解いていたが、全然TLEが取れない。仕方なく公式解説を見たら、bitset<3600001>を2001本持ちますと書いてあってひっくり返った。僕の実装でも、縦と横を同時に復元するようにしたら通った。定数倍2分の1が効きすぎている。その後bitsetを大量に持つ解法でも通しておいた。

コードゴルフを続ける。EFは飛ばして、Gを縮めた。Ruby多倍長整数をbitsetのように扱うと、必要なだけのメモリしか確保されないので軽め。C++で書くより速くてびっくりした。しばらくチマチマ縮めて167B。文字列"Yes"と復元した解を出力するのに、sumメソッドの引数に"Yes\n"を指定すると縮んだのが面白かった。Hは当時の最短を単純にCrystalで書き直しただけ。熨斗袋さんのユーザ解説と同じ遷移で、実のところ僕のコンテスト中の解法とも、貰うdpと配るdpの違いだけでほぼ一緒のようだ。

さらにABC前にatgolferに流れてきていた更新もいくつか取り返した。Rubyである非負整数の変数iが0に等しいとき0、そうでないとき1を得るのは、これまで-2[i]を使っていたが、負号が付くことを許容すればi/~iでも計算できる。これでさらに2問ばかり縮めることができた。

そんなことをしているうちに昼前になってしまった。来週木曜日に迫った4年ゼミに向けて、しばらく前学期の最後のほうの発表を復習していた。正午を回ってから布団に入り、ラノベを1冊読了。

VTuberなんだが配信切り忘れたら伝説になってた」2巻。今巻は前にもまして例のアレのネタや下ネタ・コピペ・パロディが盛りだくさんで、ちょっと正気では読んでいられない。しかし作中世界にどっぷり浸かると面白く読めた。特にシリアスなシーンが多かったりするわけではなく、正直シリーズとしての内容はあまり覚えていないが、読後感がまったりしていて非常に良かった。後書きで、次巻にはweb版で屈指の人気を誇ったシーンが収録される、ということが書かれていた。気になる。今すぐweb版を読みに行きたいところだが、ぐっとこらえて3巻の発売を待ちたい。かなり売れているらしく、続刊することはほぼ確実らしい。

10/03(日)午後2時半就寝。

10/03(日)

午後6時起床。第8回PASTの過去問が公開されるかもと思って1時間おきに起床して確認していたのだが、その時にDMでSUSURUがゆゆうたとコラボしてやばいクレーマーのSUSURU TVを歌ったことを知り、飛び起きた。

ゆゆうたからツイートされたほうの曲(特にラストのフレーズ)、ほとんどSuper Driverに聞こえる……。勢いの良い曲調が共通しているが、それに加えてコード進行とやらも同じだったりするのだろうか。

しばらくコードゴルフをした後、昨日の続きで4年ゼミの発表の復習をしていたが、また途中で切り上げて午後11時半からCF #746 div.2に出た。

Dashboard - Codeforces Round #746 (Div. 2) - Codeforces

F1までの6完。Aは大きなほうから2つ取って交互に使うのが明らかに良い。Bは両端からそれぞれn-x要素を自由に並べ替えられるので、その範囲が数列全体を覆っていれば良いし、そうでなくても、実際にその部分だけでソートしたら全体が揃うような場合も良い。Cは、適当に分解した結果の連結成分3つを、全体のXORを変えずに纏めることができるので、分解するのは2つか3つであるとしても良い。2つの場合は簡単で、木全体のXORが0ならば(またその時に限り)適当に1頂点抜けば達成できる。そうでない場合は、分解した各連結成分のXORが定まるため、木全体から2つ抜けるかをチェック。切る辺2本の片方がもう片方の祖先になっている場合は注意が必要。ちょっとした木DPを行ったが、帰りがけ順に頂点を見てXORを計算しつつ切り離していくと処理がまとめられて簡単そう。

Dは、どこかの辺が答えになるとしてよい。辺全体を半分に分けていった。分けるときは、現在残っている辺からできるだけ連結になるように選び、選んだ辺たちに含まれる頂点を聞く。その中に答えと一致するものがあればよいし、なければ以降選ばなかった辺たちを聞くときに今聞いた辺の情報が邪魔になることがない。木の辺をdfs順に並べて二分探索という解法を見たが、結局それも今言った「できるだけ連結になるように選ぶ」を満たそうとしているという理解でよさそう。Eは、まず区間の長さが偶数でなければならないことがわかる。そのときANDで残るbitを決め打つと、それ以上のbitは全部XORで消える、つまり偶数個なければならない。これはZero-Sum Rangesの要領で累積XORを持っておけば求まる。ANDで残るbitも含めてキーにすれば、区間の長さが偶数であるという条件も同様に書けるため、楽。mapを書き換えるのは計算量が悪化してまずいので、配列とそれを書き換えたタイミングを持って頑張る。このテクは昨日のCF 5hでも使った。

F1は、左下と右上の操作は左上の操作2回で再現できるため考えなくてよい。右下の操作は高々1回しか行わないようなので、それを全探索して、残り左上の操作は貪欲に決めてよい。隣り合うマスが異なるかどうかを持っておくと、右下の操作では1列の高々O(n)箇所しか変更しないので、差分の計算もO(n)で行えて全体で3乗になる。実装を安全側に倒してそこそこ定数倍の大きなコードを書いたら1300msくらいで怖かったが、通った。F2も左上と右下の操作しか考えなくてよいことは同じだったが、右下の操作が何回も行われる可能性があって、それを最適に選べなくて解けなかった。僕は「隣り合うマスが異なるかどうか」を見ながら計算しようとしたのだが、それよりも「どこのマスを右下にして操作するか」を最初の状態で求めて、これを適切に右下の操作で置き換えることを考えるのがよかったらしい。この見方の元、二部グラフの最大マッチングに落ちるようだ。

水曜日にAtCoderProblemsに出した、ゲノコン2021をクロールするようにするプルリクがマージされたので、atgolferのほうも対応させておいた。

add genocon2021 by kotatsugame · Pull Request #21 · kmyk/atgolfer · GitHub

また4年ゼミの復習の続きをして、今度こそ最後の発表まで読み終わった。次回自分が発表する番なので、担当することになる箇所を読んで式変形を追っていたのだが、埋まらない行間を1か所見つけてしまった。教科書を見返しても、まだ証明されていない事実を使っているように見える。今読んでいる章では素数定理と同値な命題を大量に示したのだが、素数定理そのものはまだ全然示していないため、使って良い命題とそうでない命題を慎重に区別する必要があった。

考え込んでいるうちに椅子の上で意識を飛ばしてしまったらしい。ふと気づくと時間が1時間くらい飛んでおり、変な体勢だったので首が痛いし、寝ながら舌を噛んでいたらしくそこも痛い。満身創痍で布団に潜り込み、改めて就寝。午前4時半だった。

そういえば、第8回PASTの過去問は(この部分を書いている2021/10/04(月)午後3時時点で)まだ公開されていない。