週記（2022/01/31-2022/02/06）

01/31(月)

先週の週記を投稿してからの話。まず本を1冊読んだ。

「犯罪社会学者・椥辻霖雨の憂鬱」2巻。1巻の内容をほとんど覚えていなかったが面白かった。相変わらず主人公のキャラが立っていてよい。過度に理論的で人情を解さない（と周囲から思われる）ようなスタイルを格好いいと感じる。この巻では事件の加害者に焦点が当てられていた。特にネット上での誹謗中傷の描写などは、最近Twitterでも問題になっているのを見る分リアリティがあって辛かった。取り扱う事件こそ1件であるものの、登場人物たちがそれに対して様々な関わり方をしており、そのうちの誰に肩入れしても上手くはいかないのだと思わされた。そのようなバランスも含めて、取り扱いの難しい題材である。そう後書きにも書いてあった。

自分の中でのバランスも難しいところで、事件の内容を聞いて義憤に駆られることもあれば、過度な反応を諫めるツイートに納得することもある。後者は特に、少し前に話題となったいわゆる「上級国民」の事件に関するツイートで「あまりにネット上で叩かれるとその分刑が軽くなる可能性がある」との言説が記憶に新しい。いや、これに納得すること自体も、すでに「できるだけ重い刑罰を求める」という心理が根底にあるのかもしれない。一応言っておけば、自分が納得しているのは「ネットで叩かれることが情状酌量の余地となる」ことであって、当の事件自体にはあまり関心がない。それもそれで問題か？

https://www.itmedia.co.jp/news/articles/2110/21/news070.htmlwww.itmedia.co.jp

「悋気は女の慎むところ、疝気は男の苦しむところ」という言い回しが出てきた。悋気はわかるので、前半の言っている意味はすんなり理解できる。しかしどうも後半が全然わからない。「疝気」という病気があるらしいが、そこから何か別のもの、例えば物の考え方についての意味が派生して、全体として男女の違いの格言になっていると考えていた。しかし調べても出てこなかったので、結局疝気は男性特有の病気という意味そのままで、後半部分はただ対句でリズムを取っているだけだという理解に落ち着いた。

学食に行って食事し、菓子パンを購入。今日は購買にたくさん菓子パンが並んでいたので、普段遠慮して2つしか買わない商品を3つ買ってきた。帰宅して、眠気が強いので一瞬寝ることにした。先週もほぼ同じ感じで徹夜に失敗して寝た。その時の経験から、ダメそうなら早めに寝てちゃんと睡眠時間を確保しておくほうが良いとわかっている。午後1時半から午後4時半（のちょっと前）まで寝ていた。つまり、インターン先定例会ギリギリまで起きられなかったということ。

先週の進捗もスカスカのカッスカス。ショボいことを書いて、あまつさえ今週はレポートの締め切りがあるので……など逃げを打つ始末。はっきりモチベが失われているのを感じる。これまでの人生では徹頭徹尾自分の好きなことしかやってこなかったので、興味の対象から少しでも離れると一巻の終わりらしい。労働に向いていない。先週水曜日のペアプログラミングの結果、もうそろそろしこたまコードが書けそうな気配なので、何とかもう少し踏ん張りたい。明日火曜日の1on1に期待。

コードゴルフを1問。ABC237-Cが縮んだ。最初に左側に'a'を大量に追加しておいて、そのようにして作った文字列に元の文字列を逆から読んだものが含まれるかをチェックすればよいらしい。こうすることで、左端から連続する'a'が右端から連続する'a'の文字数以下であることと、真ん中の部分が回文になっていることが同時に確かめられる。Perlのindex関数で実装した（下の提出では文字列を全部逆向きにしている）。すんなり通ったので最初は気づかなかったことだが、冷静になると106文字程度の文字列検索を行っている。残念ながらRubyやPythonではTLEしてしまった。しかしPerlで書いたほうがそのTLE解より短くなったので問題なし。

atcoder.jp

