週記(2021/01/04-2021/01/10)

01/04(月)

先週日曜日は、寝ようとしていたら両親が起床したので一緒に朝ご飯を食べて、さらにレポートを1問進めてから寝た。午前11時半のことであった。

午後6時、起床。夕食は外で食べるということが予告されており、また起こしてもらったため起床に成功した。回転寿司の店に行き、帰りに本屋に寄って帰ってきた。前回本屋に行ってから1週間も経っていないので新刊が出ていたりはしなかったが、棚を入念にチェックして3冊買ってきた。

夜、レポートを進める。大問は7まであるが、6以降は発展的な問題に位置づけられており、解かなくてもよさそう。また、最低でも3問は解くようにとのことだが、この基準はすでにクリアしている。それでもさらに大問4くらいは解けそうなので、頑張って書いた。

午後10時、完成。父にスキャンしてもらう。その間に風呂に入ったりしており、提出は午後11時だった。今日はこどふぉのdiv.3があり、レポートがあったのであきらめていたが出られそう。出る。

全完した。15位だった。

Aは自明。Bは適当に場合分け。Cは後ろから計算する。Dは値の降順に選べばよい。Eは誤読していて時間がかかったが、まずh<=wを満たすように交換してよくて、このもとでhの昇順に並べた後wの最小値を管理すれば特別なライブラリは何もいらない。

Fは最初入力で与えられるのが白マスかと思っていたが、さすがに違う。よくわからなかったので偶奇を保ったまま座圧して二部マッチングした。座圧周りがかなり怖かったが何とか通った。Gは遠い順に見ればよい。

コンテスト後のTLで見たが、Fは左から2個ずつ黒マスをペアにして見ればよいらしい。1つのタイルで偶数マス埋まることを考えると、一番左の黒マスについて、その上または下のマスは黒マスまたは1x2のタイルの左のマスに対応している必要がある。次に2番目の黒マスでこの状態は解消され、同様にしてペアにした黒マスの間はそれ自体で完結しなければならない。かなり頭が良い。

今日は本を買ったので、買った本の記録をつける必要がある。ちょうどいいのでこれも年ごとに切り替えることにしよう。

kotatsugame.hatenablog.com

このとき気づいたのだが、今年の読書記録に2020年と書いていたようだ。そのままツイートしたので非常に恥ずかしい。ただせっかく元旦に投稿したので固定ツイートは変更せず、2020年のままである。

「人生∞周目の精霊使い」を読んだ。最近は「一億年ボタンを連打した俺は……」や「……は時の牢獄で最強を超える」など人の身では不可能な期間の修行を理由にしたチートが多くて、そういう系列の本だと思って購入したが、1巻は結局ほとんど修行時代の話で終わった。マジで修行シーンを書いているとは思わなかった。ループの中で行動を変えたり、緊急回避的にcontinueしたりしていて面白い。こういう無限に強くなれる系の話は修行の辞め時が見つからなさそう、と思っていたが、この作品では「始原の神霊」と契約したところで精霊使いを極めたと判断して修行を終えている。次のループから物語が動きだして、そこで今巻は終わり。

AndroidのTweetDeck用ブラウザがTLに流れてきたのでダウンロードしてみた。かなりよさそう。最近公式のクライアントが落ちやすくて困っているので、乗り換えてもいいかもしれない。通信量削減のために画像や動画のサムネイルを読み込まない設定がほしいな、と思ったが、そもそもTweetDeck自体が通信量的に激重かもしれない。

もう1冊ラノベを読み始めた。「パソコンにおまけでついてるゲームね。爆弾を解除するやつ」「いつも一手目で爆弾を爆発させちゃうから、ゲームは嫌いよ」という発言があった。これに違和感を覚えて調べてみたところ、Windows Vista以降の付属マインスイーパは初手の瞬間に盤面を生成するため、一手目は必ず爆弾ではない(どころか周囲8マスに爆弾は存在しない)ようだ。より古いバージョンでプレイしているのかもしれない。または盤面のリプレイをしているだけかも。

両親が起きたので今日も朝ご飯を食べ、午前8時半に就寝した。

01/05(火)

午後7時、起床。昨日読み始めた「クラスの大嫌いな女子と結婚することになった。」というラノベを読み終えた。かなり面白かった。YouTubeに投稿されていた(?)漫画が原作らしい。これは今週の月曜日に買った本の1冊だった。つまりラノベの刊行予定を見ながら行っている新刊チェックに漏れていたということだが、表紙・タイトル・あらすじを総合してかなり良さそうだったのに何で買ってなかったのだろう。

