週記(2021/07/12-2021/07/18)

07/12(月)

先週の日曜日、週記を投稿してからの話。橙diffを1問開いて考えていたが、かなり面倒そう。目を瞑って細かい部分を考えていたら寝そうになったので、すぐ布団に移動した。午前8時就寝。

午後2時前に目を覚ます。二度寝しようと思いつつ布団でなろうを読んでいたが、今日も寝るのに失敗した。午後5時にあきらめて布団から出た。

atgolferを確認する。昨日90問追加されたにもかかわらずあまり更新が流れてきていなかった。1問、Crystalが縮んでいたが、これはto_i64to_fに変えたものだった。確かにそうだ。Crystalの/演算子は結果を浮動小数点数で返すので、オペランドを整数にしておく必要はない。あんまり意識していなかった。これでほかのCrystalコードが縮まないかと少し試してみたが、縮まなかった。

しばらく他の人の日記を読んでから、大学院の入試について調べ始めた。確か出願が今週いっぱいだったはずだ。まだ何も用意していない。募集要項や出願書類自体はインターネットでダウンロードできるようだが、教務課で紙の冊子を配布しているそうなので、念のためもらっておきたい気持ちがある。また出願書類が家のプリンターで印刷したペラペラのコピー用紙というのも格好がつかないだろうという考えもある。明日はこれをもらい、ほかにも家の外で行うべき様々なことをする日にしたい。

午後7時くらいになって学食の夜の部に行った。今日はソースカツ丼とカレーを注文。1つだと確実に足りないので、まだ今日1食も食べていないことを鑑み、2食ぶんの購入に踏み切った。結果から言えばこれは正解だった。何とか満腹中枢が刺激される前に食事を完了できた。

家に帰ってちょっとYouTubeを眺めていた。ヒカキンが一人焼肉をする動画がおすすめされたのでしばらく観ていたが、焼けた肉を網の上から取るのにちゃんと箸を使っていて感動した。僕はこれを怠った結果、夜中に腹痛で救急車を呼んだのだった。

www.youtube.com

生肉を網に移したのと同じトングで焼けた肉を皿に移すのもいけない

日記(2020/11/06)あるいは僕が深夜に救急車を呼んだ話 - kotatsugameの日記

YouTubeを見るのはそこそこで切り上げたが、そのあともTwitterのTLをボーっと眺め続けるなど、意味のある行動をできていない。とりあえず風呂に入って、橙diffを1問通した。これは昨日寝る前に考えていたものとは別の問題。

Submission #24185848 - AtCoder Regular Contest 065

考察は簡単。実装にあたって、区間に包含関係がないように整理するのが面倒だなと思ったが、上手い実装方針を選べた。これまで出現した区間の右端の最大値を持っておいて、毎回インクリメントできればしていくというのが、その区間内の文字種類を見るのも含めて上手く書けたと思う。

その後しばらくこの問題のコードゴルフをしていた。最初はRubyで書いていたが、特に速度面で問題があるわけでもなし、Perlに書き直したらグッと縮んだ。未初期化の変数だったり配列外参照をしたら0が得られるのがうれしいところ。

もう1問橙diffを開いて考えていたが、急激に信じられないほどの眠気に襲われた。洗濯機を回している最中だったが、これは耐えられないと思い、素直に布団に移動して就寝。午前0時だった。早寝。

07/13(火)

午前11時に起床。途中何回か目を覚ましたような気もするが、この時間まで寝ることができた。とりあえず洗濯物を干し、ゴミをまとめて出した。

ちょっとだけ院試の問題を見たりTwitterをしていたら午後1時を回った。昼の部が終わる前に学食に行こうと思ったが、昨日開いた橙diffが解けたので、コードを書くことにした。昼食は家で摂る。

Submission #24195772 - AtCoder Regular Contest 072

結構悩んでいた。変更前はよいとして、変更後が問題。変更したところでは、目的地に近づくなら任意の位置に進めるので、そのあとの入力でゴールできないような最も近い点の座標が分かればよい。実はこれは後ろから計算できる、ということに気づくのが本質。d_i=1なる最大のiについて、その入力以降でゴールできないような最も近い点の座標は2であると言いたいが、d_j=2なるj\gt iがあったらそれでゴールできてしまうのでは?と思っていた。実際は、i2から1に動いてしまうので、jの入力でもゴールできない。

ゴールできない点を計算する式は頭で考えたものが間違っており、サンプルが合わなくて困惑したが、紙に書いたら分かった。

食事してシャワーを浴び、久しぶりに原付に乗って山のキャンパスに向かう。昨日の予定通り、出願書類などをもらいに行く。僕が原付に乗っていたのは主に2019年の後期だったから、原付といえば吹き付ける風の寒さに震えている印象しかなかったが、夏の原付は風が涼しくて非常に気持ちがよい。微妙に曇っていて日光が強くないのもよかった。

教務課で院試の募集要項をもらう。次に数学科の資料室でゼミの教科書をコピーする。同じゼミの人々が大量にコピーするので教授に話が行き、コピー済みの資料が何部か配布されることになったという話は聞いていたが、1か月以上前のことであるからもう置いてないだろうと思って、コピーの申込書を書いていた。すると資料室の職員に「資料が配布された場所を確認しましたか?」「配布されたものの余りがないか教授に確認できないんですか?」「なんでその時取りに来なかったんですか?」など激詰めされ、困惑。資料を受け取れなかったのは完全に僕が悪いのだが、コピーの申込書を提出してからも何か言われたので、もう許してくれという気持ちになった。

山を下りて川内キャンパスに原付を停め、徒歩で地下鉄の駅まで行って、駅前の証明写真機で願書用の写真を撮る。このためだけに、Tシャツの上に羽織る襟付きの衣服を持ってきた。証明写真機の写真を撮ってTwitterに上げたところ、くっついている鏡に僕の姿が映りこんでいることを指摘されてびっくり。慌てて確認したが、顔の前にスマホを構えていたのでギリギリセーフ、か?

写真を撮って、今度は郵便局に行く。入試の検定料を振り込み、書類を提出する封筒を買う。すでに願書を出しに来ている人が結構いてビビり散らかした。検定料の振り込みは、後で書類に貼り付けるためにATMの利用明細票をちゃんと持っておかなければならないが、ペラペラの紙1枚に3万円を保証されるのかとわびしい気持ちになった。

購買で買い物をして帰宅。ちゃんと必要なものはすべて買い集めることができたと思う。あとは書類を作成して、郵便局で出すだけ。とりあえず調査票以外の何も考えずに書ける書類を作成した。大学受験の願書を書いていた時のこと、また当時どんな気持ちだったかなどを思い出してかなり気分が落ち込んだ。正直トラウマである。人はトラウマを増やしながら生きていく。

残すは調査票のみとなった。何を書いたものか全然わからないので、いったん後回しにして、午後8時からのSRM809に出た。EMの2完で18位、レートは2538→2535(-3)。ちょっと前までずっと上がり調子だったはずだが、いつの間にかこの順位でも下がるようになってしまったとは驚き。

Easyは昔のARCで見たことがある。解法も覚えていたので、それを再現するだけだった。

A - 掲示板

Medは3^NのDPを書いた。最大ケースで2secを超えてしまいびっくりしたが、__builtin_popcountをメモしておいたら1secを切るようになって助かった。実は2^Nにいくつかくっついた感じで解けてしまうらしい。Challengeフェーズの終わり際に一気に僕を含む3人に対して失敗している人がいたが、おそらく3^Nが落ちないかイチかバチかで試したのだろう。

昼に解いた橙diffのコードゴルフをした。Perl。入力が5\times10^5\times 2くらいあるので、いくら線形時間でも厳しいか……と思っていたが、なんとC++より速かった。一応endlではなく"\n"を使ったのだが、そもそもcin/coutが遅かったのだろうか。

TCO21のRegional Eventsへの招待メールが来たのでGoogleフォームを入力して参加登録しておいた。いつもはMサイズで出しているコンテストTシャツだが、毎回毎回着丈が長くてケツまでかかっているので、今回はSサイズで出してみた。もし変なサイズが来たところで、1回くらい構わんだろう。

もう1問橙diffを解いた。

Submission #24207952 - AtCoder Grand Contest 015

普通bitの問題といえば上のbitから場合分けすることが多いように思うが、この問題では下のbitで場合分けすることでうまく解くことができた。最下位bitを立てたい場合で、区間の右端の数が偶数の場合にちょっと場合分けが発生する。具体的には、区間の右端の数(を2で割ったもの)がそれ以外の数(を2で割ったもの)のORで作れない場合だけ答えが1減る。ORで作れない場合でも、それ以外の数と一緒にORを取った数についてはちゃんと最下位bitを立てることができる。

ところが、解説を読んだら上のbitで場合分けをしていた。上のbit「から」ではないこともポイントで、なんと場合分けは3通りにしかならないらしい。これで900点か……。最短コードもこの方針だった。試しに僕の方針でも書こうとしてみたが、明らかに想定解のほうが短い。粗があったのでちょっと縮めておいた。

改めて願書の調査票を書く。とりあえずコピーを取って、シャーペンで下書きのように書いてみる。計算機数学で出そうとしているが、ふと調査票の記入例に「理論計算機科学」というものがあることに気づく。Wikipediaで調べてみた限りだと、アルゴリズム論とかを指す言葉であるようで、これはかなり競プロに近いのではないだろうか。この方面で攻めてみたい。

表面は希望を少し書くだけで埋まるが、裏面の「興味がある数学の問題」と「進学後の抱負」はかなり悩みどころ。表面との関連を考えできるだけ競プロに近いことで埋めようとしているが、「なぜ工学部の院に出願しなかったのですか?」など聞かれると困る。英語の試験を受けていないからです……。ウチとは違うんじゃないの、と言って落とされるかもしれないのも怖いところである。

全然書きあがらないので、日記を書いて布団に入り、すぐ寝た。午前3時半だった。

07/14(水)

午前9時くらいに目を覚ましてしまう。すぐ二度寝しようと思ったのだが、うっかりスマホを触り始めてしまい、眠気が吹っ飛んでしまった。

そういえば、昨日のSRMでbit DPを書いたわけだが、1<<N-1とかk-1&rとかの記述に警告が出て、それを消すのに非常に苦労していた。このくらいの優先順位はわかって書いているので、むしろ謎の基準で警告を出されているように感じられ、どこを注意されているのかわからないため。と、このようなツイートをしたら、実は警告を消さなくても(Appletなら)コンパイルされて、提出もできるということを知った。知らなかった……。コンパイルエラーが出るのと同じような感じで表示されるとビビる。

昼過ぎ、学食に行った。本当はこの時間までに調査票を書き上げて、願書の発送まで済ませるつもりだったが、二度寝に失敗し続けていたので昨日から1文字も進んでいない。学食ではつけ麺を頼んだ。つけ汁に黒胡椒が効いていておいしい。最近見なかったメニューだが、タイミングが悪かっただけだろうか。

購買で買い物をしている間に数学科の同級生と会い、少し話した。やはり院試のことが話題に上がるが、そんなに不安視はしていないようで、お互い頑張りましょうという感じで別れた。この会話によって僕もそこそこ元気が湧いてきた。昨日までは調査票と、それをもとに質問されるだろう面接について悩んでウジウジしていたが、どうせ面接は10分程度のことだし試験ができていれば問題ない、という気持ちになった。調査票で悩むのはそこそこに留めておくべきだ。

家に帰ってきて、朝方メールが届いていた東北大学のワクチンを予約した。とにかくAtCoderのコンテストに被らないように、と月曜日を選ぶことだけを意識していたら、うっかり院試の直前に2回目の接種が予定されそうになって焦った。1週間遅らせることで対処。2回目の接種は院試後になる予定だ。ワクチン接種券というのが何を指すかよくわからなかったが、住民票を移していないのでどうやら富山の実家に届きそう。

最近本屋に行けていないし、これから先もしばらく行く予定はないので、大学生協で新刊ラノベなどを注文しておくことにした。17冊で14000円弱。生協の割引で1000円以上浮くはずだ。

調査票が1文字も進まない。うっかりYouTubeニコニコ動画スマブラ淫夢実況を見始めてしまった。動画を見るのを切り上げることができた後も、書く内容が決まらずうだうだしていた。ホスフィンからの情報によれば今セメスターで開講されている計算機数学Bではラムダ計算をやっているらしい。ちょっとClassroomにお邪魔して資料を見るくらいなら許されるようなので、見てみたりもしたが、本当にチラッと眺めた程度で参考になるわけもなく。

しかし昼間にもあんまり悩むべきではないという結論に至ったのだから、もうそろそろ本当に覚悟を決めねばならない。決意したらそこそこスルッと書きあがった。悩んでいたのは、主に「興味がある数学の問題」に何のアルゴリズムを書くかということであり、「進学後の抱負」は競プロの話をしていたら終わった。一応面接対策として書いた内容を写真に収めておく。

そのあと、封筒に宛名を書いたり書類をまとめて入れたりして、ついに願書が完成。郵便局で封筒を買ったときに貰っていた速達簡易書留の申込書も記入して、あとはこれを郵便局に持っていくだけとなった。結局今日の日中はすべて潰れてしまったが、完成することが第一。これが午後11時くらいのことで、30分後からECR111に出た。

Dashboard - Educational Codeforces Round 111 (Rated for Div. 2) - Codeforces

コンテスト終了時点では全完12位。

Aはできるだけ値を大きくしていきながら総和を求めて、ギリギリ超える場所を探す。Bはbの値だけ気にすればよくて、1文字ずつ分解するか同じ文字をできるだけまとめるかの2通り考えればよい。

Cから難しい。a_iについてa_j\le a_iなる最大のja_k\le a_j\le a_iなる(k,j)が存在するか、またこの2つの不等号を逆向きにしたものについても判定しつつ尺取り法をする。前者はセグメント木、後者はBITで、kを削除するときにjから1引くような実装で実現可能。実際には両方セグメント木で書いた。

Dは信じられないくらい難しい。a_i-iを考える。これを何らかのkについて\pm kにそろえることになるので、kとしてありうる値の数と符号の割り振り方を数える。負にする最小のインデックスと正にする最大のインデックスを固定して立式すると、2項係数と最小値関数の積になる。適当に場合分けして最小値関数を消し、負にする最小のインデックスのほうを変数xとしてみると、\binom{N-x}{M-x}x\binom{N-x}{M-x}の和の形になる。これをWolframAlphaに投げると閉じた式になってくれたので、あとは正にする最大のインデックスを全通り試す。いちいちnの偶奇で場合分けしていてかなりヤバいコードになったが、すぐサンプルが合ってくれた。

Eは二分探索。判定については、先に達成可能なインデックスを求めておいて、巡回セールスマン問題のようにbitDPっぽくdijkstraをする。よく考えたらbitDPのままでよかった。

Fも二分探索。今度は並列二分探索をした。辺を全通り張っているとどう考えても間に合わないので、いくらか絞る必要がある。これについては、自分の左右の頂点から辺を張るよりも短くできるような辺(これは区間になる)と、その左右1個ずつを見ておけば通った。

コンテスト後のTLで他の解法をいろいろ見ていた。A問題は交差2の等差数列になるが、これの先頭からの和はある平方数になる。よって答えは\left\lceil\sqrt s\right\rceilになるらしい。Cは、実は長さ5以上の列が必ず条件を満たさないということが確認できるので、毎回愚直にチェックしながら尺取りしても間に合う。DはLaycrsさんの解法がシンプル。kとしてありうる値を座圧するという話もあって、腑に落ちた。

Rubyコードゴルフで新手が出た。入力の1行目を読み飛ばし、2行目以降にmapを適用するようなコードは、injectで代替できる。適用できるものを探して縮めておいた。

atcoder.jp

午前4時就寝。明日は早く起きてゼミの前に郵便局に行かなきゃな、と思っていたが、寝る直前になって明日のゼミが休みだったことを思い出し、心地よく眠ることができた。

07/15(木)

午後0時半起床。昨日縮めたコードのうち1つに粗があって縮められていた。ブロックの最後で評価した値をそのまま返せることは、先に掲出した提出でも利用されているが、見落としていた。悔しいのでしばらく考えていたら縮んだが、代わりに学食の昼の部が閉まってしまった。

昨日のECR111はopen hackingフェーズも終了し、まだ落ちていないようだ。この後hackケースを追加してシステスがあるのかとも思ったが、よくわからない。

郵便局に行って願書を発送し、購買でパンなどを買って帰ってきた。家で食事し、荷物を整理してゲーセンに向かう。

今日も午後3時から夕食を挟んで午後11時半までみっちりプレイした。チュウニズムデュエルが1日で終わってしまった(ところでキャラのイメージとCV:釘宮理恵がミスマッチすぎる)。5月頭にホームにしていたゲーセンが潰れてしまったため、今通っているゲーセンは微妙に遠くなったのだが、そのせいでせっかく一度行ったのなら目いっぱいプレイするべきだという認識になってしまい、毎回閉店までプレイし続けている。

今日の成果は上々。13+のSSSが1つ、13のAJが6つ増えた。

先々週頑張っていたもの。

Halcyonをプレイしていたのだが、3時間くらい連奏しても出ずに閉店時間となってしまった。

週記(2021/06/28-2021/07/04) - kotatsugameの日記

先々週の週記ではツイートを引用してタップスライド(25、90小節)について触れているが、その部分は確かに一度手を離してちゃんと擦ることで驚くほど通るようになった。今日の最初のほうは、週記の記述を完全に忘れて親指やら人差し指で擦ろうとしていたが、大きな間違いだった。

あとはラスト、特に105小節の右手拘束交互も先々週非常に苦労していたところ。ここについては、意識的にスライダーに顔を近づけて判定線と手元を睨みつけるようにしたらかなり安定した。結局、先々週の時点でこれら合計3か所が通るかどうかというところまで持っていけていたので、安定してしまえばAJはすぐ出た。

今日3回で出た。意味不明。何もかもが上手くいった。ほとんどの部分は見たまま押していた(これができるようになっていたことが成長)が、これまでのプレイ経験から意識していたことや運指は一応ある。

17、25小節にある速い交互は擦る。これはリズムが良く分かっていないから、また緩急の差に対応できないからで、それ以外にもこの速度(32分)の交互は擦っているが、あとのほうに出てくる24分はある日急にできるようになったので押している。

48小節は前まで右手のリズムを意識していたが、それは直前2小節とまったく変わらないのだからむしろ左手を意識するべきだと考えてやってみたところ、上手くいった。

f:id:kotatsugame:20210717054156p:plain
97小節

逆餡蜜という話は聞いていたが、そのまま階段として押そうとして、結果ここで大量に出してしまっていた。逆餡蜜と見て擦るのが正解、のはずだが、そもそもこの運指を試した一回目でうまくいってSSS達成してしまったので、まぐれ当たりの可能性を否定できない。

これで解禁済み13+の未鳥は4譜面、パッソ・ハーレ・神威・大鳥居。全部定数13.9だ。13.8以下は全鳥ということになる。

帰宅してシャワーを浴びたら日付が変わっていた。酷使した腕が痛むが、そもそもここまで長時間プレイし続けられているのも成長で、自分の脱力意識はある程度の成果を見せているはず。

数理統計学の講義資料を3回分くらい読んだ。正直あんまりよくわかっていないが、式変形は追ったつもりなので講義資料はこれで完走できたとしてよいことにしよう。期末課題が出ていて、期限ももうすぐだが、今日は講義資料を読むだけにしておく。

うっかりまたスマブラ淫夢実況を見始めてしまう。以前見た覚えのあるシーンがもう一度見たくなり、どの動画だったか探して一度見た動画をもう一度見返すフェーズに入ってしまい、そのまま3時間が経過した。ちなみに探していたシーンは無事見つけることができた。この動画の4分29秒から始まる対戦で使用される御伽原江良の語録と、

nico.ms

この動画の4分46秒から始まる対戦で使用される自分を大蛇丸と信じて止まない一般男性の語録が見たかった。

nico.ms

午前6時半就寝。

07/16(金)

正午くらいに目を覚ます。追跡サービスで昨日の願書が大学に到着していることを確認した。二度寝するつもりでゴロゴロしていたが、失敗。午前中に届いていたメールで水曜日に注文した本が大学生協に届いたことを知り、受け取りに行くことにした。大量なので、高校の時に使っていたサブバッグを持っていく。競プロ合宿に行くときに着替えを入れたりもしていたが、最近とんと使っていないので、埃が積もっていた。

かなり重かった……。サブバッグで肩に斜めに掛けながら自転車に乗ると、本が入っている場所が腰や自転車に擦れるので、できるだけ片手を開けて支えるようにしながら持って帰ってきた。

安くなるのはいいのだが、大学生協で本を買うとよく微妙に角が潰れていたりするので、かなり気になる。生協の本の扱いが雑なのかとも考えたが、どちらかというと本を1冊1冊扱うことによる傷という感じがしてきた。本屋で平積みになっている本の下から掘り出したりするのが、状態的には一番良いのだろう。

invertは七夕あたりに出た相沢沙呼さんの新刊。せっかく大きな本で買うのだから初版本が欲しかったが(といっても現在の流通量で初版本に価値があるかというと……)、確認したら再版だった。Twitterで、発売日前にすでに再版が決定しているというような話は見聞きしたので、横着せずリアル本屋の在庫を狙うべきだった。

サークル解説会の準備をする。今日はABC209。CとDの解説スライドを用意した。Cをどのように思いつくべきか、というのはなかなか難しい話であるように感じられる。つまり、自分のコンテスト中の思考をうまく言語化できない。方針ガチャで当たりを引かなければどうしようもないと思っているため、これが灰diffというのには驚かされたのだった。

E問題の解説を行ってくれた人がいた。文字列の末尾3文字に対応する頂点を特別作らないことによって、探索の始点=ゲームの終点を1点に絞るのは面白い実装方針であると思った。

2021/07/16 定例会 | puzzleknot 公式サイト

毎週Google Meetの会議リンクを生成して、解説会の直前にSlackに貼っている。これは何とかしたほうがいいかもしれない。来週の解説会からは固定されたリンクで活動できるように準備しておきたい。

yukicoder 304に出た。全完。

yukicoder contest 304 - yukicoder

Aは、実はグリッドの左上と右下に半々に人を配置するのがよい。これは2人の時は明らかで、3人目をどこにおいても値が変わらないことを確かめ、4人目に思いを馳せるとわかりやすい。Bは先頭から貪欲に揃えていく。どこから揃えようとしても、結局必要な操作回数はあまり変わらないように感じた。これは解説でうまく説明されていて、逆順列を考えると隣接swapによるソートに帰着されることからわかる。Cは行列のサイズを有向グラフと見て、始点と終点が決まるか、大きなループになるかを調べればよい。Dは列を鳥で分割すると、合間にどちらの動物を詰めるかでdpができる。Eは二分探索。

Fは面白い。いつものように蟻がすれ違うと読み替えておく。最後に落ちる蟻の時間と端を固定したとき、向きが決まる蟻と自由な蟻の2種類に分かれる。向きが自由な蟻のうち何匹が左向きか(あるいは右向きか)を固定したとき、右から落ちる蟻と左から落ちる蟻の数がわかって、この状態で元の問題に戻ると、蟻の順序が変わらないことから左から何匹目の蟻が最後に落ちるかがわかる。最後に落ちる蟻を決めるのと、向きが自由な蟻を考えるのでO(N^2)。Gはいったん?を無視して考えると、実は(全部?の場合以外)その時の操作回数が達成できる。具体的には、最後の操作で消される文字列を計算して、間にある?を直前の文字(存在しない場合a)に揃えるようにすればよい。これで、すべての?は最後の操作に巻き込まれて消える。その前に消えてしまうかもしれないが、ともかくこれが辞書順で最小なのでよい。

買ってきたラノベから1冊読んだ。「お隣の天使様にいつの間にか駄目人間にされていた件」5巻。非常に良い。Web版のころからこの辺りの展開は本当に好みであった。以下ネタバレになる。

4巻のラストでヒロインが公開告白もどきを行う。ここまで焦れったかった関係が確定するのもよいし、それまであまり目立たなかった主人公が一気に注目されるようになるのもかなりドキドキした。4巻はそこで終わって、5巻の冒頭からその後しばらくの学校生活が描かれる。これまで主人公は、ヒロインとお出かけするときだけ髪をセットし、ヒロインの隣に立っても恥ずかしくないような恰好になっていた。ついにこの度ヒロインと交際を始めたということで、学校でもその恰好をするようになって、いきなり格好よくなった主人公に対する周囲の反応がまたいい感じでニヤニヤできる。

読んでいる最中、あまりの良さに耐えられなくなり、精神の安定を取るためしばらく院試の問題を眺めていた。院試を解くゼミが発足して、そろそろ第1回目が近づいている。僕に割り振られた問題を解いておかないとそろそろヤバい。しばらく考えた感じ、まあまあ解けそうだったので、安心して読書に戻った。

ラノベの新刊チェックをする。「転生ごときで逃げられるとでも、兄さん?」の2巻が出るらしい。1巻がかなり面白かったのだが、1年以上続刊が出なかったので打ち切りかと思っていた。作者が忙しすぎたのだろうか?ほかにもいくつか新作をほしい本のリストに追加していたら、また来月も20冊ペースになってしまうようだ。大量に本を買うのは楽しい。願わくば、このようなお金遣いをずっとできるような生活をしたい。

日記を書いて布団に入り、午前6時半就寝。

07/17(土)

午後2時くらいに目を覚ます。布団でしばらくYouTubeニコニコ動画を観た後、ラノベを1冊読んだ。

「幼馴染で婚約者なふたりが恋人をめざす話」2巻。1巻からあんまり合わない感じはしていたが、2巻でその印象を強めた。出てくる女の子が怒るときの描写がいっつも「怖い笑顔」系統なのが肌に合わない、と思ったが、そのような描写は別にこの作品に限らないことに気づいた。ここまで癇に障るということは、坊主憎けりゃ袈裟まで憎いということで、そもそもキャラたちの性格が気に入らなかったのだろうか。

午後6時くらいに二度寝に入り、午後7時半に目覚ましで起床。睡眠時間は1時間半の倍数が良いという話を昔に聞いて、今でも意識しているが、そのようなことは関係なく1時間半で起きるとクソ眠い。

第7回PASTが終了したようなので、過去問公開を待ちながら院試の答案を作成していた。結局公開されずABC210の時間になったので、出た。全完26位。

AtCoder Beginner Contest 210 - AtCoder

A問題はちょっとした場合分け。kコマンドを使えばdcでもかなり簡単に書けそうだが、ちゃんと縮めきるのは難しいように思う。Rubyで通して、ゴルフは後回しにした。B問題は制約が優しい。とりあえずPerl@-を利用しちょっとだけ縮めておいた。C問題から面倒なのでC++を使う。適当にmapで管理して、毎回ちゃんと要素をeraseすることで要素数も得られる。

Dはかなり難しく感じた。下の行を固定すると、上の行からその行まで一直線に下りてくるときの(駅の建設費用も含めた)最小コストは上から順に求まる。このもとで、今固定している行内の2点を選んで同じ問題を解けばよくなる。実際に解くには区間add・区間minの遅延セグメント木を用意して、自分の左右に分けてコストを足したり引いたりしながら求めればよい。Eは簡単。操作iを使って目一杯操作すれば連結成分の個数がN\rightarrow \gcd(N,A_i)になるので、N=1となるまでC_iの小さい順に使えばよい。

Fは面倒。2-SATに落ちるまでは良いが、辺の数が大爆発する。実はそれぞれ直前の要素との関係ぶんだけ辺を張るだけで再現できたりしないか、と思って実装してサンプルを合わせたが、当然のようにWA。適当な超頂点を用意するにしても、意図せず自分から¬自分に辺を張ってしまったりして、まずい。この時点で「区間に辺を張るテク」のことは思い浮かんでいたが、さすがに面倒すぎるのでしばらく別の方法を考えていた。残り時間が40分くらいになって、諦めて区間に辺を張るテクを実装する。自分のライブラリのセグ木を参考にしたら以外と簡単に書けた。うっかりセグメント木ぶんの辺を張り忘れてさらに1WAしたが、何とかACできた。

Dは数値を106個読み込ませていて、なかなか攻めている。Fはもっと頭が良い辺の張り方があったらしい。

コードゴルフ。Aは残り時間を使ってdc 17Bを書いておいた。X(N-\max(N-A,0))+Y\max(N-A,0)。Bはsedで書くのが短い。CはPerlAWKに書き換えた。EはRuby。ソートをbashで行うことも考えたが、入力の1行目だけ取るのが難しくて諦めた。

CF #733 combinedに出た。6完48位、レートは2843→2852(+9)で微妙に最高値を更新した。

Dashboard - Codeforces Round #733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine)) - Codeforces

