週記（2021/05/10-2021/05/16）

05/10(月)

先週の週記の最後の部分で、ARC118-Aの最短コードに使われている式を導いた。これについて、よりシンプルに見える手法がTLに流れてきた。

実は周期ごとに分けて考える必要はなく、A=\left\lceil\frac{100N}t\right\rceilでN回目の番号が飛ぶことになる。ceilとfloorが入り混じることになるが、結論から迎えに行こうとすればそれほど難しくなさそうだ。

布団に入ってなろうを読みつつ寝る準備をしていたが、大学生協に注文していた本がちょうど届いたらしいので、受け取りに行くことにした。また、かなり毛が伸びてきたので、床屋にも行く。昼休みとかち合うとまずいので急いだ結果、正午になる前に食事を終えて床屋に入店することができた。それでも昼休み直前だから結構混んでいた。3つ座席があって、ここ1年は真ん中を飛ばして使っていたのだが、今日は全部埋まった。

ほとんど寝そうになりながら髪の毛を切ってもらっていた。今日担当してくれた人は、すべての工程が終了した段階で微調整しようとしたのかバリカンを再度使用したりしたため、服に細かい髪の毛がついたりして大変かゆい思いをした。帰宅までつけたマスクにもかなり多い毛が残っていた。

生協で本を受け取った。これは完全に昼休みとかぶってしまい、今日受け取る11冊をレジに通してもらっている間に後ろに結構人が並んでいてびっくりした。

研究室に配属されたということで、安全教育の案内が来た。Classroomで動画と資料を見て、フォームの小テストに回答する必要があるらしい。適当に30分くらい動画を流しながらWikipediaで世界一の一覧を読んでいたが、それも読み終わってしまったので、小テストを確認してから動画のそれっぽい場所を探す作戦でサクッと完答した。

買ってきた本をさっそく1冊読んだ。「元スパイ、家政夫に転職する」2巻。やはり主人公が強いとよい。半ばにある模擬戦の描写がよかった。クライマックスのほうは敵役がかなりへなちょこだし、物語のピントもヒロインに集中していたので、バトルという観点から見れば消化不良気味。次巻へ続く引きもあったが、後書きはこれで完結かのような書かれ方をしていてビビる。打ち切りだろうか。

典型90問を解いた。今日はOctaveがよさそう。N行2列行列における各行(x,y)を(x+y,x-y)に変えるのは、右から[1,1;1,-1]という行列を掛ければ一気に行える、が、WA。このWAの原因は分かっていないが、以前の経験から行列を転置して左から掛けるとACできることが（僕に）知られている。以前の経験というのはこれだ。

atcoder.jp

今日のサークル解説会の準備をする。また何一つ始まっていない状態でこの日を迎えてしまった。これまで3回新歓イベントとして外部に解説会を公開してきたが、今日で最終回の予定だ。なのでそれなりに頑張る必要があると思ったが、頑張れなかった……。

ZONeプロコンの問題を取り扱った。今日は結局B問題とC問題のスライドを作成した段階で時間切れだったが、C問題の解説スライドは結構熱を入れて書いたつもりなので、解説会自体は結構喋ることがあって30分以上続いた。解説スライドは↓にある。

2021/05/10 定例会 | puzzleknot 公式サイト

布団に入ってからしばらくなろうを読み、午後11時就寝。

05/11(火)

午前10時起床。

書類を送ったインターン先から返信があって、とりあえず面接をしてもらえるらしい。1度書類選考で落とされた経験から、これも大変にありがたいことだという感覚がある。どこの馬の骨かもわからない輩のために面接官の1時間を使うのはありえないはず。

学食に行く。昼休み直前くらいの時間に入店してしまい、食べている間に周りの席がどんどん埋まっていて、感染症対策～！という気分になった。一言たりとも喋らないでほしい。

家に帰ってからは夜までずっと「数学基礎論特選」という講義のレポートを書いていた。3回分の講義資料を読んで、途中にある問題からいくつか選んで解く。かなり疲れた。特に最後のほうでは「数」と「数項」と「ゲーデル数」が入り混じるのも辛いし、だいたいゲーデル文「自分自身を証明できない」だったり対角化だったりは脳にめちゃくちゃ負担をかける。昔数学ガールで読んで挫折したが、今になっても満身創痍であった。