こどふぉでメッセージが来ていた。昨日のE問題のコードがわからないから教えてくれというもので、どこがわからないのか書かれていなかったのでコード全体にわたってそれっぽいことを頑張って書く。30分もかかり、終わったのは今日のこどふぉdiv.1の直前だった。コンテストが始まってからありがとう見たいなメッセージが来た。

4完して2656→2675(+19)。

AはTLが1secだが気合を入れてlogをつけた。このlogpriority_queueによるものなので、400msくらいで通った。

Bは難しいが、結局xyが平方数のときにxyadjacentであるらしい。もうちょっと考えると、素因数分解した後各素数の指数をmod 2で考えて、完全に等しいペアがadjacent。さらにこの関係は推移律が成り立つので、数列はグループに分かれる。0秒目におけるグループのサイズが偶数である場合、総積が平方数となるため、同じく平方数となった別のグループとくっつく可能性があるが、1秒目におけるグループはそのあと永遠に変化しない。また、グループが分裂することはない。

よって、0秒目におけるグループの様子さえわかればw==0w>=1の2通りが計算できてよい。素数の指数をbitで持ったりvectorにしたりすることを考えたが、冷静になると素因数分解する前に戻せばint1つで表現できる。後から知ったことだが、これは整数をsquare-freeにする操作と同等。

Cはパッと見どんな感じに変化するのかわからなかったので実験コードを書いた。いろいろ試していたが、ふと数列のpを中心とする区間が単調になることに気づく。あとは単調になっている区間を探せば二分探索で中心が求められそう。単調になる範囲は質問クエリごとに2増えるようなので、それを間に挟めないような幅で順に聞いて回ればよい。ちょうどpの位置を聞いてしまうとまずそうなので、毎回隣り合った2マスを質問することにする。かなり怖いのでチェッカーを書いて、oj t/rで試す。oj t/rに慣れていないので、ちゃんとオプションを指定できていないのにコードの間違いを探し続けたり、テストが実行できたら楽しくなって無為に何百回も遊んだりしていたが、どうやら通りそう。提出しつつ時間を見ると残り40分になっていてかなり焦る。順位表を見てもCがかなり通されていて、さらにDのほうが簡単らしくヤバい。

まあ40分もあるんだし、とDを読む。二部グラフが思い浮かんで、奇閉路が問題となるが、これもできる。結局連結でさえあればよさそう。問題は構築で、最初条件を勘違いして教師が隣接しても構わず出力していた。結局貪欲に取っていくしかなくて、そこで幅優先探索ではなく深さ優先探索をすること、教師を置いたらその瞬間に隣接する頂点をマークすることさえしておけばよい。提出したら通って、Eは全然通されていなかったので諦めてTwitterをしていた。

heno239がLGM到達していてかなり感動した。で、伝説……。

「僕はリア充絶対爆発させるマン」を読んだ。直截的な表現が多くてびっくり。

明日(狭義今日)は朝の10時半からコンテストがあるので、寝なければならない。しかしなかなか寝られず布団でハーメルンを読んでいた。午前4時半就寝。

01/06(水)

午前10時起床。目覚ましでも起きたし、前日に朝からコンテストがあると伝えていた母も起こしに来てくれた。朝ごはんもゆっくり食べていい感じ。パ研合宿2020第1日「SpeedRun」に出る。

Oが解けなかった。最初はコードゴルフをしつつだったが、途中からコードゴルフしている場合ではなさそうなことに気づき、必死に考察したものの届かず。そのあと他の人の提出を見ていろいろ縮め、昼ご飯を食べようとしたときに解けた。基底を取ることは考えていたが、ABを別々に考えてしまっていた。以下、各問題について。

AはText。改行が必要らしい。Bはget.comb.max.sayが最短となっている。さすがにこんなはずはないだろうといろいろ考えてみたが、見つからなかった。CはRaku演算子を使う。これはASCIIコード範囲では(&)と書ける。どちらも3Byteだが、パースの関係で空白が必要なくなるのほうが短くなることがある。今回はどちらも同じ。

Dは場合分け。答えを4通り用意してK/Nでインデックス付けするとよさそう。dcではrotate操作で実現できる。Eも場合分け。AWKで書くと短くなった。Fは見つからなかった場合のエラー処理が必要かと思ったが、-1を出力するケースは存在しないらしい。P==1の場合分けを頑張る。dc

