週記(2021/08/30-2021/09/05)

08/30(月)

先週の週記は、文章を書きながら意識を飛ばしそうになっていたので、投稿してからは比較的すぐに布団に入って寝た。午前6時半だった。

途中、午前11時くらいに目を覚まして、ちょうど届いたAmazonの定期購入の荷物を受け取った後、少し布団でゴロゴロしていた。この時間に起きたら学食に行けるなあとか、注文した本が生協に届いたようなので受け取れるなあとか、そのようなことを考えていたが、結局また寝入ってしまった。

次に起きたのは午後6時くらい。寝ている間にSlackでDMが来ていて、sotanishyさんが次代のサークル代表に立候補してくださった。一応サークルの規則で、総会を開いて代表を決定することとあるが、正直そのためだけに通話をホストしたりするのはコミュニケーションコストが高いと感じているので、Slackのリアクション機能を利用した信任投票で決を採ることにする。コロナ前の碧黴さんが代表の時代は、通話で会議した記憶もあるし、僕自身借りた教室に集まって開かれた総会で代表に決定した経験もあるが、このあたりの文化はだいぶ消し去ってしまった。

atgolferの更新を追いつつコードゴルフする。最近あまり週記で触れていないが、今でもatgolferは数時間に一度確認しているし、短縮されたら取り返そうと努力している。今日も2つ更新されていて、1つは取り返したが、もう1つはどうにもうまくいかない。僕が初めに書いていたコードから変わっていない部分があって、そこは短時間で思いついた書き方なので縮みそうな感じはしていたのだが、思ったより頭が良かったらしい。

リストの途中の連続部分列を取得したくて、ただし取得したい位置が空の場合もある。このとき、例えばarr[3..2]は空のリストになるが、arr[3,-1]nilが帰ってきてしまう。また実は先頭にいくらかパディングしてarr[3..2]とできているのであって、本来はインデックスから3引いてarr[0..-1]という感じになるが、これだと-1がリストの末尾要素を指していると解釈されて、arr全体を取得してしまう。どうにも上手くいかなかった。

先週のABC216-Dの嘘解法が流れてきたので、縮めておいた。1回でも操作できること、つまり先頭要素に重複があることと、同じ筒の中に重複した要素がないことの2点を確認すれば通るらしい。

Submission #25466179 - AtCoder Beginner Contest 216

7セメスターの成績が出たので、いつも時間割と成績をツイートしているリプライツリーにつなげておいた。このリプライツリーももう3年半。こうやって何年も同じことを続けていると、いよいよTwitterアカウントが2つとない、失ったら最後取り返しのつかないものに思えてくる。もし今後何かの間違いでこのアカウントが凍結されたりしたら、自分はどうなってしまうのだろうかと、以前から不安に思っている。

先週金曜日のyukicoderのC問題の解説を見て、解いた。これはコンテスト当時思いつかなかったのだから仕方ないだろうという感じがあるが、もしこれがRatedに出て大敗を喫したらたまったものではない。

#694290 (Ruby) No.1658 Product / Sum - yukicoder

次に、こちらも解説を読んで、ARC216-Hを通した。

Submission #25470126 - AtCoder Beginner Contest 216

LGV公式ということでしばらく考えてみたのだが、自力では超大量の行列の行列式の総和を求められなかった。行列式の線形性というのは、各行各列に対しての概念であって、全く異なる2つの行列の和を考えられるような概念ではなかった。行列式には様々な意味づけがあって、この問題では置換による定義を採用して計算している。ARC054-C「鯛焼き」では、逆に置換による定義を使って問題を行列式の計算に落とし込み、計算は別の方法を採用していたので、対照的とも言えそう。

さらに置換を全探索して計算することにした後もいくらかステップがあり、順列ごとのdpを考えた後bit dpですべての順列をまとめて計算するくだりなどは、置換の符号もbit dpでちゃんと計算できる点など非常に美しいと感じた。出来上がったコードが非常にシンプルだったのも良い。総じて、凄まじい問題だった。