ずっと、といっても途中途中で集中が切れたりなんだりして別のことをやっていた。まず今日の典型90問のゴルフ。C++で遅延セグメント木を使って書いたが、反省してスライド最小値を実装した。こちらだとRubyでもちょっと余裕がある。

ノクターンノベルズを読んだりもしていた。

https://novel18.syosetu.com/n1848fz/

https://novel18.syosetu.com/n4476gq/

https://novel18.syosetu.com/n2204eu/

午後11時になって完成。普段考察用紙に書きなぐるのとは違ってレポートは丁寧に書くべきではあるが、なぜか字を丁寧に書けなくなってしまっていて、非常な悪筆。連絡が来ていて、東北大学の感染症警戒レベルの引き下げに伴いこの講義では対面講義をしようとしているらしい。意味が分からない……。対面になったら行かないと思う。せめて講義資料のアップロードは続けてほしいが、どうなるだろうか。

勢いづいて数理統計学の課題も解いた。今週は簡単なものを1問だけ。数値計算でもないので、計算機を使う必要もナシ。

木曜日のゼミはいよいよ僕の発表の番である。これの準備を（今更）始めることにした。少し教科書を読んだが、まあまだ難しくはなさそうなので、どのように発表するかに意識を割く。これまで2回、他の人の発表を見てきたが、皆手書きのノートをスキャンして映しているようだ。しかし僕の悪筆を人に見せるのはためらわれるし、どうやら丁寧に書く能力も失われてしまったようなので、LaTeXを使う。Beamerというヤツでスライドを作成することにした。

最初はdefinitionやらのblockが表示されなくて頭を抱えていたが、適当に調べたチュートリアルに従って\documentclass{beamer}を\documentclass[dvipdfmx]{beamer}に変更したら表示されるようになった。枠で囲まれていなかったのでblockとは……？という気持ちにもなったが、これはテーマによって変わる部分で、デフォルトだと枠で囲まれないらしい。なんとなくよく見る気がするorchidを選択しておいた。数式のフォントもデフォルトだとかなり垢抜けない感じだったので、変えておいた。

4時間くらいスライドを作成していたが、どうやらまだ発表範囲の半分も進んでいないらしい。しかも出来上がったスライドを見てみると、ただ教科書を翻訳しただけにも見える。そのような発表は唾棄すべきである、という言説は「数学 ゼミ」等で検索すればいくらでも目にできるが、実際自分がやる段になるとどうしていいかわからない。今読んでいる教科書は、ほとんどの事項を丁寧に解説していて、僕が気付けるような行間はない。

朝方日記を書いて布団に入り、少しだけなろうを読んで就寝。午前5時だった。

05/12(水)

正午、起床。今から学食に行くとちょうど混雑とかち合うので、ちょっとだけ二度寝し、午後1時過ぎに家を出た。学食は午後1時半にいったん閉まってしまうので、あまり時間の余裕はない。

帰ってきて、今日の典型90問の回答コードを作った。今日の問題も簡単なので、できるだけ早く提出できるようにしたい。また15秒おきに提出を試みるスクリプトを書いて、提出できるまでずっと動かしておくことにした。それはそのまま放置して、昨日の続きでスライドの作成を進める。

スライド1ページでは証明が終わらないようだ。そこをギュッと縮めて簡潔に記述する必要性を生じさせるのもスライドという媒体の醍醐味かもしれないが、今は普通に困っている。調べたところ、\end{proof}の直前に\let\qedsymbol\relaxというのを書いておくとよいらしい。確かに証明終わりの記号が消えていた。

さて、早くもスライド作成がいやになってきたため、ラノベを読んだ。「魔王2099」2巻。1巻の時点で非常に面白いと感じていたが、この巻を読んでさらにその思いを強くした。帯にも書いてあったことだが、笑えるシーンもシリアスなシーンも含まれていて、どちらもそれぞれこの作品らしさが（主に主人公のキャラがぶれないという意味で）あって、良い。

ストーリー的には、この巻では主人公の一行が学園に少しだけ通うことになる。これも非常に好みのシチュエーションだ。これに関しての僕の考えというのは以下のようなツイートのものだ。

「科学の力使いまくって隠居生活」の更新があった。ホスフィンに教えてもらった。やはりいつ見ても変わらない安心感がある。

www.youtube.com