Gはゴルフしていない。HはRubyで書いた。他の言語ではあんまり考えていない。Iはゴルフしていない。Jではというのが出た。$_²と同じ。これを適用して縮む問題がほかにあったので縮めつつ、変数の初期化などで改善して最短を奪取。4,6...だと$_を初期化しておく必要があるが、これは8,16...とすれば回避できる。出力する値には余裕があるので、公差を大きめにしてもACできる。

Kはゴルフしていない。Lはdc。すでに相当短いものが提出されていたが、隙を見つけて奪取した。MNOはゴルフしていない。

昼から4時間程度塾に滞在した。帰省のたびに顔を出している。

今日も塾に行く。採点のバイトをするのだ。水曜日もやたら長く塾に滞在したのは、話の流れで同じく採点していたからだが、今日は初めからバイト目的で向かう。

週記(2020/08/24-2020/08/30) - kotatsugameの日記

今日は年末年始の休み開けであるから、宿題の採点が追い付かないことが予想されていて、手伝いが必要なようなら採点バイトに入るくらいの気持ちで行った。数人とんでもない量の宿題をこなしてきた生徒がいて、僕は任された分が間に合わずヒィヒィ言っていた。結局先生にいくらか戻したが、先生はほかの生徒の指導をしつつ素晴らしい速度で採点しており、年季が違うなあという気持ちに。生徒への指導にしても、今日は言葉に迷うことが多くて残念な結果となった。

対面で指導する(僕が採点している前のテーブルに来て質問したりする)のは感染リスクが高めだなあと感じた。マスクをとる必要がないのでギリギリセーフか。

帰ってきて新春 TechFUL Coding Battle 2021に追加された3問を解いた。逆転チャンスと銘打たれているが、上位陣にとっては当然満点を取らなければならないレベルの難易度。まんまと1ミスしてしまい非常に厳しい気持ちになった。逆転(される)チャンスなんだなあ。

明日の夕方からドカッと雪が降るらしく、土曜日に予定があるので、明日のうちに仙台に帰ることにする。今日早起きだったので昼のうちに新幹線に乗れるだろうという計算。

「僕はリア充絶対爆発させるマン」の2巻と3巻を読んだ。シリーズ完結。正直なんの面白みも感じられなかった。本当は2巻を読了した時点で日付が変わっていて、早く寝なければならなかったのだが、3巻だけ持って仙台に行くのもなんだかなと思って無理して読んでしまった。

午前4時就寝。

01/07(木)

午前10時半起床。食事して荷物をまとめ、家を出る。

母に車で黒部宇奈月温泉駅まで送ってもらう。切符を買おうとしたら、12/23でみどりの窓口の営業が終了しており、学割を適用できない。あきらめて通常料金で買おうとしたところ、駅員さんに「みどりの券売機プラス」という機械の存在を教えてもらう。起動するとどこかのセンターにつながり、学割をカメラで読み取ったりして普通にみどりの窓口で行うようなやり取りののちに学割を適用した切符を発券してもらえた。10分くらいかかった。今日は結構時間に余裕があったので良かったものの、ギリギリだと間に合わないだろう。混んでいる場合もまずそう。今度からは事前に買っておくのがよさそうだ。

ホームは非常に寒い。外を見ると風が結構出てきていることがわかる。駅から自宅まで車で帰る母のことを心配しつつ、乗車。コンセントとフリーWi-Fiを確保し、今日の昼からのパ研合宿2020第2日「パ研杯2020」に備える。

6完で全体8位だった。終盤、部分点を狙うのを完全に忘れていた。

A問題はdc。空白区切りではなく改行区切りにしても通った。B問題は短くならなさそうなので、H問題のマラソンに行ってしばらくコードゴルフをしていた。

B問題は01BFSで書いたが実際はDP。C問題はいくらか考えると入次数と出次数の差がポイントになることが分かった。D問題はトポロジカルソート。E問題は各点についてそれが乗る直線の個数を数えたくなって、これは直線の傾きをsqrtで分けて処理すればできる。制約が2secなのでかなり不安になりつつ出したが、450msとかなり速かった。