それからはしばらく本を読んでいたが、疲れを感じて布団に移動すると一気に眠気が襲ってきて、生活リズムの是正も考えて素直に寝ることにした。午前1時前だった。

08/31(火)

午前8時起床。

そのまま布団で、昨日読んでいた本を読み切った。「かくりよの宿飯」1巻。先週古本屋でシリーズ11巻をまとめ買いしたものに手を付け始めた。この作者は「浅草鬼嫁日記」で初めて触れて、本の内容というよりは設定や見せ場の作り方が好みと合っていたので、それ以来ほかの著作にも少し手を出していた。最初はファンタジーの本を書いていたようだが、人気シリーズは今名前を挙げた2つで、どちらもあやかし関連の話だ。ちゃんと面白かったので、今後の展開も楽しみ。

昨日嘘解法で縮めたABC216-Dがさらに縮んでいた。見た感じさらに条件を弱めたというか、そもそも先頭要素の重複があることをチェックする代わりに特定の文字列があるかをチェックしていて、いよいよテストケースハックの本領発揮といったところ。さらにafter_contestが追加されたらしく、もう縮むことはないだろう。まあこれもAtCoderコードゴルフをする宿命か。

学食に行って昼食を摂り、注文していた本を受け取った。今日は6冊。どれもかなり楽しみにしていた本なので、早く読みたいところだが、昨日から手を付けたシリーズも読みたい。どうすればいいものか……。

とりあえず今日買ってきた本の中から「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変3」を読み始めたが、昼下がり急に眠くなったので、耐え切れず布団に倒れこんでしばらく寝た。

午後1時くらいに意識を落として、次に目を覚ましたのが午後5時だった。アナログ時計は午前午後がわからず、外が微妙な明るさだったため、さては朝の5時か!?と思ってうろたえたが、ちゃんと確認すると全然そんなことはなくて一安心だった。

そのままずっとラノベを読んでいたが、午後8時半くらいになって、昨日サークルSlackに投稿した新代表のアンケートの信任が過半数を超えそうになっていたので、アカウントの権限付与などの作業をsotanishyさんと一緒に行った。特にGmailアカウントは、一度ログインしてもらってこちらから認証しなければならないため、2人の手が空いているときに行ってしまう必要があった。それ以外は順調に進み、定期的にサークルのメアドを確認してもらうことだけ伝えて終わり。ICPCICPCの、新歓は新歓の時期にまたいろいろ伝えることになるだろうが、通常の業務はこれくらいとなる。

日付が変わったあたりで「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」3巻を読了。今巻も非常に面白かった。単純なのでお嬢様が表舞台に立っているだけで面白く感じられて、その意味では今巻の卒業コンパのシーンや、特に桂華タワー落成式のシーンはWeb版から好みの部分だった。恋住政権が発足してから、以前のように政治にバリバリ関わることが難しくなったお嬢様だが、今後も経済のほうで活躍する姿を見たい。

明日から始まるインターンの初日の予定がメールで知らされた。同じ時期に業務を開始する面々や社員の方々との顔合わせ、社長からのお話もあるため、ありったけの社会性を用意して臨みたい。

布団に入って少し本を読んだが、すぐにやめて午前4時就寝。

09/01(水)

午前9時半起床。急いで食事し、オンラインの入社式に備えて上半身だけ着替えたりノーパソを壁に向けたりしていたら、ギリギリの時間になった。

午前10時から開始。全体向けの会社の説明、個人向けの説明、インターン受け入れ先の部署とお話、メンターの方と1対1でお話、と今日は一日喋る日だった。一応仕事に参加するにあたっての必要最低限のアカウントをセットアップしたりはしたが、逆にそれ以外何もできていないのに金銭が発生しており、かなり困惑する。早く成果物を作り出したくてたまらなくなってきた。午後7時で上がり。

終わってからしばらくは微妙な眠気で動けなかったが、何とか身を起こして学食に夕食を摂りに行った。帰ってきてからは本を読んだり動画を観たりしていた。