ラノベを2冊読了。1冊目は「神狩1〈下〉」。上巻を読んでひと月も経たないうちに内容を忘れてしまい、厳しい。展開に驚かされると聞いていたのでわくわくして読んでいた。実際オッと思うようなものがあったとは言え、その驚きは単発のものであって、ストーリー的にもすぐ元の状態に戻ってしまい残念。上巻では正直振るわなかった主人公が無双しているのはよかった。全体としてあまり肌に合わない。

2冊目は「カワイイけど慎重すぎるお嬢様の笑わせ方」。主人公とヒロインが似た者同士で意気投合するという馴れ初めだが、あまりに気が合うせいか会話がハイコンテキストすぎて非常に読みづらい。主人公はよくわからないところでジョークを交えるし、ヒロインもよくわからないところで芝居がかって主人公に甘えて見せたりする。ただ、その読みづらい文章からでもヒロインの可愛らしさは感じ取れた。読者すら入り込めない二人だけの空間をそっと見守っていると考えればいいのだろうか。

1月はつい最近まで頑張って1日1冊ペースを超えていたはずだったのに、一瞬ハーメルンに囚われた結果すべてが崩壊。しかし今日、物理的に薄い本（250ページ前後）ばかり3冊読んだことで、今月はピッタリ1日1冊で終えることができた。記録を調べたところ2020年12月以来らしい。

少しコードゴルフをして、午前2時就寝。

02/01(火)

午前9時起床。二度寝に失敗した。1月の読書の集計をツイートした。

微妙な眠気でボーっとしつつ、レポートのため講義動画などを流し見ていた。昼過ぎに学食に行って食事し、散髪して帰宅。帰ってきたら先月の電気料金のはがきが届いており、年末年始で丸々一週間いなかったはずなのに電気代が10000円に届こうとしていてビビった。しかしよく見ると昨年同月と使用量がほぼ変わっていなかったため、ただ電気料金が値上がりしただけだと判明して一安心。インフラの単価は気にしてもしょうがないと考えている。

午後3時くらいからインターン関連のコーディングを始め、1時間の1on1を挟みつつ午後10時過ぎまでずっと頑張っていた。今日はかなり手が動いたというか、興が乗ったというか。今はエクセルファイルをPOIで扱っている。ここで、2つのブックをマージする必要が発生した。方法としては、あるブックから別のブックにシートをコピーできればよい。簡単なことだと思っていたし、実際そういうことをしたい人はたくさんいるようだったが、特別な関数は用意されておらず、いくつかそれを行うためのコード片が見つかったのみだった。しかも結構難しいらしい。

ブックをまたぐシートのコピーの難しさについて。POIでは……というかエクセルファイルという形式自体が、ブック、シート、行、セルの相互の連携によって表現されていることが問題。つまり、シートをコピーするには（あるいはセルをコピーするだけでも！）ブックの関係する要素を引っ張ってくる必要があるのだ。当初はセル自体からブックまで遡って取得できる設計の意味が分かっていなかったが、セルの書式に関する仕様を知って納得した。セルの書式は、セルに紐づくものではなくブックに紐づくものらしい。だから、単純にブックをまたいでセルをコピーしようとすると、該当する書式がコピー先のブックにないと言ってエラーが出る。対処法としては、書式をブック間でコピーした後にセルにコピーした書式を設定するというものだが、これに関しても簡単にはいかない仕様上の問題がある。一つのブックが保持できる書式は高々4000個程度にとどまるのだ。つまり、セルごとに新しい書式を作っていては到底足りないのである。だから、書式をコピーする際は同じ書式を複数回コピーしないよう、適切にMapなど使ってコピー済みの書式を取得してくる必要がある。

ここまでしてようやく、セルのコピーが可能となる。あとは行の設定のコピーをし、シートの設定のコピーをする。設定のコピーは、おおよそセッター・ゲッターが存在するありとあらゆるフラグをコピーすることで実現されて、公式ドキュメントとにらめっこして地道にコーディングしていった。と、ここまでコーディングしてから、シートに設定されたオブジェクトやブックが持っている設定のコピーが難しいことに気づいた。オブジェクトは単純に仕様がよくわからないので難しい。ブックの設定のコピーは、コピー先のブックの設定とかち合った場合どうするかという問題がある。結局、どうしてもすべての設定を保存したいブック自体をコピーして、それに今までの方法で微妙にコピーしきれないシートを追加することでマージを行うという設計にした。これが現実的で、限界でもある。

