12/21(月)
午後4時に寝て、午後7時に起きた。目覚ましで意識を取り戻したはいいものの、そのままでは二度寝してしまっていただろう。ただ眠気を吹き飛ばすようなことがあって、無事起床に成功した。
今日提出のレポートが1つ残った状態で寝たのだった。この期限は今日の日付が変わるまでである、ということは確認していたのだが、教員が何を考えたか「採点を終了しました」と講評を出していた。
「提出していない人も多く」←期限より先に締め切っているのだから当たり前である。さすがに指摘したら修正されるはずなので、一応コメントを送っておいて、当初の予定通りサークルの解説会が終わった後にレポートを書くことにした。
サークルのABC185解説会は、ホスフィンがF問題を担当してくれるとのことなので、残り時間でEから遡ってスライドが作れた分だけ発表することにした。結構時間を食うので、結局DとEしか発表できなかった。
ABC186のゆっくり実況が2000回再生を突破していてかなりうれしい。
レポートを書く。練習問題を解くが、そのすぐ上でやっている証明を真似したら簡単に解けた、と思う。自分では正しいことを書いているつもり。送ったコメントには返信がないが、かまわず提出した。
AOJのレーティングが更新されていた。一週間で250くらい上げた週もあってすごい。現在は1265.08。
日付が変わって、教員からコメントが返ってきた。
受け付けてくれるようだが、講評にヒントを書いてしまったので公平になるよう何かの処置があるらしい。僕は「ヒントが出された後に提出して」「ヒントを一切見ずに解いた」のでかなり辛い。こんなだったら思いっきりヒント見て解いたんだが……。
「ラノベのプロ！」を読んだ。ストイックなラノベ作家が主人公。描かれる主人公のラノベ書きに対する取り組み姿勢は僕の理想的な競プロへの取り組み方に似ているものがあると感じて面白かった。ゲームを一切しないとか、健康に気を使っているとか。僕は今あまり健康に気を使えていない。
月曜日公開のyukicoder アドベントカレンダーコンテストの問題は、負辺ありの最小費用流だった。これまで毎回ベルマンフォードに書き換えていたのだが、ここらで一念発起してライブラリに負辺ありの場合を組み込むことにした。結局ポテンシャル計算だけ最初にベルマンフォードで行えばよいので、add_edgeごとに負辺かどうか判定して、min_cost_flow呼び出し時に負の辺が存在したらベルマンフォードを行う。負閉路があるとassertで落ちる。min_cost_flowを複数回呼び出すことは想定していない。
午前5時くらいに就寝。睡眠時間を短くすると生活リズムも正されるのかもしれない。
12/22(火)
正午前に目を覚まして、Game of Vampireを読み返していた。午後1時半くらいになって、学食が閉まりかけていることを認識して向かう。
今日はそこそこ早起きだし市街地に出かけようか、と思っていたのだが、購買で買ったお茶などを家に置きに帰ったところ、眠すぎて布団に倒れこんでしまった。そのまま2時間弱の睡眠を3回程度繰り返し、午後8時になってしまう。睡眠時間を短くすると生活リズムが正されるというのは真っ赤なウソで、実際は一日中眠くてどうしようもなくなるだけ。
午後9時からのサークルのバチャに参加する。今日はこどふぉ#543。
A問題から難しい。途中順位表を見ていたが、ACしている人数も少なめなので、自分がドハマりしているわけではなさそう。そのまま44分+2WAかけて通し、B問題に進む。アナウンスでBよりCDのほうが簡単だといわれていたようなのだが、見ていなかった。Bは結構素早くわかって証明もできていたはずが、実装ができていなかったためこれも2WA。
CはZalgoやるだけ、Dは木DPを頑張るだけ。確かにB問題よりも簡単といわれても納得。結局4完で、現在の順位表（リアルタイムの人と僕より先にバチャをやっていた人）では19位になった。
アナウンスを読むと、この回がかの有名な「unethical and ugly behavior」の回だということがわかる。19位という数字には、unratedだったのもあって人が少なかったことも影響しているのかな。
そのあとはまたGame of Vampireを読み返していた。午前3時くらいに寝落ちした。
12/23(水)
午前9時、目を覚ます。またYouTube流しっぱなしデスクライト点けっぱなしエアコン付けっぱなし部屋の電気点けっぱなしで寝ていた。
第32回TechFULコーディングバトルの解説が公開されていた。昨日の深夜から言及が可能だったようだ。僕もここで言及しておこう。
3問目からいきなり難しい。負の数の四捨五入がどういうものかよくわからないが、ググると0.5足して切り捨てればよいらしい。誤差が怖いので全体を10^4倍して整数で持っていたのだが、負の数を切り捨てるのに失敗していた。これに気付かず2WA出して、最終的にはdoubleで持ってsetprecision(3)をしてしまった。そのあと負の数を切り捨てるのを直したコードでも通った。丸め方向の関係でsetprecisionと自前の計算で異なる場合があると思っていたが、ないことが証明できるか、テストケースにそのようなケースが存在しないだけか……。
8問目は最初TLEしてしまった。自分がうっかりヤバい探索を書いていたのか、それとも向こうの環境が僕のlog2つに耐えられなかったのか。冷静になるとlogは1つでできるので、それを書いたら通った。
10問目もTLEしてしまった。うっかりNTTに帰着してしまったが、もっと冷静になると個数無制限ナップザックみたいな更新をすることで線形時間で更新できる。そんなところに重めのlogを置くと落ちるのは当たり前なんだよなあ。ただ、手元では最大ケースでも3秒ちょっとしかかかっていないはずなのにTL 5秒でTLEしてるのはさすがに環境が貧弱すぎるのでは。
総合では5位だった。また1000円ゲットした。なんかTechFULのシステムがひたすら苦手らしく、微妙な順位しか取れない。といってもまだ2回しか参加していないからたまたま下振れしているだけかもしれない。
昨日は学食に徒歩で行ったら思いのほか時間がかかって学食が閉まりかけたので、今日は少し余裕をもって出発する。食事して帰宅、少しパソコンを触ってから今日こそ市街地に行こうとすると、電話がかかってきていたことに気づいた。折り返し電話をかけても通じなかったが、そのあとすぐさらに折り返してきてくださって、やっと会話できた。
リクルートの人事の方だった。インターン面接の結果発表。僕は一応合格ではあるらしいが、僕の適正を考え合わせると案内できる仕事がないので、冬のインターンには参加できないらしい。謎。
どうやら不合格をオブラートに包んでいるだけということはなさそうだし、インターンの面接に合格できただけで十分うれしい。つまり、自分の現在の能力や将来的なポテンシャルが評価され得るものであるということなのだから。インターンの面接に合格したという実績だけ得て実際の労働を回避した点でアドである、という指摘もあった。
実際どういう扱いがされるのか、またの機会に応募するとしたらどんなスキップができるのか（あるいはできないのか）は、何もわからないが、年明けに人事の方がまた面談をセッティングしてくださったので、そこで明らかになるだろう。
市街地に出る。まずはメロンブックスに行ってラノベの新刊を買う。「公女殿下の家庭教師7」と「辺境都市の育成者2」の連動購入特典を楽しみにしていたのだが、売り切れていた。12/19の発売日に行かなければならなかったのか、残念。他にも数店舗回って、チェックしてあった新刊で今日までに刊行されたものをすべて買い集めた。
ゲーセンにも行く。特に成果なし。午後9時からSRMがあるので、午後7時半くらいに切り上げる。ラーメンを食べて帰ろうと思い立つ。ラーメンパンチという店があって、移転したのだが、跡地もラーメン屋になったことをTwitterで見聞きした。そこへ行ってみたが、たまたま水曜日が定休日らしく閉まっていた。仕方なく一閃閣へ。無難。
今日買った本たち。
ふぁぼん氏と「このごろ毎月隣人のクール美少女と半同棲する本が出ている」との共通見解を得る。僕のラノベ遍歴においてはまず「お隣の天使様にいつの間にか駄目人間にされていた件」が出現したので、これがヒットしたことによる影響だと考えている。
SRM796に出る。EasyとMedを通して24位、2306→2328(+22)。
Easyは読解。読んでやるだけ。何がしたいのか意味不明。
Medも読解。重要な制約が2点、「ヘビは壁際にいない」「ヘビの頭は現在の胴体を跨がず空きマスのうち半分より多くに移動できる」とあった。前者はわかりやすく、想定では壁際を一周することがわかる。後者がよくわからなかった。
よく考えると、壁際のマスは8x8の盤面では28マスあるので、後者の制約を満たすためにはヘビの頭は胴体を跨がずに壁際のマスまで移動できなければならない。つまり、胴体の移動をシミュレートしなくても頭は壁際まで移動できるという話。
僕は胴体の移動もシミュレートして行動を幅優先探索し、13ステップで打ち切ったが、通った。あんまりよく考えていないが、ヘビの長さが最大の26だった場合は13ステップ以上移動すると全体で80回の移動回数制限に引っかかってしまうということから設定した。ヘビの長さがもっと短い場合を何も考えていない。
一年を振り返るブログ記事の構想を練っていた。読んだ本・なろうから何らかのランキングを作ることを考えていたが、一気読みして作中世界にどっぷり浸かるなろうに対して、新刊が出るたびに少しずつ読み進めるラノベは印象に残りにくいことに気づいた。もちろんシリーズ一気読みとかもあるんだけど、なろうと比較すればほとんど行わない。
午前3時くらいに就寝。
12/24(木)
いつから起きていたか記憶がないが、起床報告をする前から布団でゴロゴロしつつ二度寝しようとしていたはず。結局二度寝できずに午後3時に身を起こす。
学食の夜の部が始まるのを待って行く。午後5時くらい。店員さんは結構な人数がいるけど、客は全然いない。10人強くらいか。採算が合っていなさそうでつらい気持ちになる。ただ、帰宅途中にグラウンドの横を通ったら、部活をしている人が結構いたから、遅い時間になれば客の入りはそこそこ増えるのかもしれない。
午後7時からXmas Contest 2020に出る。最初に全体をざっと眺めていたが、今年はコードが極端に短くなるような問題はなさそう。真面目に取り組むことにして、最初にDの実験を繰り返していた。Nを固定してCをいろいろ変えながら出力を見ていたが、特に特徴的なことはなさそう。OEISに投げても反応なし。余因子展開して帰納的にできないか考えていたが、どうにもうまくいかなかった。
あきらめて順位表を見たところ、CのACが出ていたので、これを考えることにする。ナイーブにGrundy数を求めて出力してみたところ、0102101021021...というような出力が続く。01021と01021021で構成されているように見えるが、このどちらが出現するかはわからない。そこで、それぞれ010210→1、01021021→2と置き換えて出力してみることにした。今度は12122...となったので、さらに12→1、122→2と置き換えて出力してみる。
今度も12122...になったところで何となく予想がつく。おそらく再帰的な構造になっているのだろう。証明はしないことにする。そこで、それぞれのパーツの長さを下から順に求め、Grundy数を求めるときは上からどのブロックに位置するか求めていくコードを書いた。ナイーブな出力と突き合わせると一致したので、提出してみたところ、通った。
そのあと、H問題に挑んだ。制限時間が6secだったので、定数倍高速化だと考える。subsetに渡る和を取るのが非常につらいが、__int128を使って余りを取る回数を減らすと、手元で8sec弱になった。subsetのループを何とかする。具体的には、下6桁を64通り場合分けして、それぞれでループの内容を埋め込むコードを生成した。これはいったん和をlongに溜めたあと__int128に加算することができるのが効いて6.3secくらいになった。しかしどうやら手元よりAtCoderで動かしたほうが微妙に遅いらしい。まあそれがなくてもTLEなのだが、後から確認したところN=21のケースでは常にTLE打ち切りの6.6secになってしまっていて残念。
結局解けなかったので解説を読んだが、よくわからなかった。そもそもsubset convolution未履修。
「ラノベのプロ！」2巻を読んだ。ラノベの流行り廃りや打ち切りの方針に関する話が出ていて興味深い。こういうのは出版された直後に呼んだほうが当時のラノベシーンの空気感と照らし合わせてよかったな、と思う。打ち切りに関して、「昔はどのレーベルも2巻や3巻までは出して様子を見ていた」という発言がされていた。確かに、実感として2巻や3巻で終わるシリーズは非常に多い。どこかのあとがきで「3巻がシリーズ存続の山場」と書かれていたのを覚えている。しかし今はそうではなく、もっと早い段階で打ち切りの決定がなされるようだ。ところで、打ち切りの話をしている巻でこのシリーズ自体も打ち切られているのが皮肉的。
もう1冊読む。「両親の借金を肩代わりしてもらう条件は日本一可愛い女子高生と一緒に暮らすことでした。」という題名。題名・あらすじ・イラストに惹かれて買った。「ラノベのプロ！」によれば、これはラノベのパッケージングが僕に刺さったということ。ただ文章がどうにも合わなかった。外側だけ見て買っているのでそういうことはある。主人公の発言がほとんど地の文になっているのがなんとも読みにくい。
デレマス㊙情報というTwitterアカウントが今年も企画をやっていたので、一連のツイートを読む。去年も読んだなと懐かしい気分になる。毎年面白い。
Tamer's Mythology書籍版の続刊が決定したらしい。非常にうれしい。次は第2部ということか。あと一押し、3巻まで出てくれればフィルが王都に帰るのを読めるかもしれない。
金曜日は2限の時間帯に小テストがあるらしいので、起きる必要がある。布団でなろうを読んでいたら午前6時になってしまったので、午前10時半に起きることを強く念じつつ就寝。
12/25(金)
10時の目覚ましでは起きれなかった。10時半の目覚ましで起床。よく考えると、小テストの開始時に起きるのはまずい。慌てて顔を洗い、ブラックサンダーをかじりつつ投稿された小テストを確認する。
45分間より少し短い時間、頑張って解いたつもりだが、半分しか解けなかった。シンプルに演習不足。あとここ3週間分の講義内容に目を通しておらず、後半の問題はそもそも理解ができなかった。せっかくなので講義スライドを読んでから布団に戻り、午前1時ぐらいから二度寝した。
次に起きたら午後7時半だった。何らかの睡眠負債が溜まっていたのかもしれない。
ima.goo.ne.jp
話題になっていた記事を読んだ。創作物における天才のテンプレートみたいな感じですごいなあという気分になる。
高評価がついに100件に到達した。非常にうれしい。
こどふぉでICPCのミラーに出る。午後8時半からの5時間コンテスト。適度なところでやめるつもりだったのに意味不明なくらい好調で、結局5時間フルに参加してしまった。結果は全完で全体7位、個人としてはtouristに次ぐ2番手だった。戦略としては、1問解くたびに順位表を確認してその時点で最も解かれている問題を読む、というものを採用したのだが、1度も詰まらず毎回読んだものを通すことができた。以下、解いた順番に言及していく。
Eはやるだけ。最も簡単だった。Nもちょっと怖い見た目をしているが、やるだけ。Cもやるだけ。Fは平行で180度逆なベクトルのペアを数えればよい。Kは面倒なことを考えずに障害物の候補を全探索。判定を間違えて1WA。Dは貪欲だが、条件などの±1をミスって2WA。よくわからなくなって貪欲の順番を変えたりしていたが、大きいほうからと小さいほうから、どちらでもよい。
Jはクラスカルっぽくやるだけ。AはLISの先頭と間に大きな要素をはめ込む形になるので、はめ込める要素が存在するかをDSTで判定、LISは二分探索できないのでsegtree。セグ木は値とインデックスをペアにして区間maxだが、インデックスを反転しておかないとダメで、1WA。Iはよくわからないが、ベクトル2つを互除法みたいにして片方のx成分を0にしたあと、平行四辺形の内部の格子点を出力したら通った。
Mもよくわからない。値ごとにそれを含む集合のインデックスを持つことにして、それを調べる。ある集合を見るとき、それに含まれる値でループして、今見ている値を含むインデックスを舐め、以前に出現したかチェックする。ただしこれは最悪ケースでO(N^2)になるので、各集合について「それを含むインデックスの個数が最も大きな値」を調べるのだけ後回しにし、逆に「これまで出現したインデックスがそこにも出現するか」を調べることにしたら通った。いろいろ考えたけど最悪ケースもよくわからない。920msだったので、もしかしたらヤバいケースが入ってなかっただけかもしれない。3TLE。
Hは消す要素の小さいほうから(K-1)/2個目と大きな方から(K-1)/2個目の間に消さない要素が存在すればOK。Gは最初目との角度を持っていたが、どうも誤差が怖いので外積で判定することにした。目と並行な道を歩いている場合に注意。中途半端な場所から隠れる場合は正弦定理で求めたが、これと同じ処理を行うと0除算が発生する。Lは素数のべき乗をチェックしたいが制約が1e18なので、何とかする。具体的には、同じ素数のべき乗を2つ持ってきて、指数に関して互除法っぽいことをすると1e9以下にできる。それが終わったら気合いで場合分け。素数のべき乗を全部入れていいのか、それともちょっと減らさないとダメなのか、2個ペアしか作れないのにKが奇数の場合はどうするのか……など。最初の、指数に関する互除法っぽいところでミスしていて3WA。
最後1時間を残してB問題に突入した。solved数はいまだに一桁だった。K_iについて考える。まずsum=0とし、j日目はA_j-K_iを足す。sum<=0になったら、前回sum<=0になった日との差を計算してsum=0に戻す。最後まで終わったら、計算した日の差の最大値が答え。これをK全部について一気にできればよさそう。
足す値は狭義単調減少なので、sum<=0になるのは右端までの区間だとわかる。K_iはインデックスごとに不変なので、K_iの係数とA_jの和をもっておけば、全体にA_j-K_iを足すのは遅延セグメント木でできて、sum<=0となる区間の左端L_jも二分探索で求められる。このL_jを日ごとに記録しておく。sum=0に戻すのも、作用素にリセットのフラグを持たせればできる。
最後に、日の差を計算するフェーズが残った。K_{m+1}=infと考えると、このときは毎日売り切れるので、以降はL_jを降順に見て、隣り合う売り切れない区間をどんどんマージしていくとできる。マージするたびに最大値を更新すればよい。見えるのはすぐだったが手数が多くて実装に苦労した。サンプルは結構すぐに合ったので提出したが、ジャッジが詰まっていて10分くらい待たされた。終了10分前にジャッジが始まって、そのままAC。
今年度の新歓期間は12月の半ばまであったが、それが終了したので、サークルの名簿などに更新がある場合報告せよとのメールが来ていた。名簿を更新して提出した。
「辺境都市の育成者」2巻を読んだ。これ（というかこの作家の著作全部）は文章やセリフに非常に癖があって読みづらいが、設定は大好きなので喜んで読んでいる。「公女殿下の家庭教師」より読みづらかったと感じたが、なぜだろう。今のところは、「キャラが多くてほとんど『弟子』というポジションなので差がわかりづらい」からだと考えている。
午前7時半くらいに寝る準備を済ませて布団に入ったが、明日のAGCに向けた睡眠調整を考えるともう少し起きていたい。なろうを読みつつゴロゴロしていた。途中空腹に耐えかねて少し物を食べた。午前9時半、就寝。
12/26(土)
午後4時半くらいに少し目を覚まし、トイレしたりTwitterを見たりしていたが、もう少し寝ようと思って二度寝した。午後7時起床。シャワーを浴びてコンビニに行き、パン・おにぎり・お菓子を買ってくる。これは今日明日の食料になる。
bashで1000ACした。ここ一か月ずっとやっていた。
ついでにHeatmapもそこそこ埋まったようなのでツイート。All ACの欄はまだ少し薄緑が残っているので、これも消えたぐらいでもう一度ツイートするだろう。
3月から4月にかけては、言語アップデートに備えてOther Contestsの未ACを埋めていた。アップデート後は0msが出せなくなることが分かっていたため、今のうちに0ms出せるものは出しておこうという魂胆。ただし、Streakを意識しだすと切りがないため、わざわざ週に1回切っていた。逆に意識していないか？毎日新規で数十ACしている中で1日何もしないのは苦痛だったことを覚えている。でもうっかり続いてしまうよりはマシかな。
AGC050に出場した。結果はBCDの3完で72位、パフォーマンス2829でレートは2675→2691(+16)。
最初の1時間はずっとA問題を考えていたが、結局解けなかった。あきらめてBに行く。まず実験して規則を見ようと考える。添え字mod 3ごとに1の個数が等しければOKかと考えたが、反例が山ほど見つかる。ほかにも少し試したが、どうにもわからない。冷静になって制約のN<=500を見ると、これは区間DP。実際に区間DPできるので、できる。
Aに戻ろうかとも考えたが、今更通してもどうしようもないのでCに行く。すぬけ君が動くのを邪魔するようにブロックを置くのがよくて、すぬけ君は左にも右にもブロックがある状態になったらその中間地点にいるのがよい。ブロックを置くたびに区間の幅（すぬけ君が動けるマスの個数）-1がどう変化していくのかを見ると、BS...(k個)...SBS...(l個)...SBというターンのとき、min(l,k//2)になる。-1することによって'S'の個数と対応付けられ、式に±1が出なくてかなり綺麗。
結局、2べきごとに幅が0になるまでの手数が変わることがわかるので、0...20くらいまで持っておけばDPできる。累積和を同時に計算しておいて、それで一気に更新。'B'が出現する位置より左からは更新できない。最初に'B'が出現するときも別に処理しておく。
最初0...19で提出したらWAだったが、すぐに間違いに気づけて良かった。まあサンプル2つ目はそこそこ強そうだし、これで間違えるようならあとは制約に関することかmodを間違えているだけだと見当がつく。
Cを通したが、あまり順位がよくなかった。残り一時間、やはり今更Aが解けてもどうしようもないので、とりあえず30分くらいDを考えようとする。よくわからない制約。制約だけ見れば半分全列挙だが、この問題に対してはどうしようもなさそうなので、やたらめったらキーを持つDPだと睨む。遷移がループしそうに見えたので、連立方程式を解くタイプかと思ったが、ループはしない。具体的なDPのキーを考える。
対称性がそこそこあるので、今具体的に誰が残っているかは知らなくてよい。「今i人目を見ていて、j回目のターンで、残りの商品はk個で、すでに抜けた人はl人」くらいあればよさそう。ちょっと考えるとl==K-kが言えるので、キーは3つになる。この時、実際に商品を獲得できる確率はk/(K-j)となるので、確かに計算できている。(i,j,k)に対して、残っているN-(K-k)人それぞれの確率を計算する。つまりDP配列は4次元になる。コードを書きながら遷移を考える。
(i,j,k)から遷移するのは、(i+1,j,k-1)と(i+1,j,k)。正確にはこれらを計算した後に貰ってきて合算する。ただしi+1==Nのときは人が一周するので、例えば(i+1,j,k)の代わりに(K-k,j+1,k)を呼び出すことになる。この時、残っているN-(K-k)人をK-k...N-1にマッピングしている。今見ている人が商品を獲得できなかった場合はK-k...N-1それぞれを今のDP配列に足す。商品を獲得できた場合は、人数が1人少ないDP配列が戻ってくるので、自分の場所で分割してk/(K-j)を割り込ませる。
しばらくガチャガチャやっていた。サンプル1は比較的早い段階で合ったのでオッとなったが、サンプル2が合わない。いろいろ修正して、最後に割り込ませる処理の添え字が少し違ったのを直したら合った。サンプル3を試すと実行が終わらなくて顔面真っ青になるが、よく見るとメモ化できていなかった。そこを修正したらなんとサンプル3も合って、提出したら爆速で通った。これで64位まで浮上した。残り30分である。
solved数を見ると、やはりCもDもかなり解かれている。これは解けるべき問題だったので、チャレンジしてよかった～という気持ち。EFはもうペンペン草も生えない不毛の荒野と化しているので、満を持してA問題に再度向き合った。無向辺のつもりでa->bとb->aを両方張ると一瞬で終わることに気づく。2べきで一生考えていたが、どうにもうまくいかない。そもそも、ループを2つ組み合わせたらそれ以上新たにつなげるのが難しくなる。残り5分で3のべき乗じゃないかと考え、三角形をたくさん作ってみたが、全然うまくいかず、絶望のうちにコンテスト終了となった。
Dに取り組んでいるあたりはコンテスト時間足りないと感じていたが、終わってみればAが結局解けなかったので、むしろこの時間で終わってよかったという感じ。TLに流れてきたi->2i,2i+1という解法を目にした瞬間、あまりのシンプルさに絶望する。これでAGC-Aは2連敗。
コードゴルフをしていたところ、A問題は1..Nを2回出力すればよいことに気づく。これは0-indexedで2i,2i+1を出力している。実現する方法はいろいろあって、Rakuは18B、dcでffと2回出力するのは17B、Vimでseqの出力をヤンク&ペーストするのは14B。ここで打ち止めかと思ったが、sedで11Bを達成できた。
atcoder.jp
面白い。まずs/^/seq /でNという入力をseq Nに変える。eオプションで、シェルスクリプトとして実行した結果に置き換える。これで1..Nが得られた。そのまま処理を終えるときに1回出力されるが、2回出力する必要がある。pコマンドを使ってもよいが、s///に存在するpオプションが（文を区切る必要がなく）短い。置換が行われたときだけ出力してくれるが、今回のコードでは必ず置換が行われる。
EとFも読んでおく。Fはまあよくわからないなあという感想しか抱けない。Eの問題設定のシンプルさはすごい。これに1800点がついて、3時間半で0ACなのはいっそ感動的ですらある。
ラノベを2冊読んだ。まず「異世界でチート能力を手にした俺は、現実世界をも無双する7」。テンプレチーレム無双。爽快感はあるので好き。
次に「隣のクーデレラを甘やかしたら、ウチの合鍵を渡すことになった」。これは非常に面白かった。最近よく見る「隣人のクール美少女と半同棲する」話。ただ序盤から一気に溶けていくので、クール美少女過激派にはおススメできない。なろう発でもなさそうだし電撃大賞の応募作品でもなさそう。どういう経緯で出版されたのか気になる。続きも気になる。僕は実は溶けてからが好きだったりするので、続刊で描かれるだろう学校での交流とかも非常に楽しみ。かなり売れてそうなので間違いなく続刊は出るだろう。
これで今月読んだ本は31冊となった。1日1冊。年単位で集計したら全然足りない。現在は366-105冊なので、あともう6冊読んで、せめて1年で366-99冊読んだことにしたい。3桁と2桁の違いを気にしている。
ECR100の録画の編集を始めた。まだF問題を解いていなかったので、解説を読んでACしておいた。全然考察できていなかったな、という感想。特に周期の長さが決まることに気づいていないのはよくなかった。勘付くくらいはしてよかったはず。C問題の途中までセリフを入れたら午前10時になったので、いったん切り上げる。
布団に入って少しだけハーメルンを読み、就寝。午前11時。
12/27(日)
午後6時くらいに目を覚まし、そのあと二度寝できずに午後7時くらいに起床。食事をしてシャワーを浴びる。AGC051。
AB二完で177位。パフォーマンスは2255、レートは2691→2654(-37)。ひどい、が、仮にもBは800点だったので、Aで3回ペナを生やしたにしては最悪ではないはず。
まずA問題。一目見てわからない。正方形と正三角形は分割できるので、どんな正整数dでも1通りはありそう。ここで順位表を見るとみんなペナを生やしているので、全部1ではないだろうと感じる。何を思ったか、dが2べきでないと作れないと考えてしまう。さっきの考察をすべて放り投げてこれを提出し、当然のようにWA。次に疑心暗鬼になり、全部1を提出して同じくWA。このあたりでようやく真面目に考える。
d=2の場合をよく見ると、内部の状態は正方形と正三角形がずれて2通りあることに気づく。これだ！と飛びついて2^(d-1)を提出し、WA。さすがに顔面真っ青になってよくよく見ると、内側に行くにしたがって辺の長さが(a,b)から(a-1,b)または(a,b-1)になることがわかる。これはcomb(2d,d)で、いちばん外側の回転を考えるとcomb(2d,d)/2。ようやくAC。
B問題に進む。Lの鏡映の形に並べるとよさそうに見えるが、実際に計算するとどこまで大きくしても2倍弱にしかできない。それでは、とこれをくっつけて繋げても同じ。そこで、Dからは全部見えるようにちょっと離して3つ並べることを考えると、どうやら再帰的な形になりそう。比も2倍を超えた。さらにもう一段階大きくして計算した結果、見える個数の比が指数的に増えることが分かったので、実際にフラクタルな図形をプログラムで生成してチェッカーに投げた。良さそうなので提出し、手元の出力を再度確認していたらすぐACが帰ってきた。
そのあとCに2時間、Dに1時間半をかけたが、どちらも解けなかった。Cは最初、2x3の長方形だけじゃなくて3x2の長方形も使えるとなぜか考えてしまっていた。これだと全部の黒マスを左上に集めて全探索できるので、誤読に気づいた後も端に集めることをずっと考えていた。解説にある不変量らしきものも発見していたが、僕はこれを具体的に操作した結果として得ていたため、それを不変量だと認識したうえでの考察ができなかった。ある黒点(x,y)は(0,y mod 3)、(0,y)、(x,y mod 3)に変換できるが、こういう操作で考えると（操作前も操作後も）x==0を特別扱いする必要がある。Dはマジで何もわからない。適当に変数を2つおいて立式したら二項係数3つの積の和が出てきて、WolframAlphaに投げたり計算量が少ないとうれしいなと思ってサンプルを試したりするにとどまった。
僕と同学年の競プロ事情に関する話題が出てきたので、夏季セミナーの写真や情報オリンピックの名簿を見たりして懐かしい気持ちになる。夏季セミナーにおける僕のふるまいは思い返してみれば黒歴史にふさわしいものであったので、深く考えないことにする。
今日もラノベを1冊読んだ。「痴漢されそうになっているS級美少女を助けたら隣の席の幼馴染だった」3巻。読みづらいと感じながら読んでいたが、この読みづらさはセリフをしゃべっているキャラが即座に判断できないことに起因しているように思う。原因の多くは自分の読書姿勢に帰属していて、「場面におけるキャラの（物理的な）立ち位置を想像せずに読んでいる」「そもそもキャラと口調をまともに覚えていない」がある。
月曜日はこどふぉに出たらすぐ寝て、火曜日の帰省に備えたい。それまでに動画も完成させたい（実家には編集環境はない）ので、明日の夕方が勝負どころか。