TSGがAnarchy Golfを使って小さなゴルフ大会を開いていた。特に参加はしなかったのだが、一応問題だけ見ると、コラッツ問題で与えられた数が1になるまでの経過を出力せよという問題だった。dcのコードが提出されていて、念のため確認したところ、これまでAtCoderで僕が使っていたコードより1B短くなっていることに気づいた。かなりびっくり。焦って2問ほど縮めた。

http://golf.shinh.org/reveal.rb?Collatz+Problem/tails+%28Carlos+Gutierrez%29_1332227477&dc

Anarchy Golfにいつの間にかJellyが入っていた。Unicodeで見ないと何もわからない。わけのわからなさでいえばgs2も似たようなものだが、Jellyは一応Unicodeの形に基づいて設定されているような命令もあるから、そこの違いは大きい。

しばらくなろうを読み返していた。以前に読んだなろうは、自分の好きなシーンだけつまみ食いすることができるので、読み返すのは結構好きである。実家にいるときはラノベもそうやって少し読み返したりしていたのだが、仙台に来るときに既読本はほぼ置いてきたし、今は数か月おきに読み終わった本を送り返さないと本棚に入らなくなってしまうので、ラノベを読み返す機会は帰省のときのみと極端に減ってしまった。

8月の読書記録をツイートした。先月は結構頑張って読んだつもりだったが、それ以上に本を買ってしまった。まあ、本は買えば買うだけよいということを常々思っているため、問題はない。

布団に入ってしばらく本を読み、午前1時半就寝。

09/02(木)

午前11時起床。午前10時からSRMがあったらしいが、さすがに早朝すぎて不可能だった。着替えて学食に行く。雨が降りそうではあったが、天気予報は40%だったのでそれを信じ、原付に乗って行った。この時間帯は道が混んでいないため、自分のような怖がりでも乗ることができる。

1万円札の新しいデザインが発表された発表されたのではなく印刷が開始された(2021/09/06追記)。以前のデザインは2004年から使われていたらしい。ところで、1万円のことを諭吉と呼ぶのはかなり自然な表現に感じられて、実際本などでもたまに目にすることがあるが、これは1万円札の肖像画福澤諭吉になってから登場した表現だったのか。たった17年前のことだとは思えないくらい広まっている……というようなツイートをしたら、実はその前の1万円札から福澤諭吉だったらしい。1984年からで、都合37年間だった。それなら納得だ。

今日は午後1時からメンターの方とまたお話をした。実は昨日のうちに、この後しばらくやることを決定していて、それに関することを重点的に話した。また更にいくつかのサービスでアカウントを発行してもらい、いよいよ自分の手元にコードを落としてきて動かしてみることになった。ちょっと環境を整備した後、さらに別の人と話す必要性を確認して、そのためのミーティングが明日にセッティングされ、今日は終了。午後3時だった。手元にデータを落としてくることくらいはもう可能なので、そういう準備をできるだけ進めておく。

思ったよりバリバリ機械学習をすることになりそうでビビっている。メンターの方に手ほどきを受けることになっているが、さすがに基礎的な事項くらいは自分で抑えておくべきだと感じ、とりあえずKaggleにアカウント登録をした。コースがいくつか用意されているので、これを手当たり次第に埋めていこうと思う。まず最初にPythonのコースを終わらせたが、さすがに全部既知の事項だった。最後のボーナスレッスンでTitanic Tutorialというコンペに提出を行ったが、今度は逆に知らないことだらけだった。どこからランダムフォレストが生えてきたのか一切わからないが、とりあえずデータは生まれたので、提出できた。

次にIntro to Machine Learning。こちらは結構勉強になった。いろいろなブラックボックスの使い方を学んでいて、中身が知りたいという気持ちもあるが、実際のところ機械学習の詳しいアルゴリズムを知らないと、むしろ知っていてさえ中身を見てもどうしようもないだろうとは思うので、とりあえず今は何があって何ができるかを知っていきたい。pandasのDataFrameをいろいろいじくりまわしているが、かなり柔軟な使い方ができるようで、とりあえずそれを重点的に学びたいとの思いから、次のコースはPandasにした。