CodeChefのどこかのコンテストでいい成績を残したので、100USDがもらえるらしい。メールから飛べるフォームに個人情報を入力する必要がある。顔面の写真など、ちょっと怯むものもあったが、問題はSNSのアカウントについて。Twitterやfacebookはよいとして、LinkedInやInstagramのアカウントを入力する欄があり、しかも回答必須項目になっている。バカじゃないの？ただ、面倒さよりお金の欲しさが上回ったので、いい機会とアカウントを作ることにした。

LinkedInは問題ない。しかし、Instagramのアカウントを作成した瞬間ロックされてしまった。謎。個人的には、認証コードのメールが届くのが少し遅かったので再度要求した後、初めに届いたメールのほうのコードで回答してしまったからだと思ったが、確認すると届いたメールは2つともコードが同じだった。ともかく、24時間くらい待つ必要があるらしい。

IDは取得できていると思うので、それを入力してフォームを送信した。パスポートのコピーも必要だったのでスキャンを行った。これは高3のときにIOLに行くため作ったパスポートであり、有効期限がかなり近づいていることに気づいた。その更新もしたいと考え、住民票が地元にあるまま仙台で手続きできるか少し調べていた。一応できることにはできるらしい。ただ住民票が限定された形でしか取得できないようで、これについては不安が残るため、親に取って送って貰いたい。

しばらく布団に転がったりコードゴルフをしたりして、午前5時半就寝。

02/02(水)

午後0時半起床。学食で食事し、予約していた本を受け取って帰宅した。帯が少し破れていてかなり微妙な気持ちになった。

ラノベを1冊読了。「宅録ぼっちのおれが、あの天才美少女のゴーストライターになるなんて。」。良かった。ヒロインの一人のことを狙っているイケメン男子生徒がおり、彼もバンドを組んでいた。いかにも主人公に嫉妬してギスギスしそうな設定で警戒していたが、実際はかなりいいやつで、ヒロインの気持ちが主人公に向いていることをちゃんと認めるし、主人公も最初は彼の技術だけを見て軽んじていたのに、最終的には彼なりの表現に気持ちを揺さぶられていた。主人公はボッチで作曲していたのでバンドの楽器を一通りできるという設定があり、主人公無双チャンス！と思ってしまった。この本にはそういう描写はない。

今読んだシリーズの2巻を今日受け取ってきた。それを読み始めたが、うっかり布団で力尽きた。午後4時半くらいに寝落ち。

02/03(木)

02/02 午後10時半に起床した。

そろそろInstagramのアカウントがロックされてから24時間が経過するころだった。まだかまだかと待っていたら、ちょうど24時間くらい経ったあたりでロックどころではなくアカウント停止になっていた。不服を申し立てようとすると、サポートから来たメールに特定の文字列を手書きした紙と一緒に写った自撮りを返信しなければならないらしい。海外の犯罪者の写真みたいで非常に気分が悪い。送ってもどうしようもない、という体験談がリプライされてきたりしたが、ダメもとで送ってみることにはした。

午前1時からSRM823に出た。

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

Easyは簡単。2回連続でジャンプするのと1回大きくジャンプするのが完全に等価なので、現在地に加えて今どの方向にジャンプ中か、あるいは一切ジャンプしていないかの5状態を持ってBFSすればよい。これでO(HW(H+W))になる。直前でジャンプした距離を持ってもO(HW(H+W)\max(H,W))になるだろうが、こちらは定数倍で落ちてしまうのだろうか？もしかしたら考察は一切問うていなくて、実装だけで点数がついているのかもしれない。

Medはかなり難しく、面白かった。面白かったのは自分が解けたからかもしれない。Dで昇順ソートして、各点を終点にするようなパスを1本ずつ管理し、伸ばしていくことを考える。すると、ある辺を処理する際はパスが2本選ばれ、互いに1辺ずつ伸びて終点が交換されることになる。このような操作を繰り返すと、N本のパスが合計で2M回伸びることになる。今\frac{2M}N\ge \frac{2\times 10N}N=20なので、どれか1本のパスは処理の結果長さ20を達成できる。実装の時はまだ正当性を信じ切れていなくて、パスの終点を交換するときにそれまで作ってきたパスと長さを比較して長いほうを取ったりしていたが、まあそれでも問題はない。