僕は一時期Minecraftをプレイしていて、そのときは工業化MODを大量に導入していたが、それは主にこの実況シリーズの影響を受けてのことだった。このシリーズに限らずほかの工業化MODの実況者のような、機械や配管であふれた拠点にあこがれて、とりあえずクアーリーで掘りぬいて巨大な箱を作ったは良いものの、モチベが続かず途中で技術を進めることができなくなり、スカスカなまま終わる……ということを経験した。どうやら早い段階で大量生産をしようとするとダメらしい。そのような段階で資材を溜め込むことにはあまり意味がない。まあもうMinecraftはしないはずなので、今となってはただの思い出。

ラノベを読んだり動画を視聴したりする間にもスライドは少しずつ進んでいて、ついに日付が変わるころ完成。句読点を。、から. ,に置換したりしてそれっぽい雰囲気は出ている。発表範囲的には昨日で半分弱のスライドが完成していたはずだが、後半はちょっと計算が多く、ページ数では今日は昨日の倍くらい作った。出来上がったので興奮してホスフィンに送り付けたところ、微妙にはみ出しているのはフォントサイズを変更することで対処できる、という指摘を受けた。それはそうすぎる。

夜、別のラノベを読んでいた。非常に良いシチュエーションがあった。

途中で眠気に耐えかね就寝。午前4時だった。

05/13(木)

午前11時起床。起きた瞬間感覚的に寝坊を感じ取ったので非常に焦っていたが、時計を見れば全然そんなことはなかった。学食に行く。

「個数制限なしナップサック問題の解」と言われた。確かに、胃袋をナップサックと思えば、僕の満足度を最大化できている。平常時はご飯（特大）を注文していたが、今日は提供されないらしかったので、迷った挙句ご飯（大）とご飯（中）を購入した。ちょっと多かったので、次回は中サイズを2つ注文することにしよう。

家に帰ってTwitter Web Appを開いたら、autocompleteが暴発してキーワード検索の欄に自分のメアドが入力されるようになってしまっていた。Chromeを再起動すると直ると聞いたが直らず。設定から手動でChromeの更新を行うと修正されたが、まだDMのあたりで暴発しているように見える。

午後1時、ゼミが始まる。また今週もゼータ関数の教科書は手に入れられていない。今日の内容としては、先週証明したゴツい公式をこねこねして解析接続を行うらしい。正直ゼミ後でもあんまりよくわかっていない。というかそれはそうで、途中で今日の典型90問のコードゴルフを始めていてはわかるものもわからなくなるだろう。資料を見直してキャッチアップしていきたい。

その後、僕が使っているほうの教科書の発表に移る。まず先週の残りがあるため、それが発表された。今日はそれだけで1時間くらいかかった。その後僕の出番が来た。30分くらいだと予想して、なんとかオタク早口を駆使してキリのよいところまで進めた。内容的にはそう……というものしかやっていないので、あんまり質問も来ないし、突っ込みもなかった。今日は15ページまで発表して、残り19ページあるので、来週は僕が残りを発表するためまた次の人がずれていく……。もうそろそろ1周すると思うが、このずれは初回にどのような感じかわからないまま1人が大量に担当してしまったためなので、担当範囲については気を付けたい。

僕が作ったスライドは以下に公開しておこう。読んでいる本は「Introduction to Analytic Number Theory (Apostol)」だ。

Apostol_Chapter2_2.8-2.11.pdf - Google ドライブ

終わってからラノベを読んだ。「隣のクーデレラを甘やかしたら、ウチの合鍵を渡すことになった」2巻。良かった。あとがきによれば、1巻で知り合って、2巻で仲を深めて、3巻で合鍵を渡すという構成だったらしく、無事に2巻が出るどころかすでに3巻まで決定しているのは安心感がある。

夜、サークルのバチャに出た。#522 div.1。4完して非常に良い出来。

Dashboard - Codeforces Round #522 (Div. 1, based on Technocup 2019 Elimination Round 3) - Codeforces

Aは、まず直接向かう場合を試して、そのあとスタートから縦または横に進んで直線に乗り、どこかで降りて縦または横に進んでゴールにたどり着く、というのを2x2通り調べればよい……はずだった。直接向かう場合の計算でオーバーフローして1WA。

Bも難しい。同じ重さのものだけ抜き出す必要があって、抜き出し方の通り数をdpで計算する。ところが、全体で重さが2種類しかない場合は、片方の重さを全部抜き出すことでもう片方も判別できるようになる、というケースが存在する。これに気付くのはかなり難しかった。

