01/03(月)

先週の週記を投稿したあとは、すぐ布団に入り、ラノベを少しだけ読んだ。冒頭に主人公がカツアゲされるシーンがあって、どうせ後々復讐の機会があることはわかっているけれど、それはそれとして精神的なダメージを受けてしまった。しかし30ページくらい進んだところですぐやり込めるシーンが出てきた。インスタントに力を得ているのが気になるものの、ストレスフリーなのは助かる。ほどほどで切り上げて午前6時就寝。

午後1時半ごろに起こされて昼食を摂り、また寝た。次に起きたのは午後6時半だった。寝てしかいないがなんとか夕食を詰め込み、ラノベを読んだ。2冊読了。

1冊目、「VRゲーで最強無双の少年、現実にステータスが同期し人生逆転」。展開は好みだったが、主人公がVRゲームで最強無双である理由が「一人だけステータスの伸びが異常で滅多矢鱈にスキルを覚える」というもので、受け入れられなかった。それはずるいだろ。そうするくらいなら、もともとトッププレイヤーだった等でいいのに。ただ、どこに「ずる」の境界があるかを考えているうちに、よく分からなくなってきた。プレイスキルの話でないなら結局何らかの形で運営から優遇されている必要があって、程度の問題に見えなくもない。主人公の状態の理由はまだ明かされていないが、ストーリーの根幹に関わっていそうな描かれ方をされているので、そのうちわかるのだろう。

2冊目、「劣等眼の転生魔術師」6巻。実はこれに限らず柑橘ゆすらさんの書くラノベはあまり好きではない（が、このシリーズは1巻を買ったのでそのまま購入を続けている）。テンプレな主人公TUEEEが多く中身がスカスカに感じるというのがその理由である。さて、この巻の後書きで、もうそろそろこのシリーズを完結させるというようなことが書いてあった。小説を未完のまま放り投げたくないという思いがあるそうだ。この作家は多作なので、そのほとんどをちゃんと完結まで持っていけていると知り驚いた。コテコテのテンプレ展開を書いてもちゃんと続刊できるほど売れているのは凄い。多作な作家は売れないシリーズに見切りをつけてぶん投げがち、という偏見もある。

入浴し、午後11時半からHello 2022に出た。

Dashboard - Hello 2022 - Codeforces

Aから題意を掴むのに苦労した。1マスずらしてもルーク同士が互いに攻撃し合わないという条件らしい。1行おき・1列おきにルークを配置する必要があって、対角線に並べておけば最大を達成できる。Bは左右両端にくっつく区間のうち最も安いものを持っておく。ただし両端を同時に達成できる区間は別に考える必要がある。どちらも前から舐めつつ更新できるが、丁寧に書いていたら結構時間がかかった。Cはサンプルを見るとわかって、未定の場所を連打してループを探せばよい。

Dにかなり時間がかかった。ある行を引っこ抜いてある列に挿入するという流れを考えると、これを達成するために必要なパスと、引っこ抜いたり挿入するときのために余分に確保する隙間がいくつかの長方形の組み合わせで書ける。実は考察ミスでちゃんとコストを計算できていなかったが、実際のところある8マスのうちどれか1マスを除雪すれば良かったようで、それをコスト計算に含んでいたため通った。この事実を知ってから改めて必要な場所を眺めると、確かに8マスのうちどれか1マスは必ず使っていることがわかり、驚愕。

Eは実装が面倒。クラスの年齢の平均値と先生の年齢をそれぞれ降順に並べると、先頭から順に対応させられればよい。生徒が一人消えるのは、クラスの列から1つ引っこ抜いて別の場所に挿入することに相当するため、1つ前後にずらして対応させたものも前計算しておけば、いくつかの区間をチェックするだけで答えられる。区間のチェックは累積和で行う。クラスの年齢の平均値を扱う代わりに総和と人数を持って頑張っていたが、切り上げ除算すると楽というのを聞いてかなり感心した。

Fは場合分け。0が隣り合っている箇所と1が隣り合っている箇所を数え、それの大小を見る。1が隣り合っている箇所が多いなら、0を消して11を増やしたり、あるいは両端の0を含めて追加で操作してもよい。0が隣り合っている箇所が多い場合は、...10...01...となっている場所をいくつ...101...まで持ってこれるかを数えて、その分だけ追加で操作してもよい。