Aは数字列と見てmax。Bは適当に貪欲に詰めても良さそうだった。自信が持てないので、提出する前に適当に縦横の偶奇をいろいろ手で試していた。Cは勝つまで試合数を増やしていってもよい。O(n)回で解が見つかる。Dは貪欲にマッチングしたあと、余りも貪欲に詰め込む。最後に自己辺が残る可能性があるが、これは条件を満たしている頂点から適切に選んで行き先をswapすればよい。見た目に反してかなり簡単だった。

Eは最初辞書順最小を見落として1WA。次に、答えを必ず1以下にできることに気づかず1WA。答えを1にするときは、aababacacaのように詰めるか、abaaaaaacbcのように詰めるかの2パターンあって、どちらも辞書順最小の文字を先頭に持ってくることができる。abbaaaaに注意。

Fはよくわからない。1マスずつ決めるdpの計算回数を適当に見積もると、持つべき情報が列が揃っているか・2本の対角線が揃っているか・今の列が揃っているか・これまで揃った列が存在するかの25bit必要になってしまった。ここから少し減らす。まず、揃わない確率を計算すれば、これまで揃った列が存在するかの情報は必要ない。次に、列ごとにdp配列を保存しておいて、1列終わった段階でその列が全部揃う場合の遷移を抜くことにすれば、今の列が揃っているかの情報も必要なくなる。これで23bitになって、2^{23}\times 21^2\approx 4\times 10^9。気合を入れたら行けそうな気がしないでもない。

実際はかなり時間がかかってしまうようだった。まずmodintを書かず、直接modを取ることにする。これだけで結構希望が持てる時間になったのではなかったか。あとは遷移をいじる。遷移は、行・列によって決まる特定のbit(3つ以下)をそのままにするか一気に落とすか、という風に読める。よって、関係するbitだけ取りだし、他のbitで部分集合を走査して毎回計算することにしてみた。ほかにdp配列をin-placeに更新するようにしたりして、多少は速くなったが、むしろ部分集合dpにしてしまったことによってこれ以上の高速化が望めなくなってしまった。

ここで、消えるbitが3つ以下であることに注目する。どれが消えるかで場合分けし、それ以外のbitを上位桁からまとめてループすることで、一番内側のループにベクトル化を効かせられないだろうか。とりあえずゴリゴリ場合分けしたところ確かに速くなった。手元では間に合うくらいの時間になったので、以降こどふぉのコードテストに移る。こどふぉではまだ間に合わないようだ。そこで、一番多く入る場合分けの部分にさらに手を入れた。具体的には、ループを分割し、毎回の演算を軽いものにする。また、in-placeに更新していたdp配列を一度別の場所に移し、計算順序を任意に変えても問題ないとわかりやすくした。これで最大ケースでも7秒に間に合うようになったので提出、AC。

Submission #122848521 - Codeforces

システスを見つつ、明日に迫った院試ゼミに向けて答案の作成を再開する。昨日は案外解けるな……と思っていたが、実は全然解けていなくてびっくりした。

熨斗袋さんからファンアートを頂いた。嬉しいのでカラーで印刷し、部屋の壁に飾っている。

院試は、担当する問題2つの最後の大詰めが解けないまま、午前8時に就寝。

07/18(日)

午後2時起床。寝ている間にいくらか考えが整理され、ゼミの開始までに何とか回答を作成しきることができた。

午後3時から午後7時半までゼミ。非常に有意義な時間だった。あと、自分が思ったよりヤバそうであることに気づいてちょっと焦る。あと1か月で仕上げていきたい。

途中、第7回PASTの問題が公開されたので、最初の数問を通しておいた。この辺りはたまにコードゴルフが自明な問題があって、激戦区。とりあえずE問題まで読んだ。ACEは面倒そうだが、B問題は\min\left(\frac A B,C\right)、D問題はsedで一発だった。どちらも取れて満足。Eもゼミ中に縮めていた。

ゼミが終わってからしばらくAとCを縮めていた。午後9字からARC123に出た。

AtCoder Regular Contest 123 - AtCoder

5完18位、パフォーマンス3178、レートは2774→2821。赤コーダーになった。

A問題はちょっと難しい。場合分けで攻めようとしたが面倒に感じ、しばらく考えていたら、A_1+A_3-2A_2=0という式に気づけた。

B問題は簡単。直感的な解法としては、次のようなものが思い浮かぶ:3つの列をそれぞれソートし、Bを見つつ先頭からAとペアにし、相手が見つかったものを残す。こうして残った要素を新しくAとし、B\leftarrow Cとしてもう一度繰り返す。これで正しいことも簡単に確かめられる。つまり、これで残る要素を残さないことで得しないことが言えればよくて、これは要素数の面でも、値の大きさの面でも小さいものから貪欲に取った時が最適になることから従う。実装も同じことを2回する部分をループにするといい感じにシンプルになる。

C問題は桁dp。答えの最大値は、それぞれの桁で3ずつ引いていくようなことを考えたとき、3×18でだいたい60くらいあれば安心だろう。答えを1ずつ増やしつつ桁dpでチェックする方法を実装してみたところ、サンプルは合うようだが間に合わないので、いくつか並列で計算する。61回bool値のdpをするので、long longに情報を詰め込むことで一度にdpできる。また遷移を少し工夫することで、簡単に間に合うような計算量に落とすことができた。ちゃんとサンプルも合ったままだったので安心して提出、AC。

D問題は最初、Bが必ず非負の数になる!と思い込んでしまった。このとき、B_{i+1}=B_iC_{i+1}=C_iのどちらかが成り立つことはかなり簡単にわかる。それで実装したらサンプルが合った。あまりにすんなり書けたので疑って順位表を確認したところ、結構通っていたので自信を持って提出、WA。残念!しばらく考えると、先ほど考えていたことが大嘘だったことに気づく。しかしこれは良い点もあった。B_{i+1}=B_iC_{i+1}=C_iのどちらかが成り立つことはまだ成り立ちそう。先ほど考えなかったB_i\le 0\le C_iのときが怪しいが、このときは数列の先頭のほうから押し縮めていくようなイメージでわかる。このとき、B_0の値を変数とすると、それ以外の値はすべてB_0に適当な値を足し引きしたものとなる。それらの絶対値の和の最小化をするには、いつもの中央値とすればよい。これでACできた。

DのAC時点でもそこそこいい位置につけているが、Eがたくさん通されるとまずい。実際floor_sumが効きそうでそれなりに通されそうな見た目をしていたので、頑張って考える。あまり考察がまとまらないまま、やっておいて問題はないだろうと思ったこと、つまり適当な場合分けと、あとは{\rm lcm}(B_X,B_Y)の倍数だけギリギリまで動かしておくことを実装した。しかし問題そのものは変わっていない。

場合分けしてB_X\lt B_Yとしている。このとき、f(n)=\left\lfloor\frac n{B_X}\right\rfloor-\left\lfloor\frac n{B_Y}\right\rfloorが特定の値になるようなnを求める問題だった。ここで、f(n)の値はそう簡単に減らないことに気づく。一度-1されたら、次は必ず+1されるという意味。このとき、f(n)=Kとなる最小のnf(n)=K+1となる最小のnの間では、f(n)の値はKまたはK-1であることがわかる。そのような範囲は二分探索で求めることができて、範囲内では2通りの値しか取らないので、f(n)=Kを満たすnの個数はf(n)-(K-1)の総和に等しい。これはfloor_sumで求めることができる。やっとfloor_sumに帰着することができた。

最初に書いておいたコードは、場合分け以外は必要なかった。実装して提出するとWA。範囲を二分探索で求めるところにミスがあった。直接nを求めるとf(n)が単調でないためWAとなるが、実は求めるnB_Xの倍数なので、それだけ調べれば単調性が表れそう。すぐに修正することができて、今度こそACした。残り時間はFが結構絶望的だったので、コードゴルフをしていた。こうやって諦めるのはあまりよくないんだなあ。

コードゴルフ。A問題は適当にdcで解いておいた。B問題はRubyで、うえで説明した解法だとinjectが効く。

かなりうまくいったので、もしかしたら赤になれるかもしれないと思っていた。実際のレート更新が来るまでは自分がどうなったか知りたくないので、predictorの結果がツイートされている可能性のあるTwitterは開かないようにして、PASTの問題をいくつか解いていた。Hは適当な嘘を何度か投げた後、1004のdpを投げたら通った。浮動小数点数を扱っているし、そこそこ攻めた制約に感じられる。コードゴルフとしては、FはPerl、IはRuby、Jは取り合えずALPCのSCCの最短コードを移しておいた。networkxの関数をいくつか試していたが、どれもTLEしてしまうようだ。

午前0時半くらいにレート更新が来て、赤になっていることを確認した。

しばらくPASTのコードゴルフをしたりTwitterしたりした後、午前3時くらいから色変記事を書き始めた。前々から、色変記事を書くときはGoogleフォームで質問を募集しようと思っていて、実際に行動に移したのだが、ありがたくも公開時点で59個の質問が集まっており、書くのにかなり時間がかかった。

kotatsugame.hatenablog.com

記事を公開して布団に移動し、午前8時半就寝。

AtCoder 赤色になりました

AtCoderで赤色になりました。

統計情報

レート遷移

パフォーマンス

解いた問題数

Achievement

AtCoder Pie Charts

Difficulty Pies

Category Pies

kotatsugameに質問コーナー

皆さんご協力ありがとうございます。以下のGoogleフォームはまだしばらく開けておく予定なので、これからもドシドシご投稿ください。

07/26追記:質問の受け付けを終了しました。

ん?今何でもするって

するとは言ってないんだよなあ……。

水洗った?

洗った

尊敬する競技プログラマは?

尊敬ですか……。昔、latte0119さん、beetさん、ei1333さんに対して抱いていた感情はおそらく尊敬だったと思います。またコードゴルフ関係では、testestestさん、kimiyukiさん、%20さんを尊敬していました。が、最近はあまりほかの競技プログラマのことを意識しなくなっているため、今尊敬する人と言われてもパッとは思い浮かびませんでした。

質問などなんでも

そうだね、質問などなんでも書いてくださいとあったからね

性欲と競プロ力の関係はあると思いますか

う~んどうでしょう。直接的には関係ないと思いますが、例えばパートナーが居て毎週ある程度まとまった時間をその人と過ごすために使うというような人は、そうでない人と比べて競プロ力の向上が見込めないと思っているので、そのような意味では間接的に関係あるかもしれません。

俺はAtCoderレート2824だけど、お前は?

2821笑

AtCoder以外の過去問は主にどこで拾っていましたか?

直接的に精進に寄与したのはAOJ-ICPCとyukicoderですね。他にも、最初期はJOIの予選問題を埋めていました。codeforcesは虚無埋めしかしていないですね。

赤色おめでとうございます!!!!!!!!!!!!「致した」とツイートした後にリンクを貼ることは競プロのレートにどのくらい寄与しましたか?

そのようなツイートを始めてから今まで2回のコンテストで+072しました!

次富山に帰るのはいつ頃になりそうですか

院試終わりです。8月の終わりになるか9月入ってからになるかは未定です。

競プロを引退する予定はありますか

ありません。今のところ引退しそうな気配もないですが、もし競プロを止めるなら、それはおそらくフェードアウトのような形になるでしょう。

赤おめでとうございます!いくつか質問させてください

  • 自分の得意分野、強みは何だと思いますか?

悩みどころですね……。まず、得意分野はないと思っています。逆に苦手な分野がないことが強みだと自負していましたが、最近数え上げが周りと比較して解けないように感じています。まあそれ以外に苦手だと思う分野はないので、ある程度まんべんなく解けると言っちゃってもいいかもしれません。

  • 作問はされますか?

その予定はないですが、機会があれば有志コンに出題するくらいはやってみてもいいかも?といった心構えです。

  • 同じ大学で注目している競プロerはいますか?

ちょっと前、立て続けに東北大学の競プロerが黄色になったので、これは僕もうかうかしていられないぞと彼らを注視していました。今でも注目していることはしているんですが、それ以来皆さん伸びが止まってしまわれて……。他にも、普段から順位表で所属:Tohoku Universityの動向は確認しているのですが、毎回いくつかの問題について僕より早くACする人が数人いて、気になっています。

  • 今後の目標は何ですか?

特にないですね。消極的ですが、色落ちしないことが目標と呼べるでしょうか。

解説ACをすることはありますか?それとも分からなかったら時間を置きますか?

コンテスト中(追記:これはバーチャルコンテストも含みます)に考えていた問題の解説を見ることもたまにありますし、コンテスト後のTLでキーワードを目にしたりもするので、確実なことは言えませんが、過去問精進で解説ACというのはここ2、3年くらいはほとんどないはずです。

競プロの得意分野は何ですか?

上のほうでも書きましたが、ないと思っています。強いて言えば簡単枠の速解きだったんですが、最近SSRSさんという化け物レベルの方が現れて……。

コードゴルフが好きな理由は何ですか?

昔は縮むごとに可読性を失っていくコードに惹かれていました。今はどちらかというと好きな理由ではなく止めない理由のほうが強くて、コードゴルフで負けることへの抵抗感からコードゴルフをしています。

最近読んだラノベで良かったものを教えてください

Twitterとかであまり言及していないものを見繕ってみました。「クラスの大嫌いな女子と結婚することになった。」「魔王2099」「時々ボソッとロシア語でデレる隣のアーリャさん」「D級冒険者の俺、なぜか勇者パーティーに勧誘されたあげく、王女につきまとわれてる」「隣のクーデレラを甘やかしたら、ウチの合鍵を渡すことになった」

一番好きなアルゴリズムはなんですか

SA-ISですかね。とにかく手数が多くて定数倍が重そうに見えるのに、競プロの入力サイズにおいてすら実用的なのが面白いです。

この世で最も尊敬する人物を聞かれたらこたつがめさんと答えます!!!致したツイートのオカズ助かります!!!!!!

ありがとうございます。これは一般論ですが、良いものは積極的に共有しましょう。

ゲーム問題のコツを教えてください

サイズが小さい状態・終わりに近い状態から考えることです。こう明言してしまってよいでしょう。また、実験の手間を厭わないことも重要です。実験を手で行うかプログラムを書くかは場合によりますが、例えば僕なら、dpテーブルが2次元以下の場合は目で分かりやすく表示できるので、プログラムを書くことが多いです。

就活してますか/どうでしたか

とりあえず長期インターンに内定をいただきました。院に進む予定なので、今の時点ではこれ以上のことをするつもりはありません。インターンに採用されるための努力のようなものは一切行わなかったので、かなり簡単に進んだなという印象です。

赤になってから一番初めに何で致しましたか?

この質問のおかげで、致すことに対していやに身構えてしまいました……。ツイートをお楽しみに。

2021/11/02追記:遅まきながらここに貼っておきます。

ゴルフ以外で、精進としては週にどのくらいの練習をしていますか?

ここ1、2週間はちょっとばかり問題を解いていましたが、普段はほとんど精進していませんね。コンテストに参加するくらいなので、週10時間程度でしょうか。

ゴルフはアルゴの役に立っていますか?

立っていると思います。ごちゃっとした操作をまとめるアイディアだったり、典型的な問題のシンプルな解き方だったりは有用です。普段書くコードから短いというのも、タイプにかかる時間的に役に立っていそうですが、これはテンプレートを過剰に整備するほうが強いかもしれません。

ゆっくり実況動画、いつも楽しませていただいています!!

全然続編出なくてすいません、一度動画編集から気持ちが離れるとなかなか戻ってこれず……。一応画面の録画は今でも続けているので、素材(だけ)は充実してきています。

名前はこたつ 亀 ですか?こたつ game ですか?

亀です。こたつむりという言葉のシノニムのつもりです。こたつむりはあまりに一般的すぎるので、このように変えました。ヘッダーは4年ほど前にTLに流れてきたものを(作者の方に断って)使わせてもらっています。あまりにピッタリなイラストで、当時はびっくりしていました。

何学部ですか?

理学部です。

赤コーダーになったkotatsugameさんおすすめのpixiv絵(R-18)を教えてください

#コミックグレープ 告知/コミックグレープ - ぴょん吉のマンガ - pixiv

ぶっちゃけ、才能は何割くらい必要だと思いますか?

5割くらいですかね。残りは努力なんですが、こっちにも努力する才能のようなものが必要になる気がします。

好みのR18絵はなんですか?

2つ上の質問をご参照ください。

致したを報告することになったきっかけってなんですか?

高3の夏ごろからツイートしているようですが、まったく覚えていません……。「ねね」や「ぽきた」も同じ時期からツイートしているようなので、その頃から日々の行動をルーティンのように(同じ文面で)ツイートすることにハマっていたのかもしれません。今もハマっています。

精進の際意識することはありますか?(質問者は緑です)

ACした後に他の人のコードと自分のコードを読み比べてみることでしょうか。僕はコードゴルフをしようとして他の人のコードを読んでいたのですが、それによって知った実装方針などは普段のコーディングのときも非常に参考になりました。

コンテスト前のルーティンはありますか?

「ぞいぞいしてきた」とツイートするくらいです。

卒業できそう?

正直ここまでくれば余裕です。2年生の時に頑張ったのと、3年生からオンラインになって出席の必要がなくなったことが効きました。

解説 AC について、e.g: 「n 点問題ならしていい」「AGC はしないほうがいい」

ABCの問題ならすべて解説ACしてよいです。他にも、コンテスト中に考えて解けなかった問題の解説も(コンテスト直後なら)見てよいと思います。あとはあんまり見ない方向で。

トッポうまい

そういう意見もあります。僕は極細のポッキーが好きです。

赤色ってどれくらいすごいの?

わからん……。定量的な評価は置いておくとして、僕はここにたどり着くまでに5年かかった。

ベン・トーっていいよね.ところで競プロって半額弁当争奪戦みたいじゃないですか?ぼくどっちも未経験なんですけど.

競プロerは基本ハンドルネームで活動するし、オンサイトに遠征するし、そうかもしれん……。

最近golf参戦中のPython使いです。kotatsugameさんがgolfをする際の基準のようなものはありますか?「200Byte以下のgolfは興味がない」的なツイを以前見たので。

典型90問の時のツイートですね(以下ではなく以上でしたが)。あの時は90問一気にコードが公開されるから、長いコードを全部読む元気はないなあという意味合いでした。基準についてですが、dcやsedで解ける問題はゴルフするとして、他には、C++で実装するときに「別言語のあの機能を使うと簡単に書けるのに」と考えた問題を好んでゴルフしています。例えば、Pythonでいうmapanyが使える問題ですね。僕はあくまでC++使いなので、最初に実装するときは全部for文で書いているわけです。

AtCoderのコンテストのwriterになる予定はありますか

ありません。ここまで育ててくれたAtCoderで作問バイトして恩返し!みたいな気持ちはありますが、それ以上に、AtCoderでは常にcontestantでいたいという思いがあります。さらに言えば、contestantの立場でコードゴルフをしたいからです。

競プロにおける次の目標とかありますか

上のほうにも書きましたが、特にないので色落ちしないことを目標としておきます。

射精するたびに「致した」って呟くのはなぜですか?

botみたいに毎日の行動を同じ文面でツイートすることが好みだからです。寝るなら「ねね」、起きたら「ぽきた」、物を食べたら「食事」、その一環です。

今後の目標を教えてください

競プロに制限されていないので、別の趣味の話をしましょう。CHUNITHMでLv.14の鳥を出すことです。

いま一番会いたい競プロerは誰?

桃音モモさんです。

卒業したらどんな仕事をしたいですか

コードを書く仕事で年収高めなら何でもいいです。あまりこれがしたいという好みは考えていません。

Qiitaのコードゴルフ記事の更新まだですか?

す、すいません……。ですが現状、コードゴルフ記事の優先順位は僕の中でだいぶ低いので、予定は未定です。

まだ理解してないけどいつか理解したい競プロ知識ってなにかありますか?

いつかというか、すぐにでも理解したい・しなければならない競プロ知識として、「Segtree Beats」「HLD」「FPS」が挙げられます。これらは未履修ですが、最近有志コンでよく見るので、ちょっと焦燥感があります。あとは「平衡二分探索木」「Wavelet行列」もいつか理解したいですが、あまり焦ってはいません。

フェチってありますか

特にないと思います。敢えて言うならば胸が好きですが、フェチという言葉に暗黙的に含まれている「特殊さ」には当てはまらないものと思います。

beetさんに一言

鍵垢にフォロリク送ったら通してもらえますか?

黄色になってからの精進について詳しく教えて欲しいです。

精進の記録をつけていないので、ちょっとあやふやです……。確か、AGCの900点以下を(解説を開いた問題もありつつ)埋めたのが橙になる少し前のことだったと思います。橙になってからは、ARC-Cを埋めたり、AtCoder ProblemsのRecommendationを下から順に埋めたりしていました。埋め具合はこの記事の冒頭にあるスクリーンショットの通りです。合間合間でAOJ-ICPCも挟んで、橙になるころには400点まで埋まっていたはずです。今は550点までのほとんどが埋まっています。他にはAOJでPCKの過去問を埋めたり、codeforcesでdiv.3を埋めたりしましたが、これらは虚無埋めなので精進とは呼べなそうです。

致すときに心掛けていることはなんですか

時間をかけないことです。

大学生のうちにしておきたいこと

特に思いつきませんね……。ひたすら好きなことだけやって過ごす、とかはすでに今やっていると言えます。

ん?今何でもするって言ったよね?

するとは言ってないんだよなあ……。(2回目)

ライバル、期待している競プロerについて教えてください

ライバルは特に考えていません。順位表で自分の上にどんな人がいるかくらいは確認しますが、自分の下は見ません。期待している競プロerについてですが、桃音モモさんには頑張ってほしいと思っています。俺、ここで待ってるからよ……!他にも、僕が高3のころに科オリ界隈で繋がった人々が続々競プロに参入しているので、彼らにも注目しています。

AtCoderコードゴルフの思い出が深い問題を教えてください

atcoder.jp

いつだかの配信中に縮めた問題です。謎の式変形の結果、ほとんどdc専用のような式が得られたのが印象に残っています。その式変形については以下の週記の土曜日の項を参照のこと。

週記(2021/03/29-2021/04/04) - kotatsugameの日記

また heno239 さんとコラボする予定はありますか?

予定は特にありませんが、いつでもコラボするくらいの心構えでいます。自分から話を持ち掛けたりはしないんですが……。

好きな言語ベスト3、オススメ言語ベスト3とか

好きな言語:1位Raku、2位Octave、3位Haskell

オススメ言語:1位Ruby、2位Octave、3位AWK

得意な言語ベスト3とか

コードゴルフの意味で得意な言語を考えてみました。1位Raku、2位Octave、3位AWK

AtCoderの面白いと思った問題・思い入れのある問題を教えて!

atcoder.jp

面白いと思った問題です。サンプルのふりして巧妙なヒントになっていて、聞いたときは上手いなあと思いました。ちなみに、操作回数が1000回になるような数にはもっと小さいものが存在して、言語アップデート前の最短コードはその改善で取られてしまったものでした。

atcoder.jp

思い入れのある問題はこちら。僕が初めて解説ACした問題です。コンテスト後に解説放送を見てその解法に衝撃を受けたことを覚えています。いま改めて考えてみれば、結構分不相応な問題にチャレンジしたなあという感じですが、解法を正しく実装してACが取れたので自信につながったことを覚えています。

Perlのショートコードが全然理解できません。ABC001C風力観測のコードの解説してほしいです。

僕のQiitaの記事を読んでいるものとして、<>=~$"$-、裸の単語、/./gについては説明しません。

print<>=~$"*15>($-=$')?C:(eval$_.y/NWS/SEN/r)[-$`/225-.5],$".grep($--=2*ord,"'6?KT]clox~"=~/./g).$/for'N,NNW,NW,WNW,W,WSW,SW,SSW,'

まず、全体が後置forで囲まれているわけですが、これはループが目的ではなく、特殊変数$_に値を設定することが目的です。具体的には、$_='N,NNW,...'になります。

このとき、$_と、その文字列のNWSSENにそれぞれ置換したものを連結すると、出力すべき文字列が角度順にうまく並んでくれます。Perlコードとしてevalすることで文字列のリストを得ます。ここまでが(eval$_.y/NWS/SEN/r)の意味です。y///はそのままだと$_を書き換えてしまうので、rフラグを付けて書き換えないようにしています。

次に風力を計算します。これは、適切な数列を用意したとき、「数列の先頭から順に値をDisから引いていき、Disが0より大となる要素数」とすることができます。風速の階差を取っている感じです。ここで、適切な数列の値を2分の1にして文字コードに直すことで、数列を文字コードとして埋め込むことができます。それが"'6?KT]clox~"で、もとに戻すには/./gで文字ごとのリストを得て、2*ordを計算すればよいです。

Disは変数$-に代入されているので、そのまま引き算していくことでDisが0より大であるかがわかります。grepでそのようなDisに対する文字のリストが得られますが、この長さが風力なので、文字列$"$/と連結することでリストを無理やりスカラとして評価し、長さを得ています。

このくらいでしょうか。もしまだわからない点があるようでしたら、ぜひTwitterやDMでもご質問ください。Perlのショートコードは、まずトークンごとにパースして、演算子の優先順位を抑えつつ、値がリストコンテキストで評価されているかスカラコンテキストで評価されているかを見ていけば読めると思っています。

入赤おめでとうございます!コードゴルフやろうってなったきっかけが知りたいです!

ありがとうございます。僕は最初にC++言語でコードゴルフをしていました。教材のコードからいくつかスペースを抜いても動くことに気づき、そこから調べてコードゴルフという競技のことを知り、あとはテクニックなどを調べているうちにズブズブです。多分こんな感じの流れだったと思いますが、何分昔のことなのであいまいです。

07/20 追記分

致したタイミングとパフォーマンスの相関について

直前にはしないようにしていますが、実際あまり関係ないと思います。

よく噛んで食べたことによる変化はありましたか

よく噛んで食べることができていないですね……。便秘解消のつもりでしたが、それより毎食ちゃんとしたものを食べるほうがよほど効果があるようです。実家に帰ると格段にお通じがよくなります。

赤到達おめでとうございます。shortestコードをいつも楽しみにさせてもらっていますが、あれをやり始めたきっかけは何ですか?また、shortestコードを書いていて良かったなと思うことはありますか?

ありがとうございます。きっかけは上に書いた通りです。良かったことですが、オンサイトなどで結構認知してもらえているのはうれしい限りですね。周り中競プロerの中であっても、自分の特記事項として話のネタにできたりするのも便利です。

競プロの問題作成しないの? 興味もって!

yukicoderのエイプリルフールコンに2問出したことがあるのですが、それ以上の興味はないですね。

好きな音MAD教えてください

www.nicovideo.jp

  • けものオドル

www.nicovideo.jp

  • イナズマゼロニン

https://www.nicovideo.jp/watch/sm34036224www.nicovideo.jp

大学院でどんな研究したいの?

さあ……。まだ何にも考えてません。

ペロペロチンチーノを食べまくると赤コーダーになれるって本当ですか?

な~にがペロペロチンチーノじゃ。不敬であるぞ

赤にそろそろなれると思い始めた時期はいつ頃ですか?

ARCが毎週開催されるようになって1か月くらいしたころでしょうか。そのあたりで新しく赤になった人がたくさん現れて、たどり着ける可能性のあるものとして明確に赤を意識し始めました。

まん⤴︎こ? まん⤵︎こ?

?どちらかといえば後者でしょうか。

プログラミング言語の勉強法で、オススメありますか?

毎日触れることですね。あとは、これは質問の趣旨とはちょっと違うかもしれませんが、サブの言語を習得する際の注意について。サブの言語に集中するあまりメイン言語を書かないような期間があるのはあまりよくありません。あくまでサブ言語はサブであるということを意識して、それに慣れ切らないようにするのが良いと思います。

院進すると聞きましたが就活はどうする予定ですか?

修士で終わる予定なので、そのあたりで就活します。どこを受けるかとかは全然考えていません。

やっばりこたつでゲームしてるんですか?

冬になると実家の居間にはこたつが設置されていたので、そこでゲームをしたり、そのまま寝落ちしたりすることはよくありましたね。一人暮らしを始めるにあたってはこたつは購入しませんでした。出すのもしまうのも面倒だろうし、こたつで寝ると良くないと思ったからです。ちなみにゲームも購入していません。一度始めると止められないことが目に見えていたからです。

C++以外ならメイン言語なんにしますか

メイン言語にするなら、速くてそれなりに情報がある言語でなければなりません。C#Javaなども考えられますが、それらは触れたことがないので、おそらくRustになります。

週記の文章量に毎度驚いている