このあたりで、改めてインターンのための環境構築を進める。pythonの必要なモジュールをpipで入れる作業をしていたら、どうにもtorchとtransformersがエラーが出て入らない。こういうときはエラーで検索すればいいんだ!と思ったが、見るとPythonのバージョンを下げましょうと書いてあったり何も出てこなかったりして、非常に難しい。やはりcygwinでやっているのが悪いということで、これを機にWSLに乗り換えることにした。

WSLを入れて環境構築。といってもcygwinの設定をいろいろコピーしてくるのが面倒になってきたので、WSLを使うのはインターンの間だけということに決めて、とりあえずPythonの環境だけ整えた。ちゃんとtorchもtransformersも入って安心。しかし日本語ファイルが全部文字化けしている!文字コードを変えるのはよくわからないし、いったん全部ダウンロードしなおしかな~とも思ったが、冷静に考えるとフォントが日本語対応していないだけだった。調べると、コンソールで使う日本語対応フォントでRictyというフォントがおすすめされていたので、それを入れておいた。

GitHub - kudryavka/Ricty: Ricty --- fonts for programming

あとは.vimrcを書いたり、カラースキームを適当に決めたりして、何とか見られるようにはなったのではないだろうか。

合間合間で本を読み進め、1冊読了。「かくりよの宿飯」2巻。今巻も面白かった。主人公は基本的に他人(他妖?)を悪く言わないので、そのお人よしさがちょっと気になることもあれど、基本的には好印象。そういうところがほかのあやかしに受け入れられていく様が描かれていて、明るい未来を感じる。

夜中、opencupに参加する集まりに招待された。印象としては、やっとのことで赤の山に登ってみたら、下からは見えなかった頂上に大量の人がいて、みんなさらに上を目指していた、という感じ。りんごさんの名言「赤にいかないうちは、典型も解けていないという証拠なのでどんな問題がでても文句を言わずに解きましょう」が思い出される。つまり、今ようやくある程度の典型を学んでスタートラインに立ったということ。何とか食らいついていきたい。

布団に移動して少し本を読み、就寝。午前6時半だった。

09/03(金)

午後2時起床。午後3時に大学生協が閉まるので、起きてすぐ向かった。昼食を確保するつもりだったがパン類がほとんど売り切れてしまっており、残っていた謎の総菜パンを購入。これだけでは足りないと感じたので、帰りにコンビニに寄って追加で菓子パンやおにぎりを買った。

生協の総菜パンは思ったより美味しかったが、しょっぱいものが美味しく感じられているだけにも思える。塩分不足かもしれない。

インターンの昨日の続きとしては、もう少しミーティングしないと手が動かせなさそうなので、それを待つことにして、Kaggleのコースを進めた。今日はPandasのコース。記法があまりにも柔軟すぎてむしろよくわからなくなってしまった。あとgroupbyの挙動がよくわからない。それっぽく書いたらそれっぽく動きはするのだが、自分で何かをやりたいとなったときにうまくできる自信があんまりない。

午後3時から3時間かけてコースを終わらせると、ちょうどミーティングの時間になった。業務について前任者から引き継ぎを受けるのが1時間、メンターさんとお話しするのが1時間。これまではミーティング以外何もできなかったが、引継ぎを受けて、とりあえず何をやればいいかが何となくわかってきたので、これからは自分でいくらか手を動かすことができる。

またメンターさんとのお話しでは昨日始めたKaggleを話題に取り上げ、Kaggleへの最初の取り組み方のようなふわっとしたアドバイスが欲しいとお願いした。聞くところによれば、僕はコードの読み書きがそれなりにできるはずなので、最初からコンペに出て人々の取り組みを観察したり、提出して自分の順位の変動を見たりするのが良いらしい。そう言われるとかなりやる気が出てきた。