Fを頭に入れて、部分点の考察ができた段階で乗り換えをした。移動の合間も考えていた。レートはある程度自由にやり取りしてよさそうだが、2倍にできるものの範囲は考える必要がある。今度も自由席にコンセントがついている車両だったため、先ほどと同様のセッティングをした後にもうちょっと考察をしたら解けた。

基本は二分探索で、判定問題を解く。LRを混ぜて順に処理する。Lを処理するときは、時系列のLにレートを全部置いていく。Rを処理するときは、まず対応するL以前に置いていかれたレートを全部回収して2倍にする。足りていれば余計な分をRに置いていく。足りない場合は、ほかに置かれたレートを回収してつじつまを合わせるが、このとき時系列順で最近置かれたものから取っていくのが直感的に良い(なぜなら、より古いものはより多くの人に2倍で回収され得るから)。

以上のことを区間0クリアと区間和の遅延セグメント木で処理した。つじつま合わせは二分探索で行った。これを提出したところ、WAがたくさんとTLEが1つ出た。どうやら倍になりすぎてオーバーフローしたらしい。全員分に相当するレートが確保した時点で打ち切ると、TLEが1つだけ残った。オーバーフローを解消したら直ると思っていたが、普通に間に合っていないようだ。

冷静になると、上の操作はdequeで実現できる。L以前のレートを回収するのはpop_frontで、つじつま合わせはpop_backで書ける。これを実装すると爆速で通った。

C問題をゴルフする。Rubyで書いていたが、Perlに書き直すと速度でもコード長でも大幅な改善が見られた。謎。残り30分で順位表を見ると、G問題が思ったより通されていた。慌てて考え始めるも、CHTが見えたあたりで嫌になり始める。オイラーツアーも必要に思えてきて、どうしても実装が間に合いそうにないなとなった。

今日の新幹線はかなりガラガラだった。緊急事態宣言と大荒れ直前の天気のダブルパンチで移動する人が極端に少なかったのだろう。

仙台について、ゲーセンに行く。素手でチュウニズムを頑張る。新曲の99AJ埋めをした。午後8時くらいに夕食を食べようとラーメン屋に行った。

ラーメンパンチという店があって、移転したのだが、跡地もラーメン屋になったことをTwitterで見聞きした。そこへ行ってみたが、たまたま水曜日が定休日らしく閉まっていた。

週記(2020/12/21-2020/12/27) - kotatsugameの日記

ここは今日はスープがなくなったらしく、もう閉まっていた。かなり残念。だし廊というラーメン屋に行った。

ゲーセンを変えてさらにチュウニズム。ちょっと理論値を狙ってみたが、非常に厳しい。何でもないようなノーツでもぽろぽろ落としてしまう。最後に怒槌を数回プレイして、なんとかSSに乗せた。終盤は有名な擦りや餡蜜があるのでそれをした。密度が高すぎてどれだけ失点しているのかわからない。しかし前半がとにかくボロボロ。

帰るときになって、壁のチラシでチュウニズムにおいて200円3クレイベントが開催されていたことを知る。今日は結構お金を使ったのでつらい。

帰りはかなり雪が降っていた。マスクから出る息でメガネが曇って前が見えない。

FHCのTシャツが届いていた。

今日のH問題の最短が奪われていた。p [100]*4e4にしてWAになり首をかしげていたが、p *[100]*4e4である。なぜこれに気付かなかったのか。マラソン典型である。非常に悔しい。

帰省前の自分は相当丁寧に部屋の食糧を食べつくしていっており、夜中にお腹が空いてつらい思いをした。午前4時就寝。

01/08(金)

午後6時半起床。親から実家の屋根の写真が送られてきた。めちゃめちゃ積もっていて、ちょっと見たかったなあという気持ちになった。土曜日の予定が、コロナのせいか雪のせいかはわからないが消滅した。

パスタをゆでて食べた。yukicoderに出る。D以外の5完。Bは直後に追加されたチャレンジケースで落ちてしまった。

Eは式を根から各頂点とそのLCAまで、それぞれの距離に分解して計算すればよい。適当にガチャガチャしていたら合わせるのに時間がかかってしまった。Fは既出。

Problem - F - Codeforces

2*(区間長)<=総積が正しい条件らしい。次のように証明できる:

週記(2020/12/07-2020/12/13) - kotatsugameの日記

証明に関してはこれ(引用の続きの文)でよい。当時のコードをコピーして少し書き換え、提出したところ、WA。ちょっと計算量がヤバいことは知っていたのでTLEするかもなとは考えていたが、WAとは……。