なんかどんどん増えていったんですよね……。現在、初期のちょうど倍くらいあります。コンテストや解いた問題のコメントなどを書いていると、どうしても長くなってしまうようです。一応人に見られるつもりで書いているのに、あまり長すぎるのもよくないと思ってはいるのですが。それ以外にも、日曜日の部分を書いているときなどいちいちプレビューが重くなってしまうのもデメリットです。

一日で致した回数の最大値を教えてください

一日というのが寝てから起きるまででも、連続した24時間であっても、おそらく3回か4回ではないかと思います。Twitterで僕のツイートから「致した3」を検索しても結果はありませんが、そもそもナンバリングは1日の回数ではなく、「致した」とツイートしようとして失敗したときに文面を少し変えるためでした。

どのくらいの時間で致せますか

通常、致そうとしてから後始末まで含めて10分弱くらいです。

おすすめラノベを教えて!

おすすめというのはなかなか難しいものです。僕が読んで好きだったものを列挙するので、参考にしてください……程度しか言えません。ちょっと多くなりましたが、せっかくなので絞らずに行きます。「デート・ア・ライブ」「幼女戦記」「俺たちは異世界に行ったらまず真っ先に物理法則を確認する」「セブンキャストのひきこもり魔術王」「物語シリーズ」「ありふれた職業で世界最強」「ソードアート・オンライン」「やはり俺の青春ラブコメはまちがっている。」「魔法科高校の劣等生」「りゅうおうのおしごと!」「公女殿下の家庭教師」「ワールド・ティーチャー」「薬屋のひとりごと」「お隣の天使様にいつの間にか駄目人間にされていた件」「最強魔法師の隠遁計画」「生徒会探偵キリカ」「精霊幻想記」「継母の連れ子が元カノだった」「神様のメモ帳」「暇人、魔王の姿で異世界へ」「竜と祭礼」「最強カップルのイチャイチャVRMMOライフ」「ベン・トー」「転生ごときで逃げられるとでも、兄さん?」「我が弟子が最も強くてカワイイのである」「ホラー女優が天才子役に転生しました」「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」「天才最弱魔物使いは帰還したい」「羽月莉音の帝国」「隣のクーデレラを甘やかしたら、ウチの合鍵を渡すことになった」

巻数が出ているものは売れているということなので、普遍的に面白いはずです。6巻以上なら間違いはないと思います。

いつもつぶやいているねねとはねねっちーのことですか

そうだよ(ちがうよ)

うしさんに一言

うし遊ぼうぜ

致す時の体勢

椅子に座っています。

院試どうですか

今のままではいけないと思います。だからこそ僕は今のままではいけないと思っている。

解けない問題が来たときはどうされてますか?

過去問精進なら、いったん別の問題を開いて、寝るときとかに思い出してもう一度考えたりしています。1晩経って進展がないようであれば、解ける見込みなしとして諦め、放置します。

同じ問題の解き直しとかはされてますか?

コードゴルフという意味でなら、同じ問題を何度も何度も何度も何度も解いていますが、自分の精進に合うようなレベルの問題の解き直しはしたことがありません。そのようなことをしなくても解くべき問題は無数にあるからです。

はよ日記書け

このコメントが来た時も書いていました。

蟻本に載ってないようなアルゴリズムの知識や高度な典型的な考え方はどうやってインプットしてますか

これはもう、実際に問題に取り組んで出会うのが一番多いと思います。なので解説ACを全くしないというのも問題なんですが……。あとは、人のライブラリを眺めたり、Twitterとかで界隈の話題を追いかけたり、ですね。

1年秋学期の成績を見て親から何か言われましたか?

LINEの会話を見返したところ、どうやら怒られていたようです。その頃はかなり微妙な精神状態だったので、自分のことに集中していてあまり覚えていませんでした。

07/21 追記分

Rakuオススメできないんですか、好きなのに?

言語を設計する思想とか、機能の多さの点で非常に好きなんですが、信じられないくらい使いにくいのでオススメはできません。ゴルフ視点の話ですが、パーサの挙動が謎なので必要な空白と不必要な空白が未だによくわかっていません。0>00<0のうち片方は文法エラーになります。どちらだと思いますか?気になる人はAtCoderのコードテストで試してみましょう。

時たまツイートされている夢日記の内容や文体がとても好きです。また面白い夢があれば楽しみにしております。

ありがとうございます。そうですね、内容はともかく、夢日記の文体は何となく小説の地の文を意識しているつもりです。あんまり夢を見ない・夢を覚えていない性質なので、気長にお待ちください。

解いた後に他人のコードを読んで、勉強したりしますか?

上に書いたように、昔は(コードゴルフが主な目的でしたが)結構読んでいました。最近も、一応短いアルゴリズムがないかくらいは確認することもありますが、それもABCレベルの問題ですし、勉強とは言えないでしょう。

ゴルフで新手法が開発されたときに、それを適用できる問題を探して縮めているのをたまに見るんですが、そういう問題をどうやって探しているんでしょうか

定期的にAtCoderをクロールして、(自分がACしたことのある問題の)最短コードを全部保存しています。探すときは、新手法を適用できるとしたらこのようなコード片が含まれるはず、というのを予測してgrepしています。特殊なケースとしては、PerlのUnionFindを使う最短コードは知る限り全部ブックマークしています。書き方がいろいろあるので、どれがどのように縮むかがわかりづらいんですよね。

07/25 追記分

応援しています!新しく挑戦したいことはありますか?

何かを新しく始めるということは競プロに割く時間を減らすということなので、あまりしないようにしているつもりだったのですが、Qiitaで記事を書いてみたり動画を投稿してみたり、あまり守れている信条とは言えませんね。それらも今は停止してしまっていますが、再開したいです。新しく挑戦ということとはちょっと違うかもしれませんが。

憧れているもの/こと/行いはありますか?

生活感を出さないことです。毎日同じものを食べているのはかなり生活感がないと思っていて、個人的に憧れています。他、以前にもツイートしましたが、DEATH NOTEで毎週決まった日時にジムに通うキャラが、大晦日の日もジムに行っているという描写があって、憧れました。僕は生活リズムも安定しないわけですが……。

番役に立ったと思う自炊テク

パスタを茹でるときに塩を入れないことです。そのためだけに塩を買うのは無駄ですよね?実は塩は買わなくてもよいのです。

努力で何色までなれると思いますか?

青、と答えようとしたんですが、僕が青になった頃と今では状況がかなり違いますね。ARCで2完、すなわち4問体制のABCをそれなりに全完できれば簡単に青色になれたのですが、今は……かなり辛そうです。現行の6問体制のABCがRatedの人にとってどんな状況か全くわからないので、自分なりの答えというのも定められません。もうすぐ8問体制になるそうなので、それによってどう変わるかも未知数です。

今までで一番きれいだと思ったものはなんですか?競技プログラミングに関係がなくてもいいですが、関係ない場合相応に綺麗でないと許しません(いいえ)

この質問、答えるのに非常に難儀しました。これまで見た景色とか、読んだ小説のオチとかいろいろ考えたんですが、あまりピンと来るものがありませんでした。この提出を挙げておきます。

atcoder.jp

最近ハマっていることはありますか?ある場合、それはなんですか?

寝る前とかにYouTubeで「おうち麺TV.」というチャンネルの動画を見ています。

www.youtube.com

現在は毎日致されていますが、以前は致すのは 3 日に 1 回くらいだったと記憶しています。頻度が上がったのはなぜなのでしょうか?

あまり頻度については意識していませんが、自分が致すときというのは、TLでそういう画像を見るなどの性的な刺激を受けたり、暇だったり、集中が切れたときのはずです。最近はコードゴルフも含めそこまで熱中していることがなくて、(やるべきことが山積していますが)暇といえば暇かもしれません。

勝手にリスペクトしてます!これからも頑張ってください!

ありがとうございます!僕は自分がリスペクトされるに値する人間とは思っていませんが、それを決めるのはリスペクトする側の人ですね。

Twitter見てなくて知らなかったぜ!!!おめでとうございます!!!!干芋リストとかある?なかったら住所よこせ

(こちらに転記するにあたり、付されていたハンドルネームを削除しました。)

ありがとうございます。今回はお祝いということで、何か送ってくださるのであれば、ありがたく頂きたいと思います。

赤Diffほぼ埋まってないの意外です

自分が解けない問題に取り組むのがあまり好きではないですね。簡単な問題をなぎ倒すことが好きなので、精進はいつも簡単なものから埋めています。赤になるには赤perfを出さなければなりませんが、これは赤diffを解かなくても、橙diffの問題をそこそこ速く解くことで達成できます。今はARCがかなり多いので、そういうやり方でもレートは上がっていきます。

好きなアルゴリズムは?

上で書いたように、SA-ISです。

原作を知らない二次エロ創作で致すことはありますか

何度もあります。逆に、原作を知っているものでそういうことを考えるのはあまり好きではありません。

TwitterのIDの末尾の_t というのはsize_tのように構造体であることを明示するためですか

違います。これは僕の苗字のイニシャルです。

好きな作家さんを教えて下さい。

森見登美彦さんと米澤穂信さんです。このお二方の作品は出たら必ず買うようにしています(が、雑誌などに発表されて本になっていない作品はカバーできていません)。ラノベ作家については、ラノベを作家で買うことはほとんどないので、特に思い当たりません。

07/26 追記分

ブログ等の文章を書く上で意識されていることはありますか?非常に読みやすいので参考にしたいです。

そう言ってくださると非常にうれしいです。特に意識していることは、敬体と常体を混ぜないこと、同じ語彙・表現をあまり連続させないことです。例えばこの記事は(冗談交じりの文を除き)すべて敬体で書かれていますが、週記は逆にすべて常体になっています。同じ表現の連続についてはあまり徹底できていないかもしれませんが、読み返してくどいように感じたら書き直しています。

致すのは手ですか?何か道具をつかったりしますか?

手です。

6問から8問にする理由がなんかおかしくね?と思いましたか?

確か、F問題のストック放出と崖解消だったでしょうか。崖解消については、実際はそううまくいかないだろうと考えていますが、目標としていいと思います。F問題のストック放出というのには違和感がありますが、AtCoderの作問環境がどうなっているのか知らないため、なんとも言えません。別にwriterが多いわけではなく、原案を出したらF問題だったということが連続しているのでしょう。

富山県のいいところを教えてください

いつでもどこでも立山連峰が見えるところです。Twitterで何度か写真がバズってましたが、本当にこんな感じだったと思います(僕が印象を美化しているだけかも)。

いつもvimを使っているんですか?

コードゴルフの際にTeraPadを使うこともありますが、通常のコーディングでは常にVimです。

灰茶のあたりかなりアッパーしてますけど競プロの知識は元々あったのですか

そうですね。競プロを始めたのが2016年の5月で、AtCoderのコンテストに初めて参加したのがその年の10月でした。その間はAOJと螺旋本で勉強したり、情報オリンピックの予選問題を解いていたことを覚えています。

週記(2021/07/05-2021/07/11)

07/05(月)

先週の週記の続き。月曜日の典型90問084は余事象を考えるやつだった。先頭から順に見て、今何文字目かを答えに足し、現在同じ文字が何文字連続しているかを引く、というアルゴリズムを考え、Perlで書いて45Bになった。

さらにしばらく土曜日の典型90問083と格闘していた。まっとうな解法で縮めるのはあきらめ、例えば辺を適当に向き付けたら間に合わないかだとか、隣接リストの先頭500要素だけ見たら通らないかだとか、そういうことばかりやっていた。本当は隣接リストからランダムに選ぶのをsampleメソッドで行いたかったのだが、TLEしてしまった。実装を見たところ、n\ge 2個の要素を抜き出すときは「リストの先頭からn個取り、残りと入れ替えたり入れ替えなかったりする」というアルゴリズムで動くようで、常にリストの長さに対して線形時間かかるらしい。それもそうか。重複チェックするのも重いだろうし、重複を気にしないなら1つ抜き出すのをn回行えばよい。

crystal/array.cr at 3c48f311f98e95964d425abe23d2b353b7da07d1 · crystal-lang/crystal · GitHub

結局縮まなかった。布団に入って人の日記を読んでいたら寝落ちした。午前10時半くらいだった。

その後午後4時から午後5時まで目覚めていた形跡がある。ほかにYouTubeアプリで動画を視聴していた時間があった気もするが、よく覚えていない。

07/06(火)

午前0時半くらいに目を覚まし、昨日の典型90問が縮められていることを知った。42B。即座にスマホでコードを縮めにかかった。新しいアイディアとして「自分と異なる文字が最後に出現したインデックスを答えに足す」というのが思い浮かぶ。今回の問題だとこれが特に有用で、'o'文字コード111)と'x'文字コード120)のxorが23なので、$_に対して自分と異なる文字は$_^v23で得られる。

ここでv23Perlにおけるバージョン文字列で、文字コード23の文字1文字からなる文字列である。実際のところクオーテーションで直接埋め込んでも長さは変わらないが……。このバージョン文字列のテクニックは、特に古い問題で$/を書き換えた後に改行を得るため使われていた。v10だ。

version - バージョンオブジェクトのための Perl エクステンション - perldoc.jp

$$_=${$_}${$_^v23}を使うことで変数$o$xを自在に使い分けられるので、あとは片方に現在のインデックスを代入し、もう片方を答えに足せばよい。しかしピッタリ42Bだった。

寝たままずっと動画を見ていたが、午前4時に布団を出る。人の日記を読んだ後、ABC208-Eをoptさんのユーザ解説をもとに縮めたが、縮め切れておらずさらに短縮されてしまった。

ラノベを読んでいたら今日の典型90問の公開に微妙に遅れてしまった。今日の典型も星は少なめ。しかしどう解いたものか結構迷って、最終的に1012以下の高度合成数を求めて(プログラムはQiitaから拾ってきた)約数の個数が十分小さいことを確かめ、約数全列挙で通した。

コードゴルフについては、この方針でRubyコードが通るようだったが、やはり長い。約数全列挙しない方針はないものかと考え、1\le a\le \sqrt[3]Ka\le b\le\sqrt{\frac K a}を全探索することにした。a\mid Kという条件で枝刈りしてもRubyでは通らなかったが、Crystalでは素のまま余裕をもって間に合う。70B。計算回数はK=10^{12}でおよそ1.5\times10^8ステップくらいとなる。

昨日の典型90問をさらに縮めることに成功した。わざわざ${$_^v23}で自分と異なる文字の変数を持ってこなくても、$o+$xから引けばよい。これで41B、さらに出力部を改善して40Bになった。出力部の改善についてはほかにもいくつか適用できる問題があったため、探して縮めておいた。

atcoder.jp

$\に答えを保存しておくことで、ただprint関数を呼び出すだけで答えが出力されるというやつ。これまでは最後に;printとしていたのだが、このセミコロンは消せる場合がある。具体的には、直前の式を弄って無意味な比較などをし、得た偽の値=空文字列をprint関数に渡す。

昼までに橙diffを4問通した。先週の週記では問題リンクを貼っていたが、今日からは自分の提出へのリンクを貼ることにしよう。

Submission #24018337 - AISing Programming Contest 2019

かなり昔から、解法が2乗の木DPであることは知っていたはずだが、何度か挑戦して解けずにいた問題。しかし今見てみれば面倒なだけでかなり明らかだ。この問題が600点で最後に残った問題、のはずだったが、今調べてみると「Two Snuke」も解けていなかった。

Submission #24020011 - Code Formula 2014 本選

面白い。最大・最小の円盤の位置で分割することばかり考えていたが、それだと全然よくない。計算量評価をしようとすると、クイックソートの最悪計算量というのが思い出されて、そのつながりでマージソートにたどり着いた。そこからも微妙に面倒で、僕の実装ではiの杭にある円盤をソートされた状態で「iの杭に重ねる」関数と「j\ne iの杭に重ねる」関数の2種類を実装する必要があった。

Submission #24020511 - AtCoder Regular Contest 034

a_iの寄与にばらして求める。これは、a_iが引かれてからゲームが終了するまでに何枚bのカードを引いたかを全探索し、bの積は事前にDPで求めておくことで計算できる。値が非常に大きくなりそうでびっくりしたが、古い問題にありがちなdoubleで計算するやつだった。

Submission #24021063 - Yahoo Programming Contest 2019

結構難しい。行abには4通りの選び方があるが、これはaa\oplus bの選び方と等しい。同じことが列にも言えるので、結局入力の行列を標準形(これはWikipediaにあった用語で、単位行列が尻切れトンボみたいになっているやつ)に直すことができる。あとは簡単で、普通に線形時間かけて計算してもよかったのだが、2項定理を正負足し合わせて打ち消すようなことをすれば閉じた式で表せることに気づき、それに時間をかけた。しかもmodミスで1WA。

最後の問題のコードゴルフもした。行列のランクが求まればいいので、いつものnoshi基底を使う。\mathbb{F}_2行列の掃き出し法をするといえばARC054C-鯛焼きが思い出されたので、そのコードを参考にゴルフしていたら、ARC054Cのほうのコードも縮んだ。

atcoder.jp

昼過ぎ、学食に行く。ご飯の特大サイズの提供が再開されたらしいので注文した。

平常時はご飯(特大)を注文していたが、今日は提供されないらしかったので、迷った挙句ご飯(大)とご飯(中)を購入した。ちょっと多かったので、次回は中サイズを2つ注文することにしよう。

週記(2021/05/10-2021/05/16) - kotatsugameの日記

帰ってきてラノベを読んでいた。メールが来たのに気づいて確認すると、急に明日午後1時までのレポート課題が生えていた。実はこれは全然急ではない。数学基礎論の講義3回ごとに出されるレポートの1つなので、同様のものを今セメスターすでに2回提出している。今回は課題の提出場所を作っていなかったので今日になって課題が生えたように見えたというわけで、講義が3回ぶん溜まっていることを知りながらClassroomで資料を確認しなかった僕が全面的に悪い。

しかし、あと24時間で講義3回分の資料を読んでレポートを作るというのは……ヤバい。あまりにヤバいので現実を放棄して、読んでいたラノベをまず読了した。

「居候先の三姉妹がえっちなトレーニングを求めてくる」。タイトルから伺えるようにお色気路線のラノベで、実際巻頭のカラーイラストも設定・文章でもそういうシーンが多々挟み込まれるが、ストーリーとしては普通にスポーツを頑張っていて、純粋に面白かった。特に終盤出てきた悪役っぽい人がそんな悪い奴ではなく、主人公も悪印象を抱いていないようだったのがグッときた。初登場のシーンから受ける印象で悪役と書いたが、どちらかというとライバルだったのだろう。

満を持してレポート作成に取り掛かる。これまで講義の担当の教員が作成した資料を使用してきたが、今回のレポート範囲については、別のテキストの一部を著者の厚意により配布し、それに沿って進めるらしい。そちらのテキストのほうが丁寧でわかりやすいように感じた。

こうなることが明らかだったので、これまでの2回のレポートから一転今回はTeXを使用している。特に2重になっている角かっこllbracketrrbracketなどは1回打つだけでも頭がおかしくなっちゃうので、初めて自分でコマンドを定義したりしてみた。TeXプログラミング言語らしさを感じて楽しくなった。TeXチューリング完全

しかしこの調子で命題を3つ証明するのはさすがに面倒が過ぎた。終わったところで力尽き、午後9時くらいに布団に入る。そこからしばらくなろうを読んで、午後10時半就寝。

07/07(水)

午前5時起床。二度寝しようと思っていたがうっかりなろうに手を出してしまい、眠気が消えうせる。午前7時半くらいになって、今から寝るのはさすがにまずいということで布団から出た。

今日の典型90問を解く。解法は一瞬だが実装方針でちょっと迷い、コードを書いたり消したりしていた。しかし何とか書き上げて通す。どうやら今日こそはFAが取れたらしい。コードゴルフは素直なRubyコードで131B、ちょっと捻って128B。

昨日のレポートの続きをする。以前と同じく10問の問題から5問以上選んで解く形式。昨日で3問の問題が解き終わっていて、残り2つ。期限まで6時間くらいあるし簡単だろうと思っていたが、選んだ問題の1つが非常に難しく、かなり長い間考えていた。

ゲーム意味論におけるモデル検査ゲームに関する問題で、モデルMのグラフが2種類のラベルa,bを持つとき、始点から出発して「無限回aの辺を含むようなパスがあり、かつ無限回bの辺を含むようなパスはない」という意味の様相\mu論理式を作れ、という問題。無限回bの辺を含むようなパスを確実に検出するために、最初に\forallが駒を動かせるようにしたいが、すると今度は\existsが無限回aの辺を含むようなパスに行けなくなったりして、大変難儀した。

一度は不可能なのではないかと思って、不可能なことを極端なグラフをいくつか取り上げて論証しようとしたが、それを考えているうちに進展があった。つまり、\forallはゲームに負けないのが目的であって、誤った結果に誘導するのが目的ではない。これをもとに、最初に\forallが「今後駒を動かすのが\forall\existsか」を選ぶことで、うまく求める論理式を構築できた。(\mu x.\nu y.(\Box_b x\land\Box y))\land(\nu z.\Diamond z)である。

何とか解けて、5問完成。興が乗ったのでもう1問解いておいて提出した。期限の30分前だったので、まあまあ余裕があった。

今日も学食に行こうとしたが、外は雨が降っていたしなんとなく眠気もあるので断念。七夕なので特別メニューが提供されるという話があった気もするが、あまり興味はない。

なろうを読んだり週記を書いたりしていたら、昨日と今日の典型90問が縮められていた。昨日の問題はどこが縮んだのかわからないので諦めて、今日の問題について考える。冷静になると、Rubyの数値に配列のようにアクセスすることでその位置のbitを取得する機能を使っていないことに気づいた。それを使って124B。調べてみると、これも配列と同様に連続したbitを一気に取得するような機能が追加されていたらしい。なかなか面白いが微妙に使いにくく、今のところこれで縮むコードは思いついていない。

Integer#[] (Ruby 3.0.0 リファレンスマニュアル)

昨日解いた問題から1問コードゴルフをした後、橙diffをさらに3問解いた。

Submission #24046495 - Dwango Programming Contest 6th

前のほうを貪欲に取って最後全探索して無理やり帳尻を合わせる、ということを考えたが、この場合他の要素の後ろに来れないものがあった場合に破滅する。この破滅する条件を発展させると、前をいくつか決めたところで「必ず残りの列の先頭にいなければならない要素」が出現したときにそれを置くようにすればよいことがわかる。最後3要素はうまくやらないとこれまた破滅するが、そこの条件を間違えて1WA。

Submission #24048310 - AtCoder Grand Contest 019

ずらしつつ1を0にした後、最後に一気に0を1にする、という順の操作と固定してよいことがわかる。ここで最終的にずらす幅を全探索すると、ずらす途中に0にできる1とできない1が存在する。できないものについてはもう少し余計にずらしてつじつまを合わせる必要があるが、この時必要な幅を左右で計算しておいて、「全部左でつじつまを合わせる」状態から「全部右でつじつまを合わせる」状態に1個ずつ変換していく過程で左右で必要な幅の合計を毎回計算し、最小値を求めればよい。

Submission #24048744 - Dwango Programming Contest 6th

解法を覚えていた。あまりに衝撃的な数え上げ。しかもここで知っておきながら、すぐ後に出た似たような問題も落とした覚えがある。もう忘れないようにしたい。

今日の典型90問がさらに縮められていた。123B。僕のコードも、初期値が何でもよい変数を宣言するのに、配列の先頭要素を取得するn,=の空いていたコンマの横に押し込んで-1Bできた。これは悔しい。そもそも初期値がなんでもよいことを自覚していなかったようだ。

さらに橙diffを1問解いた。

Submission #24050436 - AtCoder Regular Contest 075

大きな桁は打ち消しあわないとダメだろと思っていたら、残りの桁全部が打ち消すことでもOKらしく、数ケースWAが出てしまった。最終的に大きな桁は極端な値しか調べないようにしたら通った。解説はもっと考察していて頭が良い。大きな桁じゃなくてもできるだけ打ち消しあっておく必要があって、少しでも残ってしまったら以降の桁はすべてその解消に専念する必要があるらしい。

RecommendationのEasyを下から解いてきたが、今一番下にはハシポンがいる。嫌なので見ないふりをしている。それ以外で次に解く問題を頭に入れ、午前1時半就寝。

07/08(木)

午前7時半、目覚ましにより起床。今日の典型90問の公開を待つ。二分探索+ワーシャルフロイドのはずが、焦って辺ごとに二分探索しようとしてしまった。さらに二分探索の初期値を間違えて1WA。散々な結果だ。

通してから布団に戻って二度寝した。午前8時から正午まで寝ていた。

起きたらABC208Cが縮んでいた。インデックスを含めてソートしていたが、そんな必要はなく、小さいほうからK%N番目の要素を持ってそれ未満か以上かを確認すればよい。これは僕の前最短コードのアルゴリズムがアホすぎたから縮んでいただけで、言語を変えればさらに縮めるのは容易。Rubyで通して取り返した。

午後1時からゼミに出席。発表を聞きながら橙diff3問にチャレンジし、2問通した。

F - Distribute Numbers

チャレンジ失敗。

Submission #24055458 - AtCoder Regular Contest 095

昨日の夜頭に入れておいた問題。右から見た累積minの更新点に注目すると、グラフでも1本のパスになる。残りの頂点はどうなるかなと思って考えてみたところ、全部葉になってしまうらしくてびっくりした。あとはパスをどちらから埋め込むかで2通り求めて、辞書順で小さいほうを出力すればよい。

Submission #24055865 - AtCoder Regular Contest 079

簡単。ループ部が問題だが、適当な頂点の現在のMEXを求めると、それがその頂点の値になるか、それともループで1つ先の頂点の値になるかの2通りしかない。

ゼミの最終版、今後の予定を教授が話している最中、急にパソコンが落ちてしまった。慌てて再度起動してZoomに入ったところ、すでに解散しており、教授に呼びかけられてちょうどよいからと面談が始まった。院試についてお話を聞けたりしてかなりありがたかった。教授だけカメラonなのはよくないかなと思い、僕もカメラをonにしたが、パジャマだし背景にはシャツが干してあるしでちょっと恥ずかしかった。

上でチャレンジ失敗と書いた問題をずっと考えていたが、全然解けそうにない。そうこうしているうちにコンテストの時間が近づいてきたので、別の橙diffを通してunique AC 4問にしておくことにした。昨日の最後に通した問題も、日付が変わった後なのでカウントに入っている。

Submission #24060381 - AtCoder Regular Contest 018

最小全域木の辺を交換して同じ重みの全域木を作ろうとしたら、同じ重みの辺と入れ替えるしかない。なので重みごとに辺を見て、辺の使い方の通り数を求める。これは行列木定理を知っていればやるだけ……に見えるが、全域木ではなく全域森を求める必要があることに注意。関係する頂点だけ抜き出して、森を仮想的な辺でつなぐ作業が必要になり、かなり面倒だった。

午後8時からTCO21 R3に出た。2完58位、レート2567→2538(-29)。R4通過らしく、まあ通行料かな……。

Easyは3種の文字の残りをキーに持つdp。僕の実装だと0文字の文字列で壊れて、サンプルにあって本当に良かったという感じ。

Medはより偏りが大きくなるように値をまとめた後、聞かれた回数が多いほうのバッグを判別するだけ。怖かったから慎重にやっていたが、通してみるとすでに黄色が無限人通した後でびっくりした。

Hardに挑戦したがシステス落ち。mapで平面を持ってひっくりかえせるだけひっくり返しまくるようなコードを書き、入力がランダムだからそう酷いことにはならないだろうと提出したが、落ちてしまった。正解は2-SAT。関係するマスが1マス飛んでいるのに惑わされたが、確かに2-SATだなあという気持ちになる。ただ読んでみたコードがどれも異常場合分けで辺を張っていて、かなりつらそう。

システス前はMedを通して80位ちょいだったのでヤバいなあと思っていたが、蓋を開けてみるとMedが焼け野原で、なんとか助かった。

yukicoder 303に出た。5完。

yukicoder contest 303 - yukicoder

A、Bはよい。Cは下のような感じ。Dは適当に深さ優先探索。Fのsolvedが多かったのでEを飛ばす。Fは寄与分を足し合わせる。ある数について考えるとき、それ以外の数は今注目している数より大きいか小さいかにまとめてよい、というのは最近のCF #729 div.2 Dで見た。

000001
000011
000111
112222
122222
222222

その後Eに1時間半ほど費やしたが解けず。僕が考えていた方針は、要素をK個選んでANDを取ることを繰り返し、その答え全部のORを求めるもの。取り出す要素の組み合わせはテストケースを見て選ぶので、場合によっては答え全部のXORを求めても合うようにできる。値を保存するためのレジスタがもう1つ必要で、どうしようもなかった。コンテスト後に解説を読んだところソートと書いてあり、椅子から転げ落ちた。テストケースが入力されるというのは完全なミスリードだったらしい。