しかしまあ、とりあえず今はインターンのコード読み書きをやってみたいので、そちらに注力する。実行に6分くらいかけたコードが最後のデータ書き出しの部分の文法エラーで落ちてしまって非常に辛かった。ちゃんと小さいケースでテストするよう心掛けたい。そうやって格闘していたら午後9時になったので、中断してyukicoder 312に出た。

yukicoder contest 312 - yukicoder

6完。Aはよい。Bは00が許されていないのに気づかず1WA。ここでk乗根を二分探索で計算するコードを書いたのだが、この後D問題でも使うことになって面白かった。オムニバス形式なので特に意図されたことではなさそう。Cは素因数ごとに独立になると勘違いして1WA、grundy数を直接計算して通した。grundy数はそんなに大きくならないだろうと思って64bit整数のbitを立てつつ計算したが、実際必要な範囲では最大19にしかならないので、これで十分。

Dは難しかった。二分探索をするのはよいが、累乗数を重複なく数えるのに手間取った。最初、素数乗の数を包除原理を用いて数えようとしたが、WA。3乗以上であって平方数でない数を全列挙したあと、改めて平方数を数える(ここで2乗根を計算する)方法で通した。Eはケイリーの公式でM=N-1を計算してそこから戻す……ということを考えたが全然ダメ。しかしケイリーの公式を使うのはよくて、連結成分ごと一気に遷移するようなdpを書いたら3乗になった。Fは隣接する値が異なるマスに対応してグラフに辺を張り、そのDAGの最長パス……としたがWA。隣接していないマスの値の大小関係も保存されなければならないことに気づいていなかった。値が小さくならないようにするには1から順に値を確定していけばよくて、DAGの作り方からこれはトポロジカル順序にもなっているので、正しく定めることができる。

そのあとGを考えていたが解けなかった。この問題にはあまり関係がなかったが、行や列を一気にflipする操作で黒に揃えられるのは全ての2x2正方形で黒マスが偶数個存在することと同値、というのは以前も見た覚えがあるし、ちゃんと覚えておきたい。今日も同じことを考えていたが、証明をつけるのに手間取った。

最近「やばいクレーマーのSUSURU TV」にハマっているが、本人がカバーして動画を出したのを知った。非常に出来が良い。

夜中、またインターンのコードと格闘を再開した。リモートワークでかなり自由度高く働けるので、この時間にコードを書いていても全然平気で給料もちゃんと発生する。かなり楽しい。しかしだんだん頭の働きが鈍くなってきて、この状態でのコーディングに対価が発生するのはなんだか申し訳なくなってきて、午前2時半くらいに切り上げた。

寝ようと思ったが、Kaggleも少し進めておこうかという気分になって、参加するコンペを適当に決めて問題を読んだ。「Optiver Realized Volatility Prediction」というやつで、金融に関する値を予測せよということらしい。データの内容や公式のチュートリアルを読んでいたが、英語にかなり壁を感じた。慣れていないためか競プロの問題文を読むのとは全然勝手が違う。結局最後まで読み切ってもよくわからなかったので、また明日取り組むことにした。

Optiver Realized Volatility Prediction | Kaggle

布団に移動して読書。1冊読了した。「かくりよの宿飯」3巻。冒頭ちょっと剣呑なシーンもあったが、その後は終始のんびりと進行。登場するイケメン男性キャラクターの振る舞いを女性主人公の視点から見て可愛がったりしていた。しかしラストシーンがかなりとんでもないことになって、4巻に続く!と終わった。どうなるのか非常に心配している。

4巻もちょっと手を出して読み進めたが、いい加減眠たくなってきたので、午前6時に就寝。

09/04(土)

午後1時くらいに目を覚ます。二度寝するつもりだったが、うっかりスマホを触ったりしてしまい、そのまま眠れなくなってしまった。今日は生協の冷凍弁当が届く日のようなので、午後3時からは起きていなければならない。布団でゴロゴロしていたが、午後4時くらいになってようやく身を起こした。今日は何をしようかしばらく迷って、Kaggleの昨日の続きをすることにした。昨日はこの公式チュートリアルみたいなものを読んで、読解が終わっていなかったのだった。