Gは間に合わなかった。増加列を数えるためのBITを2本用意して、1本目から2本目にどんどん値を移していくことで寄与を数える。ただし「 $i$ を含み $j$ で終了する」ような部分列の数を引く必要がある。この条件は $O(N)$ 個あるが、実は $j$ でまとめて $A_i\lt A_k\lt A_j$ なる $k$ だけ考慮してみると、そのような $k$ も $O(N)$ 個である。 $A$ の降順で並べると、 $j$ の決め方から各要素が $k$ として高々1回しか現れないとわかるからだ。よって $i$ と $j$ の間の増加列の個数は愚直に計算してよく、左側は前計算できるので、ちゃんと引く値が求まる。システス後に投げたら通った。

結局6完78位で、predictorによれば-15である。2900を割ってしまったが、Dでかなり詰まっていたことを考えれば耐えたほうとも言える。

しばらく日記を書いてから、C++のコードゴルフを行った。boostライブラリを使うもので、手元にコンパイル環境がないしテザリング状態で落としてくる勇気もないので、コードテストでちまちまやっていた。なにもわからない。append関数の第2引数の型を第1引数から推測する、みたいなことはできないらしく、またinitializer_listを直接渡してもどうにもならないようだ。point_xyに暗黙的に変換可能な型も見当たらない。

atcoder.jp

布団に入ってしばらくラノベを読んだ後、少しだけハーメルンを読んで、午前7時前に就寝。

01/04(火)

午前11時半に目を覚ます。

眠れないままハーメルンを1作読了。「さよなら愛しき記憶たち。」。以下少しだけネタバレになる。前半、悲しみの中にも少しずつ希望の光が見えてきたと思っていたのに、ちょうど真ん中の話でまた絶望の底に叩き落とされた。同じことを2回するのかなとも思ったが、今度はもっと速いペースで希望→絶望のサイクルが繰り返され、ヘトヘトになりつつ、なんとかハッピーエンドまでたどり着いた。正直バッドエンドもあり得ると思っていたので、救われた気持ち。ともかく感情を大きく揺さぶられる話だった。良い。

syosetu.org

今日の夕食に向けて、起きているなら今のうちに昼食を摂っておく必要があると考え、用意してもらった。食べ終えて布団に戻り、また眠れないままハーメルンを1作読了。

「好きな人を幸せにする能力【一話完結】」。1話ごとが長いものの、5話で諸々すっきりまとまっていて良かった。しかしハーメルンにおける他者の評価ほどには感じられなかった。必要最小限の情報だけを書いているという意味で、この作品は上手であるはずだが、作中の世界に浸りたい自分としては短い作品はあまり、ということかもしれない。

syosetu.org

その後もいろいろハーメルンをあさり続けている間に夕方になり、夕食のため出かけた。

大学の卒業祝いということで、今度は僕が両親を連れてきました#柿里 https://t.co/E5UWHgAsEv pic.twitter.com/icOPif5Zj4
— こたつがめ (@kotatsugame_t) 2022年1月4日

4年ほど前、高校卒業・大学入学祝ということで連れていってもらった店（の本店）に、今日はこちらが両親を連れてきた。連れてきたと言っても車の運転は父だったが、会計は僕が持った。インターンで、初めて正式な契約を交わして金銭を得たので、そのお祝いという意味もある。少し早いが、初任給でネクタイを贈るのと同じ気持ちだ。僕が13時間働いたくらいの金額になったものの、今年も頂いてしまったお年玉と相殺された感じがする。

懐石料理で、メインディッシュの肉を目の前で焼いてくれる。出た料理は上のツイートとそのリプライに記録してある。各料理の見た目や味は自分には評価できないが、例えば煮物に入っていた里芋について、外が崩れていないのによく中まで火が通っているということを母が言っており、なるほどそういう点もやはりプロなのかと感心したことを覚えている。肉を焼く際には仕上げにフランベが行われるので、これを動画に収めようと画策していた。4年前に行った店では事前に撮影タイミングを声掛けして頂いたので、今回もそうだろうと期待して席でちんまり待っていたら、一言もなくにわかにマッチを取り出されたので、慌ててスマホを構えた。結果、少し遠いものの思った以上に上手に撮影できており、その中の1フレームを上のツイートに添付している。