Cも難しいと思ったが、それっぽいことを書いたら通った。木なので端から詰めると最大マッチングが達成されるらしく、このとき頂点が「マッチングで使われた」、「マッチングで使われていない」、「その1頂点のみ孤立している」の3状態に分けられて、木dpできる。1頂点が孤立している場合は、素直に考えると「マッチングで使われていない」に該当しそうなものだが、1頂点だけ切り離すことが可能なため、このように分けて考える必要があった。

Dは基本的にはダブリングで、各階層でテーブルをセグメント木に乗せておく。円環における区間の端の扱いに気を使って実装したが、45ケース目でWAした。最大値の単位元が大きすぎるのでは？とか、以降探索しなくてよいと示すためのヤケクソな値が小さかったのでは？とか考えていたが同じケースでWA。結局ランダムケースを生成して試すことになったが、WAの原因はN=1の時だけ答えが0にならなければならないというものだった。正直愚直解の実装を少しでも違ったものにしていたら検出できなかったのではないかと思う。まあ通せたのでセーフ。

Eは時間を巻き戻すという機能を持つesolangで足し算を行う問題だった。まず2数の桁がそろっていないのがヤバそう。

夜、ラノベを読みながら眠気に負けそうになっていたら、Rubyで新手が出た。splitはブロックを取れるらしい。

atcoder.jp

日記を書いてすぐ就寝。午前5時だった。

05/14(金)

午後5時起床。12時間睡眠でいい感じ。

今日の典型が解けない。布団にうずくまって考えていたが、埒が明かないので学食に行った。夜の部はあまり行かないので混雑状況が読めなかったが、午後6時はかなり混む時間らしい。

帰ってきてまたずっと考えていたが、さらに1時間くらい経ってようやく解けた。燃やす埋めるであることに気づくのにこれだけかかったということ。コードゴルフはC++でACLを使うくらいしかできることはないと思っていたけど、普通にNetworkXでよい。そもそもC++で書いている段階で辺の張り方がよくなかったらしい。鍵を開けるのにW円かかり中でA_i円得られる、というのを+A_i-Wと一本の式にして考えており、この場合負のペナルティを表現するために先に足しておいてから引くことになるが、実際は先にA_iの総和を求めておいて、鍵を開けるなら-W円、開けないなら-A_i円というふうに書ける。これで結構縮んだ。

NetworkXのグラフの頂点はかなり無茶苦茶できる。今回は使わなかったが、sourceとsinkを表現するのは0とN+1でなくてもよくて、例えば-1とかG.add_edgeが使える。何回も呼び出す関数を変数に入れることで縮めるテクの副次的な効果。また、今回は使わなかったが、NetworkXのクソ長関数名を使う代わりにeval(dir()[])を使うテクニックを思い出した。

ラノベを1冊読んだ。「辺境都市の育成者」3巻。設定が非常に良い。「弟子がたくさんいて、皆大変に偉くなったが、まだ師匠を慕っている」というのも僕の好みの1つらしい。他にも同様の設定のなろうはいろいろあると思う。一点気になることがあって、これはこの作者の作品を読むたびに触れている気がするが、ひたすらセリフが読みにくい。「Aについて喋る。Bについて喋る。」「Aについて答える。Bについて答える。」というのはテキストによるコミュニケーションでありがちだが、これをセリフで一生やっているのは何とかしてほしいところ。

作品同士であまり関係はないが、同作者の「公女殿下の家庭教師」とは世界を共有している（ただし年代は全く異なる）ようだ。今巻ラストでは、「公女殿下」のほうで最近出てきたキャラと同じ姓の人が出てきてオッとなった。

2021/04/22に参加したバチャのupsolveを1つ進めた。

Cは二部グラフのように塗ってみてダメなところを少し修正するもWA。

週記（2021/04/19-2021/04/25） - kotatsugameの日記

https://codeforces.com/contest/1019/problem/C

解説を見てあーあとなるタイプの構築問題。今日書こうとしたら、解法だけ覚えていて問題を全く覚えていなかったため、有向グラフなのに双方向に辺を張っていた。この回のD問題は解説自体もかなり難しかったが、理解は済ませている。残りは書くだけなので、そのうちupsolveしたい。

yukicoder contest 295に出た。5完。

yukicoder contest 295 - yukicoder

Aはよい。BはA=1の点が重要。Cは余事象を考える。ここまでは一瞬で解けた。Dは、後ろから見て「ここにいたらマズい」という範囲を管理した。移動前にここにいたらマズいのか移動後にここにいたらマズいのかを取り違えていたらしく、4WA。