ソートは簡単。a ba&b a|bにすればよくて、(a|b)==(a&b)^(a^b)であることを考えれば、まずXORを番地Nに保存して、in-placeにa&bを作り、最後にその2つからa|bを作ればよい。

コードゴルフ。まず、ACLのデータ構造の宣言について、コンストラクタ呼び出しがあたかもint型かのように代入で行えることを知った。

Submission #24067317 - AtCoder Library Practice Contest

また、下の問題の更新が流れてきて、見ると僕が以前提出していたC言語のものより短い式で計算していたので、それを参考にしてdcで書き直しておいた。多分テストケースハックだと思うが、1か所minを取らなくてもACできてしまい、これがかなり効いた。

Submission #24069050 - 第4回 ドワンゴからの挑戦状 本選(オープン)

布団に入ってすぐ就寝。午前4時だった。

07/09(金)

午前7時半、今日も目覚ましにより起床。今日の典型90問を通す。よくわからなかったが再帰関数で探索してよさそうだったので書いたら通った。枝刈りをしていることになって、それが効いているようだ。適当にRubyで縮めて184B。

布団に戻ってなろうを読んでいたが、正午くらいに就寝。午後6時起床。

サークル解説会の準備をする。今日はABC208で、C問題とF問題の解説をすることにした。と言っても、F問題の解説と書いておきながら実際は多項式補間のやり方しか書いていない。しかも書きあがってみるとほとんどWikipediaの記述そのままになってしまい、悲しい。

2021/07/09 定例会 | puzzleknot 公式サイト

yukicoderのコンテストに出る。8完。

競プロ典型 90 問 期末試験 - yukicoder

AからWAを出した。正規表現/../としたが、これは2文字以上であることしか判別できない。正しくは/^..$/。Bはよい。Cもよいはずだったが、平方根を求めるのに洒落っ気を出して二分探索したらオーバーフローしてしまい2WA。WAの原因に気づいたのがコンテスト最終盤だったのもつらいところ。Dは全探索。Eは10x10x10のテーブルを項番号で埋めていって、同じマスを参照したら差でKを割った余りを取る。Fは無料になる移動それぞれについて、それを使う場合の数を求めて全体から引けばよい。GはそのままとPを足した値の2つに対して二分探索でカウント。ARC092-D Two Sequencesで見た。

Hは非常に面白かった。典型90問で以前出題された、マスを左上から1つずつ埋めていく解法かと思ったが、できない。正解は、未決定の場所と決定済みの場所に分けて、スコアへの寄与を毎回足していくというもの。ABC025-D 25個の整数で見たことのある考察だったから、何とか思いつくことができた。

残り時間でIを考えていた。交差点の間で連続して2回以上受け渡しが行われる場合どうしていいかわからず、そのようなケースはないのでは?と思って実装してみたらサンプルが合わなくて終了。

深夜、昨日から引き続き考えていた問題に取り組んで、4時間くらいかけて通した。

Submission #24087155 - CODE FESTIVAL 2017 Final

前に見たアダマール行列だ!と思ってチャレンジしたが、とんでもない目に遭った。

手で実験すると(N,K)=(3,2),(7,3)が見つかる。N固定、K全探索で深さ優先探索をするコードを書いて回してみたところ、さらに(N,K)=(13,4)が見つかった。どうやら[tex:N=K2-K+1]らしい。実際、13より大きなNに対してはまともにプログラムが終了しなかったため試すのを諦めていたが、(N,K)=(21,5)のケースも深さ優先探索で見つけることができた。これ以上はさすがに無理なようだ。

以下、紙にある数字が書かれているか否かをビットで持つN\times N行列を解と同一視する。K=5の解の一例を下に示した。深さ優先探索で解を見つけているので、行列はそこそこ特徴的な形をしている。ここから攻めていこう。

000000000000000011111
000000000000111100001
000000001111000000001
000011110000000000001
111100000000000000001
000100010001000100010
001000100010001000010
010001000100010000010
100010001000100000010
100001000010000100100
010010000001001000100
001000011000010000100
000100100100100000100
001010000100000101000
000101001000001001000
100000100001010001000
010000010010100001000
010000101000000110000
100000010100001010000
000110000010010010000
001001000001100010000

まず、上端のK行と右端のK行はこの形で固定してよい。ビットをソートしたと考えれば納得できる。K'=K-1と置くと、残り注目したいのはK'^2\times K'^2の領域になるが、よく見るとK'\times K'のマスにK'個のビットが立っているような小行列を組み合わせた形となっている。小行列自体も4種類しかないようだ。

小さいケースで構築したものを用い、K'を1増やしたり倍にしたりすることでより大きなケースを構築するのがよいと考えたが、どうにもならず。ただ、K'を倍にすることを続ければ、K'=32のとき元のK=33となり、N=1057でピッタリ(?)解として提出可能なサイズになる。これが筋がよさそう。

ここまでが昨日考えたことだった。あとは小行列をいろいろ取り出して眺めていたが、進展はなし。

今日になって、小行列4種類というのが次のように分類できることに気づいた。

小/小\
大/0001
0010
0100
1000
0010
0001
1000
0100
大\0100
1000
0001
0010
1000
0100
0010
0001

これに0から3の番号をつける。番号はどれでもいいはずだ。番号で上で示した行列を解釈すると、次のようになる。

0000
3210
1320
2130

一番上の行以外は順列になっていて、さらに2つの行を取ってきてxorを取ると、それもまた順列となる。ちょっと考えると、これが成り立っていればよいようだ。順列とならなかった場合はxorが等しい列のペアが出現するが、そこで「2つの列で同じ位置に立っているbitがちょうど1つ」が満たされなくなる。

これはK'が大きくなっても扱いやすい。K'としては2べきのみを考えればよいから、K'=2^kとしておく。まず番号から小行列への変換については、小行列2^k種類は上の表をk次元にした感じで再帰的に見ていくことでできる。あとは番号だけ考えていればよい。問題は「0\dots 2^k-1の順列2^k-1個の組であって、どの2つの順列も要素ごとにxorをとるとまた順列になるような組」を構築することに換言された。

が、これもまあしんどかった。bitごとに見ればアダマール行列っぽくなるが、それをどのように重ねるかがわからない。順列をひたすらシャッフルして頑張るプログラムで2^32^4の解は見つかったが、2^5は無理そう。そこで2^3の解をひたすら睨む。

00000000
01234567
05142736
04376251
06715324
07521643
03657412
02463175

アダマール行列(の-1を0に置き換えたもの)の各行を次のように番号付けよう。

0:00000000
1:01010101
2:00110011
3:01100110
4:00001111
5:01011010
6:00111100
7:01101001

これを用いて見つかった解を表すと、1bit目が上の行から順に01326754、2bit目が02463175、3bit目が04157362であったようだ。1bit目が昇順に並ぶようにソートすると012345670264573104512673。これもまた3bitと見て桁ごとに分解すると、それぞれ124436243。2bit目と3bit目を入れ替えると124243436。ここにきてようやくパターンが見えてきた。つまり、{1,2,4}から隣接する項のxorを取って{1,2,4,1^2,2^4}、この隣接する3要素を抜き出す感じ。

これを実装して試してみると、K'=2^4K'=2^6ではうまくいったが、K'=2^5ではダメだった。かなり絶望しかけたが、ふと隣接する項のxorではなく1つ飛ばしに取ってみたところ、構築に成功した。

喜びのツイートをしたらmaspyさんに射影平面の直線を利用した構築があることを教えてもらった。スゲー。

Distribute Numbers(CODE FESTIVAL 2017 [F]) | maspyのHP

これは性質が適切すぎるが、より一般に、対称性があるものを構築するときは数学の言葉で説明するのが簡潔になりがちだと感じる。また上で用いたアダマール行列というのを筆頭に数学の経験から得られる構築の手順もある。こういったものに慣れていないならば、数をこなすことで身に着けていくしかない。アダマール行列はちょうど半年くらい前にコンテストで出たので、知っていた。

現在のD問題の最短コードはアダマール行列を利用した解法になっている。

週記(2021/01/11-2021/01/17) - kotatsugameの日記

日記を書いていたら朝になった。土曜日の典型90問を解く。セグ木のノードにvectorを持ってもいいのでは!?と思って書いたが、手元で適当に生成した最大ケースでは当然のようにTLE。ACLのセグ木は参照渡しできないからダメだ、と思って書き直していたが、これも全然通らなかった。多分セグ木上の二分探索が重すぎるのだろう。

全然ダメだったので改めて考え直すと、尺取り法で解けることが分かった。転倒数は数列の先頭・末尾を弄っている限りは簡単に差分更新できる、というのはABC190Fで見た覚えがある。

午前10時半就寝。

07/10(土)

午後4時過ぎに弁当を受け取るため起床。その後布団に戻って二度寝しようと思ったが、うっかりYouTubeアプリで動画を見始めてしまい、眠れなくなった。午後6時くらいに諦めて布団から出た。

昼過ぎにyukicoderでコンテストがあったようだ。2問構成で、1問目は普通の拡張ダイクストラ、2問目は星5で論文などが参考資料として掲出されている。1問目だけ通しておいた。

No.1601 With Animals into Institute - yukicoder

ABCが始まるまでの時間で橙diffを1問通した。

Submission #24099997 - NOMURA Programming Contest 2021(AtCoder Regular Contest 121)

つい最近の問題。その日の日記を見たところ、解説で1行目だけ読んだということが書かれていた。なんとなく記憶が蘇ってくる。解説では「頂点iにはiの子孫であるような頂点の番号を書き込むことはできない」と書かれているが、問題文をただ解釈しただけでは子孫ではなく親となるべきはずで、意味が通らない。これについてTLに質問を投げると、逆順列についての言及が返ってきたのだった。つまり、問題文では「頂点a_iから頂点iに到達できない」となっているが、このia^{-1}_iを当てはめて「頂点iからa^{-1}_iに到達できない」と読み替えるということ。

逆順列を考えると自分の子についての条件になって扱いやすくなるらしい。

週記(2021/05/24-2021/05/30) - kotatsugameの日記

今日の挑戦で最初に選んだ方針は、コンテスト中と同じで「自分の子でまだ値が決まっていない頂点数」をdpのキーに持つものだった。愚直に書いてもサンプルが合わずに絶望していたもの。この方針だとあまり逆順列を意識しなくても書けるな、と思いながらとりあえず愚直な遷移を書いたら、今日はサンプルが合った。これは来た!と思ったが、そこから高速化できなかった。係数をうまく分離して畳み込みなりするのだと思っていたが、この分離が全然できない。lrからの遷移先は0\le x\le l0\le y\le rのそれぞれに対して存在し、係数には4つの変数が入り混じって存在する。

結局方針を転換し、包除原理で解いた。当時のTLで見聞きしたことを覚えていたのかもしれない。この方針だと逆順列を意識するのがかなり効く。

もうすでに眠くなってきているが、ABC209に出た。全完24位。

AtCoder Beginner Contest 209 - AtCoder

Aはよい。式の値が負になる場合のケアもすぐ気づけた。Bは割引額が\left\lfloor \frac N 2\right\rfloorだとわかる、と思って書いたがWA。入力を1行目しか受け取っていなかった。アホ。

Cは難しい。しばらく考えると、A_1\le A_2の場合の先頭2要素について場合の数がA_1(A_2-1)となるとわかる。これを一般化して、Aを昇順ソートして引きつつ掛けていけば求まる。Dは最近作ったLCAライブラリを使いたくなって、あまり考察せずに貼り付けて通した。

Eはかなり難しい。文字列を有向辺と思うと523頂点のグラフになる。出次数が0の頂点は当然負けで、そこからトポロジカルソートの要領で決めていけ、ループ上の頂点は引き分けになるのだろうと思ったが、WA。ほとんどのケースで答えが間違っているらしい。しょうがないのでループを検出するメモ化再帰を書いたが、これもWA。実はトポロジカルソートから微妙に変える必要があって、ある頂点から出る辺の先にある頂点が全部決定する前であっても、負けの頂点に遷移できると分かった時点で勝ちだと決定させてしまう必要があった。これはメモ化再帰でも実現できていたのだが、そちらはループ検出のために途中に置いたフラグを毎回クリアしなければ正しく検出できず、逆にそれをすると計算量が増えてしまう。

Fは簡単。隣り合う項との順番にしか興味がないので挿入dpができる。遷移は一見O(N^2)に見えるが、ある値以上・以下の要素を全部足しているだけなので上から・下から累積和を取ればよい。

コードゴルフをする。A問題は開始16秒で提出した8Bだろうと思っていたが、7Bがあった。?r-1+ではなく1?--のほうが短い。これは何度も見たことがあるはずだった。以下のツイートはABC180の時のもの。

Bはdc。\left\lfloor \frac N 2\right\rfloorではなく\frac N 2でも通るようだった。他に、N=1の場合の対応をしなくても通ったことを利用して微妙に縮めている。CはPerl

Dは、LCAなど持ち出さずとも深さの偶奇が異なることさえチェックすればよかったらしい。頂点間の距離の偶奇にしか興味がないので、LCAを求めても関係する項は\bmod 2で消えるというわけ。とりあえずRubyで通したがPerlで書いたほうが格段に短い。Perlでグラフの入力受け取り・dfsを行うコードは、典型90問のコードゴルフでいくらか新手が出て整備された結果、シンプルになりすぎて取っつきようがない。

Eは適当にRubyで書いておいた。ゴルフしていない。Fは2方向から累積和を取る関係でOctaveが強いはず。

今日のdifficultyもなかなか崖が大きかった。Cまで灰色、Dが茶色、EFが黄色。Cは難しいと思ったが、AtCoderで数え上げが出すぎた結果この程度なら普通に解けるように訓練されているらしい。

CF #731 div.3に出た。pretest全完10位。

Dashboard - Codeforces Round #731 (Div. 3) - Codeforces

Aは面倒。x座標とy座標のどちらかが全ての点で等しく、かつ障害物が2点の間にある場合だけ関係する。Bは'a'を探して、左右から貪欲に取る。Cも貪欲。Dは、どこかのbitを打ち消すくらいならそれ以降常にそのbitを立てるほうが辞書順で小さくなるので、xorではなくorだと考えてよい。Eは線形時間でやってほしそうな雰囲気を出していたが、思いついた方針がだいたい0-N BFSと同じだったので、面倒になってdijkstraした。Fは素因数ごとに見るのを考えたが、素因数が多すぎて間に合わなさそう。列を倍にしたセグメント木上で二分探索した。GはSCCして、内部に辺を含むような強連結成分を通ったら-1になる。

終わってみると順位表の1ページ目に日本人が10人いてかなり面白かった。Eは左右から累積minすると線形時間になるようだ。頭がよい。

典型90問089がRubyで通されていたので、自分もやってみる。そこそこ普通に通るようだった。しばらく格闘して現在報告されていた最短を更新したが、実は報告し忘れでもっと短いコードになっていたらしい。悲しい。嘘です、報告してくれるだけで嬉しいです。

眠気に耐えかね布団に移動。ちょっとだけなろうを読んで午前3時半に就寝。

07/11(日)

午前8時くらいに目を覚ます。典型90問の投稿までもうちょっと寝ようと思ったが、結局なろうを読んでいた。

今日の典型90問を解く。今日は10点満点。最初、頭が働いていないのか全く何も思い浮かばず絶望していたが、小課題をどんどん進めていく方針で無理やりにでも考察を生み出す。といってもK=1の場合は隣接2項がどちらも1にならなければよくて、N=K=6は何やっても解けて、それ以降は途端に難しくなる。

とりあえず、数列の値としてはKを割ったあまりでまとめて考えることで\sqrt K種類しか考慮しなくてよいことに気づいた(実はこれはなくても解ける)。次いで、l=\left\lfloor \frac K a\right\rfloorとなるようなaたちの置き方について考えるときは、l-1の場合をいくつか並べて間にaとしてありうるどれかを置く、というdpで求まることに気づく。これは、l-1の場合とa1つを組にして一度に遷移し、最後に1つずつずらすことで求まる。l=Kの場合まで求まったら、あとは同様のdpを長さNで行うことで答えがわかる。これをナイーブに実装したら大きめのサンプルが合った。

このdpは遷移がインデックスによらないということで、多項式で表現できそうな見た目をしている。遷移をfと置くと、(1+f)^\inftyを適切な範囲で求めればよいのかと思ったが、これは遷移を選ぶ順番も考慮してしまい合わない。正解は1+f+f^2+\dots=\frac 1{1-f}で、多項式の除算はライブラリを持っていないのでどこかから窃盗してくることが確定した。とりあえず拾ってきたライブラリを貼ると、ちゃんとサンプルは合ったまま、計算量だけが落ちている。

最後のdpだけはx^Nの項を求める必要がある。高速きたまさ法が使えるので、それまで実装されているライブラリを新たに探してくることにした。それを参考に今貼り付けてあるライブラリから新たに実装しようと思ったが、やはり中身を理解していないアルゴリズムをその場で書くのは難しく、結局見つけたライブラリに置き換えてしまうことにした。verifyコードを見つつ書き換えてサンプルを試すと答えが一致し、最大ケースでも十分高速に求まる。提出するとAC、261msだった。Nyaanさんのライブラリを使用したのだが、いろいろ闇の魔術を使っていて、熱意に唸らされる。

線形漸化式の高速計算 | Nyaan’s Library

解法50分ライブラリ窃盗50分みたいな感じで、都合100分弱でAC。かなり手ごたえがあった。コード長は40000Bを超えている。

提出する直前に宅配が来た。

布団に戻って4時間ほどなろうを読み、午後3時に就寝。午後6時半ごろに起床。

昨日のCF div.3のシステスが終了し、ちゃんと全部通っていた。

午後7時に典型90問のコンテストが終了。統計情報を聞くと、全体の提出のうち1%が僕によるものだったらしい。

直ちに提出がすべて公開されると思っていたのだが、まだ凍結が解除されない。どうやらYouTubeで行われる閉会式の後、午後10時くらいまで待つ必要があったらしい。その間に日記を書いていた。

www.youtube.com

3位だった。これまで89問すべて解いた人の中で最終問題を解いたのが3番目だったということで、最終問題だけで見れば5番手以降となる。

午後10時半くらいにすべての提出が公開されたので、001から順に最短コードだったり自分のコードとのdiffを確認していった。複数人のコードがほとんど一致しているものがいくつかあり、例えば001なんかは変数名と改行位置の違いを除いて4人が同じコードを提出していて面白い。以下のリプライツリーに、特筆すべきであると感じたコードについての言及を連ねておいた。

といっても、典型002は正規表現の改善で-1Bされてしまったのだが……。公式ドキュメントの\gの使用例が「正しい括弧列にマッチする正規表現」そのもので、等価な書き換えをするだけで縮む。

それ以外にもいくつか覚えておきたいコードがあったので、ここに書き残しておく。

典型013:Submission #22965470 - 競プロ典型 90 問

eval(dir()[N])(ただしNは適切な定数)で長い関数名を省略するテクは使っていたが、dir(G)とすることでGに関連付けられた関数名が得られることは知らなかった。公式ドキュメントを見ると「有効な属性のリスト」とある。

組み込み関数 — Python 3.9.4 ドキュメント

典型016:Submission #24168759 - 競プロ典型 90 問

min_ofというメソッドがあるらしい。min_byはargminを返すが、このメソッドはminの値そのものを変えす。RubyにはないCrystal独自のメソッドで、こんな便利なものがあったのかと魂消た。

Enumerable(T) - github.com/crystal-lang/crystal

典型055:Submission #24171449 - 競プロ典型 90 問

each_combinationsには第二引数があって、そこに真と解釈される値を入れると速くなるらしい。

each_combinationsを使用してイテレータを用いるとよいのではないか、とも考えたが、こちらも結局TLEしてしまった。

週記(2021/05/31-2021/06/06) - kotatsugameの日記

実装を読んだ。第二引数はreuseという変数である。これが真である場合、reuseには新しく取り出す個数分の長さの配列が確保されて代入される。

crystal/array.cr at 4401e90f001c975838b6708cc70868f18824d1e5 · crystal-lang/crystal · GitHub

イテレート中にpool_sliceという内部メソッドが呼び出される。ここでreuseが使われ、reuseに配列が代入されているならそこに値を詰め込むが、そうでないなら毎回配列を確保する、という実装らしい。この再確保のオーバーヘッドがなくなることで、TLEが解消されるということのようだ。

crystal/array.cr at 4401e90f001c975838b6708cc70868f18824d1e5 · crystal-lang/crystal · GitHub

典型089:Submission #24169798 - 競プロ典型 90 問

昨日格闘していた問題。どうやって縮めたのか気になっていた。配列ではなくHashを使うことで、座圧をせずにBITを実現している。必要なところだけ作るセグ木、あるいはBinaryTrie木と理解できる。これで間に合うというのも驚きだ。

典型90問の問題がAtCoder Problemsに追加されて、最短コードが1600を超えた。

そのほか、Longest Streakが48日になったりしていて面白い。日曜日以外は典型90問で新規ACがあって、日曜日はコンテストがある、ということがかなり長く続いていたようだ。

朝方、数理統計学の講義資料を3回分読んで、1つだけ設定されていた課題を提出した。残り2回分あるが、こちらは課題がないようだ。実質後は期末レポートのみ。

週記(2021/06/28-2021/07/04)

06/28(月)

先週の週記を投稿してからの話。まずラノベの新刊チェックをした。そういう情報がまとまっているサイトで調べて、気になるものをhontoのサイトでほしい本に追加する作業。本屋では基本的にそれを見ながら本を探している。

今日の典型90問がツイートされた。今日は星2。まともにグラフを作るのは長くて、辺(u,v)(ただしu<v)についてdeg[v]++などした後、deg配列を見ればよい。あるいは、deg[v]の更新のタイミングで答えに±1するのでもよいだろう。後者をAWKで実装したら45Bになったので、これを自動で提出する設定にしておいた。

先週の典型077のコードゴルフをしていた。C++ACLを使う。自分の二部マッチングライブラリでも通るようだったが、それをわざわざ実装するのはやっぱり長くなりそう。自分のライブラリは蟻本の二部マッチングから下の記事を参考にちょっと高速化しているやつで、蟻本の実装そのままだと結構シンプルになるが、それで通るのかは確認していない。

snuke.hatenablog.com

しばらく頑張って縮め、現在報告されている最短コードを更新できたのだが、実はclimpetさんがツイートし忘れていただけですでにもっと短い解が存在するらしい。残念。

次に典型073のコードゴルフ。以前、今見ている頂点と同じ文字を持つ頂点であるかどうかだけ考慮すればよいという話を聞いていたので、そのようにして持つ値を2種類に減らす。正しい答えが出るようだったので適当に縮めたら、現在の最短コードを更新できた。

なろうを1作読んだ。「世界から天才音楽家と呼ばれた俺だけど、目が覚めたら金髪美少女になっていたので今度はトップアイドルとか人気声優目指して頑張りたいと思います。」というやつ。以前TLで流れてきて、そこそこ好きそうな設定だったので後から読もうと思っていたもの。

https://ncode.syosetu.com/n2658gz/

いざ読んでみると、30話ちょっとですでにエタっていた。セリフのノリもあまり肌に合わなかったので、連載が続いていても読み通せたかは謎。内容については、風呂敷を広げる段階で途切れているので何とも言えない。

今日の典型90問がAtCoderに公開され、自動で提出したコードがちゃんとACできていた。しかし即座にbash 43Bが報告される。どうやらsort|uniq -uで1回しか出現しない要素を得るのが強かったらしい。悔しいのでしばらく考えていたが、Rakuを使用することで40Bまで縮んだ。各行2つの値のmaxを取るのもかなり短いし、出現頻度のカウントはbag一発でできる。1回しか出現しない要素だけ抜き出すというのは、対称差集合を用いて[(^)] listでも求まるようだったが、65536要素以上のlistを適用することができないらしくREしてしまった。REしなくてもTLEになるかもしれない。

ラノベを1冊読んだ。「VTuberなんだが配信切り忘れたら伝説になってた」。元はハーメルンで、ハーメルンから書籍化というのはあまり聞かない(最近偽聖女クソオブザイヤーが書籍化発表されたくらいか)のでびっくりしていたが、帯を見るにマルチ投稿しているカクヨムからの書籍化だったらしい。ちゃんと調べると偽聖女クソオブザイヤーもカクヨムとマルチ投稿だった。以前ハーメルンで読もうとしたときは序盤でページを閉じてしまったが、今回本になったことで再挑戦。

文章としては、ところどころに例のアレネタが挟まれており、商業として大丈夫なのか心配になるような人を選ぶものだと思うが、内容は面白かった、あるいはやけに惹きつけられた。主人公の人柄のくだりは好ましいし、ほかのVTuberとの絡みも微笑ましく感じられる。VTuberにハマる人はそういう関係性にも惹かれているのだろうか。この本を読んで、一度VTuberを見始めると抜け出せなさそうだと感じたので、これからはもうちょっと慎重に距離を置きたい。空想のVTuber(?)はよいが、現実に存在するVTuberにのめりこむのはまずい。

午後7時就寝。

06/29(火)

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

毎週午前3時にClassroomに講義資料を投稿する教員がいて、親近感を感じている。

週記(2021/06/21-2021/06/27) - kotatsugameの日記

今週もピッタリ午前3時だった。これは毎週その時間帯に活動しているということで、むしろ生活リズムが安定している側の人だったらしい。

なろうを読んだり動画を見たりして、午前7時前にまた寝落ち。次、午前10時半に起きた。

今日の典型90問を解く。左上から貪欲でよさそう。コードゴルフ的にはかなり面倒そうなので、あとは実際にジャッジが公開されてからということにする。

まだ寝足りない気がしたので、眠気を求めてずっと布団でスマホを触っていたが、どうにも眠れなさそうだったので、諦めて起きた。

大学院について調べてみた。あまり住環境を変えたくないという思いがあるので、東北大学の院に進学したい。あとはまあ、競プロに近いことができればいいなと考えて「情報科学研究科」というところを調べてみた。研究室一覧を見てかなり興味がわいたが、出願の方法を確認すると、ほとんどの研究室でTOEICなどの試験の記録が必要らしい。ないので、もう無理。

おとなしく数学科の院に行くことになるだろう。こちらは試験の記録は必要ないようだ。だから周りでTOEICの話を聞かなかったわけなんですね。

今日の典型90問が公開された。問題文をよく読むと、操作回数の最小化をする必要があってちょっとびっくりするが、冷静になると貪欲でよいことの理由から最小化にもなっていることがわかるので、よい。オーバーフローの危険性に気づけたのもよかった。実際、現在存在するテストケースにおいては、配列の値は収まるが答えの値はオーバーフローしてしまうようだ。コードゴルフとしては、Yes・Noのチェックをどれくらい行うかも重要。いろいろ試してみたところ、僕の実装だと一番右下が非ゼロかどうかを見ればよいことになった。正当性はわからないが、ACしているのでこれでよい。Ruby 134Bで満足していたが、実はPerlで書き直すともっと縮む。97Bになった。

先週の土日にyukicoderでコンテストがあったが、その時間は眠っていた。upsolveをする。

灘校文化祭コンテスト 2021 day1 - yukicoder

灘校文化祭コンテスト 2021 day2 - yukicoder

まず1日目から。Aはよい。Bは真面目に解いたが、提出する段階になって実はだいたいYesではないかと感づいた。実際、最短コードを見てみるとN=1のときだけNoらしい。Cはソートする。DはBFS。Eは、任意の2x2領域の和が0で、3つ斜めに並んだマスの和が1であることに気づけば、(1,1),(1,2),(2,2),(2,3)の4マスを決め打つことで残りのマスを決めていける。実際10x10のマスを生成するコードを書いて確認すると、すべてのマスが1である場合以外は条件を満たさない5x5の正方形領域が存在するようだった。

ここでコードをいったん消してN\le 4の場合は2^{N^2}の全探索、N\gt 5の場合は全マス1の場合だけ調べるコードを書いたが、WA。冷静になって先ほど書いた実験コードの出力を確認すると、5x5、6x6の場合はギリギリ矛盾しないような決め方が他に存在することに気づいた。このサイズだとマスの全探索はできず、しかし実験コードは消してしまったので、泣きながら再度同じコードを書いてAC。コンテスト中に書いたコードは消さないようにしよう!実はこれ毎月のペースでやってます。

Fから解けないので、2日目に移った。Aは周期N+1の数列になる。Bはどこかで見たことのあるような、適切な比較関数でソートするやつ。

Cを考えていたがWAが取れず、そのうち椅子でちょっと寝てしまったので、これはまずいと布団に移動して再度寝た。午後10時だった。

06/30(水)

午前1時半くらいに一瞬起きたらしい。またすぐに寝て、次に午前5時半に起床。月曜日に縮めた典型073が縮め返されていた。