探してみるといろいろバグが見つかる。そもそも上の問題は+とか*をそのまま出力する問題なので、書き換えでミスしていた。それと制約の違いを直し忘れていたのと、オーバーフロー。それでもWAが取れなかったので、コードの根幹部分を一気に書きなおしたところ、通った。謎。ちなみに計算量がヤバかったのも直している。間の1が連続する箇所は切り分けるが、その区間の演算についてもbit全探索していた。そこは抜いておいて積に相当するか和に相当するかで変えればよい。

チャレンジされて落ちているBを放ってこどふぉdiv.2に出る。Eにめちゃくちゃハマってギリギリ全完。今日もスクリーンキャプチャしていた。

Aはギャグ。先頭は98にするしかなく、このとき8を境に折り返すことで989にできて、一番よい。Bは値の総和を求めるのだと勘違いしていた。hillvalleyだけを取り出したvectorを作ってそこだけ見たところWAで、冷静になると値を隣に合わせるのがよく、このとき差分は回りを少しだけ見れば計算できるのでよい。

Cはそれぞれの総和と最小値だけ持ってうまいことやる。AtCoderで似た問題を見たことがあったが、今回の場合難しいのはそこからだろう。リンクを貼るために問題を探していたが、ABCで出題されたと思い込んでいたため見つからず、TLに聞いた。

atcoder.jp

Dは明らか。Eは同じ値の頂点のペアに対して、それぞれを根にしたときのもう片方の頂点以下の部分木に入る頂点に1加算して、最後に0だった頂点を見つければよさそう。適当に根付き木にしたとき、加算は木上のimos法でできる。ペアの列挙については、同じ頂点を何回も見る必要がないのでペア数はO(N^2)ではなくO(N)になる。部分木の頂点をmapに入れて保持し、更新時に同じ値の頂点が見つかったら1加算の操作を行う。マージテクで間に合う。

根付き木にしたときに、ある頂点とその部分木に含まれる頂点のペアを処理するところでミスし続けていた。imos法において-1してキャンセルしなければならない頂点は、上にある頂点ではなく、そこから1歩ペアの頂点に向けて進んだ頂点でなければならない。これは部分木をマージしてから処理するのではできず、マージ前に部分木ごとに行う必要があった。

「見習い巫女と不良神主が、世界を救うとか救わないとか。」を読んだ。ストーリーはそこそこいい感じだが、ひたすら読みにくかった。三人称視点で書かれているのに急に主人公の一人称視点で感情が書かれたりするからだと推測したが、ではどう書けばよかったのかとか、他の三人称視点の作品ではどうしているのかは知らないので、これが本当に的を射た指摘であるかはわからない。

振り返ってみれば、本を読んでも内容にはほとんど触れず、読みやすかっただの設定が好みだのしか言っていない気もする。読むときに何も考えていないからそうなってしまうのだが、これからは意識的に内容に触れる感想を書くようにしたいと思った。

布団に入ってハーメルンを読み、正午就寝。予定が消滅したので思うさま生活リズムを崩壊させているが、レポート提出などで昼に起きなければならない用事はほかにもある。

01/09(土)

午後6時半起床。目を覚ましてしまったものは仕方がないが、もう数十分くらいは寝ておきたかった。この時間から二度寝するとまずそうなので起きる。

コンビニに行って食べ物を買う。サラダを2つと菓子パンを4袋、あとお菓子を少し。かなり空腹だったのでうっかり山ほど買ってしまった。

ARC111に出た。5完23位。パフォーマンスは3079でレートは2654→2704(+50)。大成功。直前まで作業していたため、画面を録画するのを完全に忘れていた。

Aは解法が降ってきた。C++でコーディングしたら結構時間がかかってしまったが、このくらいだったら最初からdcで書いてもよかったかもしれない。提出してからB問題に進む前にdcコードゴルフしたところ、12Bになって現在も最短コードである。難易度的には、ABCの300点問題というよりはAGCの300点問題だろう。

Bは既出。UFに辺の数も持たせようとして、ライブラリを書き換えるのではなく最初からフルスクラッチしようとしたら、typoしてしまった。1WA。

Cは置換なのでサイクルに分けることを考える。2頂点以上のサイクルがあったとき、そこにすでに疲れた人がいるとダメで、そうでない場合はできそう。実際、一番体重の重い人はサイクル内のどの荷物を持っても疲れないので、この人を使ってサイクルを縮めていけばよい。