Introduction to financial concepts and data | Kaggle

何度か読み直して、ようやく理解できた。10分間の情報が与えられるので、次の10分間についてのある値を予測せよという問題で、チュートリアルの提出では与えられた10分間の情報からその10分についての値を計算して答えとしているようだ。それでも多少のスコアは出る、ということらしい。

やることは分かったので、とりあえず何か提出してみたい。チュートリアルのコードをそのまま出すのも味気ないので、自分なりに何かコードを書くことにした。Parquetという初めて扱うデータ形式が出てきて、あんまりよくわからない。どうやら与えられたデータがあまりに大量すぎて、1度に全部読みだすのはメモリの関係上やめたほうがいいらしく、いくつか区分けされている中で順々に処理していくことになる。

とりあえず1つだけ読み出してそれっぽい特徴量を計算してみた。あとは学習だが、今回は連続値を予測しなければならないので、適当にモデルを調べて、最初に回帰木のランダムフォレストを試してみることにした。その中身については全然知らないが、とにかくfitpredictのメソッドを呼び出してみると、それっぽい値が出ている。csvファイルに書き出して初めての提出を行った。提出してから20分くらい待ったら結果が帰ってきた。

つらい。再度notebookに戻って1文字消し、もう一度セーブして提出。また20分かけて、ようやく正しくスコアが得られ、順位が付いた。チュートリアルのコードよりも精度が悪いらしくてかなり下のほうだが、まあ最初だしこんなものだろう。試しに読み出すデータの区分を5個に増やしたら、大幅にスコアは上がったものの、相変わらずチュートリアルのコードに負けているため、順位的にはほとんど変わりがない。データの区分けは112個あるのだが、5個読み出して処理するのにも2分くらいかかっているので、全部やるのは気が進まない。そういう待ち時間がいちいち発生するのはあんまり好きではない。

スコアを上げる方法が全然わからないので、他の人のnotebookを読むことにした。1回の実行に70分以上かけているらしく、ヤバ……という気持ちになった。そうこうしていたら午後9時になったので、ABC217に出た。

AtCoder Beginner Contest 217 - AtCoder

8問体制になって初めて、ようやく全完できた。

AはAWKがよい。BはRakuで集合の引き算を行った。CはPerl。ABC142-Cとまったく同じコードを書いた。ここからC++で、Dはset。Eはちょっとびっくりするが、優先度付きキューとキューで管理すればよい。Fは区間dp、重複をうまく弾けておらず1WA。各区間について一番左の要素のペアを固定して考えるとよい。Gは、空のグループを許容する場合の数が、あまりが同じ人数などを考えると簡単に求まって(一旦箱を区別して最後にk!で割る)、そこから包除原理で答えを出した。Hはslope trick。maspyさんの記事を読みながら書いた。スタート位置が0と決められていることに気づかず、サンプルが合わなくてしばらく悩んでいた。

atcoder.jp

コードゴルフをする。Aは最初に提出したものが今も最短。Bは文字列のxorを使うのが短いらしい。Cは上の問題の最短コードをコピペ。DはC++を頑張って縮めた。endを指すはずのイテレータにアクセスするとなぜか1が返ってきたので、よくわからないがそのことを仮定したコードを出したら全ケース通ってびっくり。

GをPyPyで縮めているとTOKI Regular Open Contest #22が始まったので、出た。

https://tlx.toki.id/contests/troc-22

5完18位でレートは2588→2596(+8)。途中D問題が解けたときになぜかD問題だけサイトのエラーが出て提出できなくなってしまい、非常にイライラした。それでも何事もなくRatedになってしまい、びっくり。