昨日の続き、C問題を解いた。昨日の時点で分かっていたことは、Tが偶数なら頂点1に接続する辺の重みを\frac T 2とすることで達成可能であること、TNの倍数ならすべての辺の重みを\frac T Nとすることで達成可能であること、またN=3の時は常に達成可能であることの3つ。このうち解法に関係するのは1番目の考察のみであった。

1番目の考察とは逆に、頂点1に接続しない辺の重みを\frac T{N-2}とすることでも達成可能である。これはN=3の時常に達成可能であることの理由となる。さて、これらを別個に考えてもWAは変わらなかった。実はこれらは組み合わせることができる。つまり、すべての辺の重みが0であるグラフを考え、ここに辺の重みを足して求めるグラフを構築することを考えると、サイクルの重みに2加えることとN-2加えることが独立に行えるということ。2つを組み合わせるとN加えることは可能なので、これは考えなくてよい。

つまり、T=2k+(N-2)lとなるような整数k,l\ge 0が存在すれば構築できるということで、これを調べたら通った。ちゃんとすべての場合が尽くされているかはよくわからないので解説を読んだ。Nが偶数のとき奇数のTが達成できないことの証明は面白かった。T=1で構築できないこともよい。あとはN=7T=3のとき作れないことを調べる必要があるが、解説では全探索していてびっくりした。まあ言うだけならそういうものか。

Dはサイコロ問題だった。これを機会にサイコロライブラリを作ろうと思ったが、設計をどうするかなどいろいろ悩みどころがあるので、後回し。ここで、あさかつの並走者を募集するツイートを見かけたので、yukicoderを途中で切り上げて参加してみた。

当然全問解いたことがあるわけで、単純に出るのでは面白くなかったのでPythonを使ったのだが、思ったより遅くてびっくりした。PyPyで出しなおしてAC。大体の場合は最初からPyPyで出すようにしたほうが良いのだろう。Pythonのほうが速くなるケースもあるという話は聞くが、そのあたりまで調べて覚えておくほどPythonを使う動機はない。

最終的に、定数倍高速化を頑張ってすべての問題をPythonで通しておいた。

atcoder.jp

全然通らなかったので、ほかの提出を参考に二分探索の判定関数だけ切り出したらかなり速くなった。その状態で6回くらい投げたら通った。

今日の典型を読む。すんなり包除原理が思いつけてよかった。

yukicoderのupsolveに戻る。E問題は総和記号をいろいろ分解すると1\le i\le mに対して\left\lfloor\frac n i\right\rfloorが分かればよいので、商の値でまとめて遷移するコードを書いた。前は苦手意識があったが、「\left\lfloor\frac n i\right\rfloor=rとなる最大のii=\left\lfloor\frac n r\right\rfloorである」ということを念頭に置くとだいぶ見通しが良くなった気がする。Fは星5だしsolved 2なので読みすらしなかった。

さらに、コンテストとは別に問題が追加されていたので、2問解いておいた。

No.1576 織姫と彦星 - yukicoder

No.1577 織姫と彦星2 - yukicoder

どちらもBFS。前者は簡単で、各頂点からは毎回全頂点に対して遷移できるか調べる。後者はこの遷移を高速化する必要があるが、ハミング距離1の頂点を調べればよいということで、どのビットが異なるかだけ全探索してmapなどで頂点番号を求めればよい。

学食に行ったり本を読んだりしているうちに今日の典型のジャッジが公開されていたので、解く。問題なくAC。そのままRubyコードゴルフもしたが、1900ms台と結構ギリギリだった。105B。

ゲーセンに行く。今日は夕食・本屋を挟んで午後3時から午後11時。進捗としては、RebellionでSSを出して、現在解禁してある14の未SSが混沌だけになったことと、13のAJが3譜面出たこと。これで13のAJが99譜面になったので、100譜面目としてHalcyonをプレイしていたのだが、3時間くらい連奏しても出ずに閉店時間となってしまった。

最初はそこそこ押せていたのに、連奏し続けるといたるところに癖がつく。擦りなどを交えてごまかしていたが、「ちょっとヤバそうだけどまだ何とか押せていたところ」で緊張に負けて出してしまった。そういうことが何回かあったが、そのあとも最後まで通ってしまうと特別辛い。ちなみにこの部分はこの後、左手2鍵で押していたのを右手2鍵に変えた。

閉店間際はここがマジで通らなくなった。AJ動画など見ると、いったんスライドを離して素早く流すのがよさそう。僕も今日の始めのほうではちゃんとできていたはずだったが、スライドを離すタイミングを見失った結果全然ダメになった。もしくはタップスライドの速さが違うのかもしれない。

疲労困憊して帰宅。何とか風呂に入り、洗濯機を回した。日記をつけようと思ったが、タイプしている最中に瞼が下りていって、本当のブラインドタッチをしていることに気づく。さすがにまずいと思い、何とか洗濯物を干して即座にベッドに倒れこんだ。即座に就寝。午前1時半だった。

07/01(木)

正午、起床。今日の典型90問はちょっと考えたが、2次元平面にプロットして正方形領域の和をとればよい。

食事してゼミをした。ゼミの間に日記を書いたりしていた。今日も1コマぶんの時間で終わり。二項係数が絡む等式の証明に微分が登場してびっくりした。総和記号の中に現れるk^nという項を消すために、k^n=\left.\left(x\frac{dx}x\right)^n x^k\right|_{x=1}という式変形を行っていた。これでkが指数に行き、二項定理を用いることができるようだ。

今日のゼミは1コマ分で終わり。来週もそう。

週記(2021/06/21-2021/06/27) - kotatsugameの日記

ゼミが終わってからもしばらく日記を書いていたが、午後5時くらいになって典型90問のジャッジが公開されたため、通しておいた。

月が変わったので6月の読書記録をツイートした。先月は、何度か週記に書いていたように、なろうにすべてを破壊された月だった。なろうばっかり読んでいてラノベを読んでいないからと言って新刊を買わない理由にはならないので、積読は増える一方である。なろうを読んだ量を記録することも考えたが、難しいし、第一なろうと商業の小説では文章を読むにあたっての精度が違う。結局、文章自体は先月もたくさん読んだが、記録には表れない。

典型90問のコードゴルフを少し行う。スクリプト言語だと通りそうになかったので、C言語コードゴルフして205B。

本を1冊読んだ。「私立シードゥス学院」2巻。全寮制の学園で、寮が複数あってそれぞれ特色があったりし、コテコテの設定が面白い。基本3人称で描かれるが、微妙に各人の内心が入り混じって変な感じがするのと、セリフから発話者の区別がつきにくいので読みづらさはある。日常の謎ミステリとしていい感じだが、帯に「水平思考ミステリ」と書いてあるのがよくわからない。

確かに1話1話、それっぽい問題が最初に書かれていて、それに沿うような形で問題編が描かれ、次に解決編に進むというような構成になっているので、水平思考ゲームを意識してはいるのだろう。しかし日常の謎が水平思考ミステリに翻訳できるというのは、それは当たり前のことではないだろうか?ちょっと特殊なシチュエーションから意図的に情報を抜くことで不可解な状況を作りだす、というのが水平思考ゲームの問題作成であると考えているので、それに照らしてみれば日常の謎を水平思考ゲームの題材として扱うのはほとんど常に可能なように思われる。この本が何か特別なことをしているようには感じられず、帯に特別「水平思考ミステリ」と書くことの意味が見いだせなかった。

と、ちょっと難癖をつけたが、話としては良いと思う。今巻は寮長という存在にスポットライトを当てているようで、各寮の特色を体現している寮長というのも先に述べたようにありがちな設定だが、だからこそ面白い。

さらにラノベを読み始めたが、今日が期限だった論理学のミニットペーパーに気づいた。講義動画を適当に飛ばしつつ見て提出しようと思ったのだが、今日の内容はなんだか哲学的でよくわからなかったというのが正直なところ。Yes・Noで答えられるようなありとあらゆる質問に答えられる機械は意味を理解していると言えるだろうか?という話だった。その部分の講義動画を飛ばさずに見ても、特にコメントが見つからない。しばらくウンウン唸り、画像認識の機械学習シベリアンハスキーと狼を見分けさせるときに教師データに偏りを持たせると、背景の雪の有無で区別するようになった、という話を書いて提出した。つまり、機械に我々が思う意味を伝えることができていない、ということを言っているつもり。何を書いても的外れな気がして非常に苦労した。

今日の典型90問がRubyで通されていた。通らないと思ったのだが……。実際、通ることを知った今もどうやって通しているのかわからないので、勝てない。

椅子で一瞬寝てしまったので、布団に移動して本格的に寝た。午前0時半就寝。

07/02(金)

午前4時半起床。昨夜読み始めたラノベを読んで、午前7時くらいに再度就寝。その次は午前11時に起床した。

昨日シャワーを浴びていないだけなのに頭皮がかゆくてたまらない。シャワーを浴びると多少目が覚めたので、ゴミを出して学食に行き、さらに床屋にも行った。

相手はマスクをつけながら髪の毛を切っているわけだから、話しかけられるのはまあ良いのだが、こちらはマスクを外しているのに受け答えしてよいものか困る。まあ無言だと社会性がヤバいので頑張って会話するのだが、相手方はマスクもつけず喋り散らかす自分をどう思っているのだろうか。まあうっかりコミュニケーション能力がありそうな振る舞いをしてしまった自分に非がある。

帰ってきたら今日の典型90問のジャッジが公開されていた。今日のはまあどうやっても解けそうではあるが、短くする方法は特に思いついていない。とりあえず通して、次に昨日の典型を再度考え直していた。昨日は二次元累積和を取ることしか考えていなかったが、二次元imosで計算することで多少コードが縮むようだった。Cで196B。Rubyには全然勝てていないし、計算量がよくなったわけでもない。

今日の典型90問のコードゴルフを行う。まずRubyで書いて、次いでVimRubyコードを構築する方法で縮めたが、dcで通るのでそれが一番短くなる。10のべき乗をどこまで考えるか、ということについてはループを回していたが、実は桁数を得るコマンドZを用い、等比数列の和を求めることで閉じた形で書き表せることに気づいた。これで大幅に縮み、最終的に41Bになった。Zは0に適用すると1を返す、つまり0の桁数は1であるという風になっていて、視覚的には正しいが数学的にはあまりうれしくないように感じられる。実は変形の過程で(0,R]-(0,L-1]ではなく[1,R+1)-[1,L)の値を求めるように変わっており、Zを使っても一貫性のある値が得られたというわけ。

ラノベを読んだ。「史上最強オークさんの楽しい種付けハーレムづくり」5巻。ひどい題名なのであまり公然とは言及できないが、内容はテンプレ異世界転生チーレム無双なので、面白くないということはない。

今日のサークル解説会の準備をする。今日はABC207-Fの2乗の木DPを扱うことにした。

僕が知っているのは計算量T(N)T(N)がT(l+r)=T(l)+T(r)+lrT(l+r)=T(l)+T(r)+lrを満たすことからT(N)=O(N2)T(N)=O(N2)を示す方法で、シンプルだがなんだか騙された感があった。細かい理論を知らないからかもしれない。

週記(2021/06/21-2021/06/27) - kotatsugameの日記

これについて、もうちょっと精密に理解したいと思い、自分で実際に計算することにしてみた。計算回数、あるいは計算ステップ数f(N)を漸化式で表してみて、帰納法ですべてのNに対しf(N)=O(N^2)を言えたと思う。子の数が2つではなく、より一般の場合についても詳しく計算してみた。帰納法の下りはかなり天下り的であるようにも思えるが、f(l+r)=f(l)+f(r)+lr(l+r)^2=l^2+r^2+2lrの類似性で十分気持ちは伝えられるのではないだろうか。

それらを含めてF問題のスライドを作ったらもう疲労困憊になったので、今週はこれだけ発表することにした。

2021/07/02 定例会 | puzzleknot 公式サイト

yukicoder 302に出た。6完。

yukicoder contest 302 - yukicoder

Aは紙でちょっと実験して、3つの数それぞれはよくわからない振る舞いをしたが、全体の積としてみれば毎回2乗されているだけだとわかる。冷静になってみれば、確かにそう。Bも手で実験したが、ミスで1WA。正解は奇数Aに対し(A,A)または(A,A+1),(A+1,A)が負け状態。Cは面倒そうだったがそれっぽいことを書いたら一発で合ったので良かった。DはDP。約数・倍数関係を、因数を掛けたと考えると、数列の総和をキーにして遷移できる。Eは最初、二部グラフにして小さいほうの集合のサイズが答えだと思ったが、提出の直前に黒をわざと連続させることでところどころ入れ替えられることに気づいた。実際出してみるとほとんどのケースでWA。適当に木DPを書いたら通った。Fは、とりあえずソートするまではよくて、そこからしばらく考え込んでいたが、DPのキーと値を入れ替えるだけだった。気づくのが遅すぎた。

Gを考えていたら椅子の上で少し寝てしまったので、布団に移動して再度寝た。午後10時。

07/03(土)

午前3時くらいに目を覚ました。atgolferで更新があったので見てみたところ、昨日の典型と同様、ループを回していたところを桁数と等比級数の和で閉じた形にするテクで縮んだようだ。

これまでは毎回式変形で考えていたが、これは直感的な説明でよい。

ラノベを読んだりなろうを読んだりして、朝になった。今日の典型90問はグラフの隣接頂点を調べるのを高速化する問題で、適当にしきい値を定めて「周りからもらう頂点」を作るのがよさそう。実際、しきい値Kとしたとき、次数がK以上の頂点は周りからもらうことにし、その後自分に隣接する頂点であって次数がK以上の頂点(これは前計算しておく)に伝播する。次数がK未満の頂点は毎回周りを見て更新するので、更新はO(1)またはO(K)、伝播については次数がK以上の頂点が高々\frac{2M}K個しかないことからO\left(\frac M K\right)とわかって、合わせてK=\sqrt{2M}とすると最小になる。クエリ回数が105の2倍なのでかなり重そうだが、間に合うことは確かだろう。

午前9時就寝、午前11時半起床。今日は院試説明会がある。

正午からだと思って急いで食事したが、実は午後1時からだったらしい。思いがけず時間が空いたので、シャワーを浴びたり、早々にジャッジが公開された典型90問を通したりしていた。今日の典型90問はやはり重いらしく、しきい値K=650\sim\sqrt{2\times2\times10^5}で提出したが600ms弱くらいかかっている。

カメラを映すことを求められるかもしれないので、一応ノートパソコンを出して壁が背景になるように座っておいた。午後1時ちょっと前にZoomに入り、説明会が始まる。あんまりかしこまった場でもなさそうだし、こちらが何か発言を求められることもなさそうだったので、ラノベを読みつつ聞いていた。

いくつかの分野に分かれての懇親会で、僕は数学基礎論を選択したのだが、そこの計算機数学の先生の資料をもらって読んでみたところ、「グラフ理論」やら「ラムダ計算」といった見覚えがあるワードが並んでいて、非常に心躍った。このうちグラフ理論というのは、競プロで取り扱うグラフアルゴリズムとは話が違いそうではあったものの、ラムダ計算だけでも十分魅力的である。ぼんやりと数学基礎論に興味を持っていたが、特に出願の際はこの研究室を希望したいと考えた。

午後3時半ごろに懇親会も終了。ほとんど同じタイミングで読んでいたラノベを読み終えた。「転生魔王の大誤算」3巻。

主人公の魔王は自分がメチャクチャ強いのを自覚しておらず、周りにナメられないように必死になって頑張っていて、周りはメチャクチャ強い魔王様を信奉しているという設定。

週記(2021/01/25-2021/01/31) - kotatsugameの日記

魔王なら魔王らしく泰然自若としていてほしいと感じるが、そういう何のひねりもない魔王像はもはやありきたりすぎるのかもしれない。

週記(2021/01/25-2021/01/31) - kotatsugameの日記

相変わらずナヨナヨした魔王に思うところはあるが、基本的に面白く読んでいるので、面白いのだろう。

懇親会が終わってからずっと日記をつけていた。

橙diffを3問解いた。

D - 見たことのない多項式

前に見て、ラグランジュ補間のライブラリを作るきっかけになったが、verifyだけしてこちらの問題には提出していなかったらしい。貼るだけ。

E - RGB Sequence

これは数回考えて解けなかった記憶がある。今日の解法ガチャは大当たりだった。最後に出現したRGBの位置をキーにしてdpするとよい。

D - 旅行会社高橋君

2辺連結成分分解する。した後も木の任意の2頂点間の距離を求めるクエリに答える必要があり、それはライブラリになっておらず毎回書いているが、かなり面倒。蟻本のLCAの実装を使っているが、これはdfsした後parentの配列をダブリングで求める必要があって、手数が多いと感じる。ので、それのライブラリを整備することにした。Library Checkerを探すとズバリLCAを答える問題があったので、これをverifyに使う。

library/LCA.cpp at master · kotatsugame/library · GitHub

そういえば、こういう頻出のライブラリを整備していないのには理由があって、グラフや木を表現する構造体をちゃんと設計してから、それに沿うように作りたいという思いがあった。現状では、強連結成分分解や2辺連結成分分解といった分解後のグラフにも興味があるものは、隣接リストをvector<vector<int> >で返すようにしている。LCAも隣接リストの形で受け取れるようにするのがよいかと思ったが、現状はadd_edgeだけ実装してある。同じ辺を2回張るとまずいので、隣接リストからLCAを構築する際は気を付ける必要がある。辺(u,v)についてはu\lt vである場合だけadd_edgeを呼ぶのがよいだろう。

CF #729 div.2に出た。5完。

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

Aはよい。Bから難しいが、bを足す操作は最後に行うことにしてよいので、結局aのべき乗がどれくらいになるかを全探索すればよい。a=1の場合がコーナーケース。Cは答えがk以上になる数を数えて足していく。これには{\rm lcm}(1\dots k)が関係してくるので、ループはすぐ終わってくれる。考えていることと求めるものが微妙にずれており、サンプルを合わせるのに手間取った。Dは面白い。ある+ xが最後まで残る場合の数を知りたくて、これはx以上か以下かを01にすればdpできる。xと等しい値には、インデックスの大小を使って大小関係を定めるのが良い。つまり、優先度付きキューに値とインデックスのペアを入れるような感じ。

E1は2つの列をまとめて挿入dp。数列の後ろから構築して、現在の大小関係と転倒数の差を管理する。あらゆるところを愚直に書いてO(N^5)。E2にはこれを高速化する方針で挑んだが、任意mod畳み込みを含むO(N^3\log N)で、手元で13secかかってしまいコンテスト終了。

E問題はそもそも2つの列をまとめて扱うのがよくなくて、転倒数と最初の項に対して残りの順列を数え上げた表を前計算し、2つ組み合わせるべきだったらしい。

今日9問解いて、これでRating Historyでの表示が7000ACに到達した。

布団に入ってなろうを読もうとしたが、非常に眠かったのですぐあきらめて就寝。午前2時だった。

07/04(日)

午前9時くらいに目を覚ます。ちょっとTLを見たりなろうを読んだりして、1時間もせず二度寝。次に午後2時に目を覚ました。もう一回寝ようと思って布団に転がりながらなろうを読んでいたのだが、今度は眠れず、結局午後5時くらいに布団を出た。

昨日の典型は、「次数が大きいほうの頂点に向かうように辺を向きづける」のでもいいらしい。確かに、向き付けた後にある頂点から辺がm本出ているならば、その先の頂点たちはすべて次数m以上であるから、m^2\le 2Mが成り立つ。つまり毎回の取得・更新がそれぞれO(\sqrt M)で行えるようになって、これでも計算量が改善されている。

橙diffを1問解いた。

E - Bichrome Spanning Tree

まず1回最小全域木を作ってみて、それで条件を満たさなかった場合は、例えば白く塗られた辺しか存在しないならば、別の辺を選んで全域木に入れる必要がある。この時、クラスカル法で最小全域木を作るならば、最初に選んだ辺を使うようにすると言い換えてもよい。この言い換えから、元の最小全域木に対して追加1本・削除1本しか変化しないことがわかる。このようにして辺を入れ替えたときの重みが最も小さいものを選びたい。ちょうどXになるためには、最小全域木で選んだ辺がすべて同じ色である他、辺を入れ替えたときの重みがより小さくなる辺についても同じ色である必要がある。逆に、より大きくなる辺の色は自由なので、そこが自由度になる。

辺を入れ替えた時の重みは、解説では最小全域木のパスに含まれる最大重みの辺を使って計算していたが、毎回最初に使う辺を選んでクラスカル法し直すだけでよい。こちらのほうが簡単。

今日の朝、TLでLGV公式というのを耳にして、資料を読んでいた。

https://www.ioi-jp.org/camp/2017/2017-sp_camp-kumabe2.pdf

この3ページ目にあるLGV公式の前提は誤っている(と思う)。反例も以下のツイートのように構成できているはず。このグラフでLGV公式と同様に行列式を求めると、[2,1,1;1,2,1;1,1,2]で4となるが、本来は0である。