Eはいつもの偶置換・奇置換かと思ったが、ちょっと計算すると全部奇置換だとわかる。A<=Bとすると、まずmod Aが等しいインデックスの順序は自由にできて、このA個の自由に入れ替え可能なブロックをBで繋げるかという話になる。gcd(A,B)==1はよいとして、すべてのブロックから別のブロックに辺が生えていればよいと考え、1..N-BとB+1..Nにすべてのブロックが含まれるかを見たが、WA。左と右のブロックで同一の組を繋いでいるとまずいのかと考えるも、A<=N-Bだと例えば4 2 3や6 3 4でWAになるので、ではA+1<=N-Bではどうかと投げてみると通った。繋げるということを考えると、グラフの連結性の話になって、辺がA-1本以上ないといけないというのがわかるらしい。ひたすらWAを生やしまくった。8WA。

Fはダメ。WolframAlphaでエスパーしようとしたが、Aがdistinctでない場合にゼロ除算が発生する。通分することでゼロになる項が消せるらしかったが、計算不可能だった。どうやら留数定理でも解けるらしい。試してみたが、微分するパートがわからなかった。

もう1冊ラノベを読んだ。「両親の借金を肩代わりしてもらう条件は日本一可愛い女子高生と一緒に暮らすことでした。」2巻。あんまり合わなかった。1巻読了時点では文章が合わないということを書いていたが、今回はさらにストーリーにも合わなさを感じた。どうやら性的なスキンシップを伴う恋愛ものがダメらしい、と言葉で書いてはみるが、正直自分でもよくわかっていない。なぜこのラノベのお色気シーンは受け付けなくて、「お隣の天使様にいつの間にか駄目人間にされてしまった件」のそれはオールOKなのか。

題名・あらすじ・イラストに惹かれて買った。「ラノベのプロ！」によれば、これはラノベのパッケージングが僕に刺さったということ。ただ文章がどうにも合わなかった。

週記（2020/12/21-2020/12/27） - kotatsugameの日記

日記を書き、布団に入って少しなろうを読んで寝た。午前7時半だった。

05/15(土)

午後3時起床。

今日はGW明けて初めての生協の弁当配達の日なので、起きておく必要がある。普段は生活リズムが完全にぶっ壊れていて、弁当を受け取ったら即座に二度寝するような体制で配達を待っていたが、今日はいい感じなので普通に起きていることにした。

弁当を受け取りつつ、午後6時までコードゴルフをしていた。最近更新が活発で10個以上取られている。勝てない。信じられないことに自分のモチベーションがあまりないらしく、古いコードを探して縮められているのを目にしながら、自分もそれをしようという気にならない。

今日の典型90問を解く。格子点だけを整数で扱う幾何ライブラリを整備していて、凸包も貼るだけ。あとはピックの定理で適当にやる。典型だなあという感じ。コードゴルフはRubyのComplexで、climpetさんに負けていたが何とか追いつき、変なことをして1Bだけ抜いた。

ABC201に出た。全完2WAで26位。適当にやりすぎ。

Mynavi Programming Contest 2021（AtCoder Beginner Contest 201） - AtCoder

Aはコードゴルフがどうなるかわからないので、Rakuで適当に書いた。FA。BはBashだと思ったが、挙動がよく分かっておらず2WA。そのあとしばらく時間を使ってVimで縮めていたが、結局負けている。Cはoと?の個数をカウントしてどうにかするのかと思っていたが、冷静になると暗証番号のほうを全探索できる。Dは適当にDP。Eは、パスのxorが親とのxorから計算できることも、数列から2つ選んだxorの総和を計算するのも、それぞれ既出。組み合わせるだけ。Fは番号の小さいほうから何人かが左端に移動し、番号の大きいほうから何人かが右端に移動すると考えてよい。どちらかの人数を全探索して、もう一方をデータ構造で持つ。適当に書いてみるとRange AddとRange Minができればよいことが分かったので、遅延セグメント木を使う。

コードゴルフ。Aは3つの数の中にsum(A)/3が存在することを見るという解法がすごい。Bはなぜかd}が頭からすっぽり抜けており、負け。この2つは取れなくてかなり悔しさを感じる。CはRuby 73B、Perl 72B。よくわからない。DとEは適当にRubyで書いておいた。Fは僕のコンテスト中のC++が現状最短。