Aは0があるかどうかを見る。Bはabcabc...を出力すればよい。Cは文字列を2文字になるまで操作した場合のスコアが一意になると気づいて喜んで実装したが、実は操作を途中でやめてもよかったらしい。そちらの解法は操作によって消す部分文字列を決めるdpで、遷移を高速化するために次の先頭となる文字で分類して値を持っておく。Dは二分探索で、ある番号以下の学校だけで全員が通えるかを判定するには多始点ダイクストラをすればよい。

Eはちょっと面白かった。先頭から二分探索して01が切り替わる境界を見つけるのを2回行い、axをそれぞれ求める。二分探索では、まず範囲として2べきを順に試し、次にその範囲内で通常の二分探索を行うので、都合4回、つまり最大4\log 10^9\gt 100くらいの質問回数が必要に見える。ここで、試す範囲はaに対応するものよりxに対応するもののほうが真に大きいため、xについてはaの値の続きから試していくことにすると、二分探索の回数が1回減って3\log 10^9\lt 100回くらいの質問回数で答えがわかるようになる。あとはb\lt 2xからbを求めて、最後にyを求める。baxから求まることに気づいておらず1WA。

ABC217-Gのゴルフの続きをする。PyPyでは負けてしまったので、Crystalを使ってみる。複数の値を出力するのがなかなか難しくて、どうやらjoinする必要がありそう。これだと出力の長さでPyPyに勝てなかったが、dp配列の埋め方を縦横逆にすると、毎ループの最後に1つずつ値を出力すればよいことになって、pで簡単に書けた。昨日入れたWSLにCrystalをインストールできたので手元でCEやREの様子を見ながらコーディングしていたのだが、AtCoder上のバージョン0.33.0と手元のバージョン1.1.1でもまたいくつか違いがあって大変だった。

また本を1冊読了。「かくりよの宿飯」4巻。前巻のラストシーンでとんでもないことになった主人公だが、なかなかたくましく生きている。さらに味方キャラがすぐ助けに駆けつけてくれて一安心。シリーズ最初のほうでは主人公は鬼神の大旦那に対してつんけんした態度をとっていたが、だんだん溶けていっているのもいい感じにニコニコできる。女主人公の視点で見ているので、溶けているという表現もちょっと違和感があるか。大旦那の良さがわかってきた、という感じ。

午前6時就寝。

09/05(日)

午後2時くらいに目を覚ます。またしばらく眠気の様子を伺いつつ布団でゴロゴロしていたが、やはり眠れないようだったので、今日も午後4時くらいに布団から出た。

昨日のABC217-Dは、Pythonのarrayとinsertを使ったコードでも通っていたが、C++コードよりは長かった。起きてみると自分のC++コードが縮められていて、どうにもこれ以上縮みそうにないので、改めて愚直にinsertするコードを考えてみる。Crystalでも同様のことができるのではないだろうかと思って書いてみると、通ってしまった。しかもコードがC++より短い。さらに何度か提出を繰り返して、111Bまで縮めた。

このように愚直なinsertが通ってしまうのはなぜだろうかと考えた。何か特殊な実装をしているわけではないだろうし、実はC++でも普通にinsertで通るのでは?と思って書いたら、見事に通ったので、特に不思議でもなんでもないようだ。ただPythonの通常のlistを使うと通らないので、型を制限することによるメモリ効率の向上が定数倍高速化に大きく寄与しているのだろうと思っている。

atcoder.jp

先週日曜日にLibrary Checkerに立てたissueがcloseされた。僕がissueの文面で提案していたケースがそのまま入ったらしい。実際に作業してくださった熨斗袋さんに感謝。

Add a test case to multipoint_evaluation by noshi91 · Pull Request #706 · yosupo06/library-checker-problems · GitHub

多点評価のハックケースをLibrary CheckerのGitHubにissueとして上げておいた。

週記(2021/08/23-2021/08/29) - kotatsugameの日記

午後6時からRECRUIT 日本橋ハーフマラソン 2021〜増刊号〜に参加した。

RECRUIT Nihonbashi Half Marathon 2021 (long) - AtCoder

まだ開催中のマラソンコンテストなので何も言えないが、一瞬だけ1位を取れた。