本屋に寄って帰宅。睡眠不足と長時間車に乗った疲れから、日付が変わるまで2時間ほどこたつで寝てしまった。起きてから、01/06の夜が期限になっているレポートのために講義動画の視聴を始めたが、最後までいかないうちに家のWi-Fiからインターネットに接続できなくなってしまったので、諦めて自分の部屋に戻った。

昨日コードゴルフしたC++コードが縮められているのを見つけ、1時間ほど格闘したがどうにもならなかった。appendの代わりに内部のコンテナにアクセスしてpush_backすれば推論が効くようになったが、微妙に伸びてしまい不発に終わった。

布団に入ってラノベを2冊読了。1冊目は「クラスで2番目に可愛い女の子と友だちになった」。非常に良かった。冒頭でヒロインと初めて会話を交わしてからお互いに急接近し、なんと1巻の間にお互いの想いを確かめ合うシーンまでこなしてしまうハイスピードでありつつ、しかしいろんな過程をすっ飛ばしたわけではないという印象で、満足感があった。主人公は友だちの作り方を知らないぼっちという設定だったが、それでいてあまりもじもじし続けることはなく、締めるところは締めてくれて、その点も気持ちよく読めた。

朝食にラーメンを挟みつつ、2冊目は「エプロンの似合うギャルなんてズルい」。ヒロインと主人公は疎遠になっていた幼馴染で、序盤から小動物みたいなイメージのヒロインと主人公のいちゃいちゃが描かれていたが、ヒロインの重めな設定が明かされるにしたがって、甘いだけのラブコメではないというような印象に遷移した。

さらにラノベを開いたり、複数のハーメルンに手を出したりして、午前10時就寝。

01/05(水)

午後7時半起床。即座に着替えて、帰省の度に訪れている塾に今回も少しだけ顔を出した。

帰ってきてレポートの続きをしようと思ったら、まだインターネットへの接続ができないままだった。たまに一瞬繋がるらしいが、それでは意味がない。父が回線速度を計ると、3.5Mbpsだったようだ。家に引いている固定回線でそれは、流石に旧石器時代との謗りを免れないだろう。ルーターもかなりの年代品なので、そこを取り替えればマシになる可能性があるかもしれないが、いっそのこと回線から契約を切り替えてくれるそうである。次回の帰省までには改善していることを願う。

父が身を切ってテザリングしてくれたので、そちらに接続してレポートを進めることにした。幸い動画自体は説明文から見なくても良さそうとわかったので、早速レポートに着手。Google Colaboratoryでコードを書いたりTeXを打ったりする。レポートのテーマは昨日の時点で考えていたが、スタートとゴールを決めず途中の何を計算したいかだけ考えていたため、かなり大変だった。適当なスタートを設定して、そこからBFSみたいにいろいろ計算して、なんとか結論っぽいものをひねり出しつつ、さも最初からそれが目的だったかのように書く。今気づいたが、これは論文を書くときにやってはいけないこととして最近TLに流れてきた記憶がある。

3時間ほどかけて完成。その後2時間ほどかけて日記を書いた。帰省先で読んだ本は当然仙台に持っていかないので、感想などこの場で書いておくのが望ましかった。

布団に入り、ラノベを1冊読了。「神狩1〈上〉」。巻数と上・下が同時に存在するので、読書記録などどう表記したものか迷った結果、背表紙に忠実に書いた。帯の推薦文に「厨二心を刺激される」とあって購入した。実際、戦闘シーンは丁寧かつスピード感あふれる潔さで書かれていて、なかなかものすごかった。ただ設定や描写は肌に合わないと感じてしまった。裏表紙にあるあらすじが、購入特典の短編に隠されて読めないまま購入を決めてしまったのだ。「魔王2099」を僕がおすすめする理由として、スチームパンクな世界観を支える設定に忠実な描写を挙げていたが、こちらも舞台こそ変われど同じことが言える。スチームパンクなら受け入れられて、江戸は受け入れられないというのは、ただの自分の好みらしい。

世界観の精密な描写に圧倒されます。
今年読んだ本のまとめ - kotatsugameの日記

明日新幹線に乗るため眠らなければならないのに、眠れない。TLに逆紅クイズというものが流れてきたので、引き込まれていくつか解いてしまった。本家をクリアした後、有志が作成したものにも複数手を出したが、やはり本家は謎解き要素も作りこまれているし、ちゃんと正解できる程度の難易度・順番が考慮されている分、格別に面白く感じられた。スマホで見ていると、問題文が折り返されてしまい文字数がよくわからなくなっていたが、逆紅クイズメーカーで作られた問題のほうには、文字を空白に置き換える代わりに黒い四角に置き換えるようにする機能が付いていて、そちらはわかりやすくて良かった。