Hardは簡単。約数を列挙して、それらの間の約数・倍数関係でdpをすればよい。N\le 5\times 10^{12}なので、d(N)（約数の個数）は最大で10^4個くらいになる。dpにO(d(N)^2)かけるのはちょっとまずいかと思って、素因数を列挙して細かく求めたりしていたら時間がかかってかなり点数を落としてしまった。しかも実際にはO(d(N)^2)で通るらしい。残念。

そういえば、火曜日の部分に書いたCodeChefの賞金の件はうしさんのツイートを見て気づいたのだった。ところが今、うしさんの賞金が手違いだったというメールが来たらしい。自分も実は手違いで顔面の送信しただけ損だったか……と思いつつメールをチェックしたところ、そのようなメールは届いていなかったので一安心。どうやら賞金を貰ったコンテストが異なるらしい。それにしても、いつの間に賞金付きのコンテストに出ていたのだろうか。コンテストのトップページを調べてみても特に賞金に関する言及がないので、もしや詐欺メールかとも思いかけた。しかしリプライでCodeChefの毎月行われるdiv.1コンテスト2つ（Lunchtime、Cook-Off）には毎回賞金がついていると知り、驚き。上位10人に100USDらしい。

How do I win a CodeChef Goodie? - #2 by admin - faq - CodeChef Discuss

ラノベを1冊読了。「宅録ぼっちのおれが、あの天才美少女のゴーストライターになるなんて。」2巻。前の巻にも増して良かった。後書きで知ったことだが、もともと文庫本2冊くらいの分量があったものを1冊にまとめたらしい。確かに様々なイベントが続けざまに描かれる濃厚な1巻だったと感じた。前半は入り乱れた恋模様だったり過去の出来事が影を落としたりで、微妙に辛くなりながら読んでいた。しかしそれも濃縮された文章でスッキリ解決して押し流されていき、最後の文化祭のシーンは屈託なく楽しむことができた。ステージに登場するそれぞれのグループに感動的な描写があり、このあたりの畳みかけるようなエモさも濃厚さの一つか。

朝方、計算物理学のレポートを書き始めた。時間軸以外に2次元以上あるような偏微分方程式を自分で設定し、数値計算で解くもの。講義動画で見た波動方程式による波のシミュレーションが綺麗だったので、それを扱うことにした。しかし普通にやっても講義動画のコピーにしかなりえない。そこで最初は球面上の波をシミュレートしたいと考えていた、のだが……講義で学んだ方法では不可能だと気付いた。グリッドの縦横隣接するマスから値を集めて次の瞬間の値を計算するのだが、球面に等間隔のグリッドを設定することができない。ビジュアライズしたら綺麗だっただろうなと悔しい気持ち。波のシミュレーション自体はすでにコーディングしてしまったので、残り何とかそれっぽいことを書いてレポートを締めたとは言え、結局講義動画のコピーになってしまった。

ともかくレポートは終わった（ことにした）。ラノベをもう1冊読了。「陰キャだった俺の青春リベンジ」。かなり良かった。高校生活を後悔している人が逆行してもう一度やり直す話ということで、つい2月前に似たような設定のラノベを読んだ気もするが、まあ逆行モノはいくらあってもよい。ただいろいろ違う点もあって、最も大きなものとしては高校2年生からやり直すためすでに主人公の評価が定まっていたということが挙げられる。前半はその評価を覆していく描写から始まって、後半は文化祭におけるクラスの出し物を、社会人生活で培った能力で成功に導くというもの。これはもう好みど真ん中である。↓のハーメルンを思い出した。

syosetu.org

逆行して得られるチートは、未来知識を利用するものと未来で身に着けた能力を利用するものの2つがあると思う。前者のほうが強力ではある一方、自分が知っている時点までたどり着いてしまうという動かしがたい終わりが存在して何となく不安になる。一方後者はそういう不安がないという点で好みなのかもしれない。未来知識をもとに、破滅を回避するため努力して能力を身に着けるという展開もあるが、それはほとんど「転生したけど意識があるので小さいころから訓練できていました」という展開と一緒で、逆行だけのものではなくそこまで好みでもない。