[https://twitter.com/kotatsugame_t/status/1411650442996555776:embed#逆に「パスが交差しない場合恒等置換」が言えればよくて、これはijとパスj->k(ただしk

単純に考えるなら「i,j<k,lについてパス(i,k)とパス(l,j)が交差する」ことを前提にすればよいが、微妙に弱められる。変数が少なくなっているし、たぶん弱まっているはず。

逆に、パスの交差に関する条件を全部外せば、一般のDAGに対して始点N個と終点N個を1つずつ組にして交差しないパスで結ぶ場合の数が数え上げられるかと思ったが、置換の符号が負になりうるためダメだった。\bmod 2なら解ける。

ABC208に出た。5完。ABC全完streakは177から207まで、31で途切れてしまった。

AtCoder Beginner Contest 208 - AtCoder

Aはよい。Bは額面が倍数になっているため、大きいほうからどん欲に取ってよいというやつ。Cは適当にソート。Dは見た目に驚かされるが、実はワーシャルフロイドの途中段階を全部足せという問題になる。これはワーシャルフロイド法の証明で、kを固定してO(N^2)のループを回している部分は頂点kを通るパスを探している、ということを知っていればわかる。Eは桁DPで、積の形で書けるK以下の数は少ないので間に合う。if文のミスで、最終的に数字の積が0になる数をうまく数えられておらず1WA。

Fは解けなかった。今週木曜日の部分に書いたように\left(x\frac{d}{dx}\right)^Kを掛けるのが効くかと思ってずっと計算していたが、全然きれいな形にならなかった。

コードゴルフをする。A問題はコンテスト中に書いたdcが最短。2回比較を行うが、1回目の比較に成功したら必ず2回目の比較に失敗するようにしている。つまり(a||b)==a+bみたいな感じか。スタックに出力を積み、その上にゴミを積んでrで適切な出力を持ってくる、という方針なので、比較に2回成功してしまうのはまずい。

Bもdcだが、最初に書いていた階乗を生成して大きいほうから割っていくコードからかなり変わった。基数が変わる階乗進法(?)のようなものを考えると、P2で割った余りが1桁目にきて、\frac P 23で割った余りが2桁目にきて、……という風になる。つまり毎回割っていくことで階乗を生成する必要がなくなり、大変に縮んだ。これはしーあるさんのコードを読んで気づいた解法。

atcoder.jp

Cは取り合えずPerl。先週見たテクを使っている。大きな数の整数除算で誤差が発生するらしく、いちいち余りを引いているのが気になるところ。

インデックスを、対応する値を比較してソートしたい。これはPerlでやるよりbashでやったほうが短い。

週記(2021/06/14-2021/06/20) - kotatsugameの日記

DはOctave。ワーシャルフロイドを行う問題はOctaveが強く、実際同様の最短コードは複数存在する。ところで今日のワーシャルフロイドはN\le 400だった。これまでのワーシャルフロイドを使用する問題は、古い問題が多いということもあるだろうが、僕が知る限りN\le 300だったので、ここにきて一段階制約が上がった感じ。実際今の最短コードは入力部で縮む余地がありそうだったが、提出してみるとTLEしてしまった。

F問題を通す。「補間」というワードを知ってしまい、すでにげんなりしているが、どのように補完するのかは自分で考えておきたい。maspyさんの記事を読んで頑張る。

maspypy.com

まず、コンテスト中にf(N,M)=\sum_{i=0}^N i^K \binom{N+M-i-1}{M-1}となることはわかっていた。これはf(n,m)のテーブルを見ると上のマスと左のマスを足していることになり、m=0のマスそれぞれの寄与を考えるとわかる。ここでa_n=n^K \binom{N+M-n-1}{M-1}と置くと、これはnK次式とM-1次式(nが関係する項をM-1回掛け合わせているため)の積で合わせてK+M-1次式とわかる。f(N,M)=\sum_{i=0}^N a_iより、和を取るので次数が1上がり、f(N,M)NK+M次式となる。

これでもよいが、f(n,m)のテーブルにおいてm\leftarrow m+1としたとき、累積和を取っているということに気づけば、m=0K次式からM回累積和を取るのでK+M次式、とただちに言えてしまう。こちらのほうがシンプルか。

次数が分かれば、あとはラグランジュ補間で解ける。補間としては多項式から補間するものと線形漸化式から補間するものの2つあると思っていて、後者はライブラリを持っていないため、それに帰着されたらどうしようと考えていたが、無事ラグランジュ補間で解けた。最初のK+M+1項を計算するのは、毎回a_nを計算して足していけばよい。こちらは普通に計算しても各要素につき二項係数のO(M)で解説と同じ計算量になり、その二項係数をずらす感じで定数時間で計算することにより多少オーダーが改善される。

これで今日AtCoderで7問解き、3000ACを達成した。本当は昨日の7000ACと合わせたかったが、そのために何かするのもなあということでこんな感じになった。

朝方、日記を書き終わったので投稿しようと思ったが、今日から典型90問のジャッジが必ず朝に公開されることになっていたので、それを解くことにした。時間までは昨日の典型90問のコードゴルフをしていたが、なんの進捗も得られなかった。233B。今日232Bから更新されているので、多分朝のところに書いた「次数が大きいほうの頂点に向けて向き付ける」ことで縮んだと思うのだが、縮む前のコード長にすら届いていない……。

解いて通したら1位になったのでFA獲れたかと思ったが、これまで全問ACしている人の中で最速だっただけで、FAはまた別の人だった。残念。内容に言及しようとしたが、もうすぐこの日記を公開するため、何も書けないことに気づいた。いよいよ来週で終わりである。来週日曜日に全提出が公開されるので、多分しばらくはコードゴルフしっぱなしになるだろう。

週記(2021/06/21-2021/06/27)

06/21(月)

午前7時、目を覚ます。日曜日は布団から出ずに寝るのと起きるのを繰り返していたため、時間の感覚があまりない。まあ朝だし、このあたりで日付を区切っておくのがよいだろう。生活リズムが整っているように見えなくもない。起き抜けにTLを見ていると、今日が夏至であることに気づく。夏至は好きだ。

しばらくなろうを読んでから、投稿された典型90問を確認した。今日も特にゴルフする気にはならない問題。HW\le 16なので、まあなんでもできそうな気はする。とりあえず通るマスとして2^{HW}通り全列挙して、同じマスに二度入らないように一回りする閉路(ハミルトン閉路)が存在するか確認する、という方針を考えた。オイラー路と勘違いし、次数を確認すればよいと思い込んでいたが、思い直して調べ、間違いに気づいた。ちゃんと冷静になると、bitDPでできる。

解けたのでまたなろうに戻る。そのまま午後2時までなろうを読んでいた。途中で典型90問がAtCoderのほうに投稿されたことにも気づいていたが、放置して読み続けていた。

布団から出て先週の週記を完成させ、投稿する。金曜日の終わりあたりから溜めていたので、2日ちょっと分を2時間くらいかけて書いた。日曜日はほとんど虚無だったので、実質1日分かもしれない。投稿してから典型90問も通しておいた。

先週金曜日に注文した眼鏡だが、今日の午後3時以降なら受け取れる、ということを金曜日の時点で言われていた。先週の週記には下のように書いたが、実際はピッタリ月曜日に出来上がるということ。

出来上がるのは月曜日以降になるらしい。

週記(2021/06/14-2021/06/20) - kotatsugameの日記

大学に行く準備をする。眼鏡屋と購買が午後5時閉店で、学食が午後5時から開店なので、そのちょうど境目を狙って行くことで待ち時間なく買い物をしたり食事したりしたい。シャワーなど浴びていたら午後4時半で結構いい時間になった。ATMに寄って眼鏡の代金を下ろしたらギリギリになってしまったが、何とか購買で買い物をすることに成功。眼鏡屋のほうは、調整などしてもらっていたら午後5時を余裕で回ってしまい申し訳ない。食事して帰宅。

DDCC2021本戦の動画が公開された。インタビューを受けたことを覚えていて、30人しかいないのだから使われている可能性は高いぞ、と思ってドキドキしながら視聴したが、使われていないどころか映り込んでいる瞬間すらほとんどなくて拍子抜けした。感染症対策のビニールで人がよく判別できない。

https://www.discoverychannel.jp/campaign/ddcc2021/

布団に倒れこんでなろうを読んでいたらすぐ寝落ちしてしまった。午後7時半から午後11時半まで寝ていた。起きてからまた午前5時までなろうを読み続け、再度寝落ち。

毎週午前3時にClassroomに講義資料を投稿する教員がいて、親近感を感じている。

06/22(火)

午前11時起床。典型90問を確認。今日はただの木DPで、またゴルフする気は起きない。午後5時までなろうを読み続け、また寝落ち。次、午後8時半に起きた。夢を見た。

布団から出てサークルの運営関連の作業を少しした後、典型90問を通しておこうと思ってページを開いてみたが、問題がAtCoderに投稿されていない。スーパーリロードしても変わらず。順位表で現在の最高点を確認し、ようやくまだ投稿されていないことに確信が持てた。なろうを読んだり、いろんな人の週記を読んだりしていたところ、午後10時前になってようやく投稿されたので、通した。

またなろうに戻る。午後10時、ついに最新話に追いついた。

https://ncode.syosetu.com/n5534co/

布団に入ってから新しいなろうに手を出した。

週記(2021/05/24-2021/05/30) - kotatsugameの日記

記録によれば、05/24から読んでいたらしい。今日でちょうど30日。この作品は文字数が1277万文字ということで、1日あたりでは42.5万文字くらい読んでいたということになる。特に設定が好みで非常に楽しめたが、その代わり今月の物理本の読書記録は壊滅的である。ここにこの作品の感想を書こうと思ったが、久しぶりということもあり、また長く読み続けすぎたこともあって、何を書いていいかわからなくなった。

あらすじにもある通り、主人公は一度転移して異世界で勇者になり、3年後に再度、今度は通っている学園丸ごと同じ異世界に転移する。異世界ではその間におよそ300年が経過しており、勇者その人や当時一緒に戦った仲間たちはすでに伝説となっていた。主人公はその300年後の世界で、学園生としての立場と異世界の勇者としての立場を行き来しつつ活躍していく……。1回目と2回目の転移の間でかなり時間経過があったという設定は「神話伝説の英雄の異世界譚」を思い出す。こちらも主人公のチート具合が好ましい、が、今は置いておこう。

主人公はいち学園生であったわけだが、さすがに勇者なので、立場を隠している状態でも戦闘力については序盤から学園で最強だった。と、ここで、「勇者であったことを隠している」という設定がまず健康に良い。隠しきるわけではなくて、自分から明かしたり、あるいは見破られたりするわけだが、そのような「自分の立場を明かす」という一種のカタルシスが手を変え品を変え何度も訪れるのが良かった。さて、主人公が学園最強であるという話だったが、これを恃まれて、ある事件をきっかけに学園生出身の冒険者を統率する立場に抜擢される。「冒険部」という部活動を作り、メンバーを統率して教育し、組織づくりを行っていく。この「組織作り」や「組織のトップに立つ」というのも好みの要素だった。

あとはまあ、主人公最強モノであるので、これも好み。大まかにはこれくらいの要素が僕の好みのどストライクだったというわけだ。

来週また僕が発表することになった。今週は不甲斐ない感じだったので、来週は頑張りたい。

週記(2021/06/14-2021/06/20) - kotatsugameの日記

日付が変わったあたりからゼミの発表準備を始める。午前6時までやったが、予定している発表範囲の半分弱、教科書にして2ページ半しか進まなかった。まあその分厳密かつ細かい注釈(教科書にある証明方針が採用された理由等)も付けることができているのではないだろうか。できているとよいなあ。これまで2回発表してきたわけだが、テキストが簡単なこともあって、証明が爆発炎上したりしたことはまだない。今回もこれまで以上に気を使っているつもりだから、とりあえず正しいことは書けているはずだ。

水曜日の午後2時からインターン先とのちょっとした面談が予定されている。ちゃんと時間までに起きるためもう寝ようと思い布団に入ったが、なろうを開いてしまう。午前6時半から午前10時半くらいまでなろうを読んで、どうにも眠れないことを受け入れ、このまま起きていることにした。

起きて今日の典型90問を解く。最初少し迷ったが、\bmod 3の数列として見ることで解けた。あるインデックスを選び、そこを-1して、それより前は+1する。数列のすべての項が0になったら操作終了。非0の項を+1して得することはない(感覚的にそう)ので、先頭から順に0に揃えていく感じで操作すればよい。0-indexedでi項目を操作したとき、それより前に対する影響がすべて解消されるのには2^iステップかかる。これを各インデックスで足し合わせれば答えになる。最大ケースは2e18くらいのようだ。

入力を加工してdcで読めるようにしたり、revをかませたりするのをVimで行って、計算自体はdcで行う、というコードを書いていったん満足。それが午前11時くらいで、すでにAtCoderに問題が公開されていることに気づき、通した。35Bだった。revをかませることを念頭に置き、dcコードを反転して入力したりしており、見た目に面白かった。

その後しばらく考えていて、bash 24Bと大幅に短縮することに成功した。これは入力を2進数として読み込む手法で、2001を2進数で解釈するというのは通常だと意味が通らないが、dcにおいては構わず2×23が使われることを利用したもの。星6で24Bということで、星1つあたり4B(?)。これは今のところの最小値である。

学食に行き、帰ってきてから日記をつけていた。午後2時少し前から準備して、面談。すでに内定しているため、今日は人事の方から実際に働くにあたっての契約説明がされた。契約書のコーナーケースを指摘したりしていたが、どうやら契約書の内容を公開するのは一般にヤバいらしいので、何も書けない。30分くらいで終了。

またゼミの発表準備を進める。2時間くらいやって切りのいいところまで進んだ。いい加減眠いので切り上げることにした。布団に入って就寝。午後5時だった。

06/23(水)

消えた。

06/24(木)

06/23 午後11時半に起床。正直もうちょっと寝ておきたかった。このような時間に起きるのは好ましくない。二度寝しようと思ったが、布団でノクターンノベルズを読み始めてしまう。興奮していよいよ眠れなくなった。しょうがないので起きる。

ゼミの準備を進める。というか発表当日になってしまっている。今週もTikZで図を生成した。面白い。

2時間半くらい頑張って完成した。ホスフィンに投げつけて一旦寝ることにした。いい感じに眠気があったはずだが、なろうを少し読んでいるうちにどこかに行ってしまったので、少し頑張って寝た。午前5時半就寝。

午前9時に目を覚ます。今日の典型90問を解く。今日は簡単だが、コードゴルフをどのようにするかがわからない。bashからfactorを呼び出すのは固定として、それをどのように加工するか。最初はwcdcの順で使っていた。次にwcdcwcとなり、さらにdcwcとなった。具体的な内容は割愛。これで32Bが達成され、満足していたが、後からrakuを使って31Bが作れることに気づいた。これを自動で提出する設定にしておいた。

昨日の典型の、climpetさんの解法に至る過程が面白かった。今見ている桁より右で操作された回数を求めておき、今見ている桁を考慮すると、A+=A+(0 or 1 or 2)になる。

さて、そのようなことをしていたら1時間以上経過し、眠気が消え去ってしまった。このまま起きていることにする。ホスフィンから指摘があった点をいくつか手直ししたり、スライドに書いていないけど触れておきたい内容をメモ書き(これもホスフィンにやったほうが良いと言われたこと)していたら、学食に行き損ねてしまった。午後1時、ゼミが始まる。

今週の発表は、自分ではなかなかよかったと思っている。正確にしゃべろうとするあまり冗長だったりくどかったりしたかもしれないが、とりあえず喋りたかったことはすべて喋ることができたし、逆にちょっと先のことを喋ろうと思って、前提を話していないことに気づいて慌てて戻る、ということもなかったと思う。メモ書きを作るにあたって、自分がどのような発表をするかというのをおぼろげながらも通しで考えていたので、それがよかったのだろう。結局メモ書きの内容は覚えていたのであまり見なかった。

今週のスライドもアップロードしておく。追記と書かれたページは、発表のときに教えてもらった内容・指摘を受けた内容を反映したものである。

Apostol_Chapter3_3.6-3.10.pdf - Google ドライブ

今日のゼミは1コマ分で終わり。来週もそう。ちょうど終わったあたりで今日の典型90問がAtCoderにアップロードされたらしく、ちゃんとACできていた。

ゼミが終わってからしばらく、スライドの追記ページを作ったり、論理学の講義動画を見てミニットペーパーを書いたりしていた。06/09に提出したレポートの採点が終わっているのを見つけて確認してみたが、今回はそこそこ点数が取れているようだった。土台はよくわからないもので構成されているが、その上に乗っている理論は何となくわかる気がする、という感じ。

何とか解けそうな問題を選んで解いていき、午前5時に5問の回答が完成した。すぐに提出。

週記(2021/06/07-2021/06/13) - kotatsugameの日記

午後4時前に家を出て、購買に寄ったあとゲーセンに行く。家を出たときは、地面は濡れているけれども遠くに青空が見えていたので、自転車で大学まで行った。ところが、購買で買い物をして出てきてみると、雨が降り出していた。すぐやむかと思ってしばらく待ってみたが、どうにもやみそうになかったので、折り畳み傘を出して地下鉄の駅に向かった。自転車は大学に置いていく。地下鉄に乗って駅前のほうまで出てみると、ちょうど見えていた青空の下に入り晴れていたので、頑張って自転車に乗ってこればよかったなと後悔。

ゲーセン。午後4時半から午後11時半までみっちりプレイした。今日はかなり進捗があって、13+のSSSが1譜面、13のAJが(今日のアプデで追加されたものも含め)7譜面。さらに14のSSが3譜面増えた。

106小節

トドメだの人のAJ動画(現在非公開のはず)で知った運指。半信半疑でやってみたら全然出なかった。この運指を使って2回目でSSSが出たので、たまたま通っただけかもしれない。しかし、この餡蜜が通るのはかなりびっくり。それほどBPMが速いのか。

ついに(現在解禁している)13+の未鳥が1画面に収まるようになった。Angel dustだけ13.8で、他は13.9。

立ち食いそば屋で夕食をとる。そのまま帰ってもよかったが、晴れているようだったので置いてきた自転車を取りに大学まで歩いて戻った。

自転車を出したところでまた雨が降ってきてびっくりしたが、かまわず乗って帰ってきた。

日付が変わってから帰宅。日記を書いたりして午前3時に布団に入る。信じられないくらい疲れており、眠ろうとじっとしているのすら辛かった。疲れているのは確かなので、即座に入眠。

06/25(金)

午前8時に目を覚ます。起きる気はなかったが、典型90問を読んでいたらなんとなく眠気が消え失せてしまった。ゴミを出す。

今月は1200万文字のなろうに全てを破壊され、まだ1冊も物理的な本を読んでいない。この時間に読んでおくことにする。買ってから机の上で寝かせていた本のビニールを剥き、読み始めた。正午、読了。

ネトゲの嫁が人気アイドルだった」。表紙イラストが非常に良く、タイトルにも惹かれたので購入を決定したが、あまり面白くなかった。多分、人気アイドルだとかネトゲの要素を目的としていたのに、実際にはヒロインの性質やヒロインと主人公の関わり(のみ)を掘り下げるような内容だったからだろう。あとはヒロインがヤンデレなのもあまり受け入れられない。

続いてもう1冊手を出した。前巻の内容を一切覚えていないが、記録によれば半年ほど前に読んでいるらしい。主人公のペットであって最も最近登場したものについて、何一つ覚えていなくてちょっと戸惑った。少し読んだところで今日の典型がAtCoderで公開されたことを知り、解く。

尺取り法をしたが、やはりこれはwhileループが長い。しばらく考えて、連想配列で値の出現を記録しておけばよいことに気づいた。Perlで書き、連想配列の代わりに${-1}${-2}を使ういつものテクで縮めた。最終的には入力された配列にmapgrepをかませるだけになって、変数に配列を保存する必要もなくなりスッキリしたコードで気分がいい。

またラノベに戻ったが、午後2時半くらいに切り上げ。寝ようとしたが微妙に眠れなかったのでハーメルンでGame of Vampireをしばらく読み返していた。何度読んでも良い。午後4時就寝。

今日はサークルの解説会を20時から(SRMに被っているが)予定していた。それに向けて目覚ましを30分おきにセットしており、まず午後6時の目覚ましで一瞬意識を取り戻した。あまりの眠さにギリギリの午後7時までは寝ることを決定。午後6時半の目覚ましを取り消そうとしたが、そこまで考えた時点ですでに体が動かず、そのまま二度寝した。結局午後6時半の目覚ましでもまた起こされることになってちょっと残念。

午後7時起床。食事してサークル解説会のためのスライドを作成しようとしたが、残り15分しかなかった。ABC206-Fに登場するGrundy数について、自分なりの理解を書き記そうとしたのだが、用意が全然間に合わず、ええいままよと発表したら喋っているうちに間違いに気づいたり、口頭で捕捉しようとしたが喋る内容がまとまっておらず上手く言えなかったり……と散々な結果になった。用意は大事。このザマになるのならば、恥を忍んでB問題とかC問題でお茶を濁すのもありだった。

2021/06/25 定例会 | puzzleknot 公式サイト

午後9時20分からyukicoder 301。4完。

yukicoder contest 301 - yukicoder

Aはよい。特別な場合として24=42は有名で、小さい値をしばらく考えてみてもそれ以外はなさそう。Bは区間スケジューリング。Cは置換と合成をセグ木に乗せる。Dを読んだがわからなかった。しばらくWolframAlphaで展開した式とにらめっこしていたが解けない。ふとE問題のsolvedがかなり多いことに気づき、問題を読んでみた。ただのbitDPで、慌てて通す。

残り時間はF問題に挑戦していた。1列持つbitDPで、状態数はかなり少なめ。ここまではよくある考察で、bitDPの遷移は以前evimaさんの問題を解いたときと同じ感じでよさそう。

No.1397 Analog Graffiti - yukicoder

あとは遷移を高速化すればよくて、これは行列累乗だと思っていたが、N=9のときに状態数が2188あることを知った。間に合わない……。遷移行列は疎なので、1ステップ進めるのはかなり素早く計算できる。多分Mが小さいときの値を調べるとうまいこと求まるとかだと考え、それで殴っている人を最近TLでよく見たことも覚えていたが、アルゴリズムの名前がわからなかった。ちょっと調べているうちにうっかりラグランジュ補間だと勘違いしてしまい、ライブラリを貼るも当然通らない。そのままコンテスト終了。知りたかったアルゴリズム名は「Berlekamp-Massey Algorithm」だった。

途中で行列積の高速化について調べていた。3重ループにおけるループ変数の順番を変えてシーケンシャルアクセスになるようにする、という手法が簡単かつ効果が高い。自分のライブラリではそのようになっていなかったので、書き換えたら、テストが落ちてしまった。びっくりして調べてみたら、掃き出し法のverifyに使用していた問題にHackケースが追加されたらしい。場合分けが必要なコーナーケースかと思ったが、よくよく見ると普通にバグだった。num[i]を使うべきところでiを使用していたのを直したらテストが通った。

D問題は数学典型らしい。ここに貼られている問題のうち1問目は誘導付きだったので、それに従って考えてみようと思ったが、解けなかった。泣く泣く未だに持っている赤本を引っ張り出して調べたところ、n\leftarrow n+1とした式に漸化式を代入して式変形するだけだった。

論理学の中間課題の提出期限は明日の午後5時である。CF div.1があるが、writerのレートが低いし配点も不穏なので、見送って課題に取り組むことにした。テーマはこれまでの講義に関係していればなんでもよいという自由度の高さなので、対話形式で証明を進めてくれるプログラムを作ろうと思い立った。一部に構文解析が含まれるので、その実装に慣れているC++言語を選択。どんな設計にしようか考えていたが、考えれば考えるほど実現したいことが思い浮かんでくるので、とりあえず動くものを書こうと心掛けた。

6時間くらいコーディングして一応の完成を見る。とりあえず4つくらい、講義で取り扱った証明を再現できることは確認してあるが、それ以外ほとんどテストしていない。特に、エラーを検出してほしいところでちゃんとエラーが出るかということは全くもって確かめていない。

github.com

READMEをちょっとばかり整備して、リポジトリの作成はこれでOK。課題の文章も適当に作成して提出しておいた。kotatsugameというハンドルネームが自分自身であることは証明できないが、そこを指摘されたときはその時ということにしておいた。

そのようなことをしていたら午前9時半になってしまった。せっかくなので典型90問の投稿を待ってから寝ることにして、昼間読み止しにしたラノベを読み切った。

異世界でチート能力を手にした俺は、現実世界をも無双する」8巻。このシリーズは1巻が非常に好みだったのだが、巻を追うごとに興味が失われていくのを感じる。現実世界で無双しているのが好きだったのに、前の巻までは異世界でバトルするのがメインで、今巻からは宇宙に舞台を広げている。

典型90問が投稿された。今日は星7だが、ただの2部マッチング。よく見ると制約が少し大きめなので、「辺のキャパシティがすべて1のグラフでフローを流すときにDinicのアルゴリズムを使うと計算量が落ちる」ということが問われているのだろうか。確かにこの事実を正確に認識したのはACLが公開されたぐらいの頃だった気もするので、難しめの知識ではある。まあ何も考えず投げても通りそうだが。

午前10時半就寝。

06/26(土)

午後1時少し前起床。AHC004に参加する。

AtCoder Heuristic Contest 004 - AtCoder

問題文を読んだが、すぐには方針が思い浮かばない。15分くらいコードゴルフして、あとは布団に戻って寝ながら考えることにした。コードゴルフVimで、Nが固定であることに気づいて多少縮んだ。最初提出制限が30分になっていてびっくりした。

午後1時半くらいにまた就寝。そのあと何度か起きつつも、基本的には寝ながら生協の弁当を待っていた。午後5時、今週も受け取りに成功。再度寝ようとしたが、AHCが残り2時間くらいしかないことを考えて、起きてしまうことにした。まず典型90問を通してから、午後5時半過ぎにAHCのコーディングに入る。残り1時間半。

縦横両方向を考慮するのは難しそうだったので、とりあえず1方向のみ考慮してどうなるか点数を見てみたい。文字列がどれくらい重なっているかを前計算して、これをもとに20文字にどれくらい詰め込めるかを計算する。この時両端がループすることは考慮しない。最初に入れる文字列は乱数で決定し、残りをdpで計算して復元したものを1行として、これを20回繰り返したものを提出した。3.8e9点。

冷静になると、多点スタートのBFSなどと同様、最初に入れる文字列を固定する必要はなかった。4.5e9点。

ある文字列が別の文字列を含む場合、これまでは無理やりずらして重ねていたが、片方に吸収させてしまうことにする。その分、吸収した文字列には重みをつける。5.6e9点。1方向しか考慮していないのに2桁順位になってしまい、興奮する。残り30分。

文字列を重ねるときに、同じ行の前のほうで使った文字列を使わないようにした。遷移履歴によってどの文字列を使ったかは変わるが、使った文字列をbitsetで保存し、dpの各値に対応付けて覚えておくことで実装できる。毎回大量のbitsetを生成すると信じられないくらい重くなったが、グローバルに置いておくと爆速だった。また、行の端でループする部分列と縦方向の部分列も検出するようにした。これで5.88e9点。

トップページを探しても採点についての注釈がなかったが、AHC002と同様の形式(短時間マラソン)であることを考えると、今回もコンテスト中の最高点で順位が決まると考えてよさそう。ということで最終提出のことはあまり考えず、残り時間で2回ほど提出を行ったが、結局伸びなかった。

最終順位は68位、パフォーマンス2283でレートは1783→1941(+158)。AHC002と同様まったくランダムなことをしていない。自分では全く考えもしなかったが、この問題でも普通に焼きなましが効くらしくてかなりびっくりだった。何を焼きなますかというのは、やはり経験がないとわからない部分なのだろう。

TLでいくつかの方針を見ていたが、今回の問題では文字列同士の重なり具合に応じてマージするのが強力で、それをして(さえ)いればそこそこスコアが出るらしかった。

今朝提出した論理学の中間課題に評価がついていたが、どうやら提出だけチェックされたらしく、内容については一切触れられなかった。ウン百人と受講者を抱えているのでしょうがない部分はあるのだろうが、さみしい……。

しばらく日記を書き、午後9時からABC207に参加した。

AtCoder Beginner Contest 207 - AtCoder

全完7位。D問題は真面目にやっていたのに25分かかってしまった。これはE問題とF問題にかけた時間を合わせたよりも長い。

A問題はVim。似たような問題を数問ゴルフしたはずなので、そこからコードを引っ張ってくることにした。「ringring」という問題名を思い出せたので検索してみると、こちらは最小値。まあやることは変わらない。ACした後、試しに数値ではなく文字列として比較するコードを投げてみたら、通った。これで少し縮んだ。

A - ringring

Bは式変形。ゴルフもちょっと考えていたが、場合分けが面倒そうなので後回しにした。Cは場合分けパーティーかと思ったが、最初に全部半開区間にそろえておけば簡単。問題文をまともに読んでいなかったため、サンプル1を試して初めて実数の点を考慮しなければならないことに気づいた。気づいてすぐ、半整数に拡張することで同様に扱えることを思いつけたのはよかった。

Dは、座標も小さいので、たいがい何をやっても解けそうではあるが、逆にどのような実装方針を選んでも面倒に見える。僕は、両方の集合から基準とする点を1つずつ選んで、残りを偏角ソートし、ずらして対応させられるか見る方法で解いた。最初、基準からの距離も考慮しなければいけないことを忘れており、書き直しに時間を取られた。基準点を選ぶのにO(N^2)、ずらす度合いを試すのがO(N)、対応させられるか見るのがO(N)くらいか。日記を書いていて気付いたが、片方の集合の基準点は決め打ってしまってよかった。

EはDP。部分列をいくつ作ったか、今作っている部分列の総和の余りがどうなっているか、をキーに持つDPは3乗だが、部分列を一気に遷移することにしたら2乗に落ちそう。実際、遷移先としては一番近くて総和の余りが0になるようなインデックスだけ考慮すればよく、それらもまた2乗の前計算で求められる。Fは2乗の木DP。

Dが大爆発したが、みんな大爆発していた。黄色diffらしくてさすがにすごい。すごいぜ。まあこういう実装が面倒な問題の解かれ具合なんて予想できないだろうから、D問題においてあること自体はわかる。しかしこの問題はただひたすら面倒なだけなので、普通にアルゴリズムが難しいE問題のほうが解かれているというのはびっくり。

Fの解説では2乗の木DPが2乗になる理由としてN頂点の完全グラフのことが書かれていて、これ知らない証明だなあと思った。僕が知っているのは計算量T(N)T(l+r)=T(l)+T(r)+lrを満たすことからT(N)=O(N^2)を示す方法で、シンプルだがなんだか騙された感があった。細かい理論を知らないからかもしれない。

コードゴルフをする。A問題は最初に少し時間を使ってゴルフした。B問題は場合分けをどのように吸収するかが本題。dcは0とのmaxを取るのが簡単に書けるので、わざと答えより1大きな値を出しておいて1引くことで回答を作り、-1を出力するべきケースでは頑張って非正の値が出てくるようにする。CはよくわからないがとりあえずRubyで書いておいた。EをRubyで通そうとして、なかなかTLEが取れず苦労したが、どうやら途中でmodを取っていないのがまずかったらしい。最初のほうに試したときはむしろ遅くなっていたのだが、何があったのだろうか。

D問題は、まず重心からの相対座標に直して、あとは回転させる角度をたくさん試すと通るらしい。角度をたくさん試す解法のコードゴルフには前例がある。Octaveを使い座標を複素数として持ってexp((0:n)*i)を掛けているが、これは弧度法における0からnがだいたいバラバラに分布することを利用しているわけで、結構好みのコード。

F - Engines

これでやってみることにした。回転させた後はソート(複素数をソートすると絶対値の大きさ→偏角の大きさで比較するらしい)して一致を判定する。が、一致判定のEPSをどのような値にしても微妙に通らない。しばらくコードを投げ続けていたが、ふとソートがヤバいことに気づいた。絶対値が等しい2点があったとして、回転させた後も等しいと判定してくれるかは微妙っぽい。これは……どうしようもないだろう。たとえ実部と虚部に分けて比較したとしてもダメそう。諦めた。

朝方、D問題のRubyによるコードゴルフが行われていることに気づく。集合から2点選んで基準ベクトルとして使うコードらしい。選ぶ2点を全探索する部分が長そうだったので、配列をシャッフルして先頭2点を取り出すことにした。いわゆる乱択解法で、\binom{N}{2}通りから求める1通りを引く必要がある。時間制限との兼ね合いから180N回くらい回すことにした。当たりを引けない確率はN=100の時に最大で2.6%くらいらしく、ちょっとヤバげだが、投げたら3回目で通った。

日記を書いていたが、途中で切り上げ、明日のAGCに向けて寝ることにする。布団に入ってから少しだけラノベを読んで就寝。午前7時半だった。

06/27(日)

午後7時、目覚ましにより起床。かなり信じられない。寝る前に念のためと言ってセットした目覚ましだが、12時間もあるのだし自然に起きるだろうと思っていた。疲れがたまっていたらしい。

昨日寝る前に読んでいたラノベを読みつつAGCが始まるのを待って、参加した。AGC054。

AtCoder Grand Contest 054 - AtCoder

3完50位でパフォーマンス2974、レートは2749→2774(+25)。highestを13更新した。

Aは簡単。先頭と末尾が同じ文字'a'の場合を考えたとき、'a'以外の文字が連続する箇所がないならば、どのように操作しても常に先頭と末尾が同じ文字'a'である状態が保たれてしまう。いずれすべてが文字'a'になって終了。そうでない場合は前半と後半をそれぞれ消せて2回の操作で空文字列にできる。そこそこ丁寧に考えて解いた。明らかにゴルフしやすい見た目をしていたのでゴルフ欲が抑えられなかったが、「先頭と異なる文字」をsed正規表現で書く方法が思いつかなかったこともあり、すぐに諦めて次の問題に進んだ。

Bはよくわからなかった。値の大小を考えてみてもよい性質はなさそう。ここで方針ガチャとして、お互いの取る要素を固定することにした。まだよくわからないので、もうちょっと方針ガチャを回して「どのような順番だったらその割り当てで取れる順列が存在するか」ということを考えてみると、驚くべきことにどのような順番であっても順列がただ1つ対応することに気づいた。半信半疑でbit全探索を書いてみるとサンプルが合ってしまうので、どうやらこれが正しいらしい。

適当に部分和DPっぽいものを書くが、ループが3重になって計算量がヤバそうに見える。しかしどのように高速化したものかとんとわからないので、とりあえず最大ケースを試してみよう……としたら爆速だった。改めて計算量解析をするとO(N^2\sum W)で、これは1004になって間に合う。投げたら通った。かなり速く解けたが、解法ガチャに成功しただけで、一歩間違えれば一生解けないタイプの問題に見える。

Cは順当に解けた。一般に、転倒数を減らす方向のswapしか考えなくてよいようだ。これはP'を考えていても得られる性質だが、これ以上はPを考察の対象にする必要がありそう。そこでまず、PからP'を作り出す操作列(これは複数考えられる)が一意にならないか考えてみる。適当に実験してみたところ、どうやら値が小さいものから貪欲に揃えていくのがよいようだ。具体的にどこにそろえるかというと、まず1K+1番目以前に動かさなければならない。次に2だが、これは1K+1番目以前にある状態ではK+2番目以前に動かせばよいらしい。別の言葉で言えば、1を無視した列においてK+1番目以前に動かす。以下、同様にiK+i番目以前に動かす、あるいはi-1以下を無視した列においてK+1番目以前に動かす。

iについて、i-1以下を無視したPにおいてK+1番目以前にあったものは、i-1まで揃えた後でもK+1番目以前にあるため、動かさなくてよい。逆に言えば、i-1以下を無視したP'でちょうどK+1番目にあるような要素i、つまりP'でちょうどK+i番目にあるような要素iはそれ以降から動かしてきた可能性がある。この自由度がPの自由度になりそう。具体的には、場所の候補がN-K-i+1通りある。

サンプルでは単純にこれの総積が答えとなるが、自由度が1より大きな要素が1つしかないので、本当はこんな単純なわけがないと思い、K=24 2 1 5 3 6を考えていた。1に自由度4、3に自由度2があって、自由度が1より大きな要素が2つある。互いに干渉することで自由度が減ると思ったのだが、実際Pを作ってみると本当に8通りあってびっくり。改めて考えてみると、自由度を考えるときもi-1以下を無視することで、自分より右にはいつでもN-K-i個の要素があって、自分より小さい要素との位置関係を無視してよいことが納得できる。O(N)の非常にシンプルなコードになって、まだ微妙に疑いながらも提出してみるとAC。順位表を見ると結構通されていたようで、度胸が足りなかった。

この時点で30分しか経過していなかったが、そこから90分くらいD問題を考えてなんの成果も得られなかったので、残り時間はコードゴルフをしていた。終盤DとEがそこそこ通されたので順位は思っていたより落ちたが、赤パフォが出てよかった。

Dの解説を読んだ。括弧だけ抜き出してそろえることは考えていて、oxがどの位置に行くかで操作回数が変わりそうだと思っていたが、変わらないらしい。)o(()oとするかo()とするかで操作回数が変わらないことが、もっとたくさんの括弧と記号でも言えるということ。このあたりで僕がコンテスト中に考えていたことは終わりで、解説の残りについてはあまり考えていない。

コードゴルフをする。A問題は何かしらの言語で正規表現を使うのがよくて、sedだとダメらしいのはコンテスト中にわかっていたため、Perl。マッチの結果の0と1を使って計算をして答えを作り出すことで場合分けを減らしている。Cはdcで解けた。Nを精度kとして保存し、後から998244353で割った余りを求めるときに0kで戻していたが、実はループ内でkをどんどんデクリメントしていたので、ループ後にはちゃんと精度0になってくれている。

ラノベを1冊読んだ。「クラスに銃は似合わない。」。句点までが題名。主人公の護衛対象となるヒロインの性格があんまり合わず、読み始めはちょっとげんなりしていたが、進むにしたがって主人公にスポットライトが当たるようになって面白かった。読み終わった直後は、合わない要素が1つでもあることによってあまりよくない印象だったが、日記を書きながら冷静になってみると、最後はそこそこ楽しんで読めていたことに気づいた。最近読んだラノベを面白くないと思ってしまいがちなようだが、せっかく買っているのだからできるだけ好意的な感想を持ちたいものだ。

今日のAGCでへのkが自由色になった。へのk様と呼ばせていただきます。1999年生はmaroonさんとの間にめちゃくちゃデカい壁があると思っていたが、AtCoderのレートで見たらもうほとんど差がない。壁は相変わらず高くて、それを越えていくへのk様はすごい。

日記を書いていて、自分の文章について思うことがあった。

週記(2021/06/14-2021/06/20)

06/14(月)

先週の週記を投稿してからは、比較的すぐに布団に入った。典型90問を確認したが、どうにも短い書き方がわからない。3時間くらいなろうを読んで、午後0時半に就寝。

午後7時半起床。典型90問を通しておく。ある区間に対して、その中から1点選び、以前に出現した区間それぞれに対してどれくらいの確立で転倒数に寄与するかを計算する。これはO(N^2(R-L))。この方針でちょっと縮めてみたが、すぐに大幅に更新された。制約を大きくしたときの問題が全然解けていないが、そこで何か短い書き方が得られるのだろう。

僕と同じく毎週月曜日から日曜日までの日記をひとまとめにして投稿している人たちの週記を読んだ。

TeXで書いた数式をUnicodeで表示してくれるサイトを知った。

unicodeit.net

午後9時くらいからパソコンの前に座りつつなろうを読んでいたが、午後11時くらいに眠気が増してきたので布団に倒れこんだ。さらに1時間くらいなろうを読んで、午前0時半に寝落ち。

06/15(火)

午前2時半くらいに一瞬目を覚ましたらしいが、またすぐ寝たらしい。午前5時起床。

なろうを読んでいた。atgolferの更新を見て起きだし、パソコンの前に移動した。ちょっとコードゴルフ

atcoder.jp

インデックスを、対応する値を比較してソートしたい。これはPerlでやるよりbashでやったほうが短い。

まず空白区切りを改行区切りにするのは(全体が反転することさえ許せば)dc -e?fが短いが、この問題の入力サイズではTLEしてしまった。同様にxargs -n1もTLE。よってtr ' ' '\n'を使うことになった。あとはnlでインデックスをつけて、sort -nk2で値を比較してソートする。nl -v0で0-indexedにできるのもいい感じ。

普通なら最後にawk NF=1などとしてインデックスだけ取り出すところだが、Perlで数値として評価する限りは別にその必要はない。

今日の典型90問はぜひともコードゴルフしておきたい。自動submitの設定を行うため、Ubuntu機でコーディングしていた。

Vimのインサートモードで<Ctrl-@>を入力したかったのだが、文字コードでどれに対応するのかわからなかったため使えなかった。

週記(2021/06/07-2021/06/13) - kotatsugameの日記

先週、こういう話があったことを覚えていた。自分のメイン機(cygwin)だと<Ctrl-@>が効かなかったので、そういうものかと思っていたのだが、Ubuntuでは普通に動いた。では文字コードとしてはいくつだろうか。

<Ctrl-V><Ctrl-@>とタイプすると、^@という表示が見られる。これは<Ctrl-V><Ctrl-j>と同じなので、では<Ctrl-j>に対応する文字コード10だろうかと思ったが、冷静になると文字コード10は改行である。

そこで<Ctrl-V><Ctrl-@>をそのまま文字コードとして表示させてみた。すると、なんと文字コード0であることが分かった。つまり<Ctrl-@>に対応する文字はヌル文字だったということ。ヌル文字は提出できなかったような……と思いつつ、試しにojで提出してみたところ、普通に成功したし、ちゃんと<Ctrl-@>が動いているようだ。これを利用して、先週のコードを1B縮めることに成功した。

@Aの1つ前、文字コード64。なるほど。

まあこれは本題ではなかった。今日の典型90問のコードを書く。8進数と9進数の変換をしたり、8を5に置換する必要がある。それぞれdc -e8i9o?ptr 8 5が使える。これらのK回の繰り返しを実装する必要がある。

Vimを使うことにした。!!dc -e8i9o?p|tr 8 5K回繰り返す。繰り返しにはq...qでマクロを定義するのが一般的だが、ほかにもいくつか方法がある。@='command'とする方法は、!!がうまく動かないため使えない。文字列を入力して@.をマクロとして使う方法は使える。これがよいかと思ったが、そもそも!!...というコマンドは直前のものが@:に保存されるため、@:K-1回実行すればよいだけであった。K-1回実行するのは難しい(0が繰り返し回数ではなく行頭に移動するコマンドとして認識されるため)ので、@:に保存するために実行したコマンドについてはuで取り消しておくのが良い。このことはq...qでマクロを定義する際にも言える。

昨日の典型90問の制約強化版の解法を理解した。普通の転倒数を求める方法にBIT(あるいはセグ木)を用いるものと分割統治法を用いるものの2種類あるのと同様、今回の問題を解く方法も2つあるらしい。どちらにしても、区間[L,R]の各点について\frac 1{R-L+1}を対応させるのがミソだろう。

特に前者はコードゴルフに役立つ。座標圧縮する必要も、区間の和を高速に求める必要もないから、普通の配列操作で十分実現できる。書いてみたら、昨日縮められたものよりさらに短くなった。

昼になったので学食に行き、帰ってきてから木曜日のゼミの準備を始めた。広義積分がよくわからない。何とかググり散らかしてみたが、評価の際の不等号に等号をつけるかどうか、というところがよくわからなかった。まあどちらでも証明に問題はないが、どうせならより精密に書いておきたい。

教科書1ページで疲労困憊。典型90問のACも確認できたことだし(FAだった)、遊びに行くことにした。適当に競プロっぽい問題に仕立ててツイートしてみたが、思ったより解きにくいようだ。僕はO(N^3)のdpを考えて早々にあきらめてしまった。

ゲーセンに行く。前回のアップデートで、走っていなかったマップの譜面が通常開放されていたため、詰めた。13+が2譜面に14が1譜面。14のほうはとりあえずSSが出た。13+のほうもSSS出しておくか、と思って詰めていたら、なんと一気にAJが出てしまった。13+ではこれが初めてとなる。もう一方もすぐにSSSが出た。

そのあともしばらくプレイして、ゲーセンを離脱。たいぺーと合流してサイゼリヤに行った。注文する前に間違い探しに熱中。今の間違い探しは何とかすべて見つけ出すことができた。序盤に「角度が違う」系統の難問を倒せたのが勝因か。食事について、たいぺーはおやつの時間にガッツリ食べたらしく、ほうれん草のソテー1皿のみを注文していた。一方僕はデザートを含め4皿頼んだ。豪遊。

たいぺーのスマホでプロジェクトセカイをやらせてもらった。チュウニズムの感覚でスライドの終点を離さずにいたらミスを食らい、またフリックを縦に擦ると反応しなかったこともあり、1プレイ目は普通に落ちてしまった。なかなか難しい。

サイゼリヤを出て本屋に行き、ラノベを1冊買った。駅まで行く道でたいぺーと別れ、僕は再度ゲーセンに行くことにした。

本日2回目のゲーセンは信じられないくらい上手かった。ずっと残っていた13+の未鳥を3つ倒すことに成功した。大満足。

Giselleは、序盤~中盤で鳥許容を割らないようになっていたので詰めてみた。改めて譜面を確認し、ノーツをある程度覚えておいたところ、そこそこ勝率も高まった。ラストの微妙に速いトリルは、前まで必死に擦っていたが、リズムが掴めたのか普通に押せるようになっていた。その直前の鍵盤も右手2鍵でごり押すことでAJ通過できる。1か所だけ左手2鍵が連続しそうなところがあるが、そこだけ左右交互で捌く。

Viyella's Tearsはこの日1回目のプレイだった。序盤と中盤のホールド、その直前が上手かった。最後は崩れかけたが、何とか持ってくれた。

FREEDOM DiVEはラスクレラストで出た。これまでずっとトリルが間に合わないと愚痴っていたが、今日改めて最後のトリルを連打しながらFAST・LATE表示に気を配ってみたところ、FASTが出ているようだったので、実はそれほど速くないのでは?と疑ってみた。すると面白いように通った。あるいは、今日がたまたま腕が速く動く日だったのかもしれない。ラストの3鍵も普通に押せていた。1-2の鳥だが、そのうち1-1は最序盤で出してしまったので、ちゃんと餡蜜しておけばよかったと後悔している。

f:id:kotatsugame:20210619013315p:plain
91小節

丸で囲った部分をそれぞれ片手トリルで捌く。かなりおすすめ。速いトリルを左右に振られるとつらいので、ここに限らず序盤からこのように押している。

今日出る前にツイートした問題に対し、熨斗袋さんによる解法がツイートされた。僕が未履修のアルゴリズムを用いており、適当にツイートした問題がとんでもないことになってびっくりしている。自分では理解できていない。該当ツイートを貼っておこう。

帰ってから、このブログに存在するなろう小説に関係する記事を2本更新した。

kotatsugame.hatenablog.com

kotatsugame.hatenablog.com

しばらくパソコンの前に座っていたが、非常に眠い。布団に入ってなろうも読まずに寝た。午前3時だった。

06/16(水)

午前8時に目を覚ます。二度寝のチャンスを探すべくそのまま布団でなろうを読んでいたが、なかなか寝られなかった。結局正午に再度就寝。その後、午後6時前後にも一瞬起きたようだが、その時はまたすぐ寝ることに成功した。

午後8時起床。木曜日のゼミの発表準備が一切進んでおらず、非常にまずい。とりあえず起きて典型90問を解いておいた。今日のはなかなか面倒で、簡単な書き方がわからないため、ゴルフはしなかった。

食事をしてゼミの準備に取り掛かる。午後9時半から午前6時半くらいまでかけて、一応の完成を見た。担当範囲が微妙に狭い気もするが、これ以上は準備が間に合わない。途中、教科書と同様の図を挿入する必要に迫られ、一瞬は教科書の該当箇所をスキャンして貼り付けようかと思ったが、結局TikZで頑張ってコーディングした。グラフで囲まれた領域を塗るのは、適当に書いたら一発で動いてしまったので、よくわかっていない。

ゼミの時間まで寝ようかと思ったが、布団に入ってからなろうを読み始めてしまった。朝方典型90問の問題が投稿され、今日のぶんもかなりゴルフしやすそうな問題だったので、それの自動submitの設定を行う。今日はdcで、N=1の場合分けを少し考える必要がある。僕が最初に書いたコードだとN=K=1のときにWAになってしまうようで、気づいた時は非常に焦った。その設定が終わってからもまだ寝ず、ずっとなろうを読んでいたが、午前10時くらいになって寝るのを諦めることにした。学食の麺の部が開店するのを待って学食に行く。

帰ってきて、眼鏡のレンズを拭っていたら、ブリッジの部分で折れてしまった。

仕方がないので昔のブルーライトカットの眼鏡をかけたが、顔のサイズに合っていないのか、耳にかける部分(先セル、モダンというらしい)が頭に食い込んで非常に痛い。我慢する。新しい眼鏡を買いに行くことを考え、同じ眼鏡が良いと思って、メーカー「Silhouette」のサイトでいろいろ探していた。取り扱っている店舗はあるようだが、どうやら商品が古すぎてもう作っていないらしい。非常に残念。

Silhouette光学メガネ | 世界最軽量メガネ

そのようなことがあっても変わらずゼミは始まる。

発表は、準備した内容が薄いので、途中式を丁寧に追ったりしていた。まあやっていることはただの計算なのであまり面白みもない。そんな中でも、最後のほうに出てくる\sqrt xで分けることで評価を改善するという手法は、頑張って作った図もあって良い反応を得られた。全体的に皆さん優しい感想をくださるが、自分では発表中に大胆に詰まってしまったり、よくわからないことをモゴモゴ言ってしまったりして、今日はかなりダメだった気がする。一人で落ち込んでいる。やはり準備はちゃんとしなければならない。今日のスライドもここにリンクを貼っておく。

Apostol_Chapter3_3.4-3.5.pdf - Google ドライブ

TikZは「ティックス」と濁らずに読むらしい、ということを教えてもらった。

ゼミ中に今日の典型90問がAtCoderに投稿されたらしく、ちゃんとACできていた。しかし今日は自動submitの設定をしていたのにFAが取れなかった。FAとの差が挟んでいるsleepよりも長いのが不思議だが、継続的にアクセスしすぎてレスポンスに時間がかかったのだろうか。そのあたりのさじ加減がよくわからない。存在しないURLに対してリクエストを送るのがどれくらいの負荷なのかわからない。今はsleep 1でやっている。

途中で、最近発売されて話題のラムネの飲料を飲んでいた。あまりおいしく感じられなかった。

ゼミ終了。日記を書いていたが、あまりにも眠く、まともな文章が書けていない気がしたので、すぐに寝ることにした。午後5時就寝。

06/17(木)

消えた。

06/18(金)

06/17 午後11時半にちょっとだけ目を覚ましたが、ちょっとなろうを読むくらいで、30分ほどしてまた寝た。

午前7時半起床。いい感じ。朝からatgolferで更新が流れてきたので、縮めておいた。その後また布団に戻り、ずっとなろうを読んでいた。

正午くらいに、今日の典型90問が投稿された。今日の問題は、中央値によって絶対値の和の最小化をするやつを縦横それぞれで行う。こういうのはOctaveが強い。absを取って行列の全要素の総和を求める、というあたりが関数を入れ子にしていて長そうだが、どうしようもない、はず。norm関数も試してみたが、コード長は変わらなかった。

午後1時になってから学食に行き、ラーメンを食べた。帰る前に、生協に入っている眼鏡屋に行ってみた。この店は昨日Silhouetteのサイトで調べた取り扱い店ではないようだったが、一応確認しておこうというつもり。一応注文はできるらしいが、やはりこれまで使ってきた眼鏡と全く同じものはもうないようだ。似ている(と僕が感じるもの)も見当たらないので、すっぱり諦めて、この店でまったく別のフレームを探す。

つるがかなり柔軟に曲がるリムレスの眼鏡、ということで2つくらい見繕ってもらって、そのうち1つに決めた。が、ちょうど在庫が切れてしまっていたらしい。もう一方のフレームはあるようなので、そちらを注文することにした。視力などを図ってもらい、折れた眼鏡を渡して同じ形のレンズを作ってもらうことにした。これで注文内容は完成で、値段は2万円弱。Silhouetteの眼鏡を注文するつもりで親に報告していたが、ずいぶん安く済んだ。出来上がるのは月曜日以降になるらしい。

レンズにブルーライトカットを付けるか、という話があった。最近、実は効果がない・悪影響を及ぼす、というような言説を見た覚えがあったので、それについて質問してみたが、成人してしまったらとりあえず悪影響を受けることはないらしい。効果のほどは人によりけりだそうで、眼鏡屋さんの薦めもあって付けることにした。

帰ってからメール返信。インターンの件だ。これまで僕が返信したすべてのメールは、CCが消えてしまっていたらしい。これはよくないことだそうだ。僕がCCを使う意味がよくわかっていなかったのだが、まあ選考過程にいるのだから、人事の方も見れるようにする必要があるのだろう。今日返信するメールではちゃんと気を付けておいた。

論理学のミニットペーパーを2回分提出した。今日が期限だったが、提出は任意らしいので、まあなくてもよかった。そろそろ論理学の中間課題の期限が近づいてきている。課題の内容は、何やらこれまでの講義内容に関連して自由にテーマを設定し、2000文字以下で文章を書くということで、かなり謎。何も考えていないし何も思いつかない……。

それが終わってから、今日のサークル解説会の準備をした。E問題の解説役のみが決まっている。僕はF問題をやろうかとも思ったが、どのようにして解説したものかとんと想像つかなかったので、D問題を解説することにした。まあ特に問題なく終了。

2021/06/18 定例会 | puzzleknot 公式サイト

yukicoder 300に出た。5完。

Aはよい。dcで最短、Perlで純最短。Bも簡単、こちらもdcで最短だが、純最短はRakuだった。

Cから難しい。最大値と最小値に分けて考える。最大値がi以下であるような数列の和は平均すればN\times\frac{i+1}2になる。これがi^N通りあるので、掛け合わせることでそのような数列の和すべての和が得られる。i-1以下の分を引くと、最大値がちょうどiであるような数列の和すべての和が求まる。最小値でも同様のことをする。

DはSCCして連結成分ごとにトポロジカルソート順でつなぐ。強連結成分の中身はそれぞれぐるっと一回りするのがよいかと思ったが、そのようなループが2つ以上あれば、全部まとめてぐるっと一回りするほうが辺の数を少なくできるようだ。1WA。

Eは\frac{A_iK}{\sum A_i}を見て振り分けると思ったが、WA。タイブレークでミスっていると思いいろいろ比較を試していたが、通らなかった。実は最初に先ほど述べた値で比較するというのが間違いで、選んだ時に確率に掛けられる値が最も大きなものから貪欲に選んでいくのでよいようだ。

Fは考えていない。yukicoderが終わってからすぐにCF #726 div.2に出た。E1とE2を落とした。

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

Aは大体\sum a-nになる。負の場合は1が答え。Bは、基本的に四隅のうち2点を選ぶのが良くて、実際計算してみると左上と右下を選んでも右上と左下を選んでも同じになる。Cはソートしていくらかrotateした感じの列になるが、列が2項しかない場合はちょっといじる必要がある。あるいは、rotateした後に先頭と末尾を入れ替えるのでもいいだろう。

Dはちょっと難しい。実験してみると、序盤はあんまり規則的に見えないが、ある程度値が大きくなると偶奇で答えが分かれている(偶数ならAliceの勝ち)ように見える。これをもとに改めて序盤の規則をとらえなおしてみると、基本的には偶奇で別れて、2べきの場合だけ別の規則があるということになる。この結論から迎えに行くことで証明も可能。奇素数を素因数に持つ偶数からは奇数に遷移できて、奇数からは偶数にしか遷移できない。2べきの場合は、2べきでない偶数または2べきで一つ前の数にしか遷移できず、前者に遷移すると自分が負けるため2べきに遷移するのが良い。ということで、こちらは2を底としたときの指数の偶奇に帰着される。20のときは別扱い。

Eは、あるprefixの繰り返しになることがわかる。が、そこから自分がどのような勘違いを経てコンテスト中のコードにたどり着いたかがわからない。ともかく何やらSuffixArrayを使って怪しげなコードを書いて、E1E2共にそれでpretestを通してしまった。システスで落ちた。

Fはそこそこ難しかった。適当にエスパーすると、全域木を取って操作してよいという方針が思い浮かんだが、何の正当性もなく、出したら当然のように落ちた。改めてちゃんと考えることにする。まず、グラフが2部グラフである場合は実は簡単。2つに分けた一方の符号を反転すると、操作は次のように言い換えられる:辺を選んで一方からkを引き、もう一方にkを足す。これは、辺を通ってkだけ移動していると見てもよい。グラフは連結なので、2つに分けた頂点それぞれの変化量の和が等しければ可能であることがわかる。

グラフが2部グラフでない場合を考えたい。三角形のグラフで実験してみたところ、3つの頂点に足す値の総和が偶数ならば、どのような振り分け方でも必ず可能であることが分かった。偶数でなければならないというのは当たり前で、より一般にグラフ全体で見ると足せる値は偶数なので、変化量の総和が偶数でない場合は当然不可能。偶数である場合かつグラフが2部グラフでない場合が残ったが、これは実は必ず可能ではないかと勘づく。証明はできなかったが出すと通った。

コンテスト後にEのupsolveをした。あるprefixの繰り返しになることまでは良い。文字列stについて、s+s+s\dotst+t+t\dotsの辞書順比較はs+tt+sの辞書順比較と等しい、という事実があって、これを利用するらしい。特に今回stも与えられた文字列のprefixなので、慎重にやればZ-algorithmで判定できる。どこまで一致するか見て、その直後の文字を比較するということ。辞書順比較についての証明はTwitterでいくつか見つかる。

後者、2-2の部分はちょっと言葉が足りないような気がしていて、僕としてはs+t=t+sの場合どうなるか考えたいところである。まあ実際考えてみると、適当に置き換えていくことでs_{inf}=t_{inf}が言えるので、OK。

日記を書いてから布団に入り、ちょっと考え事をしていたら、すぐ寝落ちした。午前4時だった。

06/19(土)

午前9時半くらいに目を覚ます。今日の典型90問を確認した。ちょっとびっくりするが、結局トポロジカルソートをK通り求めよという問題で、実装方針は様々あれどどうとでもなりそう。解けたので安心してなろうを読み、午前11時くらいにまた寝落ちした。

午後5時起床。1時間くらいそのまま布団でなろうを読んでいたが、モゾモゾ起きだして食事し、典型90問の実装をした。問題なくAC。トポロジカルソートにおいてソート済みの列を入れるvectorと、探索待ちの頂点を入れるqueueは、1つのvectorで扱うことができるようだ。何個の頂点をソート済みにしたかでループを回して、vectorにおけるその位置の頂点から出ている辺を処理する。そこで新たに探索待ちになった頂点も、問答無用でそのvectorに入れておけばよい。このような実装テクを用いても普通に書いて1000Bを超えてしまった。コードゴルフは面倒なので、放置。

TCB37が始まっていた。明日までなので、時間がある今のうちに解いておく。時間があるといってもABCまで2時間しかないが、まあそれまでには終わるだろうという読み。実際終わった。この週記が公開される頃にはイベントも終了しているので、問題の感想も書いておこう。ちなみに今回も理論値を達成することができた。

https://techful-programming.com/user/event/2154

2問目は入力された2数の引き算をすればよい。制約からint型で十分だったようだが、いちいち確認するのも面倒なのでlongを用いた。4問目は入力に含まれる'f'の個数と数字を足せばよい。9問目は、ある点集合に対してはX座標とY座標のどちらでソートするかで2通りあって、どちらであっても真ん中で分割することになる。分割したそれぞれで再帰し、どちらのブロックで操作するかの順番を考慮しつつ掛け合わせる。10問目は一般の構文解析をしそうに見えるが、よくEBNFを見ると、いくつかのclauseが&で結合された形に固定されていることがわかる。それぞれのclauseが真となる条件は、\mathbb{F}_2上の演算としてとらえれば!a=a+1であることを鑑みて線形方程式で表せ、結局全体として連立方程式となる。2000行2001列の行列を掃き出し法することになるが、bitsetを用いることで十分高速にできる。

シャワーを浴びたりして時間をつぶし、午後9時からABC206に出た。全完。

atcoder.jp

Aからかなり面倒に見える。とりあえずAWKで通しておいた。Bは見たことがある。dc 8Bだが、念のため手元で確認していた。Cは適当にRuby。DからはC++を用いた。D問題はUFで、ACLのDSUは慣れていないため自前のライブラリを使った。

E問題は非常に難しい。サンプルが合っていないことに気づかず提出したりして、大変だった。まずx\lt yとしておく。x\mid yとなるものを引くと、各xに対しyの候補はR-x-\left(\frac R x-1\right)個ある。ここから互いに素な組を除きたい。各yに対し、y素因数分解し、各素数を選ぶか選ばないかで包除原理を用いることで、[L,y)にあるyと互いに素な数の個数がわかる。計算量的にかなり怪しいが、最大ケースであるところのサンプル3でも十分間に合うようだったので提出した。

一方Fは非常に簡単。区間DPとGrundy数。ただ慌てていたのか配列外参照してしまった。区間の両端の制約が1以上100以下ということで、区間の幅は99以下。DP配列を定義するときはこれを覚えていたが、計算の途中で100と勘違いしていた箇所があった。

コードゴルフをする。A問題は、冷静になると191との大小を比較するだけでよい。dc。さすがに負けたかと思ったが、勝った。B問題は見たことがあると書いたが、以前に全く同じ問題が出題されていて、十分にコードゴルフされていたということ。いつだったかの配信の途中で発見したもので、どうやらそれを覚えてい(てくれ)たらしい。1分未満で全く同じ回答が提出されており、負け。

X(X+1)2≥NX(X+1)2≥Nを満たす最小の整数XXは⌊2N+⌊2N−−−√⌋−−−−−−−−−−−√⌋⌊2N+⌊2N⌋⌋。

週記(2021/03/29-2021/04/04) - kotatsugameの日記

B - Savings

C - Go Home

Cは、先ほどはtallyを使って書いたが、普通にインクリメントしつつ引き算していくのが短い。AWK。Dはdfsしたほうが短い。Perl。Eはコンテスト後にkyopro_friendsさんの解説を読んで縮めておいた。Perlだと間に合わなかったがRubyなら何とか間に合う。さらにVimで縮んだ。Fは放置。

来週再来週とゼミの時間が微妙に縮むことになったらしい。1人が教育実習に行くということで、ゼミの発表順はある程度前後していたが、この機会に再度見直し、来週また僕が発表することになった。今週は不甲斐ない感じだったので、来週は頑張りたい。

布団に入ってちょっとなろうを読もうとしたが、すぐ寝た。午前2時だった。

06/20(日)

午前5時くらいに起きてしまう。

眠気がありつつ、寝られない。ずっと布団でゴロゴロしつつなろうを読んでいた。

途中で昨日のA問題のコードが縮まないか試していた。Rコマンドで所望の結果を得るために、3*しているのがどうにかならないかと思い、例えば190や192を使ってみたり、符号を反転してみたりしたが、どれもうまくいかないようだった。当然うまくいかないことは紙で考えればわかることだったろうが、念のため、と言いつつ実際は確認するのが面倒だったため、毎回提出してはWAを確認していた。

正午くらいにまた寝落ちした。次に午後4時半に腹を壊して起きる。確か今日は人権こどふぉだったよな、と思って時間を確認してみると、午後7時からということでまだ先のことだった。ということで、気にせずまたすぐに寝た。

午後9時に起きた。人権こどふぉはもうすぐ終了という頃合いだった。信じられないが、そこまで出ようとは思っていなかったので、特に気にせずそのまま布団でなろうを読み続けた。

日付が変わるあたりでTCB37が終了し、すぐ結果が順位表に反映された。8問目まで理論値という人はかなりいたが、蓋を開けてみると全体を通して理論値という人は3人しかいなかった。僕はタイム順で2位だった。10問目はbitset高速化だったが、TechFULのジャッジの速度を怪しんでいた人もいるようだ。これについては、いつだかのアップデートで(深い再帰がエラーになることも含め)解消されている、という認識。ほかにも、掃き出し法は上三角行列に留めることで定数倍が軽くなる、というのも効いていることに気づいた。当時は何も考えず、これしかないだろ!という感じで投げていた。

そのまま午前3時くらいまでなろうを読み続けていたが、また寝落ちした。結局この日は布団からほとんど出ていない。相変わらず読んでいるのは↓のなろう。最新話まで残り200話となっている。

https://ncode.syosetu.com/n5534co/

週記(2021/06/07-2021/06/13)

06/07(月)

先週の週記を投稿してからの話。ちょっとハーメルンを開くことがあって、面白そうなものを1つ見つけたので読んだ。ターニャ・デグレチャフダンブルドア世代のホグワーツに入学する話で、設定に惹かれたのだが、すでにエタっていて涙。

syosetu.org

いろいろな人の週記・日記を漁っていた。僕の友人の一人もサイトを自作して週記を書こうとしているようだ。サイトにこの「kotatsugameの日記」のリンクを貼ってくれているようなので、こちらからもここで紹介しておきたい。

YASUTAROのホームページ

ABC204Dが縮んだ。縮んだというか、実は解法がAGC020C-Median Sumと全く同一らしく、そちらのコード(ABC204の元最短コードより短い)をコピペしてきただけ。問題文だけ聞いても同じであるとは思いにくいが、コードを見れば解法が全く同じであることは直ちに理解できる。

C - Median Sum

大学の課題をする。まず数理統計学のレポートを終わらせた。こちらはちょっとした課題を解くだけなので、簡単。問題は数学基礎論特選のレポート。

数学基礎論特選」という講義のレポートを書いていた。3回分の講義資料を読んで、途中にある問題からいくつか選んで解く。

週記(2021/05/10-2021/05/16) - kotatsugameの日記

この日から1か月経過したということで、また3回分の講義資料が溜まり、同様に問題を選んで解く課題が出された。3回ごとに1区切りつくらしいので、前回の講義資料の最後のほうは全然わからないまま放置していたのだが、どうやらその後も続きの話をしていたらしく、慌てて前回格闘した記憶を呼び覚ましながら講義資料を読んでいた。ただ、前回ラストで僕の頭を破壊したゲーデル数や証明可能性についての記号などが、今回は様相論理として□に吸収されている(?)ので、それをそういうものと捉えることで何とか講義資料を読み進められている。

しかし3回分のスライドのうち1回目の半分まで読んだ段階で嫌になってきてしまい、布団に寝っ転がってなろうを読み始めてしまった。

かなり眠気があるが、せっかく起きているのだしということで学食に行くことにした。

平常時はご飯(特大)を注文していたが、今日は提供されないらしかったので、迷った挙句ご飯(大)とご飯(中)を購入した。ちょっと多かったので、次回は中サイズを2つ注文することにしよう。

週記(2021/05/10-2021/05/16) - kotatsugameの日記

店頭の表示ではご飯の特大がありそうだったが、注文する場所に掲示されているものを確認すると、そちらでは特大は存在しなかった。やはり提供されていないのだろう。

帰ってきてまた布団にダイブしてなろうを読んでいたが、すぐ力尽きて寝落ち。午後1時半から午後8時まで寝ていた。

起きてすぐ典型90問の今日の分を解く。今日は左右からLISをする。Rubyで書いてニコニコしていたが、すぐ大幅に縮められた。よくわからない。

解いてからまた布団に戻り、なろうを読んでいたら寝落ちした。午前1時だった。

06/08(火)

午前7時半に目を覚ます。寝落ちばっかりで自分の体調がよくわからず、なんとなく眠さを感じつつ午前11時半まで布団でなろうを読んでいたが、今日もまた起きているのだし、と学食に行くことにした。

昨日の写真でも確認できるが、ご飯はシートをかけた状態で提供される。「最近はこうなのか」という指摘があったが、これは別にコロナ対策とかではなく、僕が入学した当初からこのようにされていた。特にお昼時、混雑する時間帯のご飯の提供はすでに盛られたものが棚に並べられているため、乾燥を防いでいるのだろう。

選考プロセスが遅れるかも、という話があったものの、今日聞いた感じだともう来週には会議にかけて下さるらしい。

週記(2021/05/31-2021/06/06) - kotatsugameの日記

このインターンに内定が出た。ありがたい限り。手続きはすぐに行うが、実際に働き始めるのは僕の院試が終了してから、つまり9月くらいからになるようだ。

1333話!

今日の典型90問が投稿されていたので、解いた。コードゴルフとしては、配列の両端を変数で持っておいて左右に伸ばす実装がよい。[l,r)として持つとアクセスがl+x-1になるが、(l,r]として持つとl+xでアクセスできる。工夫としてはそのくらいだろう。

また昨日のレポートの続きに取り組む。昨日はある程度講義資料を読んでから問題に取り組もうと考えていたが、そんな余裕はない。何とか解読できた問題に全力を注ぐと、ちょっと怪しいところはあるが、とりあえず1問解けた。

もう無理!とばかりに布団にダイブし、またなろうを読んでいたが、午後7時に寝落ちした。

06/09(水)

06/08 午後11時に起きた。生活リズムがヤバい。

昨日一昨日とやってきたレポートは、06/09 午後1時が提出締め切りである。つまり、今日。全然終わっていない。3回分の講義資料があると言っていて、一昨日第1回の半分まで進めたものの、昨日は問題を解いてしかいないため一切進まなかった。つまり、残り半日で2回半進める必要がある。しかも謎の生活リズムで、自分がこれから提出期限までどの程度眠ることになるのかもわからない。

とりあえずまた講義資料と格闘する。講義資料の第2回の序盤まで読み進め、問題をさらに2問解くことに成功した。提出するには10問用意されている問題から5問以上解くことが求められている。まだ3問しかできていないが、実はそれだけ提出しても許されるのではないだろうか。とにもかくにも疲れ果てたので、布団に戻ることにした。

なんとなく眠気を感じていたので、布団でなろうを読みつつ寝る体勢を作っていた。もちろん提出期限には遅れないよう目覚ましをセットしてあった。しかししばらく待っていても眠れそうになかったので、あきらめて布団から這い出し、またレポートと格闘することにした。

Topcoderからメールが来ていた。今日はSRMらしいが、よく見るとdiv.2 onlyらしい。SRMでdiv.2 onlyなのは初めて見る。

午前3時からまたレポート。よくわからない箇所はもうすっぱり諦めて、少しでもわかる部分の周辺を何とか読んでいく。前回の課題の際によく読まないまま放置した箇所の進化系みたいな命題をバッサリ読み飛ばしてしまったが、何とか解けそうな問題を選んで解いていき、午前5時に5問の回答が完成した。すぐに提出。

前回のレポートについていたコメントを読んでいた。かなりボコボコで厳しい。講義資料で導入された関数を使用した箇所で、関数の定義がないという理由で減点されていたので、そこについてはClassroomのコメントから異議を申し立てておいた。布団に戻ってなろうを読んでいたが、午前6時にコメントにTAからの返信が来た。どうやら点数を付けなおしてくれるらしい。朝早くからありがたい話である。

またずっとなろうを読んでいたが、午前10時まで起きていられたので、今日も学食に行った。

今日は結構早くに家を出たので、午前11時過ぎには食事を終えられた。昼休みが始まる前、人が少ないうちに床屋に行っておくことにした。かなり眠くて、髪の毛を切ってもらっている間はほとんど意識がなかったが、今日担当してくれた人がかなり威勢がよく、ジョキジョキ音を立てて鋏を動かしていたことを覚えている。というか鋏に髪の毛が挟まってかなり痛かった。しかし出来上がりは良さそう。髪の毛の生え方の左右非対称性などを説明されたが、それを考慮して長さを調節しているらしい。

床屋を出て家に帰ろうとしたが、横断歩道がない箇所で道路を横断しようとした際、近づいてくる車に気づけなかったらしい。前から車が来ているのにフラフラ車道に自転車を漕ぎだしてしまい、かなりヒヤッとした。確実に見えているはずの近さだったが、寝ぼけていたのだろうか。

床屋で待っている間に典型90問が投稿されたことは確認していた。今日の問題はグラフを作ってBFS。Rubyで書いたらPerlに取られたが、ちょっと格闘したら取り返せた。BFSで使うキューを@0にすることで、グラフを作るのとBFSの始点をキューに入れるのをほぼ同じコードでできたのがよかったのではないだろうか。

また布団に戻ってなろうを読んでいたが、午後3時くらいに寝落ちした。

06/10(木)

06/09 午後8時に起床。

今週月曜日の典型90問についてはRubyでかなり負けたと書いた。その問題は数列の左右からLISを計算するが、数列の左右から同様の処理をした後にマージするという意味で似たような問題が存在し、そちらも縮んでいる。その最短コードを見ることによって、月曜日の問題がどのように短縮されたのかが少しだけ窺い知れていた。その問題のコードゴルフはちょっとだけ取り合いが発生していて、火曜日にもちょっと縮んでいた。今日も少し縮んだ。

atcoder.jp

似たような処理を2回行うということで、以前はprocを作成していたのだが、コードを文字列として2回繰り返すほうが短いらしい。毎回reverse!することで、数列の左右から処理を行うこともできている。

コードゴルフした後はまたなろうを読み続けていたが、午前1時半から午前4時半までまた寝落ちしていた。

起きてからもなろうを読み続け、午前11時半になったので学食に向かった。

帰ってきてしばらく週記を書きつつ、今週のゼミに参加した。ビッグオーの記法が導入されたが、f(x)=O(x)と書くと等号なのに推移律が成り立たないということが言われていた。これは僕にはない着眼点ですごいなあという気持ち。f(x)\in O(x)という記法もあるらしいという指摘をした。等号に右から左への向きがある、という考え方もあるらしい。あとは、PDFファイルをMicrosoft Edgeで表示していた人のURL欄にWindowsのユーザ名=本名が表示されているのでどうにかしたほうが良いのでは、と言われていたため、F11キーを押して全画面モードに入ることで副次的にURL欄が見えなくなる、という話もした。

別の人がPARI/GPの紹介をして、それでコーディングして条件を満たすものを全列挙したりしていた。コードを詳しく読んでいる暇はなかったが、チラリと見えた限りではif文やfor文の記法が独特。if(条件,真,偽)という風に関係する式をすべてかっこでくくり、複数の文章を書く場合はセミコロンで区切る。セミコロンとコンマを演算子のようにとらえたとき、セミコロンのほうがコンマより優先度が高いと言えるのが独特に感じられた。これは僕の触れたことのある言語ではImageMagickと同じだが、for文は競プロの文脈で言うrepのようになっているようだ。

途中で今日の典型90問を解いたりもした。まああからさまな制約。

ゼミが終わって布団に入りなろうを読もうとしたが、即座に寝落ちした。午後5時から午後9時まで寝ていた。

起きてからもしばらくなろうを読んでいたが、午後11時半からCF #725 div.3に出た。とりあえず全完だが、システスは明日。

Dashboard - Codeforces Round #725 (Div. 3) - Codeforces

Aから面倒。最大・最小のインデックスを見てなんやかやする。Bは平均値以上の要素を数える。Cはlower_boundとかupper_boundを使う。Dはabの素因数の個数がk以上ならばよくて、k=1の場合がコーナーケース。コーナーケースには気づいていたのに、a素因数分解するコードをコピペした時の修正ミスで1WAしてしまい赤っ恥。Eは長さと"haha"の個数と左右3文字ずつを保存しておく。面倒。Fはf(r)-f(l)と変形する。桁ごとにみるとf(n)=\sum_i \left\lfloor\frac{n}{10^i}\right\rfloorとわかる。半信半疑で出したら通った。

Gはfloorがからむ最小値で、線形計画法のような図を描いてみると三分探索できそう。ただfloorがついたそれには最近煮え湯を飲まされたので、ABC204Eと同様floorを外してから三分探索した。TLを見ていると、多いほうから優先的に引く貪欲でもよいらしい。xyが近づくまでは割り算で一気に計算し、あとは2回ずつペアにして引くことを考える。

全完してからは布団に入り、眠気をこらえつつなろうを読んでいた。午前5時半就寝。

06/11(金)

今日はぜひとも学食に行きたいと思ったので、目覚ましを午前11時と午後0時半にセットしていた。午前11時の目覚ましは、止めた記憶こそあるものの、瞬時に二度寝してしまったらしい。目を瞑った次の瞬間再度目覚ましが鳴り響いたと感じた。

今日の典型90問が投稿されていた。最初は遅延セグメント木を書いてしまったが、これは明らかに寝ぼけている。ほとんど同様の問題が僕の参加したJOI本選の第1問目だったことを覚えていて、その解説を見て、データ構造など必要ないことに思い至った。とりあえずそれで通しておき、午後1時くらいに学食に行った。

atcoder.jp

今日も納豆ご飯を食べようとしたが、お昼過ぎとあって大したものは残っていなかった。納豆も一見売り切れかと思ったが、よく見ると普段とは別のところに2個だけ残っていたので、これ幸いと確保。サラダ類は売り切れていたので、適当な副菜を購入した。

これで5日間毎日ほとんど同じものを食べていたことになる。水曜日にも言及したように、これは儀式の一種であるが、とはいえ別に何か念願があるわけでもない。毎日同じものを食べていたら面白いかなと思ったが、反応は全然ないので、結局自分の行動を常に追いかけている人、つまりは自分にしか通じない面白さだったということ。

帰りに購買に寄って新刊の短編集を購入した。米澤穂信さんの手になる短編も収録されているとのことで確認すると、見覚えのないタイトルだったため、書籍には初収録であると判断したのが購入の決め手。奥付を見たところ、この判断は正しかった。

books.bunshun.jp

ほかにもカロリーメイトを購入して帰宅。

帰ってきてしばらく今日の典型90問のコードゴルフをし、そのあと布団でなろうを読んでいた。ちょっと寝なおそうかとも考えたが、なろうを読んでいるうちに時間は過ぎていき、結局寝ないまま午後6時半になった。サークル解説会の準備をする。

今日はABC204の解説会の予定。F問題の解説を書いたらもうかなりいい時間で、E問題の解説も書けるかと思ったが、微妙に間に合わなかったのでかなり適当なスライドになってしまった。今日はこの2問だけの発表で、参加者も3人。僕がひとしきり喋って、終了した。先週の記事をふと見ると、日付がコピペ元のまま変わっていなかったので、直しておいた。

2021/06/11 定例会 | puzzleknot 公式サイト

そういえば昨日のCFのシステスが終了していた。全完10位。ちゃんと通ってよかった。

yukicoder 299に出た。滑り込み全完。

yukicoder contest 299 (BANNED CONTEST) - yukicoder

Aはよい。入力を加工してdcに流し込む方法で現在の最短コードを持っている。Bは面倒だが拡張ユークリッドの互除法で解いた。解説を見ると1\dots NMを全探索するのでもよかったらしい。Cは赤字の制約が怪しいが、実は全部同じコードで解ける。復元が怠い。Dは係数を求めると1乗、2乗、3乗の和になるので、公式を使って和を消す。

Eは最初勝敗が決まるまで延々ゲームを続けるのだと思っており線型方程式を解こうとしていたが、よく見るとただの行列累乗。さすがにもう行列累乗は飽きた。謎のREが出てしばらくコードとにらめっこしていたが、入力に制約違反があったらしい。

Fはなんちゃらモーメントなるヤバそうな単語が見受けられるが、よく見ると偏差をk乗して足しているだけ。k=1の時は0でk=2の時はいわゆる分散、つまり2乗の平均引く平均の2乗。もしかしてk=3,4のときも……?と思って計算してみると、3乗や4乗の平均まで計算しておけば求められることが分かった。遅延セグ木に5個くらい値を載せる。列が円環なのも面倒ポイント。

Gは包除原理。愚直にやれば、q=iの時は(i+1)\times(T_i+1)のdp配列を作って計算したくなる。これにはおおよそ\sum_{j=1}^i jT_i=\frac{i(i+1)}2 T_iくらいの計算が必要になる。つまり全体で\sum_{i=1}^Q \frac{i(i+1)}2 T_i\approx \frac 1 2 \sum_{i=1}^Q i^2 T_i\approx \frac{Q^3 \max T}6\approx 5\times 10^8。TL 4secなので間に合う。2500ms。

日記を書いてから布団に入りなろうを開いたが、眠気に耐えかねてすぐ寝た。午前3時半だった。

06/12(土)

午前9時に目を覚ましてしまう。

Twitterで今日の典型90問を確認し、さて寝なおそうと思ったが、考えているうちに眠気が覚めてきてしまった。星7ということで気合を入れてしばらくあれこれ考えていたが、ただの畳み込みであることに気づいてびっくり。解けたはよいが眠れなくなってしまったので、なろうを読んでいた。

午前11時半くらいになって、AtCoderのほうで問題が公開されたことを知り、布団から起き上がってコーディングした。C++ACLで書くのが一番短いだろうと考え、269Bのコードを作成したが、以前ALPCのConvolutionの最短コードをRubyで更新したことを思い出して、そのコードを流用したところ、13B縮んだ。ALPCにおいては4000msくらいかかっていたので、畳み込みを2回行うこの問題で間に合うこと自体かなり驚きなのだが、やはり数列の長さが短いことが効いているのか、それともALPCのほうは入力の読み込みがかなり遅いのか。

ALPCのConvolutionでゴルフをしていた。Ruby多倍長整数を使って、16進で20桁ごとに数値を埋め込むと、掛け合わせても20桁から溢れないので、復元できるということらしい。

週記(2021/05/17-2021/-5/23) - kotatsugameの日記

さらにVimを使ってRubyのコードを作り、実行するテクを用いて、さらに15B縮んだ。これが現在の最短コード、241Bである。元のRubyコードのほうもまだ縮みそうなので、こちらもそれに応じて更新される予感があるが、今はわからない。Vimのインサートモードで<Ctrl-@>を入力したかったのだが、文字コードでどれに対応するのかわからなかったため使えなかった。一応ASCIIコードのnon-printableな文字はすべて試したので、これ以上はUnicodeで2B文字になり、<Ctrl-A><Esc>と同じ長さになって縮まないだろう。

そんなことをしていると午後2時になってしまった。布団に戻る。今日は生協の弁当配達があるので午後3時には起きていたいが、目覚ましを信じ、訪れた眠気に身を任せて寝ることにした。

午後3時と4時にかけていた目覚ましによって浅い睡眠状態だったのがよかったのか、今日も何とかチャイムに気づくことができた。午後4時半だった。受け取って再度就寝し、午後7時半に起床。

かなり眠い。うつらうつらTwitterをしていたら、ホスフィンから書いた文章に間違いがないか確かめてくれというDMが来たので、それを読んでいた。途中で午後9時になったのでARC122に参加した。

Tokio Marine & Nichido Fire Insurance Programming Contest 2021(AtCoder Regular Contest 122) - AtCoder

5完31位、パフォーマンス2955、レートは2724→2749(+25)。D問題までは非常に良かっただけに、E問題での失速が気になるところ。まあレートはいい感じに上がったので良かった。

Aは普通に考えれば最後の文字を持つdpだが、新しく足すA_iの寄与を計算する必要があるため、値だけではなく場合の数を求めるdpも同時に行う必要がある。見た瞬間に解けた。FA。

Bはちょっと計算すると\max(A_i-x,x)になる。これは下に凸な関数なので、すべて足した値も下に凸となり三分探索できるが、コンテスト中の僕は三分探索を信用できなかったため、もうちょっと考察した。\max(A_i-x,x)x=\frac{A_i}2で最小値を取る。グラフを書くと、そこを境に傾きが-1から1になっているわけで、これは絶対値関数の平行移動である。つまり、そのmaxいくつかの和は、\sum |A_i-x|の最小化と同様に考えれば、いずれかのiについて\frac{A_i}2で最小値を取る。これで探索すべき値がN個になり、左と右で和をもつことですべての場合について計算できる。さらに考察を進めれば候補の中央値を取ればよいこともわかるが、コンテスト中はすべて試す方針で通した。

Cは難しい。ちょっと手で計算してみると、値を大きく増やすにはx+=yy+=xフィボナッチ数列を作るくらいしか手段がなさそうだとわかる。フィボナッチ数列から適当に要素を選んで和を取ると任意の非負整数が作れる、というのは(それが値の大きいほうから貪欲に取って良いことも含めて)競プロでよく見る定理。今回も、適当なタイミングでxyを1増やしてやることによってフィボナッチ数列を途中から始めて合流させる感じにできそうなので、方針としてはこれでよい。ただ実装が面倒。とりあえずフィボナッチ数列が何項目まで必要かとどのタイミングで増やすかだけ確定させて、偶奇は最後に帳尻を合わせることにした。出力を見ていてもよくわからないが、ランダムテストを回した感じではよさそうだったので提出、AC。解説だと、使うフィボナッチ数列の長さを決め打つことで偶奇を決め打てるようにしていた。

Dはかなり簡単だった。まず最上位bitで場合分けするのはすぐわかる。0と1が両方偶数個あるならそれぞれで再帰し、1つ下のbitを見る。奇数個ある場合を考える。現在見ているbitが0であるような要素aと1であるような要素bについてのa^bの最小値を求めると、実はそれが答えになる。なぜなら、Aliceがabを選んだタイミングでBobがもう一方を選ぶことでa^bが作れ、Aliceがそれ以外の要素を選んだときは、それと現在見ているbitが同じ要素をペアにあてがうことでa^b未満になるから。結局Aliceは何もできないということらしい。a^bの最小値を求めるフェーズだが、これはbinarytrieで解ける。ライブラリを貼り付けてAC。10分で解けてしまい、かなり全能感を感じた。

Eは迷走してしまった。106までの素因数を求めておくと、1018素因数分解が必要なだけできる。109オーダーの素数2つの積と素数を区別するのが問題だが、これは素因数分解する値同士でgcdを計算して出てきた素数だけ考えればよい。これで出てこない素数2つの積は、今回の問題だと素数と同様に扱っても構わないため。実はこれで問題が解けて、あとは指数を見ながら数列の最後の項から貪欲に構築していけばよかったのに、何か難しいステップがあると思い込んでしまい、気づくのにかなり時間がかかった。さらに素因数分解のミスで2WA。解説を読んで気付いたが、指数を見ながら構築するというのは指数のminとmaxの話になって、これは元の数においてはgcdとlcmに対応するため、素因数分解する必要はなかった。つまり後ろから貪欲に取ってよいことさえ考察できればよく、素因数分解の具体的な方法を考えるのは後回しにしておいてもよかったのだ。

コードゴルフをする。Aはよくわからないdcコードが最短。BはOctaveだったが、謎のabsを噛ませていたのに気づかず、取られてしまった。これは非常に悔しい。EはRuby。Cを書こうとしたがすでにdcで縮め切られており、しばらく考えてもこれ以上縮まなさそうだったので諦めた。

ホスフィンの文章を読む作業に戻る。最後まで読んで、わからなかった部分を質問し、いくつか誤植を指摘した。扱っている問題に対する興味がなかったので、詳しい部分は理解していない箇所も残っているが、誤植を見つけるくらいなら十分だった。

朝方、布団に入ってなろうを読んだ。午前10時に寝落ちした。

06/13(日)

午後6時半起床。ABCまでずっとなろうを読んでいた。始まる直前になろうのバトルシーンが終了して一段落ついた。ABC205に出る。

AtCoder Beginner Contest 205 - AtCoder

Aはdc。精度を設定してから100で割るより、0.01を掛けたほうが短い。割り算では精度は必ず設定した値にされるが、掛け算はオペランドの精度に合わせた結果が得られる。

Bは最短コードがどのようになるかよくわからなかったのでとりあえずRubyで書いたが、putsとしなければならないところをpにしてしまい1WA。コードゴルフsed。基本は/\<\(.*\) .* \1\>/で、テストケースハックなどを行い縮めておいた。

Cは普通に多倍長整数を使うとどのようにしてもTLEする。仕方なくC++で場合分けを大量にして通しておいた。Dは適当に二分探索で、サンプルを合わせたら通った。

Eは非常に難しかった。dp[i][w-b]のようなdpを考えると、遷移は±1なのでいつもの括弧列とか格子を進む場合の数の図が思い浮かぶ。ジグザグの図を考えると、問題の条件は、特定の高さ以上に進めないことを表す。これはカタラン数を求めるのと同様にグリッドを折り返すことで求められる。答えが0のケースで値を引きすぎて1WA。カタラン数の下りは見覚えがあったが、TLによれば数学ガールらしい。

Fはいつもの行と列を結ぶグラフのマッチングだと思って二部マッチングのライブラリを貼ったが、サンプルが合わない。それはそうで、駒に対して扱える辺が決まっている。この条件を表現しようと思い、条件をどのように並べるかいろいろ試してみると、行-条件-列で表現できることが分かった。フローを流してAC。

コードゴルフをする。A、Bは最初のほうにACしたものでよい。

Cは、適当な数でmodを取ったりしてみていたが、ここでCは偶奇さえ合っていれば問題ないことに気づく。例えばC%2+2としておけば累乗した数を直接比較できる。答えを出力する際の場合分けも難しいが、BC-ACからd2^v/で符号を取り出し、61から引くことで答えの文字コードを得るのが良さそう。本当はAC-BCを使って61を足したいところだが、どちらにせよrの1Bがかかる。……と思っていたが、Pコマンドは値の絶対値を取ってくれるらしい。つまり61から引く=61-xではなく61を引く=x-61でも正しい出力が得られる。これで-1B。

DはRuby。EもRubyだが、こちらはVimRubyコードを書くテクでさらに縮んだ。

Fのコードゴルフをする前にCodeforcesに出た。今日はcombined。

Dashboard - Codeforces LATOKEN Round 1 (Div. 1 + Div. 2) - Codeforces

6完62位、2839→2842(+3)でhighest。途中詰まってなろうを読んでいたが、終盤になって気づきを得て考察が進んでしまい、通せず悔しい思いをした。しかし解法を聞く限りまだ遠そう。

Aは市松模様に塗るしかない。Bは幅1の突出している部分を縮める。Cは一緒にflipしなければならない列がグラフの連結成分として表せる。答えは2の連結成分数乗。Dは、まず適当な頂点を1回聞いて、そこからの距離が偶数の頂点と奇数の頂点のうち少ないほうを全部聞く。辺の復元は面倒だと思ったが、距離1の頂点を全部つないだ後重複を除けばOK。インタラクティブのくせに入力を2e6個ほど読む必要があって、1500msくらいかかっている。

Eもインタラクティブ。非常に難しい。すべての値を同じ回数だけ聞くことを考えていたが、そんな必要はない。結局、聞く回数として最初1,1,1...という列を用意し、順に2ずつ足しながら総和がKの倍数になるのを待った。復元については、毎回ソートして残り回数が多いものからK個ずつ使う。これでよいことは自明ではないが、コンテスト中は気づかなかった。N=4K=3という入力の時に聞く回数が3,1,1,1のような列を使ってしまい、1WA。クエリ回数が2回のはずなのに聞く回数が3の要素があるとダメということだ。

つまり、N項の非負整数列A0\lt K\le N\sum A\equiv 0\bmod{K}かつ\max A\le \frac{\sum A}Kを満たすとき、K個の要素を選んで同時に1引くことを繰り返してAの値をすべて0にできるという事実と、実際の方法は値が大きな要素から貪欲にK個ずつ選ぶことで構成できるということ。何回かこの事実を用いる問題を解いた覚えがあるが、証明は覚えていない。TLを見る限り\frac{\sum A}Kに関する帰納法が回るらしい。

コンテスト後のTLでもいろいろ解法が流れてきた。僕のようにできるだけ均す方法やフローを流す方法もあったが、一番すごかったのはSSRSさんの、聞いた回数が奇数回のものの個数をもってグラフを作成しBFSする方法。

F1は連結成分をまとめた後辺を張ってSCCし、入次数が0の頂点を数えた。後から考えてみれば、連結成分をまとめる必要はなかった。F2は、SCCした後のDAGにおいて到達できなければならない頂点がいくつか指定され、それらすべてに到達できるような頂点集合の最小サイズを求める問題になる。DAGの道被覆というワードで調べたりしていたが、よく考えるとこれは違う。グリッドからグラフを作成したので、それによってグラフが持つことになる特徴を利用するのだと思ったが、わからずに終わった。

どうやら、入次数が0の頂点を抜き出してグリッドの左から順に並べておくと、ある頂点に到達できる入次数0の頂点は区間になるらしい。つまり、区間がいくつか与えられるので、それぞれの区間に含まれる頂点が1つ以上存在するように頂点を選ぶ問題になって、これは区間スケジューリングで解ける。かなり頭が良い。

CF後にABC-Fのゴルフもした。Cythonとnetworkx。行と列に対応する頂点は、駒の条件を表すのに必要な分だけ用意しておけばよい。DiGraphは何回も同じ辺を張ると最後に張ったものが使われるようなので、それを利用して必要になるたびに行と列の頂点を用意してみた。

そういえば、今日のABCのdifficultyは灰-灰-灰-茶-黄-黄らしい。かなりすごいことになっている。

日記を書いていたら昨日のARC-Bが縮んだ。\max(x,A-x)だったが、\frac{A+|A-2x|}2とするほうが短かった。