クエスト「文字を取り戻せ」

午前8時半就寝。

01/06(木)

午後1時半起床。食事して、昨日読んだラノベの感想をさっと書き、荷物をまとめて車に乗り込んだ。仙台に帰る。仙台から持ってきた本が1冊、富山で購入した本が11冊で、そのうち10冊を帰省中に読んだので、持って帰る分は2冊だけとちょうどいい感じになった。

帰省ラッシュはもう終わったと思っていたが、それなりに人がいた。進むにつれてどんどん人が増えていって、大宮の手前でついに僕の隣にも人が座るようになった。

行くぜ！(ｶﾞﾀｯ pic.twitter.com/PaZsTg8i4o
— こたつがめ (@kotatsugame_t) 2022年1月6日

大宮につく直前にラノベを1冊読了。「公務員、中田忍の悪徳」2巻。この巻も良かった。それはそうと新しく登場したキャラクターがかなり嫌な人物で、これもまたラノベらしくない描かれ方をしていたように思う。さて、1巻からずっと異世界エルフのほうに注目していたが、全然コミュニケーションが取れるようにならない。いったいいつまでかけるつもりかと思っていたが、そもそも異世界エルフはこの作品の主題ではないということに気づいた。それもそうで、題名からして主人公・中田忍に注目するべきであるようだ。帯に書いてあった主人公のセリフ「俺は、変わっているのか？」は、自分が奇天烈な人間であるかを確認しているのではなく、自分が変化しているのかを確認していた。その変化こそが、少なくともこの巻の主題だったのだ。

大宮で乗り換えが30分ほど発生したので、ゲーセンに向かった。パラパラと雪が降っていた。ゲーセンについてチュウニズムのところに行くと、4台が全部埋まっている上に待ちも4人くらいいたので、即座に諦めて退店。別のゲーセンを探してみることにした。3年くらい前、同じく大宮でFFとエンカ（原義）したことがあって、そのときに遊んだ店を探しにふらふら歩いていたが、見つからなかった。しかしいい暇つぶしにはなったので、駅に戻って次の新幹線に乗り込んだ。

もう1冊のラノベを開くも、そちらは読み終わらず、仙台に到着。駅前でつけ麺を食べ、部屋のマスクが残り少ないことを思い出して購入し、ゲーセンに向かった。今年初めてとなる。今日は手袋もないので、新曲や通常解禁された曲をとりあえず埋めていた。目立った成果もなく、午後10時半に退店した。

部屋に帰り着いて、今月のスマホ通信量を確認。ギリギリ3GB未満に収まっているように見える。3GBからまた値段が変わる契約プランなので、少し気になっていた。

帰省中のリザルトです pic.twitter.com/5Snxh68uLw
— こたつがめ (@kotatsugame_t) 2022年1月6日

パソコンの前に座ると離れがたかったので、シャワーを浴びる前に新春TechFUL Coding Battle 2022に追加された4問を解いた。追加分のvisibleは2問で、その部分は何とかまた理論値を維持できている。その後1月発売のラノベ新刊をチェックした後、やっとシャワーを浴びた。

橙diffの問題を1問通した。「Two Snuke」。 $\prod_a a$ を $\prod_a \binom{a}{1}$ と読み替えるテクで、答えが $\sum_{l=0}^{(N-5)/2}\binom{l+4}{4}\binom{N-2l+5}{10}$ と表せることまではたどり着けたものの、そこから進めず解説を読んでしまった。dpに戻して行列累乗と知りびっくり。また僕が求めた式でも、 $N$ の偶奇で分けたあと $\sum$ の中身を展開すると、 $l$ の14次式、つまり和を取って $(N-5)/2$ の15次式になるので、ラグランジュ補完で答えが求まる。それとは別に、2個組にして考えることで偶数という条件を満足させる方法があり、こちらは直接 $O(1)$ で求まるようで、これで最短コードを取っておいた。

atcoder.jp

JOI春合宿の問題を1問解いた。問題自体は簡単だが、形式が特殊で、指定されたヘッダファイルを読み込み、そこに定義されている関数を呼び出す形で解くため、CまたはC++でしか通せない問題。std::minmax_elementを呼び出すだけのC++コードが最短になっており、そちらも配列サイズを誤魔化すと縮んだが、それよりもJOI公式サイトから見られる想定解コードが上手だった。2要素ずつループで回して逐一更新していくと、高々定数個の変数でコーディングできるようだ。そちらをC言語で書いてしばらく縮めていたら、C++コードを容易く抜き去ってそれなりに短いコードが出来上がった。しかし、Compareという関数の呼び出しが3か所に存在するので、何とか別名をつけたくなった。これは関数ポインタを使用することで達成できる。普通に書くとint(*f)(int,int)=Compareとなるところだが、C言語のゆるさを存分に発揮すると(*f)()=Compareで動いてくれた。

atcoder.jp

布団に入って少しラノベを読むも、眠気が強すぎる。早々に切り上げて午前7時就寝。

01/07(金)

午後1時すぎ、腹を壊して起床。眠気こそまだかなり残っているものの、なぜか眠れない。

昨日少し読んだラノベに手を出して、読了。「機械音痴な幼馴染が我が家でリモート授業を受けているのは、ここだけの秘密。」。特に面白くもなかったが不快感もない、総じて記憶に残らない本だった。記憶に残っていないので何も書くことがない。

その後もスマホを触りつつゴロゴロしていたが、夕方になってどうにも眠れなかったことを受け入れ、ベッドから起き上がった。ゲーセンに行くことにした。地下鉄に乗って、まず仙台駅まで出てサイゼリヤに入店。今月の間違い探しは、初手からろうそくの長さが違うことに気づくなどかなり順調に進んでいたものの、最後の間違いが見つからず諦めてネットで答えを見てしまった。最初に見つけた間違いのすぐ左に、これまた微妙な違いが残されていたらしい。難しすぎる。

ゲーセンに入店。今日は午後6時半から閉店する午後11時半までいた。成果は14の99AJが4つ、AJが2つ、14+のSSSが2つ、SSS+が1つ、15のSSが1つ。14+のSSSはどちらも比較的最近追加・通常解禁された譜面で、数回ずつプレイしたらパッと出てくれた。15は未SSが2譜面のままずいぶん長いこと経過したので、久しぶりに頑張ったら両方伸びた。メタバースは連奏して順当に伸ばしていったが、混沌はこの日最初にプレイした回の前半がめちゃくちゃ上手くて減速トリルまでで7000点くらい残っていただけで、その後ホールドトリルなどが大爆発して998kに。さらに数回プレイして、今度は逆に前半がボロボロだったものの後半耐えて、下の画像に見える点数から数十点だけ更新してある。前半が上手くいって後半が上手くいけばSSにも乗りそうだが、今のところ前半に再現性が一切ない。

メタバースSS！助けてくれ〜！ pic.twitter.com/0ZJPpLiPzk
— こたつがめ (@kotatsugame_t) 2022年1月7日

食事するため街をうろつく。一閃閣というラーメン屋は全席埋まって待ちが4人もいたので諦め、さらに歩いて油そば屋に入った。こちらは午前0時閉店で、その15分前に入店して大丈夫なのか心配になったが、店員さんに声をかけるとよさそうだったので入店。サッと平らげて、近くのドンキに入り、しかし何も買わずに出てきた。

帰宅。今日もまたスマホ通信量が増え、今2.99GBになった。多少は誤差があるだろうから、もう3GBをオーバーしているかもしれない。

ハーメルンを1作読了。「東方虚悪魔異聞（原作厨が原作キャラに憑依してしまう話）」。勘違いもので主人公の実際の戦闘能力はあまり高くないらしく、バトルは一切発生せずに会話主体で進む。小難しいことを言っているが特にヤマもオチもなく、あまり面白くなかった。

syosetu.org

シャワーを浴びて洗濯機を回し、しばらくパソコンを触っていたが、強い眠気に襲われてうっかり布団に入ったら即座に寝てしまった。午前2時だった。

01/08(土)

午後4時半起床。昨日結局干せなかった洗濯物をいまさら干した後、少しコードゴルフをして、さらに現時点で予約できる新刊ラノベをチェックしていた。今回は2月初旬までに発売されるラノベと、さらにいくつか買いそびれていたものを足して合計26冊になった。

日記を書いているうちに午後9時になり、ABC234に出た。

AtCoder Beginner Contest 234 - AtCoder

Aからよくわからない。手作業で展開していたが、あまり短くなりそうになかったので、普通に関数を定義してとりあえず通した。その後SymPyを使用して完全に展開。それはdcで書いても縮まなかったものの、 $f(f(t)+t)+f(f(t))$ を展開して最後に $f$ を適用するコードは25Bになった。と、Aに20分ほど使ってからBへ。BはOctaveで書くのが良い。ただdispで出力すると精度が足りずWAになってしまったので、出力関数を間違えたのも合わせて2ペナついた。Cを開くとあまりにもコードゴルフしやすい問題でびっくり。bashで16Bを出しつつ、これは先に出されているだろうなと絶望していた。Dはsetのイテレータをちまちま動かす方法で書き、1200msくらいになってしまったが、通ったのでOK。Eは適当に探索。Fはdp。

Gは最初、総積ではなく総和の問題を解いていた。こちらはmaxとminに分けて寄与する回数を数えればよい。しかしコーディングを初めてから誤読に気づく。しばらく考え、とりあえず同様にmaxとminに分けてdpを考えることにした。この際配るdpを考えてしまう。更新が区間addと区間mul（ただし区間mulで一度係数が掛かった要素は以降変更されない）という形で、1点取得ができればよいが、実はこの更新は遅延セグメント木に乗せることができるようで、必死に合成関数を書いた結果、addされる要素・mulされる要素・addされてからすでにmulされた要素の3つを持つことになった。こねくりまわして何とかサンプルを合わせ、1700msで通った。残り20分もない中Hを読んで、適当に近い要素を見るようなコードを書くも間に合わない。それもコンテスト終了後に提出するとTLEしてしまった。

コードゴルフ。この部分に書いてこそいるが、この日の朝方までにあった更新を含んでいる。A問題はコンテスト中に25Bコードを2つ作ったものの、そのうち片方が-1Bされて最短を取られた。スタックをdupしてからその下の要素を取り出すd3Rは、いったんkで上の要素を退避するほうが短くなることもあるようだ。Bはコンテスト中のOctave。Cはコンテスト開始3分後に16Bが提出されており、どうあがいても負け。DはPythonの優先度付きキューで、一度取られたコードを再度取り返すことに成功した。先にキューに小さい要素を1つ入れておくことで、popと出力が同タイミングで行われるようにするとよいらしい。EはRubyで全探索。Fは制約が大きいためコンパイルする言語でないと通らず、ひとまずPyPyで書いて様子を見た。combinationは階乗を前計算せずともインクリメンタルに掛け算・割り算していく方法で必要な値が取得できる。しかし途中でmodを取らないと遅くてどうしようもなかったので、 $5000$ までの数の逆元が必要になった。毎回計算していると当然間に合わないが、しかし一つずつpow関数で求める方法でもTLEしてしまい、結局線形時間で求めるアルゴリズムを組む羽目になった。これはCrystalに写してからも同じ、というか、Crystalは整数のpow関数がないのでそうするしかない。

午前2時からSRM821に出た。

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

Easyは $(i+j)\bmod 3=0,1,2$ のどれかを全部埋めれば達成される（実際はこれの左右反転したような形に配置した）。3種類の方法のうちどれかは自分で埋めるマス数の条件を満たすので、探して構築して出力。一瞬で見えたので慎重に確認してもそれなりに速かった。Medは二分探索で、判定は達成可能な区間を管理する。連続する区間を一つの要素にまとめると高速になると思って実装していた。また $0$ と $1$ はそれほどまとめられないように思えたので、bitsetで直接確認することにした。実際のところ、そのような小さいところでは区間が高々 $10^5/2$ 個でイテレーション50回の判定なのだから、何もしなくてもTL 4secには十分間に合う。慎重に慎重にコーディングしていたら信じられないくらい遅くなってしまった。Hardを読み、多倍長整数として文字列を用意し開平法を実装し終わったあたりでコンテスト終了。

Medが落ちた。二分探索の上限をtargetにしていたが、これは大間違い。久しぶりに大ポカをして非常に悔しい。70位で2588→2455(-133)。

Hardの素数判定は適当に10⁶まで用意しておけば十分じゃないかと思っていたが、実際のところ21桁の素数が登場するケースがあるらしい。long longでも扱えない整数でどうするんだと思っていたら、解説にはbashのfactorを使いましょうなど書いてあるらしく、信じられない。Hardを通している上位陣のコードを眺めてみると、JavaのBigIntegerやPythonを使っていたり、あるいは自作の多倍長整数ライブラリにミラーラビン法が実装されていたりして、本当にどうしようもない問題だった。

「最強魔法師の隠遁計画」14巻を読了。非常に満足感がある。序盤はファノン視点とアルス視点が交互に描かれて、ファノン視点では敵にいいようにやられていてつらくなり、一方アルス視点では恙なく生活している様子にモヤモヤしていたが、終盤になってついにアルスの戦闘シーンが描かれて開放感があった。まだ敵側はアルスのことを侮っているようなので、早く無双してボコボコにやっつけてほしい。やはり主人公最強は最高。

CodeChefでJanuary Long 2022 - Iが開催されている。まだLong Challengeに参加したことはないが、このコンテストはdiv.3限定なので自分はunratedらしい。そういう判定はコンテストの種類ごとのレーティングではなく全体のレーティングを見て行われるようだ。しかし物は試しということで参加を決めた。月曜日の夕方まで開催されているので、問題には言及できない。今のところ最終問題が解けていない。

https://www.codechef.com/JAN221A

Pythonの課題に取り掛かる。年末に出されたものの期限が日曜日、つまり明日までになっていた。今回はk-meansなどによるクラスタリングらしい。3次元の点集合を扱ったが、これをビジュアライズするコードがサンプルコードとして提供されていて、マウスで掴んでグリグリ動かせる形式だったのでびっくりした。以前、Google Colabでそのような表示をしようと試し、失敗した記憶がある。

午前11時半就寝。

01/09(日)

午後8時半起床。しばらく日記を書いて、午後10時からTROC #25に出た。

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

Aは愚直。Bは達成可能な最小値と最大値を丁寧に求めた。Cは非常に難しい。まず $\gcd(a,b)=1$ と決め打ってみる。その後 $a$ を $N$ の周辺にしていろいろ試していると、 $a=2N+1$ のときに $b=\frac{2N^2+N-1}{N+1}=2N-1$ と整数になることに気づいた。このとき $a$ と $b$ は $2$ 離れた奇数なので、互いに素であり、仮定した条件を満たす。Dは縦で選んだ区間と横で選んだ区間を独立に考えてもよく、それぞれの区間で1の個数を計算すればそこから花が育つマスの数を求められる。片方を決め打つともう片方の1次関数になるので、最大と最小のどちらかを使えば十分。

Eはしばらく次数の平方分割を中心に考え込んでいた。グラフが木であることに気づき、BFS順に頂点を並べなおすと区間add・区間sumでクエリを処理できるということを思いついた。Fは貰うdpを考えると $j\lt i$ かつ $\gcd(j,i)=1$ なる $j$ から遷移してくることになる。これを高速化する。 $i$ の約数であってsquare-freeなもの $p$ を列挙し、 $p\mid j$ なる $j$ から $\mu(p)$ （メビウス関数）を掛けつつ貰ってくることにすると、 $\gcd(j,i)=1$ の場合のみ係数が $1$ で他は $0$ になってくれる。素数を篩うときに素因数を保存しておくと十分高速に行える。この高速化はAtCoderで見たことがあるが、今回は包除原理を考えていたら思いついた。しかし包除原理とは微妙に違うように見える。

Gで、今増加中か減少中かを持つdpを書くも、最後のサンプルが合わずコンテスト終了。多段階に減少する列を列挙できていないようだ。6完13位で2651→2680(+29)、highest。評価が甘くて助かっている。

Gをupsolveした。yukicoderに似た設定の問題があるようで、それの解説を流用すると、どの要素まで使ったか・どの要素まで書き換えたか・何回書き換えたかを持つdpが作れる。遷移は区間加算になるので、imos法しつつ計算していくことになる。自分はその問題をよくわからない方法で解いてしまっていたし、当時の日記を読み返しても一言「dp」とあるだけで何もわからない。少なくとも僕の方法では書き換えの回数を勘案できないように見える。

No.1378 Flattening - yukicoder

「いずれ水帝と呼ばれる少年」を読了。あまり面白くなかった。文章が説明的すぎる気がして、引き込まれない。展開も今のところテンプレ通りに思える。

夜中から朝方にかけてyukicoderのテスター作業をした。年末に依頼されたものをずっと放置していた。結構数が多かったのでいくつかはまだ残っている。時間に余裕はあるらしいが、うっかりするとすぐ忘れてしまうので、注意したい。