Dはパッと見難しいが、制約がこれでもかというくらいに「解が存在する」ことを主張しているので、まあそれを使うんだろうなあとわかる。冷静になると、異なるcを持つ頂点を結ぶ辺の向きは決定できて、そうでないものはループの一部にならなければならない。あとはループになるように辺を向きづけるが、これは、できる。ある頂点からdfsすると、どこかのループに乗ってスタートした頂点まで戻ってこれる。そのループを縮約して同様に進める。実際には縮約せず、ただのdfsでできる。

Eはとても面白かった。まずA+BiA+Ciの差を考えることでiとしてあり得る範囲が求まる。その中で(A+Bi)//D(A+Ci)//Dの差は0または1。こういう考察はABCで見たことがあったので、すぐにたどり着けた。floor_sumをちゃんと使っているのも面白い。

atcoder.jp

A+BiDの倍数のとき、困る。僕は拡張ユークリッドの互除法で解いて実際に個数を求めたが、A+Biの代わりにA-1+Biを使えばよかったらしい。

Fは解けなかった。要素ごとに考えて、更新クエリがk回来たときある値になる場合の数を計算する。maxminがいい感じに補い合い、1..M-1のどれでも同じくM^(k-1)(2^k-1)通りだと分かった。あとはクエリの区間についての処理だったが、できなかった。インデックスiが含まれる場合の数はi(N+1-i)だが、これのi=1..Nにおけるj乗和をj=1..Qにおいて求める必要が出てきた。式変形の方針を間違えたのだろう。ほかにも考えなければならないことは残っていて、これができたとしても解けたとは思えないが、ともかくコンテスト中はこれにかかりきりになって終わった。

シグマが絡む計算の式変形が苦手であることが分かってきた。何とかしなければならない。

SRMに出るので、それまでラノベを読んでいた。

午前2時からSRM797。EasyとMedを解いて18位、レートは2328→2389(+61)。highestである。画面の録画をした。

Easyはどこまで上がるかを全探索した。最初、あんまり上がらなくても回り道すると行けるということを完全に見落としたまま実装し始めてしまい、ちょっと時間がかかった。

Medは難しい。期待値の関係を行列にして解くやつかと思って行列ライブラリを貼ったが、サイズが5000x5000になるので違う。冷静になると、行列の各行の非ゼロ要素は高々10個で、また関係する項の添え字もiに対してi+1以下となるため、iの小さいほうから順に計算していける。

具体的には、iを計算する際にj<iなるx_ja_j*x_i+b_jという形で保持しておく。このとき、x_i=a'*x_{i+1}+b'*x_i+c'という式にまとめられるので、ここからx_i=a*x_{i+1}+bに直して、それをj<iなるjの式に対して代入する。これで次にi+1を計算する際も同様の条件が満たされたままにできる。Nを項の数としてO(N^2)。実は、「前に1進む確率がpなら期待値は1/p」と「後ろ向きならx_i-x_to+1のコストで戻ってこれると考えてよい」でO(N)で計算できるらしい。すごい。

遷移関係を求めるのも少しややこしいが、こちらにもO(N^2)かけてよいので、やりようはいくらかある。僕はZ-algorithmを使用して判定を定数時間で行えるようにしたうえで全探索した。やっていることはKMP法のfailure-functionなので線形時間でも可能らしいが、名前を知っているだけで内容は知らないため実装できない。

自作のmodintを貼ったらコンパイルエラーが山ほど出て、結局直せなかったので普通にmodを取りつつ書いた。

Hardは意味不明。サンプルを手で解いて実際に条件を満たすことを確認するのに30分くらいかかった。

ラノベを1冊読んだ。「デスゲームから始めるMMOスローライフ」。スローライフ系の話は実はほとんど興味がなく、この作品は特に主人公やヒロインがチートだったりもしないので、完全に僕の趣味・嗜好からは外れていた。買ったのがもう4年も前なので、当時何を考えていたかはわからない。当時はちょうど、毎月新刊をチェックして新作を買うことを覚えたころだったが、資金は潤沢ではなかったので、現在のように「積んでいる本の続刊を買ってさらに積む」みたいなことはあまりしていなかったらしい。このシリーズは4巻まで出ているが、2巻までしか買っていなかったので、最近古本で3巻と4巻を購入して揃えた。