インターン先から技術書を貸与してもらった。分厚くて怯んでしまう。

コードゴルフをした。以下\bmod 10^9+7で考える。フィボナッチ数列を行列累乗で求める問題は、行列累乗を短くするしかない。一方、それに似てa_{n+2}=2a_{n+1}+a_nなる漸化式を持つ数列に対しては、もっと違う方法があるらしい。まずこの三項間漸化式を解くと、a_n=\frac{(1+\sqrt 2)^{n-1}+(1-\sqrt 2)^{n-1}}2という式が得られる。ここまではフィボナッチ数列とほとんど変わらないが、フィボナッチ数列においては\sqrt 5が登場する一方でこちらは\sqrt 2が登場する。実は、10^9+7を法として5は平方非剰余だが2は平方剰余なのだ。つまり、いま求めた閉じた式を直接計算することができる。

2乗して2になる数は59713600と940286407が該当する。ここで、1+\sqrt 2\equiv 59713601と1-\sqrt 2\equiv 1-940286407\equiv 59713601を選べばもっと簡単な式になると考えたのだが、合わない。冷静になるとそれはそうで、\mathbb{Q}[\sqrt 2]\simeq\mathbb{F}_{10^9+7}という同型があるのだから同型ではなく準同型であった（2022/05/17追記）2つの数のうちどちらかが\sqrt 2になるともう片方は-\sqrt 2にならなければいけなかったのだ。

atcoder.jp

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

02/04(金)

午前7時起床。そこから二度寝に失敗し続け、午後3時半までずっとハーメルンを読んでいた。

途中で少しコードゴルフをした。今日は横に長いマス目を1x2のタイルで敷き詰める方法を数え上げる問題。想定解は1列の状態をbitで持つDPを行列累乗で高速化するものだろうが、マス目の行数を固定してOEISに投げるとそれぞれ漸化式が見つかる。閉じた式はなさそうだったのでどちらにせよ行列累乗で解くとは言え、2^K\times 2^Kの行列だったものが高々4\times 4に収まるのは嬉しいところ。遷移行列を埋め込んで縮めた。その遷移行列や初項の値も結構共通部分があって、頑張って式を作ると単純な3項演算子で分けるよりいくらか短くなった。

atcoder.jp

今日はもともとゲーセンに行くつもりだった。朝から起きていたので眠気があり、しかも夕方になってしまったのでかなり迷ったものの、結局行くことにした。途中イオン地下のフードコートでうどんを食べて、午後5時から午後9時半まで遊んだ。眠気が強くなったので閉店より前に帰宅を決めたという感じ。成果は新曲を埋めたのと、あとはケルン氏と会ってしばらくマッチングをした。14の未SSS+が残り2譜面になった。

これまでB判定-1.0くらいにずらしてもFASTが出まくっていたのがさすがに気になっていた。最近フィールドウォールを設定するとよいと聞いて試してみた。まだ自分に合う判定がどこか明確に分かってはいないものの、フィールドウォールを1にするだけでB判定-0.6くらいにはなるようだ。このくらいなら普通かな、という感じ。それにしても、画面上でほんの1センチ程度見えなくなるだけでこうも変わるものかと驚きである。速度もいくらかいじってみるといいかもしれない。

立ち食い蕎麦を食べて帰宅。羽生善治九段が順位戦A級から陥落したというニュースがTLに流れてきた。将棋ラノベなどから順位戦に関するルールを知って、こういうニュースの解像度が上がって印象に残るようになった。午後11時半就寝。

02/05(土)

午前6時半起床。今日も二度寝に失敗して、夕方までハーメルンを読み漁っていた。順に書く。

syosetu.org

「小学生に逆行した桐山くん」読了。ここ数日読んでいたもの。3月のライオンは原作を全く知らないうえに主人公が原作知識ありで逆行しているので、出てきたばかりのキャラをやたら警戒したりしてびっくりした。その辺りもちゃんと後々わかってくるような書かれ方をしているので、読みやすいほうではあるのかもしれない。話は一気読みしてしまっただけあってかなり面白かった。