そのあとすぐGCJ2021 R2に出た。全完103位。Tシャツを得た。

Code Jam - Google’s Coding Competitions

Aは、単純に[1,N]、[2,N]、……を順に聞いて最小値を先頭に持ってくることが思い浮かぶ。さすがにこんな簡単なわけないだろ……と思いつつ試しに計算してみたが、どうやらこれでよいらしい。訝りながら出したら通った。Bは一番内側の多角形の辺数を全探索する。これが例えばkだったとすると、Nについて問題を解くのが(N-k)/kについて問題を解くことに落とし込まれるので、再帰的に解ける。実装して大き目のケースを試してみると爆速だったので提出、AC。

Cは難しく感じたが、頑張ったら解けた。stackを使ってシミュレートすることで、パンケーキの大小関係をグラフにできる。このグラフのトポロジカルソートを数え上げたい。一般のグラフでは難しいらしいので、グラフに何か良い性質があるのだろうと思ってじっくり睨んでみると、「すべての頂点の入次数が高々1」であることがわかる。合流しない、と言い換えてもよい。この場合は各頂点についてその子らをマージする通り数を二項係数で数えれば解ける。ほかにも「出次数が高々2」というのもわかるが、解法には関係ない。

最大のパンケーキを固定して分割する方法でも同様の解法になるが、そちらのほうが見通しがよさそうだった。

kkt89.hatenablog.com

dは、隣り合うマスをswapする以外は1点flipで済むので、どのペアをswapするかで二部マッチング。Dもフローで考えることにする。swapが連鎖するのが怖いが、ちょっと計算してみると、まずswapするペアは必ず「どちらも色を変える必要があること」「ペアの最終的な色が異なること」の2点を満たす必要があり、このときうまくswapをつなげることで(x,y)と(z,w)だけを|x-z|+|y-w|回のswapで入れ替えられることがわかる。例えばGGMMGGMMの両端を入れ替えようとすると、GGMMGMGM→GGMMGMMG→GGMMMGMG→GMGMMGMG→GMMGMGMG→GMMMGGMG→MGMMGGMGと7回でできる。書き並べるとわかりにくいが、Gが右に動くのとMが左に動くのを繰り返すことでうまくほかの位置を変えないようにしている。

さて、ここまでできればあとは辺を張って最小重みマッチングをすればよい。いろいろググってハンガリアン法などを見ていたが、最大マッチングである必要はないので使えない。流量を変えつつ何回も最小費用流をしたくなるが、これは実はACLのslopeという関数を使えばよい。

今年のGCJ R3進出ボーダーはABC3完だったようだ。CもDもかなりがっつり考察することになって、難しい問題だと感じたから、ボーダーはかなり高めに見える。年に一度古強者が集まるGCJと、普段のコンテストとでは、かなり感覚が違うのだろう。

日記を書いてから布団に向かったが、ふと思い立ってラノベを1冊読んだ。「株では勝てる俺も、カワイイ女子高生には勝てない。」という作品。あまり面白くなかった。株とかでお金持ちになる話は好きだが、この小説ではすでにデイトレードで成功した主人公がヒロインと関わって「人間らしさ」を得ようとする話で、実際の取引は（描写こそあるものの）本筋ではない。そのことはタイトルからも想像がついていて、まあそれならそれで良いのだが、話の本筋にもあまり身が入らなかった。主人公の人間味のなさというのが、すべてをお金で解決しようとすることで描かれていて、あまり受け入れられなかった。

もう1冊ラノベを開いたが、100ページくらいで眠気に負けた。午前8時就寝。

05/16(日)

午後4時起床。二度寝しようと思ってはいたが、布団でなろうを読んでいるうちにARCまで2時間を切ったので、そのまま起きていることになった。そこからコンテスト開始まではコードゴルフをしていた。

atcoder.jp

(0..59).sumのかっこを削るため、dfs関数の最後で0..59をreturnして使っている。これは僕の知る限りでは新手で、そこそこ適用範囲が広そうだったが、探しても縮むものは見つけられなかった。この問題自体も後にさらに縮められている。

ARC119に出た。5完30位でパフォーマンス2933、レートは2717→2741(+24)でhighestを更新した。

AtCoder Regular Contest 119 - AtCoder