何も言えないのでこの間の時間は一気に飛ぶ(この間僕がコンテストに取り組んでいたということくらいは書いてもいいだろう)。午後11時半からCF #742 div.2に出た。

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

全完7位。

Aはよい。Bはaa+1かだと思っていたが、XORを合わせるために追加する要素がちょうどaの場合が困るらしい。サンプルにあって助かった。このような場合も、十分大きな2のべき乗を足すことでa+2要素で実現できる。Cは2つの繰り上がりを持つ桁dp。Dはまず各桁を10のべき乗に分解して、足りなければ小さいほうから10分の1にしていく。

Eは面倒。非減少部分列への分解を管理するのは、setに区間の両端を入れれば可能。求めるべき場合の数について、各要素に対してそれを終端とする非減少部分列がいくつあるかを数えると、それらの値はちょうどのこぎりの歯のような形のギザギザになる。つまり、傾きが1で定期的に1に戻るような値の列となる。数列の値の更新があると、このギザギザがある区間で一様に上がり下がりするだけの変化をするので、区間加算の遅延セグメント木で書ける。取得は当然区間和だが、一番前のギザギザは中途半端に取得されてしまうので、スタートを1にそろえなければならず、そこだけ区間を管理しているsetを見て補正する。僕は一番後ろも補正する必要があると思ってしまったが、その必要はなかった。

Fは謎。マークされたマスの周囲の空きマスは偶数個でなければならず、それらに1と4の数字が同じ回数だけ出現している必要がある。空きマスが2個の場合はその2マスに書かれる数字が異なることがわかるので、これを2部グラフの辺と見て奇閉路をチェックするような解き方をしたいが、空きマスが4マスの場合が難しい。特別扱いして、周りがある程度埋まったらうまいこと辺を張る、という感じで解けないかと思っていたが、そんなにうまくいかなそう。良い計算量の書き方が思いつかなかった。しばらく考えていると、ふと、空きマスが4マスの場合は斜めの位置関係のマスの組が全部互いに異なる数字になるように辺を張ってよさそうだと気付いた。そこが同じ数字になる必要があるケースは存在しないと思ったのだ。実装して投げたらpretestには通ったが、改めて考えてみると証明が回っていないことに気づいた。辺にはグリッド上でまっすぐな辺と曲がる辺があって、斜めの位置関係、つまりあるマスの上と左のような位置関係の2マスを結ぶときには曲がる辺を奇数回通らなければならない。しかしまっすぐな辺を通る回数の偶奇がわからないので、数字が同じか違うかはまだわからなかった。

Fはシステスに通ってハッピー。今回のセットは僕が本番で書いたコードより頭が良い解き方がいくつかあるようで、A問題はUとDを入れ替えているだけというのはともかく、Cで偶数桁と奇数桁を独立に考えたらただの足し算とみなせるのは感動した。

Fの証明が流れてきた。グリッドを外と内に分けて考えることで、上で述べたまっすぐな辺を通る回数が偶数であることがわかる。すると、斜めの位置関係の2マスが結ばれるときは合計奇数本の辺をたどっていることになるため、その2マスに書かれる数字は異なる。

今日の夕方縮めていたABC217-Dが1B縮んでいた。insertをまとめて書くことに執着していたが、<<演算子を使えば末尾への挿入が簡単に書けるので、分けることでさらに短くなるらしかった。

かなり昔の問題のゴルフをしようとした。フローを流すのでnetworkxを使おうと思ったのだが、入力形式が正しく守られていないようで、一度全部読んでsplitする書き方をしたらC++より長くなってしまった。ちょっと調べた感じでは、改行が正しいものよりも多いケースと少ないケースがそれぞれあるようなので、余計な空行があったり末尾に改行がなかったりしているのだろう。

Submission #25641840 - 九州大学プログラミングコンテスト2014

別に土日が休日であると意識していたわけではないが、結果的にこの2日間はインターンの業務を進めなかった。せっかくなので、もっとコードを書いて貪欲に稼いでいきたい。