最新話まで追いついている作品をチェックしていたら、「東方遺骸王」が更新されていた。602話にしてついにスカーレット姉妹が登場した。父となったキャラは結構昔から出ているオリキャラで、吸血鬼だとかそんな素振りは全くなかったのでびっくり。またこれで原作の500年前に到達したということで、かなり感慨深い。

syosetu.org

syosetu.org

「ソードアート・オンライン　ラフコフ完全勝利チャートRTA　2年8ヶ月10日11時間45分14秒(WR)」読了。主人公が悪人側なのでかなり胸糞悪い描写も多かったとは言え、面白かった。途中でエタっている。まだ致命的な崩壊には至っていないので、序盤の地盤固めなど後々裏切るためだろう行動を素直に楽しめた。その点ではここで止まっていてくれて助かったという感じ。

syosetu.org

「トレーナー、仕事辞めるってよ」読了。上の作者の別作品。面白いことは面白いが、これも救いのない話が多く大変だった。そういうのもたまにはいい。

生協の冷凍弁当を受け取って、午後5時前に再度寝た。午後8時半に目覚ましで起きて、食事してABC238に出た。

Monoxer Programming Contest 2022（AtCoder Beginner Contest 238） - AtCoder

Aは小さいところだけそのまま比較しようと思って少し計算したら、答えがNoになるのが2\le n\le 4のみであることに気づいた。sedで書いた。Bは適当に。CはN以下の正整数を桁数ごとに分けるとそれぞれfの和を計算できる。Dはx+y=(x\;{\rm OR}\;y)+(x\;{\rm AND}\;y)が成り立つので、x\;{\rm OR}\;yがx\;{\rm AND}\;yをbit的に完全に含んでいるかチェックすればよい。Eは最近見た気がする。区間の両端を結ぶ辺を張って到達可能性を判定。Fはうっかり正しい解法を捨ててDAGを考えてしまいかなり迷走した。しばらく考えて最初の考察に戻ると正しかったことが分かった。Pでソートして、これまで代表に選ばなかった人のうち最小のQを持つdpを行う。GはMo's algorithmで、うっかり素因数分解を\sqrt Aまでループ回す方法で書いてしまいTLE。ちゃんとエラトステネスの篩っぽく素因数を前計算して素因数分解を\log Aにするのと、3で割ったあまりを何度も取らないようにしたり、クエリのソート順を右端がジグザグになるようにしたりと細かい調整を加えて2度目の提出でACした。Exは区間dpをしばらく考えるも微妙に間に合わないオーダーになってしまって解けず。

コードゴルフ。Aはdcで3を引くことで、答えがNoになる場合だけ値の絶対値が1以下になるためRコマンドが使えるようだ。全然気づいておらず絶望。BはRaku。Cはkyopro_friendsさんの解説の方法で、Nの桁数さえ分かれば和を全部閉じた式で表せる。肝心の桁数はdcにおいてZコマンドで取れるので、かなり短くなった。Dは1行目を読み飛ばす方法に忘れていた改善があってclimpetさんに取られた。EはPerlで書くUnionFindで、これまたclimpetさんにかなわず。Fはdpの遷移をちゃんと整理するとほとんど列をずらすことに言い換えられて、和を取るのは限られた部分のみになる。Rubyで書いておいた。

syosetu.org

「もこたん→青ニート←その他大勢」読了。読んでみたら東方古代スタートだった。以前は主人公がダークソウル由来ということで微妙に避けていたが、よくわからないアイテムの説明もちゃんと入るしかなり面白かった。主人公本人的にはたまったものではないとは言え、やはり不死による圧倒的な長命は良い設定である。幻想入り後すぐエタっているのはかなり残念。