Aはよい。Bはかなり迷走して20分かけた。最初は左から貪欲だと思ったが、これは全然違う。1の塊を丸ごと1マス横にずらすのが1手で行えて、その塊のイメージで考えていたが、何も得られなかった。頭を切り替えようとして順位表を見るとかなり通されておりビビるが、戻ってきてすぐ1と1の組を無視することを思いついた。すると隣接swapだけでそろえる問題になる……と思って実装したがサンプルが合わない。実際には、間にはめ込んだ1を乗り越えて進むのも1手でできるので、その分手数が少なくなる。結局、左から見て、Sにある1の塊とTにある1の塊のどちらかを管理しながら進めていくようにした。1発で通ったのだけはよかった。

Cは、区間の左右を0としたときに階差を1個飛ばしで足し合わせた値2つがどちらも0になることが条件。インデックスの偶奇で分けて先頭からの和を持ち、端の補正をしつつmapでカウントすればよい。これが見えるのは一瞬だが、実装で偶奇に神経をとがらせる必要があってつらかった。解説はかなりシンプルで、階差をとる必要がなかったのかと愕然。

Dは典型考察として、縦H個と横W個の頂点を作り、グリッドの点は頂点間の辺に変換することで2部グラフを作る、という方針が思い浮かぶ。問題設定をグラフに落とし込んでみると、連結成分ごとにある頂点を選んで、それ以外をすべて消すという操作ができ、最後に縦と横で残った頂点の個数の積を最小化することになる。辺を1本以上含むような連結成分だけ考えれば、縦と横どちらの頂点を残すかはどの連結成分でも自由なので、貪欲に決定することができる。復元もdfsで可能。辺を含まない連結成分も考えていたこと、ABを最小化するときはmin(A,B)を最小化しなければならないのに、逆に最大化してしまったことで2WA。

Eは最近こどふぉで見た気がする。しばらく時間を使って週記から該当する記述を探したが、当時の考察は結局意味をなさなかった。

https://codeforces.com/contest/1513/problem/F

Fはつらい。差分を計算する。

週記（2021/04/05-2021/04/11） - kotatsugameの日記

当時大苦戦したことを覚えていた。45分程度で正確に実装しきれる方針を選ぶ必要がある。どうやら当時は値でソートすることでうまくデータ構造を使ったようだが、今回は区間の両端という位置関係が重要なので、ソートはできない（後から知ったことだが、実はこれは大間違いだった）。A_r\le A_{r+1}なるrに対して、l\le rかつA_{l-1}\le A_lかつA_{l-1}\le A_rとなるようなA_lの最大値を求めるセグメント木と、l\le rかつA_{l-1}\le A_lかつA_l\ge A_{r+1}となるようなA_{l-1}の最小値を求めるセグメント木を書き、列の符号反転やreverseを4通り試して必ず2つのうちどちらかで差分が拾えるようにして解いた。これは、当時の日記における簡単だったほうのケースを無理やり拡張して難しいケースを解いたということ。

Eを通したら残り10分しかなく、Fがほとんど通されていなかったので、あきらめてA問題のコードゴルフをしていた。

Eの解説を読んで知ったが、iとi+1の大小関係が等しいlとrを選んだとき、l\lt rだろうがl\gt rだろうが同様に扱って計算した差分が達成可能であるようだ。コンテスト中はl \le rとなるように選んでいたが、その条件がなくなると話はさらに簡単になり、区間のオーバーラップを計算するだけなのでセグメント木も必要なかったらしい。というかこどふぉの解説でも同じことが書かれていた。コンテスト中は英語を読むのを嫌がってすぐページを閉じてしまったが、なんともったいないことをしたのか。

コンテストとしては、DもEも順当に解けたなあという印象。思ったより通されておらずびっくりした。B問題でかなり詰まってしまったが、パニックにならなかったのは良かった。

コードゴルフ。Aはループ条件をNの値に応じて決める必要がなく、一律で100回くらい回してよいことに気づかずに取られた。そこから6時間くらい試行錯誤して1B短縮できたのだが、よく見るとただのテストケースハックだった。b=1となるようなケースが入っていないらしく、例えばN=6で落ちる。ただテストケースハックしているだけなので、わざわざ方針を変えたのは長くなっているだけであり、もともとの最短コードを書き直すとさらに-2Bした。

BはPerl。char s:Sとchar t:Tを同時に見ていったとき、s-tの累積和をcとすると、s==0&&(t==1||c!=0)なる点の個数を答えればよい。$/=\1とすると1文字ずつ読めることを使って解いていたが、getcを使うほうが短いことに気づいて冷や汗が出た。CはAWK。