設定におけるSAOとの類似性がいくつもあってモヤモヤしたが、まあデスゲームを書くなら大なり小なり似てしまうのだろう。内容的には主人公がヒロインとずっと戯れているシーンが続くだけで、僕は面白くないと感じたが、続刊の帯によれば重版したらしい。

yukicoderの問題をいくつか解いた。

No.1200 お菓子配り-3 - yukicoder

この問題はABCが正整数であると書いてあるのを見落としてWAしてしまった。自分の最初のACコードが落ちるケースを発見したので、試しにほかの提出を確認してみたところ、いくつか落ちるコードが存在したので、チャレンジしておいた。

布団に入ってハーメルンを読む。最近は紙の本に注力していてネット小説はあまり精力的に読んでいなかった。今日やっと1作読み終えたが、これも1か月くらいかかった。

syosetu.org

東方Projectのオリ主系、好きかもしれない。

週記(2020/12/07-2020/12/13) - kotatsugameの日記

これを受けて読み始めた作品だったはず。1話の冒頭で東方先代録という作品が紹介されているが、これは途中で止まっている。

上位存在・長命種が人間の発展を見守ったり導いたりする話が好きだと言っている

週記(2020/09/28-2020/10/04) - kotatsugameの日記

「古代スタート」というタグがよさそうであることに気づいた。

午後1時、就寝。

01/10(日)

午後3時くらいに腹を壊してトイレに駆け込んだ。午後8時起床。ABC188に出る。

全完したが、Fに非常に時間をかけてしまった。今日も画面録画をしたが、どういう動画にするのがよいか迷う。コードゴルフの作業も結構録画してあるので、そちらをメインに動画を構成するのもいいかもしれない。

Fの2WAはビットシフトのオーバーフロー。1LLではなく1と書いていた。久しぶりにやらかしたので結構びっくりしている。↓と同じ問題であることに気づけなくて残念。AtCoderでメモ化再帰が頻出しているような気がする。そんなに使うとは思わなかった。

atcoder.jp

コードゴルフは現時点で全勝。Aはrangeとかminmaxとか考えてしまうが、差の絶対値を見ればよい。符号付のままでも、絶対値に関して切り上げ除算することで-2..2-1..1に圧縮すれば次の問題と同じになる。

atcoder.jp

BはRakuで書くだけだが、全完後にちょっと書き直したら1B縮んでびっくりした。遅きに失したかと残念がっていたが、蓋を開けてみれば最短だった。

Cは最初から左半分と右半分のmaxを比較する方針を取れたのがよかった。Dはコンテスト中は座圧してから解いたのでコードゴルフする気はなかったが、解説を読んでイベントソートでよいことを知り、縮めた。

Eは制約が優しいので順に見ればよい。辺をソートすると隣接リストを作らなくてもよくなる。Fはさすがにコンテスト中の方針(桁DP)でコードゴルフする気にはなれなかったが、解説でメモ化再帰解を知り、縮めた。Rubyでゴリゴリ縮めた後、仕上げにVimに移植したら一気に8B削れてびっくり。

1000ACはこれでAWKbashbcC++HaskellJuliaPascalPerlRubyの9言語。次はCでも狙おうか。

言語別AC数のページを見るたびに、Perl6Rakuが区別されてしまっているのが非常に気になるので、とりあえずIssueを立てた。プルリク用のコードもすでに書いたが、最初からプルリクを送り付けるのがなんだかためらわれて、まずお伺いを立てる感じ。別にそんな変な遠慮いらないのかもしれないと今になって思った。

github.com

新春 TechFUL Coding Battle 2021が終了した。最終順位は5位。12問目は非常に難しく、最初はO(3^N)にいくらかゴミがついた計算量で通そうとしていたものの、断念。遷移をもうちょっとよく考えると、ビット列を左から順に処理していってもよいことに気づき、i=1..Nに対してi桁目だけ処理するO(2^N)のループを書いたら解けた。15問目はS==Tで1WA。

yukicoderを数問解いた。

yukicoder.me

(1+sqrt(2))^nの整数部分を求める問題、みたいなのをTLで見たことがあるはずだが、肝心のアイディアを思い出せなかった。何らかの数とペアにして、そのペアの数の絶対値が非常に小さいことを利用することまでは思い出せたのだが……。結局解説を読んでAC。考察メモを見返した感じ、a+babを利用してa^n+b^nを求めるということができていなかっただけにも見える。