朝方、Pythonの講義の最終課題に取り組んだ。今回与えられたipynbファイルにはデータ読み込み部くらいしかなく、データの可視化・分析・予測のうち何を行うかすら自分で決める必要があるらしい。ひたすら面倒だったのでとりあえず可視化することにして、計算物理学のほうで学んだグラフのアニメーションを多用してみた。やはり自分がちょろっと書いたコードでアニメーションが作れるとはありがたいライブラリである。さらに日本地図を描くjapanmapを見つけてきて使ったりして、データをいろいろな方法で表示すること自体には成功した。ところで、今回扱うデータは新型コロナウイルス感染症に関係するもの。これを可視化しようとすると、最近の感染爆発に対するそれ以前の増減が小さすぎて全然目に見えないということになってしまい、大変だった。今思えばlogスケールにしてもよかったかもしれないが、終わったことなのでもうどうでもよい。

10万ツイートを達成した。

もう昼前になってしまった。今週ずっと溜めていた日記を少し書き、布団に入ってハーメルンを読み始めた。午後3時半就寝。

02/06(日)

午後11時起床。食事せずにCF #770 div.2に出た。AlphaCodeが参加する初めてのコンテストらしく、そういうフレーバーテキストが散りばめられていた。問題文に入っていなかったのは幸い。

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

Aは一回操作すると回文になってもうどちらの操作でも変化しないので、答えは1か2になる。Bは嫌らしいギャグ。まともにやっては絶対に解けない。必ずどちらか一方のみが達成可能という条件がミソで、これは必要条件を考えろということだった。実際、値の偶奇はどちらの操作でも同じ変化をし、初期状態で2人の偶奇が異なるため、少なくとも片方は達成できないことがわかる。Cは各行が公差が偶数の等差数列になっていればよい。これで条件を満たせることはすぐわかるが思いつくのが難しい。実は今述べたことは後から気づいたもので、自分は先頭から貪欲に作ると1,3,5,7,\dotsになるのを知り、さらに公差2なら何でもよいことに気づいて通した。

Dは難しい。最大の要素と最小の要素を更新しつつ列を舐めることを考える。つまり、4つの数から最大と最小を含む3つの数を選べればよい。これは当然クエリの答えが最大になるものを選ぶことになるのだが、よく考えると、4つの数に対するクエリ4種類のうち最大となるのは最大と最小を含んでさえいればいいのだから少なくとも2通り存在する。つまりクエリ3種類の答えを集めれば十分で、新しい要素を舐めるときは古いものの答えを持っていることを考えて追加で2回クエリを投げることで達成される。最初に1回聞く必要があるので、合計1+2(n-3)回のクエリで列全体の最大と最小を含む3つの要素が得られる。あとは3つそれぞれを外してクエリを投げてみて、答えが変わらなかったもの以外の2つ（あるいは1つ）を出力すればよい。合計で1+2(n-3)+3=2n-2回と回数制限にちょうど収まる。

Eは、同じ値でペアにして列の間に辺を張ると全頂点の次数が偶数になるので、適当に向き付けて閉路の集合にできる。始点と終点にそれぞれLとRを割り当てればよい。LとRが多重集合としてではなく集合として一致すればよいと勘違いし1WA。FはまずA'_i=A_i-B_iとし、次にC_i=A'_i-A'_{i-1}-A'_{i-2}と置くことで、クエリによる更新がCの高々3点の更新に言い換えられる。クエリごとにA'が全部ゼロになったか判定すればよくて、これはCが全部ゼロになることと同値なので、1点更新の際にゼロの個数も更新することで定数時間で判定できる。

全完8位。何かの手違いで、今日はAlphaCodeは参加しなかったらしい。そういえば、以下の記事で解けたと紹介されている問題はそこそこ難しめだったので話題になっていた。しかし105要素の列からpop(0)しているのが気になる。何らかの最適化はあるかもしれないが、まずTLEするはずだ。とはいえ、あの問題文からこのコードを生成すること自体信じられないくらいの成果であるのは間違いない。

www.deepmind.com

夜中から昼間にかけてはずっと溜めていた日記を書いていた。ちょくちょくハーメルンに時間を吸い取られもした。最近読んでいるのはこれ↓。ワンピースは80巻くらいから読めていないので、カイドウはビジュアルすら検索するまで知らなかった。先の展開もわからないまま普通に面白く読んでいたのに、ちょくちょくあとがきでネタバレを交えた原作の考察が始まってちょっと残念。

syosetu.org