読書記録(2021)

kotatsugame.hatenablog.com

1月

  • 1日
    涼宮ハルヒの直観
  • 2日
    セプテムレックス
  • 3日
    いわくつき魔族教師と天使候補生
  • 4日
    人生∞周目の精霊使い
  • 5日
    クラスの大嫌いな女子と結婚することになった。
    僕はリア充絶対爆発させるマン
  • 6日
    僕はリア充絶対爆発させるマン2,3
  • 8日
    見習い巫女と不良神主が、世界を救うとか救わないとか。
  • 9日
    デスゲームから始めるMMOスローライフ
  • 10日
    デスゲームから始めるMMOスローライフ2
  • 11日
    デスゲームから始めるMMOスローライフ3
  • 20日
    デスゲームから始めるMMOスローライフ4
    江戸の花魁と入れ替わったので、花街の頂点を目指してみる
  • 30日
    転生魔王の大誤算2

2月

  • 5日
    あくまでも探偵は
  • 11日
    幼馴染で婚約者なふたりが恋人を目指す話1
    日常ではさえないただのおっさん、本当は地上最強の戦神7
    継母の連れ子が元カノだった6
  • 16日
    暇人、魔王の姿で異世界へ12
  • 17日
    シェアハウスで再会した元カノが迫ってくる
  • 19日
    数学者の夏
  • 20日
    ホラー女優が天才子役に転生しました2
    義妹生活
  • 21日
    裏社会最強の男、終末異世界を愉しむ。
  • 23日
    ワールド・ティーチャー14
  • 24日
    盤上の向日葵 上
  • 25日
    盤上の向日葵 下
  • 28日
    魔王2099

3月

  • 10日
    自称Fランクのお兄さまがゲームで評価される学園の頂点に君臨するそうですよ?10
  • 12日
    りゅうおうのおしごと!14
  • 13日
    ねえ、もっかい寝よ?2
  • 23日
    最強魔法師の隠遁計画12
  • 24日
    現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変2
    お隣の天使様にいつの間にか駄目人間にされていた件4
  • 25日
    公女殿下の家庭教師8
    暗殺者である俺のステータスが勇者よりも明らかに強いのだが4
  • 26日
    転校先の清楚可憐な美少女が、昔男子と思って一緒に遊んだ幼馴染だった件
    幼馴染の妹の家庭教師をはじめたら3
  • 27日
    ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました3
  • 30日
    文字渦
    時々ボソッとロシア語でデレる隣のアーリャさん
  • 31日
    僕が答える君の謎解き

4月

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

04/12(月)

朝方、先週分の週記を投稿してからの話。この日から今セメスターの履修登録が始まったので、どんな講義が取れるのか一通り確認した。

数理統計学は3セメスターに開講されている講義で、当時は再履修が多すぎて単位取得上限に引っかかって取れなかったもの。今セメスター取ることにした。すべてオンデマンド型の講義なので、まあ負担にもならないだろう。いざとなったら落とせばよくて、取って損はない。

ほかに言語学と論理学もちょっと興味を惹かれる。しかし言語学のほうは毎週課題があって、そのために指定された教科書を買わなければならないようなので、取らないことにした。論理学は人気なので、定員の制限が怖い。水曜2限と木曜1限の2つのうちどちらにするかも含め、後日決めることにしよう。

3月のコードゴルフ大会の問題をJellyfishで解くコードの解説記事が公開されていた。Jellyfishの入門記事としても書かれているようで、非常に面白かった。

Jellyfish(esolang)の紹介

午前11時くらいに布団に入り、なろうを読みふけっていた。

昼頃、仙台レジャーランド一番町店の閉店情報が流れてきた。

かなりびっくりした。日付が変わってもしばらく開店していることや、チュウニズムに台を拭くための濡れタオル(今は使い捨ておしぼりに変わった)が設置されていることなどを理由に、これまで3年間頻繁に利用してきた。僕はチュウニズムしかプレイしないので少し離れたSEGAでもいいが、ボルテや弐寺がメイン機種の人はさらに離れた店舗まで行かなければならなくなりそう。確かに最近たまに行っても全然人がいないという印象だったが、閉店してしまうとは……。

ずっとなろうを読んでいたが、午後4時くらいに寝落ちした。

午後10時起床。またずっとなろうを読み続けていた。ゴミを出さなければならないので、午前4時半くらいに切り上げて布団から出て食事した。

ゴミを出す前にExperimental Educational Roundというのを埋めた。18問あって、競プロを始めてすぐの頃にFだけ解いていたようだ。

Aはよい。Bは誤差が怖いが問題文中の数字をそのまま使って出しても通った。CDもよい。Eは22ケース目でWAしてしまった。入力された点を中心とする六角形が存在するよう、入力に従って座標系が少し変わるらしい。解説についたコメントでもここでハマった人がたくさんいたことが見受けられた。

Gは2つの二項係数を1つの変数で計算しようとするとオーバーフローする。Hはちょっと考え込んだ。Iはよい。Jは「when the next number of sales is divisible by all numbers from 2 to 10」だから2519の時点でボーナスがもらえると思って1WA。KLMNもよい。Oは幾何ライブラリがあればベクトルの回転・足し算で簡単。Pは↓の記事を見て解いた。2018年の記事なのでコンテスト当時はなかったが、まあいいだろう。

つくばサイエンスエッジ2018/文京学院大学女子高校 - 「みらいぶ」高校生サイト

Qは三角錐と四角錐の体積を求めたあと、サンプルを使って五角錐の体積の計算式(係数)を求めた。Rはエスパーで解いたが、解説を見ると相手の真似をする戦略が取れるとあってなるほどという感じ。

このコンテストは全体的に面白くなかった。アルゴリズムを使うような問題がなく、またmodを取らせないことでオーバーフローに気を使わせるだけの問題も多い。

ゴミを出してからECR8を埋めた。Aは題意を把握するのに手間取った。BCはよい。Dは桁DP。Eは優先度付きキューとBITを使って、右上のマスから見たときに左下のマスになれるものを数える。Fは問題タグでフローであることを見てしまったのですんなり解けたが、コンテスト中に出たら解けたかどうか自信がない。

布団に入ってまたなろうを読んだ。午後1時くらいに寝落ちした。

04/13(火)

午後10時起床。またずっとなろうを読み続けていたが、午前2時半に最新話に追いついた。

https://ncode.syosetu.com/n4212eh/

先週からずっと読んでいた「プニキとはじめるリーグ運営 ~野球ゲーム?作って運営します~」。非常に面白かった。代表となって会社を大きくしていく系の話として捉えている。

主人公はプログラミングができるわけでも経理や広報に詳しいわけでもないが、それらは会社の代表としての仕事ではないから別の人に任せるので問題ない。会社の方針を決めて責任を取ることや、会社の顔として取材を受けたり会見をすることが仕事であって、その意味で主人公には会社の代表となる才能がある……ということが書かれていた。そういう設定は「羽月莉音の帝国」を読んで以来の好物である。主人公の性格も好みであった。

起きてコードゴルフをした。2つ取られていたが、両方取り返すことができた。片方はdcで、もう片方はPyPyだった。PyPyのほうはRubyPerlではもっと短くなりそうだったが、TLEしてしまう。ではCrystalならどうだろうと試してみることにしたが、ここで1つの発見があった。これまで入力をすべて読むのにはARGF.gets_to_endを使用していたが、言語アップデートで使えるようになったのか、`dd`で良いようだ。この更新が効くコードを探し、全部縮めておいた。

Rubymapを使いto_iを適用するとき、map &:to_iと書ける。しかし例えばto_i(2)を適用しようとしたときにmap &:to_i(2)とは書けない。&はあくまでSymbolをprocにするだけの糖衣構文であって、procにはレシーバと残りの引数を同時に渡す必要があり、procの第2引数だけを部分適用することなどはできないということだ。

一方Crystalではmap &.to_iと書く(コロンだった箇所がピリオドになる)が、to_i(2)の場合もmap &.to_i(2)と書けるらしい。Rubyの構文をCrystalに持ってくる際に新たな記法に変える必要性が生じて、その結果このような書き方が可能になった、ということが↓のページに書いてあった。これもコードゴルフで役に立つ構文である。

to_proc - The Crystal Programming Language

ラノベの新刊チェックをしていたら、「サイレント・ウィッチ」が書籍化することを知った。

kadokawabooks.jp

またなろうを1つ読んだ。逆行転生して株取引で儲ける話。

https://ncode.syosetu.com/n8435gw/

Qiitaで何か記事を書きたいと思い立ってしばらく調べていたところ、Jelly言語でABSを解いた記事を発見した。Jelly言語はTSGのコードゴルフ大会でしか触れたことがなく、日本語資料がほとんど見つからなくて毎回公式ドキュメントを必死に読んで書いていたが、なぜこの記事が見つけられなかったのだろう。かなり内容があって、よくわからない筆頭であったquickについても詳しく説明されているので、もし当時見つけられていれば非常に役立っただろう。

qiita.com

ECR9を埋めた。Aが信じられないくらい難読だった。Bはよい。Cはa+b<b+aという比較関数でソートするもので、何回か見たことがある。DはLCMの最大値が小さいことを利用して調和級数の要領でカウントする。Eは多項式のべき乗を二分累乗法で行う。Fはbitsetを使用したが、想定解では距離行列となることを利用して最小全域木を取っていた。頭が良い。

ECR10を埋めた。Aはまた難読。BCはよい。Dは適当に書いたら全然違うものをカウントしてしまった。Eは二辺連結成分分解。久しぶりに見た気がする。FはAGC013で既出、と思ったらAGC013の方が後のようだ。AGCのほうは解いてあるからそちらからコピペしてきても良かったが、これも練習だと考えて一から書いた。蟻が座標の昇順に並んでいなくてキレそうになった。そういう面倒さはいらない。それにしても問題名まで一緒であるというのはすごいことだ。

Problem - F - Codeforces

C - Ants on a Circle

昼になったので学食に行きがてら原付を点検に出そうと思ったが、家を出た瞬間雨が降り始めたので、原付を点検に持っていくのは止めにした。歩いて学食に行ったところ、学食は午後1時半でいったん閉店するらしく、食べられなかった。前のセメスターは午後2時閉店だったので、あんまり人が来なかったのだろうか。

AtCoder Jobsに登録し、インターンに応募してみた。インターンの募集は4社が掲載されていて、そのうち3社は機械学習の経験が必要だったので、残りの1社であるところのフィックスターズを選択した。プロフィールに書くプログラミング言語の習熟度について、C++とかPerlはもう4年くらい書いているが、それらはすべて趣味の範囲であるから、最低レベルになってしまう。しかし確かに競プロで身に着けた文法というのは限定的であるから仕方ないのかもしれない。ファイルの読み書きもおぼつかないのは言語を使えるとは言えない、と言われたらその通りである。

ECR11を埋めた。ABCはよい。Dは2点を取りその差を計算して重複カウントをする。Eはまあまあ面白かった。二項定理でシグマを1つ消すやつ。FはCHTになったのでうしさんのLiChaoTreeを貼った。LiChaoTreeはそのうち自前で用意する必要があるだろうが、まだアルゴリズムの詳細も知らない。

ECR12を埋めた。Aはよい。Bは難しそうだがシミュレーションしてよい制約。Cは、変える文字数の最小値を出力する問題をAtCoderで見たことがある。実際の構築も適当にやってよい。Dはありったけの1と偶数を1個以下か、偶数と奇数をそれぞれ1個以下、この2通りに絞られる。Eはbinary Trie。Fは1011以下の素数の個数をカウントする問題になって、これはLibrary-Checkerにある。本当はアルゴリズムを学んで自力で実装しようと思ったのだが、かなり難しそうだったので諦めてうしさんのものをコピペした。

Library Checker

直近のECRは2回ともFで未履修のアルゴリズムが出題されており、かなり教育的であると感じられる。

ECR13のAからDまでを埋めた。ABCはよい。Dはこれも二分累乗法の1つである。Eを解こうとしたがWAで、テストケースを見てもよくわからなかったので諦めた。布団に入って少しだけなろうを読み、午後7時半就寝。

04/14(水)

消えた。

04/15(木)

午前4時起床。TROCを逃してしまった。午前7時くらいまでなろうを読んでいた。

kimiyukiさんによってoj-mini.pyが公開された。ojの機能を制限して単一ファイルに収めたものらしい。

github.com

コードを削ったとされているので、気になって読んでみた。可読性を損なわない範囲でさらに行数を減らせるならプルリクを送るべし、と言われているのでちょっと考えていた。1か所、より良い(と僕が思う)書き方ができると感じた所があり、他に2か所ちょっと気になるところがあったので、それらを書き換えたプルリクを送ったところ、マージされた。

Update oj-mini.py by kotatsugame · Pull Request #1 · online-judge-tools/oj-mini.py · GitHub

さらになろうを読み続けて、正午くらいに最新話に追いついた。

https://ncode.syosetu.com/n5295gq/

面白かった。やはり主人公最強は最高。女主人公なのはよいが百合は好きではないので、そのあたりの描写は読み飛ばし気味だった。百合であるという前評判の作品でも、お互いに想い合っている、くらいの軽い描写なら普通の友情との違いが判らずに読み進めるのだが、この作品は結構直接的な行為に及んでいる。

風呂に入ってAtCoder Jobsを確認したところ、応募したインターン先から返信があった。書類選考ということで、Googleフォームに必要事項を記入して送った。開発経験の有無を聞かれたが、全くないのでかなり絶望的。確かに3週間の短期インターンであるから、何も下地がない人間を採用しても碌な成果が出せないのかもしれない。機械学習の知識もない、ないない尽くしなのでもしかしたら面接に進めないかもしれない。

学食に行った。先日の経験を生かし、今日は閉店ギリギリに到着できた。ラーメンを食べた。学食でラーメンを注文するときは、まずレジの列に並んでお金を払い、出来上がるまで別の列で待つことになる。この2つの列は確かにややこしい。人に、その列はどういう列か質問された。新入生だろうか。

学食へは原付で行った。大学を出てガソリンスタンドに行き給油、そのあとバイク屋さんに点検のために預けた。ガソリンスタンドは交通量の多いところにあるので、いつもかなり緊張して走っている。いつもといっても、原付を購入してから18か月経つが、まだ3回しか給油したことがない。それ以外は交通量の少ない山道を走ってばかりなので、3車線ある道路などには全然慣れない。

そのあとはゲーセンに行くつもりだったが、なんとなく眠いこと、また軍手を忘れたことなどを理由にしてすぐ家に帰ってきた。

僕は寝ていて問題すら見ていないが、ECR107のG問題はTL 5secということもあって愚直が通ったらしい。risujirohさんのコードに$50の懸賞金がかかったと話題になっていた。期限は24時間で、結局誰もそのコードを落とせなかったのだが、懸賞金の$50はチャリティー団体に寄付されたようだ。

Hack risujiroh for $50 - Codeforces

布団に入っていくつかなろうを漁っていたが、どうにも文章が合わないと感じるものばかりだった。2時間くらいそのようなことをして、午後5時くらいに寝落ちした。

04/16(金)

04/15 午後11時に起床。自分で設定した日付が実際の日付を追い越したのはこれが初めてのことであるように思う。

ECR13のE問題を考えたが、どうにも解けなかったので解説でDPテーブルの持ち方だけ確認した。自分が優勝した状態から始める逆順のbitDPであったようだ。考えが凝り固まって、そういう発想は一切出せなかった。コンテスト中のsolvedが150人くらいいる問題が解けなくて非常に悔しい思いをした。

F問題を開くと、LiChaoTreeで直線を削除するクエリもある問題だった。「LiChaoTree 削除」で検索したらこの問題そのものの解説記事が出てきてしまった。もういいやと思って記事を読むと、解説ではクエリ平方分割の方針が想定解となっている、との情報が得られた。そちらについては見ている解説記事では触れられていないので、その方針で解くことにする。

しばらく考えていたがわからなかった。布団に入ったら寝落ちした。午前3時だった。

午前8時起床。TCO21のRound2に進出していた。レートが高い人はR1に出なくてよい、というやつらしい。存在を完全に忘れていた。毎年R1はABCよりも簡単な問題しか出ず、そのくせ全員Ratedなので、とんでもないレート変動になってしまう。parallelがあるが、出ないほうがマシ。

ECR13のF問題のクエリ平方分割解がわかった。今見ているブロックで削除される線分については、最初からLiChaoTreeに入れないことにする。今見ているブロックで削除しない線分についてはLiChaoTreeで管理して、いずれ削除される線分は1つずつ愚直に見ていけばよい。クエリN個、ブロックサイズをWとすると計算量はO(\frac N W N\log N+NW)になって、これはW=\sqrt{N\log N}のとき最小になる。W=500とかW=1000だとTLEしてしまったが、W=2000にすると通った。log(N)が思ったより効いていたようだ。

うしさんのLiChaoTreeはデストラクタがなく、この状態だとMLEしてしまったので、メモリを開放する操作を入れようとした。しかしポインタを辿ってdeleteするコードもTLEしてしまったので、ACコードではvector<Node>で管理し、しかもvectorは使いまわすようなコードを書いている。

atcoder.jp

AGC053Aが縮められていた。$^Tという特殊変数は、プログラム起動時のUNIX時間を表すらしい。これは現在およそ1.6e9くらいで、しかも書き換え可能なのでmaxの初期値として使用できる。この特殊変数を用いてさらに2問ほど縮めることができた。

月曜日に言及していた論理学の履修登録をしてみた。水曜2限のほうはClassroomで350人以上が受講しており、割り当てられた教室の定員334人をすでにオーバーしているので、何人かは履修登録できないことになるらしい。木曜1限はまだ120人くらいしか受講しておらず、教室の定員174人までまだ余裕があるため、こちらを選んだ。どちらにしてもリアルタイムで受講したり講義室に行かなければならない場合はどうせ単位は取れないので、1限でも問題ない。

4時間くらい週記を書いていた。また溜めっぱなしだった。

Classroomに論理学の講義動画がアップロードされていた。少しだけ聞いたところ、どうやらClassroomではなくISTUを使って資料を配布したりするらしい。そちらを確認したところ、ミニットペーパーの提出をする欄があった。どうやらリアルタイムで受講する必要はなさそうで、一安心。

昨日預けた原付の点検が終了したらしいので、受け取りに行ってきた。午後3時半くらいだった。家に原付を停めて、今度は自転車に乗ってゲーセンに向かう。先ほど原付で走った道路はすでに帰宅ラッシュか何かで込み始めていて、危ないところだった。大学近くの道路は、朝夕信じられないくらい込むので、できるだけ避けて運転するようにしている。

立ち食いそばを食べてゲーセンに入る。店頭に閉店の案内が掲示されているのを自分の目で確認したが、まだこの店が閉まるということに現実感がない。

ゲーセンは03/23に行って以来3週間ぶりのようだ。新曲がいくつも追加されたり解禁されたりしていたので、埋めていた。途中ホスフィンと合流して食事に行ったが、夕方のそばがまだ腹に残っていて注文した分を食べきれなかった。ホスフィンとはその後もチュウニズムで遊んで、フルチェインも出た。

赤壁、大炎上!!」でSSSを出した。6回くらいだったか、結構すんなり出た。「劉備軍の旗~~~!?」までAJで、あとは一所懸命擦ったり叩いたりしていた。何回かプレイしてみたところ、主に端まで手が届いていなかったり早く離してしまったりで抜けていたようだったので、丁寧に譜面を見ることを意識していた。最後の「勘弁してくださ~~~い!」は1-2くらいだった。これはかなりうまくいった方である。

ゲーセンにいる間にyukicoderが始まっていたが、問題を見ていない。夜中にCF div.1もあるが、ひたすら眠いので出ないことにした。

ところが何となく眠る気になれなかったので、ECR14を埋めた。ABCはひたすらつまらない。Aは普通の問題に見えて、恣意的なコーナーケースが設定されている。Bはアルファベットの書体が指定されて、与えられた文字列が左右対称になっているか答える問題。Cは与えられた小数を指数表記に直す問題。本当にカス。解く価値は一切ない。Tutorialを見たら青とか緑が出題していた。レートを上げて出直してほしい。DEは典型だが、まあまあ面白い。Fは……よくわからん。全通りの答えを先に求めるという問題を出したかったのか?

ECR15のABを解いた。特に言うことはない。眠気に耐えかねて布団に入り、午前3時就寝。

04/17(土)

午後零時半起床。まだまだ眠いが、大昔に友達に貸した本を受け取るため、この時間に起きておく必要があった。午後2時、無事に受け取れた。

論理学の第一回講義のミニットペーパー提出は今日が期限である。講義資料を見ていたところ、教室の定員を勘違いしていたことに気づいた。確かに満席まで座れば174人だが、このご時世でそんな密な状態が許容されるわけがない。結果定員は大幅に減って90人。履修登録した時点ですでに超過していたようだ。

とはいえ、水曜1限のほうは倍率がもっと高くなっている。なので、このままこの講義を履修登録しておくことにした。ミニットペーパーには履修希望も含めたコメントを書いてください、とあったので、適当に書いておいた。自分のせいで卒業単位を集めている人が履修できないと罪悪感があるので、自分はこの単位が卒業のために必要ではないことも書いておいた。

続いて数理統計学に出ていた課題を終わらせた。初回なのでごく簡単な計算問題。立式後は計算機を使ってもよいらしいが、むしろそのほうが面倒に思えたので、手で書いた。特に問題なく提出完了。この講義の課題の提出期限は一律セメスター終わりなので、↓のようにずっと放置したまま何もせず終了してしまうことを危惧していたが、幸先の良いスタートを切れた。

課題の締め切りはとうに過ぎ去っていたようだ。結局何一つ提出しないまま終わってしまい、評価はDではなくN/A(?)だった。

週記(2021/02/01-2021/02/07) - kotatsugameの日記

今日は第二回日本最強プログラマー学生選手権がある。それまで30分くらい間が空いたので、ECR15のCDEを解いていた。Cは普通。Dはよくわからないが、サンプルが強めのようで、それに通るような場合分けをしたら通った。車に1回だけ乗るか、全力で乗りつぶすか、最後だけ歩くかしか考えなくてよい。Eはダブリングで全部計算できる。

第二回日本最強プログラマー学生選手権が始まった。Aからちょっと難しいが、YZ/X円より真に小さい整数が求まればよい。これはceil(YZ/X)-1==(YZ-1)//Xになる。49秒かかったがFAだった。

Bは対称差集合で、Rakuに専用の演算子、あるいは(^)がある。ところが出力でちょっと躓いた。ただソートするとsetオブジェクト1つのリストのソートになってしまう。これだとsetのキーの順番は変わらず、ちゃんとソートされていない可能性がある。これでWAを出して、keysを付け加えてAC。

Cはちょっと悩むが、答えを全探索してよい。Dはなんだか見覚えがある。そちらは解けなかったが、今日の問題は順番が固定されているのでほとんど明らか。Eは回文のレベルをしっかり理解するのにかなり時間がかかったが、わかってしまえば文字列を半分に折っていくだけ。折る回数はlogのオーダーなので、愚直にやっても十分間に合う。最後に回文を故意に壊さなければならないことにはちゃんと注意しておく。

Fは行と列をそれぞれデータ構造で持つ。クエリを先読みして座圧しておき、個数と和をBITで持てばよい。最初数列の値がすべて0なのは良心か。Gを見てすぐ行列木定理が思い浮かんだのはいいが、必ず使わなければならない辺をどう処理するか悩んだ。これは実は悩む必要などなくて、先にくっつけて頂点を圧縮するだけ。modint、matrix、UnionFindと3つもライブラリを貼ったのでコード長が6000Bを超えた。コンテスト後のTLで、行列木定理を使うAtCoderの過去問が紹介されていたが、実はその問題は解いたことがない。僕が行列木定理を知ったのはPCK本選の過去問だった。

https://onlinejudge.u-aizu.ac.jp/problems/0314

無向グラフの全域木の個数を数え上げる問題に落ちる。これをググると行列木定理というものに行き当たったので実装したら通った。かなりびっくり定理だと感じる。こんなのPCKに出したって検索なしなんだから解けないだろ……。

週記(2020/12/14-2020/12/20) - kotatsugameの日記

Hは非常に面倒だった。まずグラフがN頂点N辺の連結グラフ、いわゆるなもりグラフであることを確認する。これはループ部分とそこから生えている木部分に分解できる。荷物配送は、ループを通るか通らないかで2通りに分けられる。

ループを通らないものについては適当に処理できる。解説ではLCAと木上のimos法を使っているが、僕はマージテクを採用した。LCAはライブラリになっていないし、そもそもたくさん木があってかなり面倒に見える。この選択はよかった。かなり実装が楽だった。

ループを通るものについては、ループ上の2点を連結にする問題になって、これはループのどちらを通るかで各荷物2通りの辺の張り方がある。2-SATやフローを疑ったが全然違う。ここで、どこか1か所を通らないと決め打ったとき、すべての荷物の辺の張り方が決まることに気づいた。ほかに考えるべきこともないので、この方針で突き進んでいくことにする。ループを割り開くと列に対する操作になって、適当なデータ構造を用いることができる。それぞれの辺についてそこを通る荷物の個数を数えることにすると、ある荷物における辺の張り方を変えるというのは、区間に対する足し算になる。通る荷物の個数が非ゼロであるような辺について、その重みの総和を取得したい。

遅延セグメント木で普通にやるとまずい。なぜなら、区間に対して作用した結果、通る荷物の個数がゼロの辺と非ゼロの辺両方が生じる可能性があるからだ。これは区間の更新に失敗したということになる。ところで、「区間の更新に失敗する」という文言には見覚えがある。

rsm9.hatenablog.com

segment tree beatsで実装できるのでは!?↑のページを読むと、区間の更新に失敗する回数が上から抑えられるときに役立つと書いてある。今回の問題では、通る荷物の個数が非ゼロからゼロになるような更新が何回あるかを考えればよさそうだ。注目している辺を通る荷物の個数をゼロにしながらループをぐるっと一周するのだから、これは各辺についてちょうど1回である。抑えられた!嘘である。初期状態で0-1、2-3、4-5など1つ飛ばしに辺を使用している場合、そのような更新はO(N^2)回ある。

コンテスト中はこのことに気づかず実装に入った。そもそもなもりグラフの前処理から実装が面倒だが、何とか実装しきってサンプルを合わせた。ACLを張り付けているので7000B超え。提出するとゆっくりゆっくり実行が進んでいく。それに合わせて自分の心拍数も天井知らずに上がっていく。ジャッジにはかなり時間がかかったが、一発でACできた。

結果、全完して3位だった。僕を含め上位3人は全員同い年なので、かなりエモい。エキシビションに参加できるらしい。しばらく時間が空いたので、解説を読んだりコードゴルフをしていた。

Hは非ゼロの辺の重みを求めるのではなくゼロの辺の重みを求めることにすれば通常の遅延セグメント木で実装できたらしい。そのようにして提出すると最短コードになった。

コードゴルフについて。Aは最初に提出したdcの7Bが最短。解説にも同じコードが書かれていて面白かった。Bはコンテスト中のコードを少しだけ変えた。この辺りは実行してみながらでないとわからず、コンテスト中にそのようなことをする暇はなかった。CはAWKかと思ったが、普通にdcで書けた。Dはコンテスト中にdc 24Bを出し、さらに数分使って縮まないか試していたが、縮まなかった。

エキシビションは画面をYouTubeで配信しながら参加した。今見返すと、喋ろうと思っていたことの殆どは言葉になっていない。「あ!」とか「ええ〜」みたいな、なんの意味もない音を発するのが精々だったようだ。

heno239さんも配信していた。E869120さんは後日、編集した画面録画をTwitterに公開した。

www.youtube.com

FAならば点数2倍、というルールをほとんど無視していたのがよくなかった。また一番のプレイミスとしては、B問題のWAを終盤まで放置していたことが挙げられる。これは、問題に対して少し面倒であるという印象を抱いていたため、どこがWAなのかすぐには見つからないだろうと考えていたこと(実際はそうではなかった)、また序盤の問題であるからすでにFAは取られているものと考えていたこと(順位表を見ればまだ解かれていないのは分かっただろうに)の2点が理由であった。唯一解かれなかった問題、Semi Common Multipleは非常に難しい。そもそもこれを15分で解けと言われて解ける人も限られるのではないだろうか?僕は無理だ。考察も覚えていなかった。

コンテストが終了してからはずっとエゴサをしていた。ABC過去問から出題されるのは僕にかなり有利な戦いである、という言説には同意できる。フォロワーが50人以上増えたのにはびっくり。

結構疲れているのでTCOもCSAもサボり、ラノベを読んでいた。まず「超高度かわいい諜報戦」。設定はよい、が、ストーリーはあまり好みではない。主人公の陰キャオタクへの擬態が完璧かつ徹底的すぎてむしろ読んでいてげんなりした。あと誤字や脱字が多い。

次に「精霊幻想記19」。前の巻で主人公が重傷を負い、この巻は代わりにヒロインが頑張る話。ストーリー上必要なのは理解できるが、本能は主人公の無双を求めている。ヒロイン等は敵を圧倒できているわけでもないので、もどかしさがすごい。次の巻からまた主人公のバトルが見られるらしいので、そちらに期待したい。

さらになろうを1作読み始めた。2時間半くらい読んで、午前7時半に寝落ちした。

https://ncode.syosetu.com/n7796fc/

04/18(日)

午後3時、目を覚ます。まだ眠いのだから二度寝すればよいのに、そこから3時間なろうを読んでいた。

途中、昨日のエキシビションのE869120さん視点の動画がアップロードされた。また、昨日のD問題が-1Bされた。やはりO9^7+を2回書くのは長かったようだ。自分でもどうにかしてまとめようとしていたつもりだったが、スタックの一番下に入れておいて必要になるたびに持ってくるだけで-1B。なぜ気づかなかったのだろう。確かスタックの一番下に押し込むコードは書いていた気がするが。

午後6時半くらいになってさすがに眠気がマズいことに気づいたので寝なおした。午後8時半起床。食事してARC117に参加した。

Aは面倒だがまあよい。Bはちょっと難しいがちゃんと考えるとわかる。Cは変換テーブルをどうにかして簡単な式で表せないか考えるのは典型で、ガチャを回して一発で(-a-b)%3が出たのは大当たり。二項係数 mod 3を普通のmodintと同様に計算しようとして0になったのでしばらく悩んでいたが、そういうときの定理があることを思い出した。しかし「二項係数 mod」で検索してもmod 1e9+7しか出ない。最終的に「二項係数 偶奇」でLucasの定理にたどり着いた。Dは直感的には直径の端から端まで移動しつつほかの頂点を訪れる感じになる。順位表を見ると結構WAが出ているようだったのでしばらく迷っていたが、ええいままよと提出したら通った。証明:AC。

そのあとEを考えながら念入りに椅子を温めていた。まず全探索するコードを書いてみた。当然TLに間に合わないし埋め込みするのも時間がかかりすぎるようだったので、今度はvalidな移動における累積和のヒストグラムを全探索することを考えた。これもいろいろ場合分けしてすべてのvalidな移動を検出できるようになったが、やはり間に合わないようだ。残り10分くらいになってFを読んで牛ゲーだと思ってちょっと考えていたが、やっぱりダメだった。

結果は4完速解きで28位、パフォーマンス3033、レートは2670→2712(+42)。ずっと同じレート帯をウロウロしている。

コードゴルフ。A問題は、1..A * sum(1..B)1..B * -sum(1..A)を出力するのがかなり頭がよい解法。B問題はPerlsort{$a-$b}glob`dd``dc -e?f|sort -n`になるようで-3Bされた。CはN=3k+1のとき0番目、3番目、……、N番目を取り出したN=k+1の列と同一視してよいということを利用したコードを目にして、それを縮めた。これはなぜかというと、comb(3k,1)≡comb(3k,2)≡comb(3k,4)≡comb(3k,5)≡……≡0 (mod 3)だから。適当にPerlで書いていたらBWR012のどれかにエンコードするところで更新された。

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

04/05(月)

午前9時半起床。

二度寝するべきだとは思っていたが、寝落ちする前に読んでいたノクターンノベルズの続きを読み始めてしまい、そのまま止まらなかった。正午、読了。

https://novel18.syosetu.com/n7640gf/

主人公とハーレムメンバーのバランスのとり方とか、主人公の優しさが良さげに描かれていて良かった。

そのまま他の作品を漁って、2つ読んだ。こちらは完全にエロに振り切っていてストーリーなどないようなものなので、特に感想もない。題名も書かないので気になる人はリンク先(R18サイト)に飛んでほしい。

https://novel18.syosetu.com/n6275gw/

https://novel18.syosetu.com/n8082gs/

午後1時半ごろ寝落ちして、午後8時ごろに目を覚ました。ツイートを確認すると午後6時頃に少しだけ覚醒していたようだが、特に何もせずまた寝たようだった。

食事して週記を書いた。また数日分溜めていたので、午後9時から作業に入って投稿したのが午後11時半だった。

ECR2を埋めた。Aは不快。BCは普通。

Dは幾何で、2円の共通部分の面積を求めよという問題だった。ライブラリになっていなかったので、この機会に作っておくことにした。2円の交点を求めるライブラリはあったが、その点から角度などを復元するよりは処理自体をコピーしてきたほうがよさそう。それぞれの円に対し、2円の交点と円の中心からなる扇形の中心角が求まれば、そこから扇形の面積と三角形の面積が計算できて……というやつだ。

ところが落ちてしまった。テストケースを見ると、ほんの少しだけ重なるときに誤差で落ちているようだ。そこで、以前は角度を求めるのにacosを使用していたところを、asinで求めることにした。asinのほうが精度が良い、という話を最近のICPCで聞いた気がする(が、実際のところはよくわかっていない)。ほんの少しだけ重なっているという仮定、より一般にacosで求めたい角度が直角より小さいことが分かっていれば、3辺の長さから求めた三角形の面積(仮定から、角度を使用して求める符号付き面積と一致する)を使用することでsinの値がわかる。これで試してみると、確かに少しだけ誤差は減ったようだが、まだACにはならない。

最終的にdoublelong doubleにしたらacosのままで通った。つまらない。今回はdoublelong doubleに置換したが、より汎用的にするべく幾何ライブラリにusing Real=doubleと書いてdoubleだった箇所をすべてRealにしておいた。今回のような場合はusing Real=long doubleに書き直すことになる。

Eはマージテクで、Fは解けなかったので解説を読んで通した。二部グラフであることを巧妙に使っていて面白かった。

そういえば、汎用的なグラフ構造体というのはいつか作りたいと思っていたライブラリの一つである。これの設計に関して考えていた。メンバ変数の名前が決まっていて、ほかに必要な情報も持てるようなedge構造体だけ毎回書いて、グラフ構造体自体は常にvector<vector<edge>>で持つ、というものを考えたが、kimiyukiさんによればこれは汎用的なグラフ構造体とはならないらしい。具体的には、辺を陰に持ちたかったり、隣接行列で持ちたかったりする場合に困るようだ。それはそう。

上の設計ではedgeについて抽象化していたが、ここをvector<edge>について抽象化する(隣接リストを舐めるイテレータを作る)というのが良さげならしい。そういう方針で作成されたグラフ構造体についての議論は以前TLで見たことがある気がする。

ECR3を埋めた。ABCDは普通。Eは見た瞬間最小全域木+オイラーツアー+LCA+RMQの解法が思い浮かぶが、実装が嫌でしばらく逃避していた。RMQ以外はライブラリになっていない。そういったことをツイートすると、第2回PASTのO問題ではないかという指摘が来た。見てみると全く同じ問題だったので、コピペしてAC。並列二分探索による解法は当時感動していた気がするが、時が経ち、すっかり忘れ去っていた。Fはセグメント木上で二分探索。

Problem - E - Codeforces

O - Variable Spanning Trees

ECR4のAからEまでを解いた。ABは普通。Cはかっこの対応が一意に定まる。Dは幅0の区間をわざわざ削除してしまい1WA。Eはどこかで見たことがある。

Fを開いて、解法自体はすぐわかるものの、復元があって実装が辛そうだったので今日は止めておくことにした。布団に入ってまたノクターンノベルズを読んでいたが、午前11時ごろ寝落ちした。

04/06(火)

午後4時半起床。そのまま夜まで布団でノクターンノベルズを読み続けていた。

https://novel18.syosetu.com/n9485dy/

↑これはたこノすけさんにオススメされたものだが、50話くらい読んで放棄してしまった。

https://novel18.syosetu.com/n8462gt/

サークルのバチャに出た。CF #516 div.1。途中30分くらいこどふぉが落ちていて非常に厳しい気持ちになった。問題はvjudgeから見られるが、実装まで済ませた問題が提出できないのは辛かった。

Aはギャグ。未証明で通した。バチャ後の反省会で知ったが、回文の両端の文字が等しいことに着目すれば証明できる。文字列の文字をソートしたものが答えだが、これは回文の両端の文字になりうるペアすべてが、実際に回文の両端の文字になっているので、最大。

Bは左右の移動が打ち消しあった回数を持っておけば、どちらにどれだけ余分に移動しているかはスタート地点と現在地の座標の差から計算できる。打ち消しあった回数で01BFSをした。ほかの人は左右に移動した回数の和で01BFSしていたようだ。min(L,R)*2+abs(y-sy)=L+Rが成り立つから、L+Rで01BFSしようとmin(L,R)で01BFSしようと変わらない、ということだろう。他にも、LRでそれぞれ01BFSした人もいた。変に遠回りすることでLを増やしてRを減らす、なんてことはできないから、これも正しい。

Cは二分探索っぽくやる。2^29<10^9<2^30なので、最初の1点だけは一番端に固定する。また、X軸から少しだけ浮かせておくことで、座標が1しか離れていない2点の間を通るような直線が簡単に引けた。

コンテスト後にDをupsolveした。答えとなる値を決め打つと、それがminとかmaxの1つの引数になるので、探索する区間を適当に分割してminmaxを消し、あとは頑張る……というようなことを考えていたが、どうにもならなかった。特に単調性があるわけでもないし、割り算が出てくるのでその商ごとにまとめて見ることでさらに区間に分割しようとしたが、floorはともかくceilのほうがよくわからなかった。解説はかなり頭が良い。O(min(n^2,k/n))だが、僕の実装だとO(k/n)のほうにlogがついてしまった。k/n<1e7という場合分けだとTLEして、n>2e4にしたらACした。

このlogは、(d+1)a+db=1なるabを1組見つけるために使った拡張ユークリッドの互除法によるものだが、冷静になれば(d+1)-d=1なのでa=1b=-1が必ず解である。これでちゃんと線形になって、試してみるとk/n<1e7の場合分けでも通った。サボりすぎ。

最近はレトルトカレーを食べている。実家でよく母がやっていたように、カレーの皿を洗う前にはティッシュで汚れをある程度拭き取っている。実家では不要になった肌着などを使っていたが、そんなものは保管していない。カレーに限らず、汚れが多い皿は拭き取ってから洗う、というのは重要な典型テク。

またノクターンノベルズを読んだ。

https://novel18.syosetu.com/n5258gt/

昨日放置したECR4のFを実装した。そもそもの実装がつらかったのと、さらに円周上をどちらに移動するかの符号を合わせるのに苦労したが、サンプルが通ったものがそのまま一発ACだった。

ECR5を埋めた。ABCは普通。Dは尺取り法。Eは商ごとにまとめて見るやつ。Fは文字列を'$'などを間に挟んですべて連結した文字列を作り、それの接尾辞配列と高さ配列を計算して、高い順に要素をマージしていく感じでできる。ただこれだと全体で2回以上出現する文字列に関してしか計算できないので、1回だけ出現する文字列に関しては別に計算する必要がある。ここの計算を間違えて2WA。

ECR6のAからEまでを解いた。ABCは普通。Dはオーバーフローで1WA。109を4倍してしまった。2倍して2倍する、という形で書かれていたので気づけなかった。Eはオイラーツアーして区間set区間bitwise ORの遅延セグメント木。

せっかくなのでオイラーツアーのライブラリを作っておくことにした。今回必要なのは辺属性ではなく頂点属性。昨日考えていたグラフ構造体をいよいよ実装して、それを使って作ろうかと思ったが、何回もクエリに答えるため構造体が必要で、結局ほかのライブラリと同様オイラーツアー構造体にadd_edgeを作ってグラフを作る形になった。

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

Fは解けない。布団に入ってノクターンノベルズを読んでいたら午前7時半ごろ寝落ちした。

https://novel18.syosetu.com/n8141gc/

04/07(水)

午後2時半起床。寝落ちする前に読んでいたものをそのまま読み続けて、読了した。

https://novel18.syosetu.com/n8141gc/

かなり歪んでいて、心情的には理解できないが、そういうものに触れてみるという点では良かった。

他の作品をいくつか漁ったが、だいたいは少し読んで投げ出してしまった。1作だけ読了。

https://novel18.syosetu.com/n9412dj/

そうこうしているうちに夜になったので、サークルバチャに参加した。CF #511 div.1。

Aは誤読して1WA。削除しなかった要素のgcdが、削除した要素のどれよりも大きくなる必要がある、という風に読んだ。正しくは、削除しなかった要素のgcdが最初の全要素のgcdよりも大きくなること。こちらだと、最初に全体をgcdで割ることで、総gcdが1でないような部分集合のうちサイズが最大のものを計算する問題になる。もっと言えば素数pで割り切れる数列の要素の個数をpそれぞれに求められればよく(p|gcdとなるような部分集合のサイズとなる)、これはエラトステネスの篩の要領で各数に対して素因数を1つ求める前計算をし、O(log A)素因数分解すればカウントできる。なんとなく怖かったので同じ値の要素をまとめて計算したが、別にそのような必要はない。

Bは気合いで場合分け。1x6が必ず埋められるので、縦横をmod 6で考えることにした。2x53x4が埋められるのは結構非自明な構成だが、運よく手で作れた。他には、2x2は1つも入れられないが2x8だと埋められるとか、2x3は2マス空くが8x32x9だと埋められる、1x27x2も2マス空くが13x2だと埋められるなどの処理が面倒だった。書いていて発見したが、僕のコードは7x8で落ちるようだ。7x2と同様に2マス空くと思っていた。

Cは頑張る。グループのvalueの和がpであるような分割(pによる分割と言うことにする)が可能であることの必要十分条件は、分割の仕方が一意であることに気づくと、全体のvalueの和(sumとおく)がpで割り切れて、かつ部分木のvalueの和がpで割り切れるような頂点の個数がsum/pに等しいことだとわかる。このとき直ちに、pによる分割とq|pによる分割があった場合、pを経由してqの分割が作れることがわかる。

あとはpを全探索。ただ毎回チェックすると間に合わないので、sum素因数分解して、素因数ごとにbitsetでチェック結果を持っておき、具体的なpに対してはp素因数分解してテーブルをbitwise ANDすることにした。すべての倍数に対して遷移するDPを書こうとしたが、よくわからなかったので、pとしてありうるものを列挙した後2乗かけた。これはsumが高度合成数のとき最大で268802ステップくらいになりそうだったが、通った。

解説は頭がよく、コードも簡潔ですごかった。sum/pに着目する。s_uを、uを頂点とする部分木のvalueの和とすると、p|s_usum/gcd(sum,s_u)|sum/pは同値になる。sum/p<=nなのでsum/gcd(sum,s_u)<=nとなるような頂点だけ考えればよく、個数のカウントやDPの遷移も添え字がnまでなので調和級数の要領でできるというもの。

またノクターンノベルズを読んだ。

https://novel18.syosetu.com/n7438gs/

溜めていた日記を書いていたら午前5時くらいになった。広義明日は午前10時から学科ガイダンスがあるので起きなければならない。まだ途中までしか書けていなかったが切り上げて布団に入った。しかしそれからもしばらくなろうを読んでしまい、結局寝たのは午前7時頃だった。

04/08(木)

午前10時起床。学科ガイダンスに参加する。

4年目ということもあって特に目新しいことは言っていない気がする。院試の日程とか、インターンとかに触れられていた。資料もアップロードされるので、無理やり起きて出る必要性は感じられなかったが、出なかったら出なかったで自分の知らない情報があるのではないかと心配になるはずだから、出ておくべき。

途中で昨日の分の日記を書いていたら、バチャのB問題が落ちることに気づいた。自分でHackしておこうと思ったが、コンテストが終了したのでそのような機能はないらしい。とりあえず修正したものを投げておいた。

ガイダンスは時間が少し余ったので近況報告をしようという話になり、数人喋っていた。僕も何を話そうか考えていたが、結局すぐ解散になった。謎。こういう交流イベントは心臓に負担がかかるが、それでも今は久しぶりに(カメラ越しに)顔を見た同級生が懐かしいという思いが強い。僕はカメラオフだったので、一方的に観察していたことになる。

午後1時から4年次ゼミの初回、初顔合わせがある。それまで2時間くらいあるから寝ておこうかとも考えて布団に入ったが、万が一寝坊すると大変なので、なろうを読みつつ起きておくことにした。

ゼミが始まった。自己紹介のタイミングで皆カメラをオンにしていたので僕もオンにしたが、パジャマだし洗濯物を片していないしでもう大変。自己紹介については、競技プログラミングから数論に興味を持った……ということを言った。プログラムで問題を解くとは何をするのか?ということを聞かれた。これはよくある質問だが、いまだに何を喋ればいいのかわからなくなる。今回は「AB乗を普通にB-1回掛け算するより高速に求められる方法がある」という話をした。といっても二分累乗法の説明をしたわけではなくて、そうやってプログラムをアルゴリズムの力で高速化する競技である、とだけ言う感じ。

今年読んでいく本を決める。「Introduction to Analytic Number Theory」と「Multiple Zeta Functions, Multiple Polylogarithms and Their Special Values」の2冊の候補があって、それぞれグループを作る。前者を希望したところすんなり通ったので、それをやっていくことになった。3人チームで順番に発表を担当し、僕はその3番目だ。ゼミ生同士の連絡手段をどうするかという話になって、博士課程の人の主導でLINEグループが作られた。SlackとかDiscordを提案しようとしたが、そういうところで目立つのもどうかと思い止めておいた。

読む本を手に入れなければならない。僕が読む本についてはネットにPDFが落ちていると言われ、探してみると確かにあった。しかしこれは……いいのか?あんまり触れちゃいけない話題なのかもしれない。もう1冊はないようなので、また後日入手方法が知らされるか、あるいは自分でコピーしてくるかしなければならないだろう。

library--/Introduction to Analytic Number Theory (1976) - Apostol.pdf at master · isislovecruft/library-- · GitHub

ゼミが終了したので即座に布団に入り、午後3時から午後8時まで寝た。起きたらりんごさんの配信が始まっていて、TLでその話題がたくさん流れてきた。

布団でなろうを読んだ。「金で買えないスキルはない ~『外資投資銀行に勤める俺が、異世界転生して金の力でチートする』~」。

https://ncode.syosetu.com/n7340da/

かなりテンポよく進んでいった。意図的にリーマンショックを引き起こすのは面白かった。ところで、美醜の基準が違うのでヒロインは異世界ではとんでもない醜女だとされている、という設定はいらないと思う。周りの反応が読んでいて不快だった。

続いてもう1作。「スゴいカードを拾ったので株式投資で資産家目指します」。

https://ncode.syosetu.com/n6412fu/

面白かったが、自分がこれを面白いと感じてしまうことがちょっと信じられなかった。お金が無限に使えるようになったので株を買い漁って財閥(コングロマリット)を作る、という話。経営の話は一切出てこなくて、主人公が社会的地位を得たり有名になったりお金を使ったりするシーンが延々続くが、それでも面白いと感じた。

前々から「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」が好きだという話をしているが、その流れで会社を経営したり投資したりする話に興味を持ち、それで検索して読んだ作品だった。ほぼ無限にお金を使える設定のものは他に書籍化したものを読んだことがあるが、そちらは全然合わなかったので、自分は「どうやって稼いだか」ということに興味があるのだとばかり考えていたが、この作品を面白く感じてしまった以上、結局主人公が社会的地位を得るのを一番面白がっているということが明らかになった。

布団から出て食事し、火曜日解けなかったECR6-Fと向き合ったが、やはりわからない。適当に提出したらTLEしてしまった。手元で試行錯誤した結果26secが23secになったが、TLは10secなので焼け石に水。ふてくされて布団で丸まっていたら寝てしまった。午前2時だった。

04/09(金)

午前5時半起床。うつらうつらしていたら神崎さんのなろう読了ツイートが流れてきて、それを読み始めたら止まらなくなった。「転生したら皇帝でした~生まれながらの皇帝はこの先生き残れるか~」。

https://ncode.syosetu.com/n6066gi/

午前11時までかけて一気読みした。非常に面白かった。傀儡を演じるため思うように動けない主人公のもどかしさや、そんな中で少しずつ自分の味方を増やしていく緊張感が良い。

読み止しにしていたノクターンノベルズを読んだ。

https://novel18.syosetu.com/n0019fz/

正午にまた意識を落とし、途中一瞬の覚醒を挟んで午後8時まで寝た。食事してyukicoderに出た。全完。

AはPerlで置換したが、制約をよく読むと文字数が5e6だった。よく間に合ったものだ。22Bで、これ以外ないと思っていたが、tailsさんが同じくPerlで16Bを出していてびっくり。コンテスト後に見るとy/a-z//s(の短い書き方)を使用していた。オプションsは同じ英子文字が連続している箇所を1文字にまとめてくれる。なるほど。このオプションはBashtrでも使えるので、tr -cs _を提出して8Bとなった。

B、Cはよい。Dはよくわからなかったので飛ばし、先にEを解いた。Eも特になし。Dに戻って、9が連続すると考えて提出したがWA。ここでようやく実験コードを書いてみると、どうやら最初に1文字8が入るらしい。実装してAC。

Fは面白かった。ある人に配られたPの個数をX、qの個数をYとすると、Y=0であるか1<=Y<=S<LかつX>=L-Yである必要がある。このときY>0であるような人数とそのYの総和が分かれば絶対に使わなければならないPの個数が求められ、残りのPは自由に配ってよいことになる。人数と総和をキーにするDPが計算できるので、余ったPの配り方をさらにかけ合わせれば解ける。

ECR6-Fがどうにも解けないので解説を読むことにした。Mo's algorithmのようだ。僕も考えたが、削除ができないと思い諦めた。しかし今回の問題では削除が必要ないらしい。

長さNの数列aに対してクエリ[l,r)が飛んでくるので、数列のl番目からr-1番目までの要素から2つ(u<=v)選んだときのu^(u+1)^...^vの値の最大値を答えるという問題。まずMo's algorithmの前提の話をしよう。f(x)=0^1^...^xと置けばf(u-1)^f(v)の最大値を答える問題になり、Trie木が使える。Trie木は2本用意し、f(u-1)を入れるTrie木の各ノードにはその値を達成する最小のuを持つ。これで、ただ^f(v)した最大値を答えるのではなく、u<=vなるuによって達成され得る最大値が求まる。f(v)を入れるTrie木も同様にする。これでuvのどちらからも相方を探せるようになったので、Mo's algorithmにおける区間の伸長ができることが分かった。

削除不要とはどういうことなのか。区間から2点選んで計算する形式の時にそうできるようだ。ブロックサイズをB=sqrt(N)とし、クエリ[l,r)であってl/B(切り捨てとする)が等しいものを集める。ここでmid=l/B*B+Bとおき、[l,r)[l,mid)[mid,r)に分ける(空になる区間は今は考えない)。区間から2点選ぶというのは、どちらかの区間から2つとも選ぶか、1つずつ選ぶかの3通りに分けられる。rで昇順ソートすると、[mid,r)から2点選ぶ方法に関しては区間は伸びる一方なので削除の必要がない(①)。あるクエリに対して[mid,r)を処理したとき、いったんストップして、[l,mid)を考えることにする。挿入せずにペアの相方を探すだけにすると、Trie木を変更せずに2つの区間から1つずつ選ぶ場合が計算できる(②)。最後に、クエリそれぞれに対してTrie木を初期化して、[l,mid)から2つ選ぶ方法を計算する(③)。

計算量を考えよう。Trie木のlogは一旦無視して、区間の伸長だけ考える。B=\sqrt Nであった。①は\frac N B個のブロックに対してO(N)なのでO(\frac{N^2}B)=O(N\sqrt N)。②はクエリの個数Qに対してそれぞれO(B)なのでO(Q \sqrt N)。③もクエリごとにO(B)なので同じくO(Q \sqrt N)。合わせると確かにO((N+Q)\sqrt N)である。

この問題ではN<=5e4Q<=5e3だった。計算量はO( (N+Q)\sqrt N \log \max a)である。解説にはO(N^2+Q)で通されたと書かれていた。TLが10secということもあり、なるほど確かにO(N^2)が通りそうだ。N\gg Qであることに気を取られて、区間を全探索できることに気づいていなかった。Trie木だと\log \max aがつくからどうするのだろうと思ってtouristのコードを読んだら、シンプルなO(N(N+Q))で解いていた。ペアの一方を決め打ってもう一方をそこからインデックス順に試しつつ累積maxを取り、決め打った項を含むようなクエリに対してクエリの右端rでの累積maxで更新する。

ECR7を埋めた。慎重にコーディングした結果全部1発ACだった。AtCoderではコードゴルフに関係する再提出がたくさんあり自分の提出一覧が汚くなりがちだが、CFではそんなことはないため、全部ACで揃わないかとちょっと気にしていた。div.3を埋めているときは何度も発生した状況だが、ECRはやはり難しく、これが初めてであった。

ABCはよい。Dは必ず0にできる。Eは簡単なバージョンを2018年のICPC横浜大会で見たので、それの解説を参考に解いた。

Fは\sum_{i=1}^n i^k1\le n\le 10^91\le k\le 10^6で求める問題。kがもっと小さな制約の問題を2019年のICPCバンコク大会で見て、当時解けなかったのを覚えている。多項式補完が思い浮かぶが確か漸化式でも解けたはずで……と当時のやり取りをSlackで漁ったが、O(k^2)だったので今回は使えなかった。いい機会だと多項式補完を実装することにした。

多項式補完というとxには相異なるという制約しかないはずだが、例えばうしさんのライブラリを見るとx=0,1,...,N-1と決め打ちされているようだ。この制約は何だろうと思っていたが、アルゴリズムを見れば当たり前だった。より一般にxが等差数列であれば、1点とその他の点の差の積を求めるのが簡単。というか逆にxが等差数列でない場合の処理がO(N log N)でできるのがびっくり。

適当に書いて実験したらよさそうだったので提出、AC。ライブラリにもしておいた。求める値xは最初modintで与えられることを想定していて、この時大小比較ができないのですでに計算された値であっても知らないふりをする必要があった。後から必ずlong longで与えられるように修正した。

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

ライブラリのverifyにはyukicderの「貯金箱の溜息」を使用した。これはうしさんやbeetさんのライブラリのverifyを真似している。しかしこれが多項式補完になるというのはにわかには信じがたい。解説をいくつか読んで議論は追ったものの、狐につままれた印象。maspyさんの解説を読むと、累積和を6回取るので5次式であるということが式から見て取れるので、少しだけ理解できた気持ちになる。

ついでにコンビネーション類の計算をするライブラリも作った。毎回fac[]invfac[]を作って前計算していたが、さすがに面倒になった。以前はmodpowも毎回書いていたのだが、今から考えるとちょっと信じられない。

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

ライブラリの設計に関する議論だけは済んでいた。これはLayCurseさんに教えていただいたものだったと思う。

mod上の逆元リストを必要に応じて生成する方法についての議論があった。前から作成する方法は、オーダーだけ見ればO(N)だが、実際は変数による除算や連続的でない配列アクセスなどがある。その点、後ろまで作ってから1回だけ逆元を計算する方法は、O(N+log mod)と変なのがついていても、定数による除算しか行わなかったりシーケンシャルアクセスが保たれたりと良いこと尽くめ。必要に応じて生成する場合も、倍々に増やしていくことで対応できる。これに関しては、呼び出しごとにif文による分岐が入るのが気になっていたが、分岐予測がかなり効くだろう、という話を聞いた。

週記(2021/02/01-2021/02/07) - kotatsugameの日記

ノクターンノベルズを読んだ。

https://novel18.syosetu.com/n6343gw/

午前10時からGCJ R1Aなので寝なければならない。午前6時、布団に入るも寝られない。なろうに手を出したところ午前10時直前まで読んでしまった。そのまま食事も摂らずコンテスト。

Abcで646位、何とか通過した。Aは愚直にやってよい。これを通したときは6位くらいだったのでびっくりしたが、両方Visibleなので確かに正しい答えを出力できたのだろう。

Bはわからない。とりあえず積を全探索する愚直なコードを書いてVisible 2つを取った。しばらく考えてもわからなかったので次に進むことにした。

Cは難しい。まず値がとても大きくなるようだったので言語をRubyに切り替えた。問題ごとにそれがT(もしくはF)だったときの場合の数を数える。これはどの問題で計算しても和が等しくなるはずで、場合の数が大きい方を選択すればよい。場合の数を数えるのは計算量的にちょっと大変かもしれないが、N人の回答は2^N通りしかなく、それぞれの個数を数えてメモ化することでQ回ではなくO(2^N)回しか計算しなくてよくなる。ここまで考えて細かい解析をせずコーディングした。小さいサンプルは合ったが、N=3Q=120がどれだけたっても終わらない。とりあえず2つ取ることを目的に提出しておいた。

しばらくRubyで高速化して、大きなサンプルも3secくらいで通るようになったが、あるとき値が大きくなるとは言っても2^120をちょっと超えるくらいであることに感づく。そこでC++__int128_tを使うことにして書き直した。大きなサンプルが0.15secくらいになったので時間ギリギリに提出したが、WA。ここでコンテストが終了した。

Bは積ではなくそれに使った数の和を全探索すればよかったらしい。xの素因数の和をf(x)とおいたときx+f(x)=sumだな~とは思っていたが、f(x)の値が全探索できるとは一瞬たりとも考えなかった。知ってしまった今では逆になんで考えられなかったのかわからない。CのWAの原因は分かった(Rubyで高速化しているときに嘘になったらしい)が、出しても結局TLEのままだった。N=2のときはどちらかの人のコピペをするか逆張りをするかで4通り試せばよかったらしい。

さらに1時間くらいなろうを読んで、午後2時就寝。AGCがあるので非常にまずい。

04/10(土)

午後3時、新年度1回目の弁当配達を寝過ごさないための目覚ましで起床。ここからうすぼんやり意識を保てればよかったのだが、思いっきり寝てしまった。午後5時半くらいに弁当が来て、何とか受け取れた。またすぐ寝ればいいのになろうを読んでしまう。午後6時半に再度就寝。

午後8時半起床。眠すぎて動けないが、食事だけでも摂っておく必要があったので、さっそく弁当を温めた。焦りながら食べてAGC053に臨む。

2完3WA、136位、パフォーマンス2447でレートは2692→2670(-22)。崖がデカすぎる。

Aは各項をできるだけ小さくした数列を引く方針で2WA。たくさん引いておいたほうが良い項もありうると気づく。隣合う項の差の最小値だと感じて、とりあえず最小値を取る2項を構築しようと思い立つ。極端に偏らせると別の項にしわ寄せがいくことがわかり、できるだけ均して置くことを思いつく。実は全ての項でできるだけ均したほうが良いのではないか?と思い考えたところ、証明がなんとなくつけられたので、提出してAC。

Bは大きいものから貪欲に取ることを考えた。setで管理するコードを書いている間に考えが整理され、中央の2i項のうちi項までしか保持してはいけないという条件になることに気づく。これはBITで計算できる……としたらWA。大きいものから貪欲というのはただの直感であったから、ちゃんと考え直し、priority_queueに2個入れて1個出す方針を生やしてACした。

Cはまず列が与えられたときの答えを考える。解説の2段落目の考察はかなり早い段階でできていた。そのあと、2Nがある山を固定して、挿入DPっぽくすることを考えていた。しかしmaxをうまく管理できなかった。maxについての数え上げで、maxの値を掛け算するのだから、p(x)を「答えがx以上になる場合の数」とおくとsum pになる。この方針を生やして、答えがx以上になる原因となりうるペア(他の場所に答えがもっと大きくなるペアがあるかもしれないが、一旦無視する)を配置し、数え上げてみたところ、全然答えが合わない。そのまま2時間念入りに椅子を温め続けてコンテストが終了した。

Cの解説を少し読んだが、p(x)を「答えがx以下になる場合の数」とおいている。これだけの違いかと思うとちょっと残念。しかしどうやって計算できるのかはまだよくわからないため、別に惜しくもなんともないのかもしれない。

AGCと少し被っていたCF #713 div.3に出て全完した。ABCはよい。Dは1個削除したときの最大値を見る。Eは大きいほうから貪欲に当てはめてよい。Fはどこで立ち止まるか全探索。Gは前計算。input validationが壊れていたらしく、AがHackされて嫌な気分になった。

AGCコードゴルフをする。Aは、均すとき、今何個目の数列を作っているか見るのではなく毎回Aの値をインクリメントすることでも実現できるらしい。a//k+(i<a%k)みたいな式を使っていたが、a++//kでよくなる、ということ。BはPythonheappushpop。Cythonによるループ部の改善があって負けたかと思ったが、n>i>=0~n<i<0にして-1Bできたので再度奪取。

朝方布団に入ってからもずっとなろうを読んでいて、寝たのは午後1時だった。最近読んでいるなろうはこれだ。

https://ncode.syosetu.com/n4212eh/

04/11(日)

午後8時半起床。なろうが面白すぎて布団からの脱出に失敗しそうになるが、食事のため何とか這い出た。ABC198に参加する。今日はスクリーンキャプチャを録画しようと思ったが、なぜか録画が始まらなかった。原因を探している時間もないので、今回はあきらめた。

44分1WA全完で3位。Fが解けたのはかなり運がよかったと感じる。

AはABCで既出。こういう問題で既出かどうかを考えるのは無駄だということはわかっている。

atcoder.jp

Bはよくわからなかったので素直に書いた。Cはコーナーケースで1WA。D、Eはよい。

Fは、面に書く数の重複度を調べる。ある重複度についての回転して一致しないような書き込み方の個数は、最初は手で全通り生成しようと思ったが、さすがに正気に戻ってプログラムで書くことにした。さいころのありうる状態をすべて列挙するのに自信がなかったので、さいころライブラリを検索して拾ってきた。初期状態で面に配置する数を6!通り全探索して、それぞれに対しハッシュ値を計算する。ハッシュ値は、さいころの面の数値を6桁の6進数として読んだ時の値として、さいころを回転させて最も小さかったハッシュ値をもとに一致判定した。いくつか試すと手で計算した値と同じなのでよさそう。

重複度の列挙は再帰関数でよい。重複度の昇順・降順ではなく、実際に重複している値の昇順に列挙することにした。これを適当に組み替えると、a+2b+3c+4d+5e+6f=Sとなる正整数a..fの組み合わせの数を数える問題になる。係数のいくつかは使わないかもしれない。

これはつい最近見たことがある。金曜日に作った多項式補完のverify用問題、yukicderの「貯金箱の溜息」とほとんど一緒だ。貯金箱のため息では硬貨の額面という設定上1|55|10など係数の間に約数・倍数の関係があるが、答えが多項式補完で求まることの証明にはあまり関係がない。結局LCM(1,5,10,50,100,500)=500だったのがLCM(1,2,3,4,5,6)=60になるだけ。というわけでいそいそと多項式補完のライブラリを貼り付けてみたところ、サンプルが見事に合った。提出してAC。

コンテスト後のTLを見ていて気付いたが、Fの最後のステップは素直に考えれば行列累乗だった。

コードゴルフをする。Aの3B解もまた既出であるから、27秒ACで82位だったのを見て絶望していたが、蓋を開けてみれば僕が最短だった。Bは末尾の0を正規表現による置換で削除して云々、と考えていたが、reverseして数値として解釈すると勝手に消えることに気づいた。+0とすると括弧が必要になるので、負号をつけて判定する。Cはdcで、sqrt((X^2+Y^2)/R^2)を考えていたが、sqrt(X^2+Y^2)/Rのほうがよい。sqrtだけ精度を高く設定して計算する。コーナーケースの場合分けはいろいろ試したが、切り上げしてしまうとちょうど1歩でたどり着ける場合と区別がつかないので、切り上げする前に答えが1未満かどうかを見ることにした。Eは適当にPerl。他は手付かず。

CF #714 div.2に出た。ABCDFの5完。どうせ全完できるだろと思ってEを飛ばしたが、Fが大炎上した。

Aはよい。Bは適当に書いて合わせる。Cはsum Mにも制約がついていると思ってO(TM)で解いたらTLEした。行列累乗でO(T log M)でもまたTLE。結局行列累乗したものを前計算することで解いたが、850msとギリギリだった。前計算することさえ思いついていればDPっぽく書けたと思うが、行列累乗のコードを流用することばかり考えていた。Dはaの昇順にどこまで辺を張れるか見る。見るのはgcdのセグメント木で二分探索する。

Fはつらい。差分を計算する。swapする2数をa_1,b_1,a_2,b_2とすると、a_1\lt a_2 \land a_1\le b_1 \land b_2\le a_2というものしか考えなくてよい。aの昇順にペアを見て、a_1,b_1の管理にデータ構造を使おう。-(a_2-b_2)-(b_1-a_1)+|b_2-a_1|+|b_1-a_2|=2\max(a_1,b_2)-2\min(a_2,b_1)なので、まずa_1b_2の大小で場合分け。

a_1\le b_2の場合は2b_2-2\min(a_2,b_1)になる。セグメント木でa_1に対するb_1の最大値を管理しておけばよい(当然座圧が必要になる)。

a_1\ge b_2の場合は2a_1-2\min(a_2,b_1)になる。このa_1が曲者。a_1の最小値とa_1-b_1の最小値の両方を見ておく必要があったので、とりあえずa_1の最小値を管理するセグメント木に入れて、b_1\lt a_2となったものから順にa_1-b_1を管理するセグメント木に移し替えた。aの昇順に見ているので、これでよい。インデックスに対して値を複数持たせるといけないので、座圧の際は複数の要素を1つのインデックスに割り当てないようabのペアでソートしておく必要がある。

Fを通した時には残り9分しかなかった。Eに適当に2回提出したが合わず、これだ!と思ったコードの提出は数秒間に合わなかった。直後にTLでそのコードも間違っていたことを知る。upsolveしておいた。

午前3時くらいから溜めていた日記を書き始めた。木曜日から4日分!いまここを書いている時点で4時間半経過して、12000文字書いたらしい。

週記(2021/03/29-2021/04/04)

03/29(月)

正午、起床。昨日のDDCCのアンケートが来ていたので回答した。

ABC158-Dが縮められていた。

atcoder.jp

非常に面白い。リダイレクトという機能があることを知っているつもりだったが、それがコードゴルフに役立つとは一瞬たりとも考えたことがなかった。これはprintからシェルにリダイレクトしているが、逆にシェルからgetlineにリダイレクトする記法もある。こちらは本当にコードゴルフには役に立たないだろう。getlineが長過ぎるためシェルの方で操作するべきで、その時役立つであろうsystem関数を使用するコードゴルフにはすでに前例がある。

ARC116-Fをupsolveした。

偶数長の列の真ん中2つだけ見る、というのが嘘だったらしい。先頭を削るか末尾を削るかで、奇数長の列に帰着できる。奇数長の列に最初に操作する側が必ず損する(しかもそれで手番が入れ替わるわけでもない)から、奇数長の列を考えるのが後回しになる。このことから、どちらが奇数長の列に対して最初に操作する役割になるか?が定まって、このとき、それぞれの奇数長の列の最終的な値を、先週書いたように真ん中3項を見ることで計算できる。これは、先週の週記に書いた「先頭と末尾のどちらかを削ることによる利得がプレイヤーによらず定まる」ことに対応している。

例えば、全ての数列の長さが2以下だったら楽だろう。長さ2の数列のどちらを選択するか?ということのように、先頭と末尾のどちらかを削ることによる利得がプレイヤーによらず定まって、高橋君はその大きな方を、青木君は小さな方を選択するというようにできないだろうか?

週記(2021/03/22-2021/03/28) - kotatsugameの日記

コンテスト中の大胆な予想というのはあんまり外れていなくて、このもとで考察を進めた後に最初に考えていたことに立ち返れば良かったのだろうか。しかし、解説を読み解く過程でいくつか大きなギャップを感じていて、正直、そのうちの1つがわかっていたとしても、それ以外がわかったかというと自信がない。

昨日は先週ぶんの週記を投稿できずに寝てしまったので、その作業をする。数日溜めてしまっていたので、これにはかなり長い時間がかかった。ずっと文章を書いていた。日曜日のDDCCについてはオンサイトであるから、別に参加記の記事を作った。

kotatsugame.hatenablog.com

kotatsugame.hatenablog.com

DDCCの参加記を書くにあたって、自分の装置実装の模様を撮影した動画をTwitterにアップロードした。ブログ記事に動画を挿入するためだったが、これをきっかけに他にも数名アップロードした人がいるようで、僕は当時失意のズンドコにいてあまり他へ注意を払っていられなかったこともあり、改めて他の人の様子を見られて楽しい。

ただ、僕の動画には微妙に顔が映っている人が2名ほどいるようだったので、正直ちょっと危なさはある。

ARC116-Aのコードゴルフが進んだ。もともと僕のdcが最短で、今日、ループ部を改善して-1Bされていたのに気づいた。そこで改めて最短コードに近い長さの他のコードを眺めていると、Perl 39Bを見つけた。これは普通に三項演算子で書いているだけ。よく考えれば当たり前で、1行に1つしか数値がない上に出力もただの場合分けであるから、dcの利点というのはほとんどない。そこで改めてRakuで書いてみると、さらに-2Bできてしまった。最近はdcでバトルすることが多かったように感じるが、それで視野狭窄に陥っていたのか。

夜、CF #711 div.2に出た。全完8位。

Aは2|gcdとなる場合を考えようと思うと、桁上がりが起こるたびにパリティが変わって良さそうだな、という気分になる。桁上がりが連鎖する場合はともかく、そうでない場合はだいたい20個くらい試したら見つかるだろう。それで書いたら通った。正直全探索で正解だろうと確信していたので、桁上がりが連鎖する場合についてはあまり考えていなかったが、冷静になれば連鎖したらさらに20回くらい調べるのでよい。

Bは二分探索して上のbitから見る。W2^29くらいのbitを持ちうることを忘れて2^19から見始めたため、1WA。これに気づくのに結構時間を使ってしまった。Cはややこしいことが書いてあるが、愚直に実装して毎回何個あるかカウントすれば通る。Dもちょっと悩んだが、数は必ず大きくなるし、クエリごとに全ての数を見ても間に合うので、小さい方から順に見ていく。操作回数の上限については、「その数を作るために現在のクエリで操作した回数の最小値」を持つdpで考慮に入れられる。kxのオーバーフローで1WA。

Eはk_u<=k_vなるu,vについて? v uを聞いて、Yesだったらuvは互いに到達可能。よってk_v-k_uが大きいものから順に聞いていけばよい。これは(正直それ以外の方針で解ける気がしないため、というエスパーでもいいが)証明も付けられる。uからvへ到達可能であることを言えばよくて、u->vという辺があれば当然よい。以下、ない場合(u<-vである場合)を考える。uでもvでもない頂点はN-2個あり、そのうちN-1-k_u個にはuからの辺が存在し、またk_v個はvへの辺が存在する。ここでN-1-k_u+k_v>=N-1>N-2のため、鳩の巣原理よりuからの辺とvへの辺を両方持つ頂点が存在し、それを経由してuからvへ到達できる。

Fはk==1Grundy数を計算するコードを書き、しばらく実験しているとわかってきた。深さはmod 2kで同一視してよく、kから2k-1までのそれぞれの深さに対して、その深さの頂点に対するaの総xorのxorが非ゼロなら先手勝ち。ほとんどエスパーみたいなものだが、一定の確からしさは感じられる。全方位木DPを書いたら一発で通った。

その後しばらく本を読んでいたが、読みきれないまま午前3時半就寝。

03/30(火)

正午起床。

本来は明日本屋に行く予定であったが、明日は昼にyukicoderでコンテストがあることに気づく。4月頭に発売される本を購入することを考えると、03/31はともかく03/30だとちょっと不安感があるが、しばらく迷った結果、今日本屋に行くことにした。

母に車を出してもらい、ちょっと足を伸ばして県内でも大きめの本屋に行った。結局4月頭どころか03/30発売予定の本もなかったが、ともかくそこで5冊買い、さらに古本屋にも行って18冊買った。

この古本屋に前回行ったのは、昨年の8月のようだ。

昼食を食べて古本屋に行く。仙台でも駅前のブックオフにはよく行っていたのだが、最近はご無沙汰。僕が最後に行ったときのものと比較すると、富山で僕が行く古本屋はラノベがよく揃っているように思う。

週記(2020/08/17-2020/08/23) - kotatsugameの日記

半年ぶりということで、本棚のレイアウトこそ様変わりしていないものの、内容にはいくらかの入れ替わりが見られた。まあ店側の商品が何も変わっていなかったとしても、その時々でどのようなタイトルの本に興味を惹かれるか、どの位置の背表紙に目を留めるか、というのはちゃんと時とともに移り変わっていくから、古本の購入は常に行える。

この古本屋、もといブックオフでは、他の店舗と同様トレカの売買も行っている。デュエルマスターズの高額カードを眺めていたが、今や売られているほとんどのカードは左上のコストが丸で囲まれた新しいデザインのものになっていた。そんな中で1枚だけ、僕にとって見慣れたデザインのカードがあった。あの「超新星アポロヌス・ドラゲリオン」……と同じパックで登場した「ザ・ユニバース・ゲート」だ。

《ザ・ユニバース・ゲート》 - デュエル・マスターズ Wiki

このパックは(子供のお小遣い程度ではあるが)かなり買った覚えがある。当然このカードも何枚か当たって、しかし実際にデッキに組み込むことはなかった。そもそもフェニックスなんてほとんど持っていなかったためである。効果のド派手さに惹かれるものはあったのだが……。それが今こうして値段が付いているというのは、なんとも面白く感じられる。ちょっと調べてみたが、別に信じられないような使い方をするわけではなくて、普通にフェニックスを捲ってターンを追加するらしい。

デュエルマスターズの漫画においては、エスメラルダがこのカードを使ってザキラ相手に3ターン追加し、シールドを14枚に増やしていた。そもそもシールドを増やすためのカードをそんなに使えたこと(そのころは墓地から回収して使いまわすなんてのもほとんど知らなかった)、また結局そのシールドがアポロヌス・ドラゲリオンのワールド・ブレイカーで1発で割られてしまったことなど、目まぐるしい展開に気を取られていたが、そもそも3ターン追加したのに殴り勝つ・あるいは究極銀河ユニバースによるエクストラウィンをしなかったことがかなり謎らしい。

ハーメルンの「輝きたくて」が完結した。

syosetu.org

この作者の前作「うちの脳内コンピュータが俺を勝たせようとしてくる」は、作者自身があとがきで指摘しているように終盤かなり駆け足だったが、今度は駆け足どころではなく、個人的には打ち切りと変わらないくらいの唐突さで終わったように感じられた。最近10話くらいかけて描かれたイベントが終わっていたので、書きたいことを全て書いたからこその完結なのかもしれない。考えてみれば、特に山も落ちもない話を延々続けるのは良くないという考え方も存在するだろうし、その点においてはすっぱり完結させてしまうのが一番良いのかも。唐突に終わったと言ったが、では唐突ではない終わり方とはなんなのか?僕がリアルのVtuber界を全然知らないため、最後の山場を感じられなかっただけではないか?

「文字渦」を読んだ。面白かったが、かなり疲れた。自分としてはそれぞれの短編をそれなりに読めていると感じていたのだが、文庫本の巻末の解説を読んでみると、さらに丁寧な解釈がされていて、自分が全然読みこなせていなかったことに気付かされ、愕然。どの短編も全くの無から生まれてきたわけではなくて、ちゃんとモチーフになる事物が存在したらしい。

モチーフ、つまり現実と、そこから小説にするにあたっての創作の境目を見極めるのには、固有名詞の創作か否かの判別が鍵となるだろう。よくわからない語彙が出てきたときに、適当にスルーするか、それとも検索してみるか。全部検索にかけているといくら時間があっても足りないので、自分の嗅覚である程度判別しなければならず、僕は普段SFを読まないためにそのような嗅覚が備わっていない。

そういえば、短編のモチーフについては1つだけ明確にわかったものがあった。「ハングル大移動」と言われて、言語ごとにまとめられた文字の話をしているから、これはと思ってUnicode関連で検索したらあたりだった。Unicodeにおけるハングル文字の配列が変更されたことと、より一般にUnicodeにおける言語の文字領域の話だった。最初からそのつもりで読んだので、この短編についてはかなり読めた方に入るのではないだろうか。

検索している途中に面白い話を見つけた。

現代の避諱。他のサイトでは、こうやって別の文字コードを割り振ることによって、この文字だけ装飾を付けたりすることが簡単にできると書いてあって、うまいなあと思った。

「時々ボソッとロシア語でデレる隣のアーリャさん」を読んだ。ふぁぼん氏がロシア語という部分に反応して言及していたラノベ。イラストが良いので、そういう言及がなくとも購入リストには挙がっていただろう。僕が引きこもっている間に売り切れてしまい、再版を待たなければならなかった。

非常に良かった。ロシア語要素はかなり限定的で、それよりも主人公の過去だとか、それから始まり本編を経ての心境の変化だとかに興味を惹かれた。設定されたキャラ同士の関係も良いしストーリーも良い。おまけに絵も良い。ラブコメとしても面白かった。次の巻が楽しみ。

さらに別の本を読み始めたが、途中で切り上げ、午前4時就寝。

03/31(水)

午後2時半起床。

せっかく本屋に行く日を前倒しにしたのに、当日起きてみたらコンテスト(yukicoderの新入生プログラミングコンテスト 2021(昼の部))が始まっていて絶望。しょうがないので遅れて参加し、途中昼食を挟んで解いた。全完。

Aはよい。Bはちょっと考えたが、たとえばハンバーグだとN+1品あればランチが1つできる、と考えられる。Cは幾何ライブラリを整備したことがあればすぐわかる、というより思い出せるだろう。Dでちょっと式を書いていたら昼食が用意されたため、Dを含めて残り5問を覚えてパソコンの前を離れた。昼食を食べながら全て解き、帰ってきて簡単なものから実装した。

HはA^Bを全探索すればよい。A^Bの各bitがどちらに割り振られるかについては、A<=Bという条件から最上位bitだけ確定し、あとは自由。FはMを全探索すればよい。Dは式を見ると4項ごとに-4倍されているようだったので、N%4N/4%2で場合分けして実装。Eは拡張ダイクストラ。Gは正直何をやっても解けると思っていたが、実装しようと思ったら実は適当にやっても解けないことがわかった。冷静になると後ろから見ればOK。

夜、外食に行き、帰りに本屋に寄った。昨日行った本屋とは違い、こちらはそれより小さな家の近くの本屋だが、ラノベの品揃えは結構充実しており、4月頭に発売される本や昨日探してもなかった03/30発売予定の本を購入することができた。

夜9時からまたyukicoder。今度は新入生プログラミングコンテスト 2021(夜の部)。最後の1問が解けなかった。

Aは、ややこしいが、制約から愚直にやって解ける。FA。Bは適当に貪欲。Cはちょっと面倒な実装。Dはさすがに親の顔より見た。EはBのコードを拾ってきて、後は平均Zを、各要素からZ引くことで総和=0に言い換えるやつ。Gはよくわからなかったが、Rubyで愚直に実装してそれなりに大きそうなケースを試すと爆速だったので提出。変数名を間違えていたりC++に提出してしまったりで、正答まで4回の提出がかかってしまった。C++に間違えて提出したほうはCEになるので、ペナ的には1WA。Gは二分探索の判定問題を考えるとX(X+1)/2>=Nなる最小の整数Xが答え。

Hは、ちょうどこの日きたまさ法の話題を目にしていたので、それをずっと考えていた。しかしかなり経ってから線形性が全然ないのでどうあがいても不可能であることに気づく。きたまさ法について、漸化式の左辺の添字を2倍するときに右辺で添字が変わる変数を勘違いしていて、線形性がなくても行けると盲信してしまっていた。後から適当に行列累乗など生やしてみるもTLEでコンテスト終了。答えを二分探索することでbit列の問題に言い換え、更に高速化できるらしい。

ところで、Gは(問題文は違えども)答えが同じになる問題がAtCoderに存在する。その問題の最短コードがこれだ。

atcoder.jp

\frac{X(X+1)}{2}\ge Nを満たす最小の整数X\left\lfloor\sqrt{2N+\left\lfloor\sqrt{2N}\right\rfloor}\right\rfloor。このコードはコードゴルフの配信中に見つけたことを覚えている。

改めて手元で調べてみたが、この式は少なくとも1\le N\le 10^9では正しい値になるようだ。どのようにして見つけたのだったか、再現してみよう。

まず、\frac{X(X+1)}{2}=Nを解くとX=\frac{-1+\sqrt{8N+1}}{2}=\sqrt{2N+\frac 1 4}-\frac 1 2になる。Xは整数なので天井関数を適用するが、その中身に1-epsを足すことで床関数に直せると考えるとX=\left\lceil\sqrt{2N+\frac 1 4}-\frac 1 2\right\rceil=\left\lfloor\sqrt{2N+\frac 1 4}+\frac 1 2-eps\right\rfloor。ここで根号の中の\frac 1 4epsが打ち消しあうとすればX=\left\lfloor\sqrt{2N}+\frac 1 2\right\rfloorが得られる。昔はこの式によるコードが最短だった。

ここでX=\sqrt{2N}+\frac 1 2として両辺を2乗してみると、X^2=2N+\sqrt{2N}+\frac 1 4。大胆にも\frac 1 4を無視すればX=\sqrt{2N+\sqrt{2N}}が得られ、さらに根号を取るにあたって毎回floorしても答えが合ったというわけだ。

SRMを見送ってラノベを読んだ。「僕が答える君の謎解き 明神凛音は間違えない」。最近「継母の連れ子が元カノだった」で売れている紙城境介さんの新作ということで、本屋で見かけて即決で購入した。非常に面白かった。ラブコメも面白いし、それでいてちゃんとミステリーしている。

ヒロインは、推理に必要な材料が集まった瞬間直ちに真相がわかる特殊能力の持ち主。これで犯人を指摘することはできるが、一方でそれを証明するための推理の流れは自分でもわからない。そこで主人公が、「ヒロインがどのようにして推理し結論にたどり着いたのか」を推理し直すという話である。これはつまり、一見それとはわからない形でストーリー中に「読者への挑戦状」を組み込んでいるとみなすことができて、後期クイーン問題に対する1つの回答である。

また、主人公が最初にたどり着いた推理の道筋が、ヒロインの当時の振る舞いと合わない(証拠を集めながら推理しているのに、集めた順番が違う等)ことがあって、さらに別パターンの推理の道筋を示すなど、多段階の謎解きになっている話もあって、巧みだなあと感じた。

さらに別のラノベを読み始めたが、半分くらいで切り上げた。午前5時半就寝。

04/01(木)

正午起床。

TechFULからAmazonギフト券が5000円ぶん届いていた。いつだかのTCBで1位を獲得した商品。回を重ねるごとにどんどん強い人が進出してきたので、今後1位を取れるかは微妙である。直近のセットなど理論値達成者がいたので、もはやそういう世界の勝負である。

このはてなブログを開設してからこれで3年らしい。RUPCの参加記を書こうと思って開設したはずだ。初期には解いた問題の解説記事を作ったりもしたが、2つ書いただけで終わっていて、それからしばらくは読書記録を更新するのとオンサイトイベントの参加記だけが積み重なっていき、最近(といってももう8ヶ月前か)になって日記を書き始めた。

ブログを開設する前、2017/03の時点から読書記録自体はメモ用紙で付けていたので、そのぶんも記事を立てたときに入れておいた。

チュウニズムのアップデートが行われていた。ノーツ数が4208の譜面が追加されていてびっくりした。これでもエイプリルフール限定ではなく通常の譜面のようだ。これまでの最多ノーツ数はKattobi KEIKYU Riderの3600ノーツだったので、一気に増えたなあという感想。

ABC197-Dが縮められていた。tauと書くと2\piになるのだが、これは素直にギリシャ文字τと書くと2Bになるようで、-1B。piπはどちらも2Bなのでどちらを選ぶかは好みであり、僕はいつもpiと書くが、それに引きずられてtauと書いたままにしていた。悔しいのでしばらく睨んでいたらZ*を使って入力に係数を掛ける書き方を思いつき、縮めることができた。さらに-1B。

atcoder.jp

夕方は本を読んでいて、夜からyukicoderでエイプリルフールコンテストに出場した。今年は自分も1問出している。

yukicoderが今年もエイプリルフールコンテストを開催するらしい。一昨年出題したが、今年も出題しようと思い立つ。

週記(2021/03/08-2021/03/14) - kotatsugameの日記

僕が出したI問題を除いて、コンテスト中にはBDEFKが解けた。

Bはシンプルで、必ずYesになる。Dは公式が存在する事実が有名。Eはなんとなくページのソースを確認したら解けた。FもBと同様エスパー要素のないシンプルな問題。Kは普通に難しくて、Y-12年とY+1年がそれぞれうるう年であるか判定して場合分けした。念入りに考えてコーディングしたところ1発ACできて気分がいい。

挑戦して解けなかった問題について。Aは質問タブを見れば良かったらしい。これは秋分コンテストでも見たもの。Cは最短コードがbash 10Bであるのを見て、tr A-Z a-zとかその逆を試していた。Text(cat)が最短でない以上入力を読む必要があると考えていたが、スペシャルジャッジで弾いていただけらしい。やられた!Hはどうしようもない。Jはfactordbで素因数分解するまでは良かったが、問題名の「除け者」という言葉に囚われて、指数が1であるような素因数だけ抜き出して連結したり掛け合わせたりしていた。特に、連結した文字列の長さは最短コードであるText(cat)の12Bと等しくなったので、これが答えであると確信したのだが……。

さて、僕が出したI問題についての話をしよう。この日記を書いている時点でFavが10個も来ていてありがたい。

yukicoder.me

最初は入力文字列に数字・空白や改行を入れてQコマンド以外も使おうと考えていたのだが、これはちょっと難しいというか面倒であることに気づいた。そこで今のような、英大文字小文字のアルファベット列を出力するソースコードを作成させる問題に簡略化した。

Esolang wikiを探してもまともな処理系はなさそうだったので、安心してオレオレルールを定めることにした。例えば作者のページではqqqqというソースコードqqqq_qqqq_qqqq_qqqq__は改行)を出力するような書き方がされていたが、いちいち改行されてはたまらないため、改行を自動付加せずソースコードだけを出力するような処理系を書いた。これで改行なしのソースコードを食わせれば望んだように、先の例で言うならqqqqqqqqqqqqqqqqが出力されることになる。

しかしこの状態では、問題の回答となるソースコードは改行なしの文字列になってしまうため、出力の最後に改行を付けてくださいという注意書きが推奨される状況においてはあまりよろしくない。そこで、半ば無理やりであるが、処理系自身で1行だけ読んで末尾の改行を取り払うようにしておいた。

このとき2行目以降に適当な文字列を付け加えても無視されるので、そうやって2行以上に渡るソースコードを書いて、実行すると1行目だけ読まれて正しい文字列が出力されるので正しい回答です、とも言える。そんなのは困るため、さらに回答は1行だけにせよとの制約も付けた。1行だと回答は一意に定まるため、これでちゃんとスペシャルジャッジを用いずとも判定できる。まあスペシャルジャッジを書いても良かったのだが、面倒……。

以上のようなことを考えていたので、問題文では「改行」や「1行」という言葉を多用して、なんとか曖昧さをなくそうとすることになった。結果、どことなく怪しげな、何かありそうな問題文になってしまった。

HQ9+以外の文字の扱いに関する質問がいくつか来た。それらは僕の書いた処理系ではnopになるが、WikipediaのHQ9+の記事だけ見ていてはわからないことだっただろう。そのあたりもカバーするつもりで「以下の処理系を使用します」と書いたものの、実際に僕が意図していたことは「以下の処理系を言語仕様の定義であるとします」であったことに気付かされた。

「新 謎解きはディナーのあとで」を読んだ。最近東川篤哉さんの手になる本を全く読んでいなかったので、久しぶりに触れることになった。記憶にあるよりもずっとギャグ調でびっくりしたが、それはそれで面白い。このシリーズの以前の本を読んだのはもう覚えていないくらい昔のことだから、キャラクターなどわからないのではないかとビクビクしながら読み始めたが、すぐ「ああ、こういうキャラだったな」というのが蘇ってきてスムーズに読めた。それほど特徴的なキャラクターたちだったのだろう。

3月が終わっていたので、3月に買った本・読んだ本の集計をした。

来月から頑張りたい。

夜中、溜めていた日記を書いていたが、全然終わらない。月曜日から水曜日のぶんまで書いて、今日のは後回しにしてしまった。布団に入って少しラノベを読んだが、流石に夜が明けそうだったので就寝。午前6時だった。

04/02(金)

午後1時起床。

新妹魔王の契約者」13巻を読んだ。シリーズ完結。12巻が発売されたのは2018/04だったので、丸3年開いたのか。これまで書かれてきた店舗特典等の短編集なので、これまで12巻のストーリーを総復習している感じで、以前の巻を参照しながら読んでみると面白かった。かなり重要なことを話している短編もあるように見えたが、確認してみると、確かにそのシーンは本編では飛ばされていたようだ。短編にたまに入る挿絵は当時描かれたものが使われているため、最近のラノベと比較するとそこまで過激すぎるということはなさそうだが、その分描き下ろしの絵はすごかった。これが全年齢対象というのは信じがたい奇跡。

異世界で美少女になった俺、地球に戻れたので裏垢やってみる。」という作品が完結した。

https://ncode.syosetu.com/n6063gu/

1作、面白いと感じるものを見つけて読了した。「異世界で美少女になった俺、地球に戻れたので裏垢やってみる。」。

週記(2021/03/15-2021/03/21) - kotatsugameの日記

この日に読み始めた。読了したと書いているが、実際には「最新話に追いついた」という意味合いであった。

主人公の友人が高校に入学したこととか、話のネタになりそうな展開はあったものの、あまり触れられずに完結してしまった。番外編で触れられるかもしれないので楽しみに待つつもりだ。

yukicoderのコンテストに出た。6完。コンテストタイトルに〇〇's Birthday Contestと書いてあって、あまり注意していなかったが、本当にお誕生日コンテスト(原義)だった。

Aの問題文を読んでまずびっくり。この時点ではお誕生日コンであることに気づいていなくて、まともな問題を出す気がないのかとキレかけていた。

Bは3進数で桁和を取って、1引くときに繰り下がりが起きてもパリティは変化しないことを確かめた。これでも解けることは解けるが、そもそも取れる石が必ず奇数個なので、そのままNパリティを見ればよかったらしい。解説を見て気づいた。

Cは多倍長整数が必要そうだったのでRubyで書いた。DはRubyto_rで一発。pで出力すると(1/2)のように括弧が付くことに気づかず1WA。

Eは逆から見て/2-3に言い換えた上、NからBFSした。実は4->1以外は/2できるなら貪欲にして良いことが示せるらしい。mod 3に着目すればよいと聞いたので考えてみた。まずmod 3=0のとき、-3しても/2してもずっとmod 3=0であるから、必ず不可能。mod 3!=0のときは-3しても/2してもずっとmod 3!=0なので、値がどんどん小さくなっていって最終的に必ず4->12->1ができる。当然減少スピードが速いほうが良いため、/2を優先的に選択するべきである。この方針だと2回に1回は/2することになるため、操作回数はlogのオーダーになる。

Fを見てTwitterでキレたところ、お誕生日コンであるとの指摘を受け、ここでようやく気づいた。この問題はだいぶ壊れていて、定数を確定させた後の式が何度も更新されることになった。僕は4!P(4n,4n-4)と書かれた時点でイコール(4n)!であると早とちりして、実際その解釈でACしてしまったが、実はn=0のことを考えると両者は一致しない。この点も考慮しつつPで書き表すのは不可能に見えていて、式はその後も何度も修正されていたが、Writerがやりたいこととそれが不可能であることがわかっているだけにもどかしい思いをした。今思えば質問タブでちゃんと指摘すれば良かった。

Gは普通に難しい。解説を読んでもよくわからなかった。

「氷の令嬢の溶かし方」2巻を読んだ。2人が自身の恋心を自覚して両片思い状態になった。これは健康に良い。身も蓋もない話だが、ちゃんと作中でそうであることが明言されているので安心感がある。列車の窓から黒い羊が見えたとき、その羊の少なくともこちら側半分が黒いことしか保証されず、他の羊に関しては何も言えないのと同様に、作中で明言されない限り、ヒロインは主人公が好きなのではなく、今でもただ主人公とお友達になりたいだけである、という可能性を否定しきれない。

なんにせよ、1巻はまだ馴れ初めといった感じなので、続刊が出るよう祈っている。

週記(2020/10/19-2020/10/25) - kotatsugameの日記

とりあえず続刊が出てよかった。さらに帯には何らかの賞を受賞したと書いてあったので、かなり売れているのだと思っていたが、どうやら打ち切り間近らしい。そういうことをかなりオープンにしている作者さんというのは珍しい気がする。それともこのラノベの出版元であるモンスター文庫特有なのか?僕はモンスター文庫を少し避けている節があるのでよくわからない。ともかくも2人が両思いになる様は読みたいので、売れてほしい。03/30に発売してから1週間が勝負……!

また週記を書く。明日は仙台に戻るつもりなので、読んだ本の感想などを実物を参照しながら書こうと思うと今日中に書いておく必要があった。午前5時くらいにこの日のぶんまで追いついたので、就寝。

04/03(土)

午前11時半起床。

バナナを1本食べて車に乗り、両親とともに仙台へ向かう。普段は来た時と同じように新幹線に乗って帰っているが、たまに両親の旅行がてら車で送ってもらうことがあり、初めてではない。非常にありがたいことである。車で移動することのありがたみというのは、主には荷物を自分の目が届く場所で運べることにあると考えている。

途中で三春滝桜を観光した。

三春滝桜 | Find!三春 【みはる観光協会~福島県三春町】

ぐるっと一回りして写真を撮ったが、その中から1枚だけ選んでツイートした。うまい文章が思いつかなかったので、位置情報だけ付けている。何回か写真を見返しているが、やはり綺麗であったと感じられる。せっかくなので、日記では他の写真も投稿しておこう。

f:id:kotatsugame:20210405232725j:plain

f:id:kotatsugame:20210405232858j:plain

f:id:kotatsugame:20210405233021j:plain

f:id:kotatsugame:20210405233036j:plain

f:id:kotatsugame:20210405233040j:plain

夜になって仙台に近づいてきた。仙台は最近新型コロナウイルス感染症の感染が急拡大しているため、市街地で食事をするのは憚られた。よってサービスエリアのフードコートで食事をした。両親はレストランがあるサービスエリアを探していたようだったが、どれも一時休業中であった。

仙台の部屋にたどり着いたのは午後9時手前であった。一緒に運んでもらった仕送りの食糧や本を部屋に入れ、代わりに読み終わった本を持ち帰ってもらう。読了済みだけど読み返したいので手元に置いておきたい本というのはいくつかあって、特に「りゅうおうのおしごと!」なんかは全巻部屋に保管していたのだが、いよいよ本棚の空きスペースがなくなってきたので、今回ついに持ち帰ってもらうことにした。非常にまずいが、本を売るというのは考えられないので、頑張って読むか、本棚を増やすか……。実家の本棚も埋まりつつある。

両親は部屋にしばらく滞在して、持ってきた食糧を棚に詰めたり、僕が放置していた水回りを掃除(!)してくれたりした後、帰っていった。今日は仙台で一泊して、明日富山に帰るらしい。調べると、富山に帰るのは「帰富(きふう)」と呼ぶのがよさそうだった。確かに「帰山」であると、該当しうる県は多数あるようだ。

しばらく放置してしまっていた競プロサークルの公式メールアドレスを確認すると、さっそく入部希望のメールが来ていた。入部届の準備をしなければならない。早速取り掛かろうとしたが、こどふぉがあったので出ることにした。

CF #712 div.1。4完して31位だった。レートは2649→2743(+94)。いい感じ。

A問題は、最初片方を(((...()...)))の形にしてもよいという大嘘をついたが、サンプルで落ちたので気づけた。s_i='0'なるインデックスの個数が偶数でなければならず、かつ先頭と末尾を含んではならない。これらが満たされているとき、s_i='0'なるインデックスだけを取り出すと()()())()()(になるように配置して、残りを先ほどの(((...()...)))で埋めるとよさそう。

Bは最初(i+j)%3で分けることを考えたが、ダメそうだった。そこでなんとなく(i+j)%2を考えるとうまくいった。そうやって市松模様で埋めると、2種類の色のうちどちらかは必ず使用できる。それでどちらかの色を使い切ったら、残りのマスはすべて隣り合っていないので、例えば色2を使い切って色1が余っていたら、色1のぶんを色1と色3の使用できる方で埋めていける。気づけたので面白い。

Cは、遷移コストの式を見ると、aの値が小さくなる方向の遷移はいくらでもできるので気にしなくて良さそう。ここで、まずaが大きくなるほうに移動して……と考えたが、スタートがa最小とは決まっていないためちょっと戸惑った。しかしよく考えてみれば、結局ぐるっと一回りするわけだから、a最小の頂点をスタート地点とみなしてもよい。あとはDPっぽく計算する。DPの値はpriority_queueで管理して、a+cが今見ているaより小さいか大きいかで管理するキューを分け、適当に移し替えながら計算した。コンテスト後のTLによれば、これはa+cの最大値を管理しつつはみ出した分を足すだけでよかったようだ。

Dはいくつか切れ目があって、分割したそれぞれのブロックについては配置が2種類しかありえない。またブロック同士は関係しないので、それぞれ貪欲に取れる。実装にしばらく悩んだ。サンプルも弱かったが、度胸試しとばかりに提出したら通ってびっくり。Eは全然わからなかった。

入部届(と継続届)の準備をする。どちらもGoogle formで作成している。継続届のほうは去年のものをコピーしてきて、いくつか質問を追加するだけで完成。追加した質問というのは、個人とSlackのアカウントとAtCoderアカウントを対応付けるための質問で、これは昨年度のICPC準備の際にうまく対応が取れずちょっと苦労した思い出から。

入部届のほうはそううまくはいかない。弊サークルの入部届は、formの回答を送信すると記入したメールアドレス宛にメールが届き、そこに記載されたSlackの招待リンクやサークルで使っているGoogle ドライブへの招待を通じて活動に参加するという形になっている。どうやら去年のものをコピーしてきただけの入部届ではうまく動いていないようだった。そもそもどういうシステムでそのような連携が可能になっているのかわからなかったので碧黴さんに確認して、返信を待つことにした。

まだなんとなく眠る気になれなかったので、第1回えでゅふぉを開いて全問通したが、かなり大変だった。

ABDEはよい。Cは105個の点が与えられて、偏角の差が最も小さいペアを出力せよという問題。偏角の差というのは時計回りと反時計回りどちらか小さいほうであって、必ずπ以下になる。制約から点の座標の絶対値は104以下であったから、atan2でソートしていけるかと思ったが、WA。

この問題の制約ならatan2を使用してもソートできるらしい。誤差の評価についてはmaspyさんが教えてくださった。

週記(2021/02/01-2021/02/07) - kotatsugameの日記

この部分に続いて引用されたツイートによれば、今回の入力では偏角1e-8くらいの差があるなので、偏角ソートは良さそう。角度を比較するところがダメだったらしいが、それに気づいたのはこの日記を書いているときであって、当時は偏角ソートすら怪しんだ結果整数の範囲で偏角ソートするライブラリを持ち出した。

さて、角度を比較しなければならない。今回は偏角の差であるから、内積を取ってからcosだけ取り出したものの大小比較でよさそう。そのままだと分母にユークリッド距離のsqrtが出てくるが、ここで分母を払って2乗し、改めて符号をつけなおすことで、ちゃんと整数範囲で比較できる。ただし値の大きさが8乗オーダーになるので、__int128を使わなければならなかったが、通った。

みさわさんに別の方法を教えてもらった。あるベクトルを回転させてX軸上にそろえて、角を構成するもう一つのベクトルも同様に回転させ、その位置を外積によって比較することを考える。回転は、以下のツイートのような考え方を用いれば、整数の範囲で行える。

これは回転行列のabs倍をしているとも考えられるが、そちらだと整数になることがあまり直感的ではないように感じられるので、上の説明が一番わかりやすかった。これだと移動後の座標の値は2乗オーダーで、外積でさらに掛け合わせても4乗、よって64bit整数に収まってくれる。Y座標を0以上に直すことで、偏角の差がちゃんとπ以下になる。

Fは幾何。自己交差のない、(凸とは限らない)多角形があって、クエリごとに与えられる直線との共通線分の長さを答える問題。かなり苦労した。基本的には直線と多角形の外周との交点を列挙し、ソートして2個ずつ見る。多角形の頂点が直線上にある場合は、その直前の頂点と直後の頂点を結んでできる線分が直線と交差するか見て、交差しなければその点は考えないことにする。

多角形の辺が直線上にある場合が一番つらい。適当に前処理して、そのような辺が2つ連続することがないように、もっと一般には内角が2直角の頂点がないようにしておく。先ほどと同様に直前の頂点と直後の頂点を結んでできる線分が直線と交差するか見て、交差すれば、交点の代わりに辺を区間として見て両端を持っておく。交差しなければ辺の両端をそれぞれ持ち、処理後にその間が答えに足されていないようなら改めて足すことにしたら通った。

布団に入ってなろうを読み、午前7時半就寝。

04/04(日)

午後1時半、目を覚ます。

昨夜碧黴さんに送ったメッセージに返信があった。Google formの回答を集めるスプレッドシートからスクリプトを動かしているらしかった。formをコピーしただけでは動かないのも当然のことだが、幸いスクリプトや設定をコピーしてくるとちゃんと動いた。

まず継続届のリンクをサークルのSlackに貼って、記入をお願いする。同時に活動する曜日に関するアンケートを取った。新入部員が出そろうまでの仮の日程で、またゴールデンウィークを目途にアンケートを取りなおす予定だ。さらに入部届を公開する。とりあえず入部希望のメールを送ってくれた人に送って、さらにサークルの公式サイトに2021年の新歓ページを作って載せてもらった。サイトのほうは記法などよくわからないことが多かったのでホスフィンに丸投げした。ありがとう……。

2021年度新歓情報 | puzzleknot 公式サイト

ホスフィンはさらにSlackに自己紹介用のチャンネルも作ってくれた。

布団に倒れこむ。眠いが、昨夜読んでいたなろうの続きが気になるので、ずっと読んでいた。途中のこどふぉも微妙な眠気を言い訳にサボり、驚くべきことに午前4時半まで読み続けていたようだ。そのまま寝落ちした。

なろうと書いていたが、正確には「ノクターンノベルズ」というなろうの男性向けR18版サイトだ。「放課後インスタントセックス」という作品。この日の時点ではまだ最新話に追い付いていないので、特に感想などは書かない。

https://novel18.syosetu.com/n7640gf/

週記(2021/03/22-2021/03/28)

03/22(月)

週記を投稿してからはすぐ布団に入った。ハーメルンを開いて少し読み進めただけで寝落ちしてしまった。午前7時半だったようだ。

午後1時起床。布団の中でもぞもぞしていたら学食の営業時間が終了してしまったが、それはそうと床屋に行っておかなければならないため、何とか身を起こす。

購買でパンを買って食べ、床屋で髪の毛を切った。今日担当してくれた人は、体を覆うカバー(散髪ケープというらしい)の首回りをゆるゆるにしたり、使っているバリカンから信じられない音が出ていたりとかなり不安を感じたが、結果的には普通だった。

明日、帰省を予定している。行く機会が極端に減るだろうから、今日はゲーセンに行くことにした。ラーメンで腹ごしらえしてチュウニズムをプレイ。今日はしっかりカウントしていて、5時間半で25クレ使ったようだ。

Blackmagik BlazingでSSSを出せた。

最近追加された新曲の「Blackmagik Blazing」をプレイしたが、手が間に合わなくてお話にならなかった。

週記(2020/11/09-2020/11/15) - kotatsugameの日記

1日に何度もやるような譜面ではないため、今日最初のプレイで決まってよかった。いまだに今回のプレイがなぜうまくいったのか分かっていないが、とりあえず手は間に合っていた。いい感じに力が抜けていたのだろうか。また、以前何連奏かした時の経験から、後半で出てくる斜め3つのタップを擦ったのもよかったと思う。押そうとするとテンポが崩されたり、直後のノーツを押すのが間に合わなかったりして苦労していた。

さらに、前の木曜日のアプデで追加された13+の両方でもSSSを出せた。事前に譜面動画を見ており、速い連打だったり微妙にテンポの違う交互だったりが難しそうだなと思っていたが、実際にプレイしてみるとそれらは誤魔化せるものであった。

午後11時、帰宅。明日新幹線の切符を買うときにお金を下ろすだろうと考えて、今日はATMに寄らなかったのだが、そのくせ所持金をギリギリまで使ってしまったので夕食を食べられなかった。

布団に入って少しハーメルンを読んだが、すぐ寝た。午前5時。

03/23(火)

午前11時起床。帰省の準備をする。とはいっても別に着替えなどを用意する必要はないので、例えばノーパソのOSのアップデートをしておくとか、必要になりそうなデータをクラウドに上げておくとかである。

出掛けにLINEが起動しなくなって焦ったが、調べてみるとこれは僕だけの不具合ではないようだ。対策についてもすでに広まっていて、「AndroidシステムのWebView」というアプリを一旦アンインストールすると良いらしい。試してみると確かに起動するようになった。アンインストールすると、環境によってはChromeが使えなくなったりもしたようだが、僕の方はそういうこともなくて嬉しい。

リュックサック1つを持って午後1時に家を出た。仙台駅に向かい、まずお金を下ろして切符を購入する。すぐ新幹線に乗るわけではなく、しばらく駅前で遊ぶことにする。

まず昼食として、最近できた一蘭に行った。僕が並んだときは先に10人くらい並んでいたように見えたが、帰りは誰一人並んでいなかった。ちょうどピークとぶつかってしまったようだ。

次にゲームセンターに行った。駅前のゲーセンには、手元撮影用のスマホアームを設置している店舗がある。そこに行って、運良くスマホアームが設置された台に入れたので、1時間と少しプレイしていた。かなり調子が良くて、それぞれ1回プレイしただけで13+のスコアをどんどん更新できた。

folern 19-2-0はマジでビビった。13+でこんなに精度が良かったのは初めてである。ただ、今回アタックが出た箇所はかなりどうしようもないと感じているので、AJは遠そう。

時刻表を見て、タイミングを見計らって駅に戻った。地震の影響で臨時ダイヤになっていて少し戸惑ったが、ずれたおかげかやまびこ(東北新幹線の自由席がある列車)とはくたか北陸新幹線)がちょうどうまく接続しているものを見つけたので、それに乗ることにした。

やまびこは上りだからかかなり混み合っていた。大宮の1つか2つ前でたくさん乗ってきて、このご時世では信じられないことに、2人がけの席に2人で座ることになってしまった。降りるときに気づいたが、どうやら立ち乗りも出ていたようだ。それに対して、はくたかはかなりスカスカで安心だった。

車内ではラノベを読んでいたが、残り2、3ページだったのに駅についてしまって残念。駅から父の車で実家まで行く。途中で2軒の本屋に寄り、本を10冊購入した。

実家のWi-Fiで、今日撮影した手元動画をTwitterにアップした。以下のリプライツリーにまとめてある。先頭のものが、先に言及したfolern 19-2-0の手元である。

手袋をしたほうがプレイしやすいと感じるが、それを撮影するとどうにも不格好に思えてしまう。

AndroidシステムのWebView」の不具合修正のアップデートが来たようなので再インストールした。

新幹線で読みさしにしていたラノベを読了。「最強魔法師の隠遁計画12」。この巻からしばらくは、Web版で僕が一番辛かったところであるような記憶がある。書籍化にあたってショックな展開はいくぶん削減されている気もするので、ドンと構えて読んでいきたい。書籍版オリジナルヒロインの影響でストーリーも変わるらしいが、そもそも元のストーリーをすでに忘れ去っていて悲しい。

別の本を読み始めたが、かなり眠くなったので素直に寝ることにした。特にネット小説を読むようなこともなく、午前2時半就寝。

03/24(水)

午前8時半起床。ちょっと目を覚ましてスマホを触ったら、それから二度と眠れなかった。起きると食事を用意してくれそうなので、起きた。

朝ご飯を食べて読書。それから昼食を挟んで午後5時までかけ、「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変2」を読んだ。

今巻も非常に面白い。Web版だといろいろな話がぐちゃぐちゃに入り乱れているという印象を受ける(もちろん、書いている本人には一貫した流れというものがあるのだろうが……)が、書籍になる際に統廃合されてかなり読みやすくなっている。

また政治経済の話は、Web版ではほとんど読み飛ばしてしまっていたが、しっかり読み込むとまた一層面白さが増すことがわかった(このせいで読了にかなり時間がかかった)。もちろん細かい話にはあまりついていけないが、少なくとも人の名前と陣営をちゃんと記憶するだけでも良さそう。

帯には、1巻発売直後からSNSで話題沸騰とある。3巻の予告も巻末についていた。次は夏らしい。好きな作品が書籍化されて、売れ行きが好調である、ということほど良いことはない。

次に「お隣の天使様にいつの間にか駄目人間にされていた件4」を読んだ。最高。Web版を読んでいる人には伝わるだろうが、今巻の最後の方は体育祭である(これは目次からわかる情報なのでネタバレにはならないだろう)。この作品の体育祭の部分は最高であることが知られている。その少しあとの部分も好きなのだが、そちらはこの巻には収録されていなかった。おそらく5巻の冒頭に入るはず。非常に楽しみである。

DDCCの移動に関して考えていた。朝は12時半集合だとわかったので、当日出発することにしても朝は十分余裕がありそう。問題は帰りである。

コンテスト終了は午後6時半で、このご時世なので懇親会などは存在しない。しかし、この時間から帰っても家にたどり着く前にARCが始まってしまうのだ。ARCの前に家に帰れないなら、ARCの後に帰るしかない。

後泊をするのが最も良いはずだが、それは流石にもったいないような感じがして尻込みした。改めて時刻表を確認していると、2012東京駅-2257富山駅という新幹線を発見。これに乗って車内からARCに出場するのは不可能ではないだろう。後ろ3分(降車準備を含めると8分くらい)コーディングできないのはちょっと怖いが、うまく2100-2300を含むような列車は存在しないのでしょうがない。また、2104-2315という列車もあるが、コンテスト開始直後に乗車するようなスケジュールよりも、コンテスト終了直前に降車するほうが幾分マシだろう。他にも、富山駅の1つ前で降りることで駅のホームでのコーディングにも10分程度のまとまった時間を取る、ということも考えられたが、これは迷った結果富山駅まで行くことにした。この決定を後悔することがないようなコンテストでありますように。

深夜、コードゴルフで新手が出ていくつか最短コードを取られた。

atcoder.jp

atcoder.jp

入力をシェルコマンドで加工してdcに渡すとき、わざわざ?で読んでいたが、<<<でdcコードに直接埋め込んで渡すと短くなるものがあるらしい。?を2回以上呼ぶものと、逆順ソートして上から数行読むもの。逆順ソートは、埋め込むことにすると下から数行が簡単に取れるので通常のソート順で良くなる。

この更新には粗が存在しなさそうなのでどうしようもない。ただのdcで無理やり解ける問題があったので、それで1つだけ取り返したのが精一杯であった。

午前1時就寝。

03/25(木)

午後1時起床。最近うまく眠れなかったぶんを取り返そうとでもしているのだろうか。

食事して、最寄りのみどりの窓口まで行って切符を購入する。昨日決めたとおりの日帰りの乗車券と特急券だ。22950円だった。DDCC運営には仙台駅から乗ると言ったのに、富山駅から乗って行くことになってしまったので、ちゃんと交通費を出してくれるか不安な部分もある。念の為メールで確認しておくことにした。

帰ってきてから読書。「公女殿下の家庭教師8」を読んだ。この巻で一区切りついたようだ。Web版からの加筆で、まだWeb版の方でも明かされていなかったはずの設定が出てきてびっくり。

帯にシリーズ20万部突破と書いてある。こちらは8巻で20万部、「お隣の天使様にいつの間にか駄目人間にされていた件」は4巻で30万部らしい。うーむ、ここまで差がつくのか。しかし書店では「公女殿下の家庭教師」も結構プッシュされているような印象を受けるから、天使様が圧倒的なだけで売れているほうなのだろう。

最近スマホTwitterクライアントが頻繁に固まって落ちるので、昨日、ちょっと調べてキャッシュとストレージを消した。合わせて800MBくらいあった。それ以来一度も固まっていないので、かなり効果があったようだ。

もう1冊ラノベを読んでいたが、こどふぉがあったので出た。CF #710 div.3。40分で全完、Dでペナを出して11位。

Aはよい。Bは文字列を直接見ていく実装を頑張ったが、先に'*'だけ取り出してしまうと楽だったようだ。Cはやるだけ。Dもやるだけに見えたが、nが奇数のときに必ず1つ残ることを見落として1WA。非常に難しい。

Eは自由になる要素をqueueで管理するかstackで管理するかで最小・最大を分けることができる。面白い。Fはビビるが、グラフの形がシンプルなのでできる。入力が不親切。制約の文言も不親切。Gは'z'から・'a'から決めるとか謎の方針を産んでしまったが、結局は冷静になってやるだけ。

読んでいたラノベを読了。「暗殺者である俺のステータスが勇者よりも明らかに強いのだが4」。前の巻の刊行から2年が経過しており、内容やキャラクターをかなり忘れてしまっていたが、それは出版側もわかっていたのか冒頭にキャラ紹介やあらすじが付いていて助かる。細かいことを忘れてしまっていても面白かったので、すごいなあという気分になった。

文章に何かしらの特徴を感じたのでちょっと考えてみたが、どうやら会話文が極端に少ないようだ。大半は視点キャラの独白で進行する。このあたり、ちょっとした仕草から読み取らなくても独白で心境などを事細かに描いてくれるので、頭を使わずに読める、かもしれない。

この本の帯にも出版部数が書いてあった。シリーズ4巻(+漫画化3巻?)で驚きの80万部だ。先に挙げた2シリーズを大きく引き離している。そこまで人気だとは思えないのだが……。

1巻が出版されてから3年経っている、という理由かとも思ったが、とはいえ1巻は最初の1年で6刷されているので、最初から売れているらしい。

この作家は僕と同い年のようで、大学受験の直前の11月と直後の3月にそれぞれ本を出版している。流石にヤバすぎる。3月に出した本には、無事大学生になれたとのことが書いてあった。

午前3時半就寝。

03/26(金)

正午、起床。UTPCのため、起床時間を昨日より遅くするわけにはいかなかった。

食事してラノベを読む。「転校先の清楚可憐な美少女が、昔男子と思って一緒に遊んだ幼馴染だった件」。最近こういう「男友達のような距離感の女友達(美少女)」をヒロインに据えたラノベをよく見る気がする。これも同じ系列の作品に思えて、ラブコメとしてはまあ……普通だという感想。ちょっとしたお色気シーンで、男友達の感覚だったヒロインが見せる女らしさに主人公がドギマギするというのもテンプレートだと考えて良い。1点、主人公とヒロインの関係を学校ではひた隠しにしている、というのは結構僕の好みの設定だと思う。

さらにもう一冊。「幼馴染の妹の家庭教師をはじめたら3」を読んだ。前の巻でヒロインと主人公がくっついて、作者もそこで一区切りだと考えていたようだが、続刊を出せたので出したらしい。新ヒロイン登場。主人公は彼女ができた余裕が現れてモテ始めているらしい。これは好きな設定。ネタバレになってしまうが、新ヒロインはこの巻の最後で告白するところまで行く。それをバッサリと断ってしまうあたり、態度がハッキリしていて現実的には好印象だろうが、ラノベ的には大丈夫か?と心配になってしまう。

昨年のICPCの写真が公開された。これは僕(灰色のパーカー)が企業賞をもらって両手を挙げて回っているところ。

yukicoderに参加した。Cで詰まって、Fもかなり難しく、結局Gが間に合わなかった。

Aは値の小さいものから貪欲に取って損しない。Bは食い違うindexをsetで管理する。Cはコンテスト後に解説を読んでupsolveした。N==Kのとき(だけ)が難しいと考えていたのは正しくて、全員がなるべく均一に誤答するというのも正しかったようだ。そこからAを使って穴埋めするのが間違っていた。Dは頑張ると解ける。添字を1ずらしたりしそうだったので丁寧に書いていたが、結局そういうことはなくて綺麗な式になった。

Eは難しかった。最初は使う航空会社を決め打って、頂点をマージしてからグラフ上の最短経路に帰着すると思っていたが、できるグラフが木ではないことにLCAを書いてから気づいて絶望。改めて考え直し、航空会社の間に辺を張って最短経路問題を解くと良いことがわかった。せっかく書いたLCAが無駄にならなくて良かった。

Fは値0だけ特別扱いして、ほかはmod 2^10でまとめてカウントする。Gも同じ要領で解けて、今度は値0と1を特別扱いして頑張る。A_i==0なる値が出現して以降は常に0になることに注意。

夜、ラノベを読みつつGCJ qualに出た。30点取れば良いらしい。

Aは愚直に計算する。Bは最後の1文字を持つDP。Cは逆順に値を埋めつつ適当な区間をreverseしていくと上手くいった。これはほとんど直感で導き出した答えだったのでびっくり。Dは要素を2つ選んでpartitionとするようなクイックソートができる。再帰的に適用して、2段階目以降は呼び出し元のpartitionと比較することで2つ選んだ要素の大小もちゃんと判定できる。Eは諦めた。

溜めていた日記を書いて、午前4時就寝。

03/27(土)

午前12時半起床。急いで食事をし、UTPCに備える。

AGHの満点とDEの部分点を取った。いろいろ手を出しては見たものの、あまり解けなかった。

Aはよい。二分探索しかないと思っていたが、線形時間でも解けるらしくてすごい。Hもまあよい。Gは、最初ある2行を選んでflipしていたが、このとき対角成分の符号を変えないようにするとずれる。正解は対角線上で交わる行と列を同時にflipすること。

Dは、Mがdistinctだとすると、選ぶ人で最もMの値が小さい人を決め打って、それより大きなMの値を持つ人からK-1人選ぶ全ての場合について1/Mの積の和が求まればよい。これはMをソートすると前からdpで計算することでO(NK)で部分点が得られる。distinctでない場合もソートで順序付けしたと考えれば良い。満点は、上の式を多項式の積と和に言い換え、積と和をペアにして持つことでセグ木のようにマージしていけるというもの。多項式の積に言い換えるのはわかったが、そこから適当に係数をいじることで積のまま和を求めようとして失敗した。結局多項式の1点しか見ないので、全体を和で持つという発想がなかった。

Eは、ある区間をまとめてソートするとしたとき、どの2つの区間に分けてソートしても同じ結果にならないときだけ遷移できる。区間を決め打ったときにそれがvalidかを計算するのはどうとでもなるはずで、これはO(N^2)。部分点。

Jをupsolveした。Aをマージしようとすると、x,x,x+1があったときに2x2x+1のどちらを作るべきか一意に定まらない。Bを分割するとよいようだ。これは全然考えなかった。さらに、Aより先にBを使い切るのもダメだということを見逃していくらかWAを重ねた。

Aをdcで、GをOctaveコードゴルフしておいた。Gは普通のbit全探索をOctave風味に直したコードで書いたが、bitを並べた行列は対称性があるため、hadamard行列のように名前が付いていて関数で一発で生成できるかもしれない。

夜、外食して帰りに本屋に寄った。本を10冊買った。

「時々ボソッとロシア語でデレる隣のアーリャさん」は、前回本屋に行ったときは在庫切れで、重版の予定も出ていなかった。本屋に行く前にネットで確認すると、依然「取扱不可」の表示で諦めていたが、念の為探してみるとしれっと入荷していた。奥付を確認すると再版だったので、無事重版してくれたのだろう。

帰宅してABC197に出た。24分全完で2位。Eで勘違いしてしばらく詰まっていたのが痛い。

Aはよい。Bは面倒。Cもよい。Dは面倒。Eは区間の両端さえ考えればよくて、これは前にCFで見た。バチャだったかもしれない。Fはパスの両端を持って縮めていく。

Aの最短はVim。明らかな5B解が存在して、1秒差で負けた。

Bは、最初はスタートから順に置換するのを連鎖させる方法でPerl 140Bを作ったが、マッチした文字列の長さを見ると良いようだ。横はともかく縦が面倒で、transposeを使ったり、行の幅で割ったりしている。CはRuby再帰する。再帰の呼び出しに入力をそのまま埋め込んでevalすることで縮められて、このとき先頭の1要素だけ初期値に抜き出すのが簡単にできる、ということで抜き返した。DはRakuで複素数を使う。

EFは手付かず。Fは嘘解法が通るということで書いてみたが、TLEしたし、そもそも提出する前にafter_contestが追加されていた。

UTPC-Aの最短が取られていた。線形時間で計算する方法にも2種類、前から見るものと後ろから見るものがある。僕は前から見ていたが、dcはスタックの言語なので後ろから見るのも比較的簡単に書ける。これでループ部が改善することもあって-2B。

「ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました3」を読んだ。清々しいまでのチートもの。まあ主人公が強いのは良いことなので、よし。キャラクターをほとんど忘れていたので、最初のほう男だと思って読んでいたキャラクターが女でびっくりしたりもした。剣聖と言われると何もなければ男キャラクターをイメージしてしまう。

夜寝る前、ARCの配点が出た。345588。全完チャンスか……?最近の800は難しいので、なんとも言えない。ただ4問目までで詰まると人生が終了することは確かか。

午前2時就寝。

03/28(日)

午前7時半起床。昨日今日と朝に検温している。これはDDCCからのメールに書いてあったこと。寒い中で計ったのが良くなかったのか、36.3℃と36.1℃だった。流石に平熱がこれであるということはないだろうが、とりあえず発熱はない。

GCJが終了したので結果を見た。Bのhiddenが落ちていた。なぜ落ちたのかわからないのでTLで聞いてみたところ、バグを教えてもらった。

点数的には69点なので、無事Round 1に進めた。

食事してノーパソやノート・筆記用具などを持ち、富山駅まで送ってもらった。午前9時の新幹線に乗って一路東京へ。車中では円城塔「文字渦」を読んでいた。ちなみにこの日記を書いている時点でまだ読み終わっていない。

ここから先の話は、別に参加記を書いた。

kotatsugame.hatenablog.com

帰りに新幹線から出場したARC116について。開始直前にスマホの電波が不調になるなど大変焦ったが、なんとかスムーズに問題を見ることができて助かった。

結果はEまでの速解きで28位、パフォーマンス2937、レートは2662→2692(+30)。

A問題は明らか。この明らかさはむしろコーナーケースへの疑いが強くなるが、自分を信じて提出した。B問題は適当に書く。C問題は比に言い換えると総積がM以下となる。2e5以下の素数を列挙して、それぞれどこに割り振るか決める再帰全探索を、ちょっとした枝刈り付きで書いてみたところ、サンプルの最大ケースでも速かったので提出した。計算量はよくわからない。Dを開いたらまた数え上げで笑ってしまったが、こちらは1桁ごとに見るDP。瞬殺。

Eはパッと見二分探索+DFSだが、正当性がよくわからなかったので、一旦順位表を確認。そこそこ良い位置についていて安心するが、すでにSSRSさんが5完していて目を剥く。こんなに速いんだから、どうやらさっき考えた適当なDFSで良さそうだと見当を付けて実装した。再帰関数が返す値を上手くイメージしておらずちょっと戸惑いつつもサンプルがあったので提出。すると1ケースだけ落ちてしまった。しかし幸運にも適当に試したケースがWAのケースだったので、すぐに修正できてAC。ちなみに落ちたのは、根に直接情報を伝達する必要があるかの判定ミスだった。

Fもよくわからないので、とりあえずA問題とB問題のコードゴルフをした。Fに戻って考えてみる。例えば、全ての数列の長さが2以下だったら楽だろう。長さ2の数列のどちらを選択するか?ということのように、先頭と末尾のどちらかを削ることによる利得がプレイヤーによらず定まって、高橋君はその大きな方を、青木君は小さな方を選択するというようにできないだろうか?結果的に言えばこれは正解の方針だが、コンテスト中の僕は利得をプレイヤーによらず定めるところで躓いてしまった。

ここでサンプル2を眺めつつ、大胆に予想を打ち立てる。数列の真ん中の方の値しか関係ないのではないだろうか?これは、自分が真ん中からずらそうとして削っても、相手は反対側を削ることでそれをキャンセルできる、ということからわかる。この考察には既視感があった。奇数長の列の真ん中を取り、偶数長の列は真ん中2つだけ見ることで、全ての数列の長さが2以下の場合に帰着できた。

しかしこれは合わない。奇数長の列の真ん中を取るのではなく、真ん中3つを見て適当に定めると良さそう。このとき、場合分けして計算した結果から、自分から選択すると相手に邪魔されるので、どうしても損してしまうことがわかる。つまり奇数長の列を考えるのは後回しになりそう。実際にどちらが選択することになるのかは、偶数長の列の個数の偶奇で定まる。これを実装するとサンプルが合うが、WA。そのまま修正できずコンテストが終了した。

終了前の数分を争うような状況にならなくて良かった、という思いもあるものの、全完していない以上、半ば諦めてしまっていた自分の弱さも感じてしまう。

コードゴルフについては、Aをdcで、BはRubyで書いただけ。dcはRで出力文字列を持ってくる関係上|コマンドを使うのが定石だが、TLEしてしまったのでおとなしく4%1+Rとした。Bは適当に書いて同値な変形を繰り返す。modの値を変数に入れるとき、そのまま和の変数を初期化しても良い、つまりsum,mod=0,998244353sum=mod=998244353が本質的に同じであるというのはよく使う面白いテク。

帰宅する。風呂に入った後は眠すぎたのですぐに寝た。午前1時半だった。

DISCO presents ディスカバリーチャンネル コードコンテスト2021 本戦 参加記

2021/03/28に行われたDISCO presents ディスカバリーチャンネル コードコンテスト2021 本戦に参加してきました。

今年はコロナウイルス感染拡大の影響で全然オンサイトがなく、なんと最後に参加したものは去年のDDCC2020本戦でした。

kotatsugame.hatenablog.com

なかなか面白いめぐり合わせですね。この状況下で開催を決断してくださった運営の方々、また感染症対策などに気を使いつつコンテストを進行してくださったスタッフの皆さん、ありがとうございました。

ちなみに、念の為予選の成績を書いておくと、30分ちょっとで全完でした。

今年はコード部門がないので、本戦開始時刻も遅くなりました。具体的には、午前13時開始なので、朝にはいくらか余裕があります。昨年は始発の新幹線に乗りましたからね……。

とはいえ、今年は僕が富山県に帰省中なので、仙台駅から向かった昨年と比べて(駅までの移動も合わせ)移動時間は増えます。なかなかちょうどよい列車がなかったこともあって、今年は指定席特急券を買い、速い列車で行くことにしました。僕は22卒の対象に含まれるので、交通費も支給されます。というわけで、09:08富山駅発11:20東京駅着のかがやきに乗りました。

新幹線の中で本戦参加者のTwitterリストを作りました。

twitter.com

東京駅から品川駅を経由して大森海岸駅まで向かいます。うっかりグリーン車の車両に乗ってしまい、わざわざ普通車に通り抜けさせてもらいました。こういうのは問答無用でグリーン車乗車券を買わされるものだと思っていたので、人の温かみに触れた気がしました。

品川駅でJRと京急の乗り換えに失敗し、検索して出てきたものより1本遅れてしまいましたが、無事到着。駅の近くで食事をしようと考え、ふとTLで目にしたなか卯に行ってみると、4人くらいの競プロerが集まっていました。5人目は流石にマズいので、挨拶だけして食事は別の席でしました。

僕「これって勝手に帰っていいんですか」

kort0nさん「(券売機を指しつつ)お金払ったでしょ」

僕「……(納得して退店)」

ディスコ本社に向かうも、受付開始の12:30までは入れないようだったので、横のイトーヨーカドーに向かいます。その途中すれ違ったkyopro_friendsさんに声を掛けていただき、2人で少しだけうろつきましたが、特に何か見るわけでもなく、すぐディスコ本社前に向かいました。本社前には他にも所在なげに立ち尽くしている競プロerが複数人いて、そのうち自宅番兵さん等と挨拶しているうちに、受付開始時間になりました。

コンテスト前

検温・マスク交換・アルコール消毒して、名札を受け取り、コンテスト会場に向かいます。交通費領収書もこのとき渡すのですが、封筒に入れなければならないところを用意していなかったので、急遽クリアファイルをもらって名前を書くことになりました。少し時間を食って他の人を待たせてしまい申し訳ない……。

コンテスト会場に用意されていた席は、上下以外の4方がビニールに覆われていてびっくりしました。企業紹介映像を見る限り、このようなブースは普段の業務でも使用しているようで、なかなか大変そうだなあという気持ちになりました。

机に用意されていたTシャツを着ていると、インタビューを申し込まれたので、しばらく答えていました。

これまでのDDCCへの参加経験を聞かれ、昨年本戦に出たということ、また予選は詳しく覚えていないが、2016年から競プロを始めたので、それ以降のものには出ているんじゃないかと答えました。DDCCもちょうど2016年から始まったということで、これも面白いめぐり合わせです。後から確認したところ、2016年と2017年の予選には参加していたようです。

また、この記事の冒頭でも書きましたが、昨年のDDCCから丸1年オンサイトがなかったことにも触れ、開催していただけてありがたいということも言いました。

本戦にかける意気込みを聞かれて、「昨年は装置に自分のプログラムを実装することができなかったので、今年はそこまで進みたい」ということを答えたのですが、今年はシミュレーションで点数を取れば全員実装できるということを知ってちょっと拍子抜けしました。まあ30人しかいなければそんなものなんですかね。

その後説明・会社紹介があって、いよいよ問題公開・コーディングです。

シミュレータ問題

問題は、簡単にいえば次のようなものです。制約の細かい値(例えば穴の詳細等)は、忘れたものもあるので、気にしないでください。

長方形の平面がある。ある辺の中心にボール射出装置があり、平面上に10個の穴がある。

ボール射出装置の向きと平面の傾きをある程度操作できるので、ボールを射出して穴に入れ、後述するスコアを最大化する。

スコアは、穴に入ったボールの個数×ボールが1つ以上入った穴の個数で計算される。 ただし、1つの穴に10個ボールが入るとそれ以上その穴にボールを入れてもスコアには影響しなくなる。

ボール射出装置や平面の操作のパラメータ、射出するボールの個数、その後の次の動作までの待ち時間をセットで指定して、装置を動かすことを繰り返す。 ボール射出装置や平面の操作のために1.7secかかり、ボールを1つ発射するのに0.5secかかる。

まずは60分コーディングし、シミュレータ上でスコアを競います。シミュレータでは、制限時間は100secで、待ち時間が終了するとその時点で穴に入っていないボールは無視されます。

まず、ボール射出装置の角度だけで狙える穴だけ狙うことにします。待ち時間は、最も遠い穴まで転がることを考えても2.1secあれば十分で、このとき1.7+0.5×10+2.1=8.8[sec]となり、10個の穴をそれぞれ狙って10個ずつボールを打っても制限時間に間に合います。

テストケース5つは、予選と同様事前に公開されたものをコードに貼り付ける形です。実は1つだけ、ボール射出装置の角度だけでは狙えない位置にある穴が存在しましたが、それ以外は大丈夫なようです。コーディングして提出すると、3070点になりました。

これは予想していたよりかなり低いスコアです。適当に提出を繰り返して何故か調べてみたところ、どうやら奥の穴を狙って打ったのに手前の穴に吸い込まれてしまっていたようでした。当たり前すぎる……。これをなんとかするためには、平面を傾けて狙う必要がありそうです。

傾いた平面における、球の傾き方向への加速度の式は、問題ページに書いてありました。傾きを\thetaとして\frac 5 7g\sin\thetaらしいです。係数が何から出ているのかよくわかりませんが、これの物理学的導出に注意を払っている時間はなく、僕は久しぶりに扱う等加速度運動にドキドキしていました。

とりあえず平面をボール射出装置(の初期状態の方向)から見て左右に傾けるだけにすることにします。最初に打ち出す角度と到達させたい場所が分かれば、平面の傾きをarcsinで求められることがわかりました。平面の傾きは、支持する軸を上下させて操作するという制約上、それほど大きく傾けられるわけではありません。適当に三分探索などして、平面の傾きが打ち出す角度が制限内に収まるものを探しました。

これで、以前に射出した角度に近いものを使用しないようにしてコーディングしたところ、3260点が出ました。思ったより伸びませんでしたが、ここでシミュレータ問題の時間終了です。

実機への実装

シミュレータ問題の順位が発表されました。僕は2位だったようです。beetさんなどの話を聞く限り、その下はだいたい3060点で団子になっているような感じでした。少しでも改善できたことが良かったのでしょう。2位なので、実機実装は2番目に行えます。

まず30分のコーディング時間が与えられ、そこで最後に提出したコードが実機に実装されます。実機の穴の情報もシミュレータ問題と同様のフォーマットで与えられますが、制約に変更がありました。

待ち時間が終了しても穴に入っていないボールが消えたりしないこと、また台を手前に向けて傾けることが可能になったことは、シミュレータで再現が難しかった部分の制限撤廃でしょう。最も大きい変更は、制限時間が60secになったことです。これによって、ボールを全て打ち切ることが不可能になりました。

実機では、ボール射出装置から見てある穴の後ろに隠れてしまう穴が4つ程度存在するようでした。テストで動かしてみる機会は1度しかなく、10発ずつ打っていると時間がなくなってしまうため、とりあえずの軌道だけ確認しようと1発ずつ打つことにしました。これは結構特徴的だったようです。

それで動かしてみたところ、他の穴に隠れていない穴には順当に入りましたが、傾けて打ったボールは1つが狙い通りに入り、もう1つ穴に弾かれて別の穴に入っただけでした。どうやら遠くの穴を狙うとかなりブレてしまうようです。

これをメモして、他の人の動作をしばらく見ていましたが、装置の不具合などもあって順調に進まず、結構暇を持て余していました。この時間はコーディング不可なので、手で少し計算するくらいしかやることがなくて、あとはなろう小説を読んだりしていました。

本番前

また30分与えられてコーディングし、ここでの最終提出を再度動かして順位を決めます。

先程見たように、遠くの穴を狙うとブレている、もっと詳しく言えば曲がりすぎてしまうようだったので、そこを補正しました。これは「頭で考えた値を埋め込むことを禁止する」というルールに抵触しそうだなと思いましたが、それっぽいif文で押し切りました。

他にも、ボールを射出してからの待ち時間を0secにしてしまったが故に、まだ転がっているボールがあるのに平面を傾けてしまいあらぬところに転がっていった人がかなりいたので、その点も調整しました。具体的には、平面を操作せずに狙える穴だけまとめて待ち時間0secで狙い、そこからしばらく待って、転がりきってから平面を操作し始めるという感じにしました。

傾けずに狙える穴へは変わらず10発打ちますが、傾けて穴を狙うのは難しいので、10発ではなくそれぞれ3発だけにして、時間制限のクリアとともに全ての穴に入れることでのスコアアップを狙いました。

本番

人生終了

穴を狙うときの射出装置の傾き同士の差が、より大きくなるようにしたのですが、それで台を傾けたときの誤差が大きくなったのでしょうか、全然入りませんでした。補正する値を適当に決めたのも良くなかったのでしょう。見返してみると謎の軌道で狙っている穴もあって、よくわかりません。

スコアは420点で、最終的に22位だったようです。同点が3人いて、タイブレークにはシミュレータ問題の順位が使用されました。

コンテスト後

実はスケジュールが遅れた影響で予定していた新幹線に間に合わない可能性が出てきて、本番実装を一番最初に行ってもらった上、最後の10人くらい(と表彰式)を見ずに帰宅しました。

ディスコ本社の看板を撮影していると、玄関口まで送ってくださったスタッフさんが声を掛けてくださって、写真を撮ってもらいました。

夜はぽかーん懐古DPさんと食事する予定を立てていましたが、時間に余裕がなく失敗。一人で食べることになりました。前に碧黴さんと行った東京ラーメンストリートのつけ麺屋に入ろうとしましたが、微妙に並んでいたので、諦めて2軒隣の豚骨ラーメン屋に入りました。

夜は20:12東京駅発22:57富山駅着のはくたかに乗りました。東京・上野・大宮で結構人が乗ってきましたが、幸い2人がけの席を1人で使えるくらいだったので、安心してパソコンを出し、ARCに出場しました。別に隣に人がいたからと言ってARCに出ないわけはないのですが、まあ気を使わなくて済むのはよいことです。

ARCはEまで速解きして温まりました。

コード

コードを公開しておきます。

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int XYin[20]={0,450,85,575,340,700,170,700,0,700,-340,700,-280,825,255,950,0,950,-340,950};
pair<int,int>XY[10];
int elapsed;
double calc(int x,int y,double th)
{
    double t=y/(500*cos(th));
    double dx=x-tan(th)*y;
    dx/=t*t/2*5/7*9.8e3;
    return asin(dx);
}
vector<double>S;
void disp(double th,int id,int N,int Tm)
{
    int x=XY[id].first,y=XY[id].second;
    double ph=calc(x,y,th);
    int up=round(tan(ph)*400*1e3);
    int theta=round(th*180/M_PI*1e3);
    if(abs(up)>25000)
    {
        cerr<<"ERROR"<<endl;
    }
    cout<<0<<","<<up<<","<<-up<<","<<theta<<","<<N<<","<<Tm<<endl;
    elapsed+=N*500+Tm+1700;
    //cerr<<elapsed<<endl;
}
bool usd[10];
void disp(int id,int N)
{
    int x=XY[id].first,y=XY[id].second;
    double pre=-M_PI/4;
    const double EPS=1e-2;
    sort(S.begin(),S.end());
    double ansth,ansph;
    double absmn=0;
    for(double t:S)
    {
        double thl=pre+EPS;
        double thr=t-EPS;
        if(thl<thr)
        {
            for(int _=0;_<50;_++)
            {
                double th1=(thl*2+thr)/3,th2=(thl+thr*2)/3;
                double ph1=calc(x,y,th1);
                double ph2=calc(x,y,th2);
                if(abs(ph1)<abs(ph2))thr=th2;
                else thl=th1;
            }
            double th=(thl+thr)/2;
            double ph=calc(x,y,th);
            int up=round(tan(ph)*400*1e3);
            int theta=round(th*180/M_PI*1e3);
            if(abs(up)>25000)continue;
            double mn=9e9;
            for(int i=0;i<10;i++)if(usd[i])
            {
                int tx=XY[i].first,ty=XY[i].second;
                double phi=calc(tx,ty,th);
                mn=min(mn,abs(ph-phi));
            }
            if(absmn<mn)
            {
                absmn=mn;
                ansth=th;
                ansph=ph;
            }
        }
        pre=t;
    }
    if(absmn==9e9)cerr<<"ERROR"<<endl;
    double th=ansth;
    if(th!=0&&y>800)
    {
        if(th>0)th+=5e-3;
        else th-=5e-3;
    }
    double ph=calc(x,y,th);
    int up=round(tan(ph)*400*1e3);
    int theta=round(th*180/M_PI*1e3);
    int Tm=ceil(y*2/cos(th));
    cout<<0<<","<<up<<","<<-up<<","<<theta<<","<<N<<","<<Tm<<endl;
    elapsed+=N*500+Tm+1700;
    //cerr<<elapsed<<endl;
    usd[id]=true;
    S.push_back(th);
}
int main()
{
    for(int i=0;i<10;i++)
    {
        XY[i]=make_pair(XYin[i*2],XYin[i*2+1]);
    }
    vector<pair<double,int> >FST;
    for(int i=0;i<10;i++)
    {
        int x=XY[i].first,y=XY[i].second;
        double th=atan2(x,y);
        bool fn=false;
        for(double t:S)if(abs(t-th)<0.03)fn=true;
        if(fn)
        {
        }
        else
        {
            usd[i]=true;
            FST.push_back(make_pair(th,i));
            S.push_back(th);
        }
    }
    for(int i=0;i<FST.size();i++)
    {
        int Tm=0;
        if(i+1==FST.size())
        {
            double th=FST[i].first;
            Tm=ceil(XY[i].second*2/cos(th));
        }
        disp(FST[i].first,FST[i].second,10,Tm);
    }
    S.push_back(M_PI/4);
    for(int i=0;i<10;i++)if(!usd[i])
    {
        disp(i,3);
    }
}

週記(2021/03/15-2021/03/21)

03/15(月)

週記を投稿してから少しハーメルンを読み、午前9時半に就寝。

午前11時、前日シャワーを浴びなかったことによる頭皮の異常なかゆみに耐え切れず、いったん起床してシャワーを浴びた。そうすると目が覚めたので、生活リズムを無理やり整えるためにも起き続けておくことにした。しかし今度は微妙な眠気でなんのやる気も起きない。

昨日のARC114Eを解いた。「各直線が使われる確率の和(+1)が全体の期待値」という考察、この一言に700点がついているという感じで、本当にすごい問題。一言聞くだけでたちどころに了解できてしまう考察なのだが、コンテスト中は解けなかった。

適当に縮めたあと、この問題では最速コードも狙ってみることにした。1からNまでの逆元を求めるのには、有名なO(N)の実装があるが、変数による剰余算や配列のシーケンシャルでないアクセスが入って遅そうに感じる。ここで\frac{1}{i}=\frac{(i-1)!}{i!}を利用してみることにした。これはO(N+log mod)だが、適当に埋め込めばlog modは消せる。しかし配列を2本使うのはやはりまずかったのか、遅くなってしまった。例えば、普通のO(N)の実装ではmod/imod%iが両方出てきているが、適切に最適化がかかっていれば、これはdivmod相当のことができて1回の演算でどちらも取得できる。やはり見た目よりは高速に動作するのだろう。

逆元の和を取る部分は、事前に累積和を計算しておくことで対応できる。ほかにも剰余を取る演算を引き算に直したり、入出力を自前で書いたものにして、そこそこ速そうなコードが完成した。少し提出して様子を見ると、Clangを使ったほうが速いようなので、それで提出を繰り返す。現在の最速は8msだったわけだが、数回の提出で無事7msを引き当てることに成功した。しかし別の提出について実行時間の内容を見てみたところ、7ms以上を記録したケースが1つしか存在しないものを発見した。これは6msも狙えるのでは!?となって、そこから20回弱の提出を繰り返し、なんとか6msを引き当てた。本当に運が良ければ5msも出ないことはなさそうだが、ジャッジアップデート後のAtCoderの実行時間はブレブレなので、これくらいで止めにしておこう。

atcoder.jp

C問題のコードゴルフをする。解説の式は、k=i-jと置くとこうなる。

\displaystyle N M^N-\sum_{x=1}^M\sum_{k=1}^{N-1}(N-k)(M-x)^{k-1}M^{N-k-1}

2つ目の\sumから先をWolframAlphaに投げると、うまいこと閉じた式が帰ってくる。

\displaystyle N M^N-\sum_{x=1}^M\frac{(M-x)^N-N(M-x)M^{N-1}+(N-1)M^N}{x^2}

M-xでループしたりしてみたが、結局このままのほうが短くなるようだ。N M^N\sumの中に入れて、

\displaystyle \sum_{x=1}^M\frac{M^{N-1}(M+Nx(x-1))-(M-x)^N}{x^2}

atcoder.jp

昨日のTROC20のC問題の解法が間違っていた。全部1のときは常にYESらしい。僕の解法(実際に試してみる)だと、少なくとも2x4の盤面でNOを出力してしまう。

そのあと、ARC114Aのコードゴルフをしたあたりで本格的に眠気が耐えられなくなり、午後6時くらいに1時間の目覚ましをかけて昼寝することにした。この目覚ましで意識を取り戻すまではよかったのだが、さらに1時間伸ばして二度寝した結果、今度の目覚ましには気づけず、日付が変わるまでぐっすり寝てしまった。

03/16(火)

午前2時半起床。あまりよろしくない生活リズム。うっかりハーメルンを読み始めてしまい、そのくせ午前7時半くらいに再度寝落ちした。次に起きたのは正午で、これはICPC 1日目の予定が始まる直前だった。ここからのことは参加記の1日目の部分に書いてある。

kotatsugame.hatenablog.com

夜作っていた2Dセグ木ライブラリについて、もう少し詳しく書いておく。これは、先週のICPCチーム練で出会った問題を解こうとしていた。

残り時間はIと格闘していた。明らかに計算量がヤバそうな解を書いてTLEを出しまくるも通らず、このタイミングで参加してきたゆきのんさんに2Dセグ木では?と言われてうしさんのライブラリをコピペしてきたが使い方がよくわからず、提出が数秒間に合わなかった。ちなみにTLEした。コンテスト後もしばらく格闘していたが、ずっとtest 5でTLEしていてつらくなったので通らないまま諦めた。

週記(2021/03/08-2021/03/14) - kotatsugameの日記

この日使っていたうしさんの2Dセグ木は、HWが105オーダーの時に必要な箇所だけ作るタイプのセグメント木だったようだ。そうではなく、HW個ちゃんと作るタイプの2Dセグ木もあるようで、今日はこちらを実装した。dat[i][j]が、iが対応する区間の行掛けるjが対応する区間の列の値となる。演算の順番は保存できないため、可換性が要求される。1点更新と2次元区間取得はどちらもO(\log H\log W)となる。

algoogle.hadrori.jp

ここにある実装を参考にした。「単純にセグメント木を拡張したもの」とだけ書いてあったので、具体的なアルゴリズムは実装から読み解くことになったのだが、わかってしまえば確かに「単純に拡張したもの」にしか見えない。上の実装は再帰関数によるものだが、通常のセグメント木とほとんど同じロジックで非再帰にできる。結局、僕の実装では以下のようになった。ACL準拠のつもりで関数opはテンプレート引数になっている。

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

これを使って、先週のICPCチーム練のIに再挑戦した。数回の挑戦の後、入力部を少し変えたら1996msで通った。

ヤバすぎ。

FastIOもライブラリ化しておこうと思ったが、設計を考えながら布団に入ったら(?)寝落ちしてしまった。午後10時だった。

03/17(水)

午前3時半起床。昨日と同じくベッドでハーメルンを読んでいたが、今日の予定は昨日よりさらに早いため、万が一にも寝落ちするとまずい。布団を出てTechFULのイベントを進めることにした。TCB34は今日から開催されている。

なんとか全完した。現時点では1位だが……。このセットだと結構ペナが出ると思うのだが、これからイベント終了までどこまで下がるのだろうか。この週記が公開される頃にはイベントが終了しているので、今回もここに解法を書いておこう。

1から5問目はよい。6問目はいくらか迷走したが、小さいほうから(K+1)/2個に1個ずつ取っていくことになる。7問目は後ろから見た。ひたすら面倒。8問目はすべての問題の中で最も簡単だが、セグメント木を使うという1点からここに配置するしかなかったのだろう。9問目は、絶対値をmaxに言い換えて左から見たセグ木と右から見たセグ木で別々に持つ。頭がなかったので1WA。

10問目は問題名を見た瞬間からbinary trieを使うのだろうとは思っていて、事前に準備しておくつもりだったが、9問目でWAを出したのでヤケクソになって突撃。見た瞬間binary trie+Mo's algorithmのO(\sqrt{N}(N+Q)\log \max X)が思い浮かんで、それ以外の方法が全然わからなかったので、書いた。最初に提出したものは初期化ミスで全ケースWAだった。2回目に提出したものはTLE。ここで、Mo's algorithmの影響で同じ値を何度もbinary trieに出し入れしているため、アクセスするノードを前計算しておくことにすると、最遅ケースで3.5secになり、通った。

かなりつらい。TechFULのジャッジは弱い、というのはわかっていたので、最初からできるだけの高速化をしておけと言われればその通りなのだが……。もうちょっとオーダーの良い解法があるのだろうか。ほかの人がどうやって解いたのか知りたい。

これをきっかけとしてbinary trieのライブラリを作ることにした。bit幅をテンプレート引数で受け取るようにする。keyを表す型は、unsigned long long固定ではなく、bit幅に応じてunsigned intと切り替えて使い分けるようにしたいが、このようなことは可能だろうか?TLに質問を投げたところ、えびちゃんさんからconditionalというものを教えてもらった。C++11かららしい。

std::conditional - cppreference.com

これを使って少し書いていたら、ICPCの2日目が始まった。コンテストとそのあとの懇親会については参加記の2日目の部分に書いておいた。昨日の日記にもリンクを貼ったが、ここにも貼っておこう。

kotatsugame.hatenablog.com

そういえば、昨日の夜格闘していたICPC練のI問題についてだが、こるとんさんのチームも最近同じセットを走ったようなので、懇親会で聞いてみたのだった。どうやらlog 1つの解法があって、ただ2Dセグ木によるlog 2つでも通らないことはないだろう、というコメントがkoosagaから出ていたらしい。

夜、参加記を書いていたが、こどふぉが始まっていたことに気づいたのでなんとなく参加した。CF #708 Div.2である。途中から眠気がすごくて大変なことになったが、何とか全完した。

Aから面倒だが、適当にやってよさそう。Bは2WAしてキレそうになったが、よく見ると(M+1)/2であるべきところがM/2になっていた。最初のWAのあと、この部分も確認したはずなのだが……。このあたりで自分が思ったより疲れていることを自覚した。C1は気合いで場合分けしたらできた。C2も気合いで場合分けしそうになったが、ふと、3個残して他を全部1にするとC1に帰着できることに気づいた。TLでは面白い問題であると評価されていたが、確かに、誘導としてのC1がないとハマってしまったかもしれない。

この時点でDはsolvedが2人とかだったので飛ばし、E1に行った。E1は自明。その後Dに戻った。メモリ制限が厳しいタイプの問題のようだ。dpをするとき、配列を使いまわすことで次元を1つ減らすテクを使えば、この制限自体は簡単にクリアできそうな気がする。適当に書いたらサンプルが合わなかったが、よく見るとサンプルの出力と説明に書いてある値が異なっている。説明を信じることにすれば、僕の出力は正しいようだったので、提出してみたところ、1ケース目のサンプルで落ちてしまった。これはペナルティに含まれないはずなので、まあよい。サンプルを合わせて再度提出すると、今度は4ケース目でWAが出た。これの解消には非常に苦しんだが、試行錯誤の過程でセグメント木を使用する必要がないことに気付いたため、実行時間が大幅に短くなったのはよかった。眠気に抗いながら考えて、何とかHackケースを見つけることができてAC。メモリも実行時間も申し分ない。

E2はかなり速く解法にたどり着くことができたが、コーディングも終盤に差し掛かったあたりでふと残り時間を見ると、コンテストがあと2分くらいになっていて非常に焦った。急いで書き上げてサンプルを確認し提出したところ、残り時間が増えてびっくり。これは、途中でコンテストが15分伸びたのに、ページをリロードしなかったせいで起こった勘違いだったようだ。

コンテストが終わってから再度参加記を書く作業に戻り、午前2時半に投稿。午前3時就寝。

03/18(木)

午後2時起床。

懇親会でkotamanegi氏に聞いてみたところ、似たような問題設定を考えていたこと、またこのような問題設定が好きであるからC問題に手を付けたと言っていた。僕も同様に、このような問題設定(または問題名「Short Coding」)に好奇心を刺激されたので手を付けた。確かに問題の見た目的に重そうではあるものの、この問題に興味を持つようなチームが2つも存在してしまった、というのがbeet_aizu氏の戦略がうまくいかなかった原因だったのだろう。そうでなければ後回しにすべき問題に見える、というのには頷ける。

ベッドの上から動かないまま寝たりなろうを読んだりしていたら、午後9時半になってしまった。起きて食事。今日は板チョコレート。そのあと、しばらく自分の本名で検索して遊んでいた。自分の本名というのは検索してはいけないワードとしてよく挙げられるものであるが、僕の場合はマイナスイメージのあるような検索結果が出ないため、かなり気軽に検索できる。

Twitter Web Appのフォローボタンが、これまでは未フォロー⇔白だったのに、既フォロー⇔白になっていた。なんで色を、よりにもよって真逆にしてしまったのか。全然慣れない。

ECR106があったので出た。4完、5完時点では1位だったが、Fに手間取って4位。Gは手も足も出なかったのでなろうを読んでいた。

Aはよい。Bは、最も右にある00と最も左にある11のインデックスを比較した。Cは何回曲がるかを全探索すればよい。

Dはちょっと難しい。数abに対し、g=\gcd(a,b)a'=\frac{a}{g}b'=\frac{b}{g}とおくと、ca'b'g-dg=xが得られる。よってa'b'=\frac{x/g+d}{c}gを決め打ったとき、左辺の2数は互いに素であればよいため、右辺の素因数を(指数ごと)a'b'のどちらに振り分けるか?という問題になる。さすがに毎回素因数分解していては間に合わないだろうから、素因数の種類数を2\times 10^7まで求めておくことにした。gxの約数を全探索するが、まあこれくらいなら制限時間に収まるだろう。実際収まったが、前計算に800ms使っているのでちょっとひやひやしていた。

Eはパッと見難しいが、初期値としていろんなところに1を入れたdp配列でdpすると求まる。片方の文字列の長さが0になってしまうケースは、dp遷移で排除できなさそうなので、別個に計算して引いておいた。Fは木DP。部分木に対して、その根からたどれる一番深い頂点の深さをkeyにして場合の数を数え、直径がkを超えないようにマージしていく。深さk/2以下はいくつでもマージしていいので一気に計算して、k/2より深い場合は、その深さを達成する子(これは全部試す)とそれ以外の子に分けて計算する。mod上の除算が必要になって、間に合うだろうと適当に出したらTLEしてしまった。ちゃんと左と右から累積積を持つことでAC。

Gは、そもそもクエリ形式になる前の最初の問題すら解けなかったが、本当に有名問題だったらしい。

noimi.hatenablog.com

結局、パスの端点がユニークで、パスに含まれる辺が交互に塗られていればよいはずだ。パスの端点のユニーク性については被ったら適当に繋げればよくて、hash全部の和と現在答えに足されているhashだけの和を持てば色のflipができる。パスを閉じてループにするような辺を追加するときだけ、パス全体を取り除いてしまうことにする。復元も難しいが、頂点ではなく辺に対してそれに繋がる辺番号を持たせておけばよい。微妙なミスでWAを出して原因の原因の原因を特定するのに非常に苦労したが、なんとか通った。重いのは出力を毎回flushしているから。

https://codeforces.com/contest/1499/submission/110399277

ゴミ出しをし、布団に入ってなろうを読んでいた。午前9時半就寝。

03/19(金)

午後3時、学生支援課活動支援係からの電話に気づいて起床。どうやら部員名簿にある人数と別の書類に書かれた人数に大きな隔たりがあるらしい。今現在の部員名簿を再度提出することになった。

昨日から読んでいた「奇運のファンタジア」の最新話に追いついた。

https://ncode.syosetu.com/n8357fd/

天才経営者、とか大企業に成長、とか書いてあったので、法人としてのチートみたいなことを期待して読んだのだが、個人のチートに重きを置かれていてちょっと見込み違い。ただ、丁寧なテンプレ展開で非常に心地よく読める作品だった。

そのまま午後5時半に寝落ちして、次に起きたのが午前2時だった。昼間受けた電話で、活動支援係の方に、夜のうちに書類を出しますと言っていたのだが、すでに夜中になってしまっている。慌てて作成を始める。

部員名簿は新歓期間の終了時に更新したものを作ったはずだが……とサークルのGoogle Driveを探して、12/26に作成した書類を発見した。これにはちゃんと正しい人数が記載されているように見える。この日の日記にも次のように書かれている。

今年度の新歓期間は12月の半ばまであったが、それが終了したので、サークルの名簿などに更新がある場合報告せよとのメールが来ていた。名簿を更新して提出した。

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

しかし、いざ送信済みメールを探してみると、提出のメールがない。どうやら作成だけして提出をすっかり忘れていたらしいことが分かった。これはひどい失敗だ。なぜこのようなことが起こったのかさっぱりわからないので、再発防止策も取れない。とりあえず、今年に入ってから入部してくださった2名の新入部員をさらに付け足して提出しておいた。

寝ている間に行われたyukicoderの問題を解く。A、Bはよい。Cは面倒だが、まあやればできる。Dはタグに尺取り法と見えてしまったが、これは設定でゆるふわモードにしているからで、変える気はない。E以降はsolved数が少ないので止めておくことにした。

水曜日にちょっと書いてから放置されていたbinary trieを完成させた。ほかの人のライブラリを参考に、適当に必要そうな機能を盛り込んでおいた。binary trieに限らずtrie木一般に、子のノードをポインタで持つ実装をよく見るが、Library-CheckerのSet Xor-Minではvectorとそのインデックスで持つ実装のほうが速かったので、そちらを採用した。trie木だけのシンプルなコードのためvectorのメモリ空間の再確保が行われないから速い、というだけかもしれない。

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

さらにFastIOを作った。

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

いろいろ仮定してできるだけ速くなりそうな書き方をしている。例えば、空白や改行が2つ以上連続したりすればそれだけで壊れてしまうし、数値の途中に変な文字が紛れ込んでいても気づけないかもしれない。わざわざFastIOを使うのだから、どうせオンラインジャッジ上で正しい入力のときだけ動けばよくて、それより余計な比較などをできるだけ省こうという算段だ。設計はclayのものを大いに参考にした。

布団でなろうを読む。いろいろな作品の冒頭だけ読んで投げ出すということを繰り返していた。1作、面白いと感じるものを見つけて読了した。「異世界で美少女になった俺、地球に戻れたので裏垢やってみる。」。

https://ncode.syosetu.com/n6063gu/

ABCに向けて、さすがに寝ないとまずい。午後3時半就寝。

03/20(土)

午後6時、地震で起床。頭の真上にあるエアコンを見て、これが落ちてきたらまずいな、と思ってベッドの足元のほうに避難し、布団を引っ被って揺れが収まるのを待っていた。前回の地震の際、本棚に取り付けてある突っ張り棒のゆるみに気づいて直していたおかげか、今回は特に本が落ちてきそうになることはなかった。

机の下にもぐっていると、本棚がグラグラ揺れているのに気づき、思わず押さえに行ってしまった。

週記(2021/02/08-2020/02/14) - kotatsugameの日記

宮城県の沿岸部に津波注意報が出たらしいが、おそらく自分が今住んでいる場所は沿岸部ではないだろうと考えて、そのまま二度寝した。さすがに眠すぎた。

午後7時から30分おきの目覚ましを聞きつつ、午後8時半起床。ギリギリまで寝られたので良かった。部屋の中を確認したが、モニターがずれているくらいで特に地震の影響はないようだった。

食事してABC196に参加した。全完18位だった。A、Bはよい。Cも全探索してよい。Dは、一行持つbitDPを書いたのだが、うっかり4Wくらいの計算回数になってしまってTLEした。1行の場合がまずいので、1行目だけ見なくてもよいとわかる部分を見ない3WにしてAC。Eは適当に関数合成。Fはこれ↓で、(a-b)^2を展開した。解説によれば、a xor ba(1-b)+(1-a)bと式変形できるらしい。僕の解法は2乗の項の処理がちょっと面倒。

?(任意の1文字)を含む文字列のマッチングがFFTでできるという話を覚えていたので、試した。?を0に、その他の文字をユニークな正整数に対応させて、Σ_{i-j=k}a_ib_j(a_i-b_j)^2を計算する。

週記(2020/11/30-2020/12/06) - kotatsugameの日記

コードゴルフをする。A問題は、まずbashで解いて、全完後にAWKで書くと縮むことに気づいた。そのあと、この日記を書いている間にさらにAWKで縮められていた。getlineを使う発想が出てきた試しがない。実際に書いたことがないため、どのようなときに縮むのか?という嗅覚が育っていないのだろう。B問題はsedだと思っていたがVimに負けた。7Bの解は、削除しようとしたときに何も削除しなかったらレジスタの状態が変わらないのを利用していて面白いと感じられたが、普通にdwで取れたようだ。6B。7Bの面白さに夢中になっていて気づけなかった。C問題はAWKが短いと思ったらdcに負けた。同じくdcで取り返したところ、等号付き不等号の等号が外せたらしく、再度取られた。26B。これも単純なミスで非常に悔しい。

DEFはRuby。Dは判定方法が面白い。畳が覆う2マスの番号をペアにしてリストアップしておき、そこからA個取り出し、覆うマスに重複がないか見る。これはCythonの判定方法を移植しただけ。なぜコードゴルフにおいて頑なにPython系の言語を使おうとするのか……。Eは、clampLRをリストで持つと覿面に短くなった。clampに渡すときはsplat演算子で一発だし、更新のときもLRは同じ処理なのでmap!でできる。Fは嘘bitset解法が通る間に縮めておいた。

今回は僕がやってることで、僕からすればデメリットが一切なくてただ嬉しいだけだったが、ほかの人がこれをやってるのを僕が見ると、ちょっとどころではなくモヤモヤしてしまうだろう。より一般に、八百長コードゴルフみたいなことをしたくないという僕のささやかなプライドが理由となり、今後も僕がAtCoderで作問作業に関わることはない。

布団でハーメルンを読もうとしたら素早く寝落ちした。午前8時半。

03/21(日)

午後2時、目を覚ます。寝落ちする前に読んでいたハーメルンを開いてしまい、そのままずっと読み続けていた。全体の話数の半分くらいで本編が終了し、残りは番外編という位置づけであることがタイトルからわかる。とりあえず本編終了まで流し読みしたが、求めていたものとは違った。

syosetu.org

現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」というなろうに似た作品を読みたいと思い、「財閥」というキーワードで検索して出てきた作品。実際にある架空の財閥の栄枯盛衰を描く話なのだが、物語というよりかは資料という側面が強いように感じられた。さすがにそういう設定だけ食べて生きていけるほど鍛えられてはいない……。

午後4時、さすがにもう少し寝ておかないとまずいという気持ちになったので、寝た。午後5時半から30分おきの目覚ましがかかっていて、午後7時のもので何とか起床に成功。コンビニに出かけて食事を買おうとしたが、時間帯の問題かかなり売り切れていてびっくりした。食べてしばらくするとARC115。

ARC115はギリギリ5完でパフォーマンス2628、レートは2665→2662(-3)。世知辛い。

Aから難しいが、しばらく考えていると、なんとなく__builtin_parityが異なるペアを数えればよさそうというのがわかってくる。これは頑張れば証明できそうだが、どうにも焦って頭が回らないので、提出することにした。AC。BはTakahashi's Information。Cはよくわからないが、ある数がxと決定した時にそれの倍数すべてにmax(*,x+1)を作用させたら通った。この時点で15分。

atcoder.jp

Dは難しい。45分考えてちっとも進まなかったので、Eに飛んだ。Eは、まず109要素のdp配列を考えてみると、おおよそdp<-sum(dp)-dpのような遷移をすることがわかる。Aの値によってdp配列の後ろの要素が増えたり減ったりするが、ある程度の区間は常に同じ値になる。これを区間ごとにシミュレートすればよい、ということまではすぐわかった。実はこれは一次関数が作用素の遅延セグメント木に言い換えられるようだが、コンテスト中は思いつかず、必死にstackをいじって値を合わせようと格闘していた。改めて思い返してみれば、一番最初だけsum(dp)の代わりに1を使わなければいけないことにハマっていたのだろうと思える。符号を交互に切り替えて足す操作を累積和で再現するのは最初から上手くいっていたが、左端のoff-by-oneエラーに苦しめられた。40分くらいかけて何とか合わせたら通った。残り20分。Dに戻る。

閉路の個数に着目すべきだと考えた。極小な閉路(これにはサイクル基底という用語があるようだ)の個数を使って云々、を考えていたが、全探索するコードの出力と考えている結果がどうにも合わない。もう少し単純なグラフの出力を観察してみようとしていくらか試していると、どうやら、すでに連結な頂点同士を結ぶ辺を追加すると値が2倍されるらしいということが分かってきた。いったんこれを認めることにすると、あとは森に対する答えがわかればよい。パスの長さを変えて観察していたが、ここで閃く。6頂点のパスと6頂点の木を与えてみると、どちらも出力が同じであることが分かった。木なら頂点数だけから答えがわかるようだ。どうやって答えを計算するのかも少し悩んだが、少し考えると頂点のうちいくつか選ぶ組み合わせの個数であることに気づく。ここまでわかった段階で、さかのぼって実験で確かめたいくつかの事実の確からしさというものが上昇したのを感じられた。もう時間もないので証明は一切考えずそのまま書くことにする。

UFで連結成分のサイズと全域森に含まれない辺の本数を数える。連結成分ごとに組み合わせの値を記録した数列を作って、全部を畳み込みで掛け合わせ、さらに要素を2の何乗倍かする。サンプル2が合わなくて焦ったが、偶数インデックスだけ抜き出した列を計算していたせいで出力するときのアクセス箇所がずれていたようだ。何とか修正して投げるとACした。残り1分もなかった。

残り20分で3完から5完まで駆け上ったはいいものの、レートを上げるには遅すぎたらしい。自分はDで45分間何をしていたのだろうか。こういうところで詰まるとダメなんだなあ。また、D問題は自前のUFとACLのmodint/convolutionを併用したので、oj-bundleで展開した後さらにACLをincludeパスに含めるという手間がかかってかなり焦ってしまった。こういうのも一発でできるようにしておきたいが、さておき常にACLをincludeパスに含めるとCFなどでもそのまま提出してしまいそうで怖い。oj-bundleACLも展開しようとすると、include"atcoder/*.hpp"などとhppを付けたりダブルクォーテーションで書かなければならないようで、ちょっと面倒。

ARCの直後にCF 709 div.1があったので出た。3完270位で2744→2649(-95)。これはひどい

Aは可能な日が少ない友人から一気に割り当てていったらWA。可能な日が最も多い友人について、ほかの友人が可能でない日から先に(m+1)/2日割り当てると通った。可能な友人が最も少ない日から貪欲に割り当ててもよかったようだ。Bはqueueと双方向リストでシミュレート。これも最後のほうの処理でミスして1WA。Cはセグメント木を書きそうになったが、区間クエリの右端が必ず全体の右端なので、priority_queueで書ける。値のほうを優先度にして持つpriority_queueも作っておいて、消えた要素は適宜インデックスに対するフラグを立てて読み飛ばせばよい。

Dは、3つ組(u,v,l)について、コストcの辺u->wを使って(w,v,l-c)に書き換えるという操作を何度も繰り返せばよいと考えた。当然vのほうからも縮めていく。lの大きいものから順に更新していきたいのでpriority_queueで見ていく。……ところがMLEしてしまった。priority_queueに入る要素数が多すぎるのだろうか。しばらく試しても通らなかったので、優先度書き換えできるとよいと考え、えびちゃんさんの記事からFibonacciヒープを盗んできて貼り付けてみた。今度はTLEした。本当に絶望。そのまま通らずにコンテスト終了。

rsk0315.hatenablog.com

TCB34が終了した。6位だった。1位は理論値らしい。このセットで理論値出すのはさすがにヤバい。埋められない差を感じてしまう。10問目のbinary trie+Mo's algorithmは、考えたもののTLEしたので諦めたという人がいくらか見られた。もっとちゃんとした解法があるらしい。1つだけTLで見たのは、使える魔法の区間の右端でソートして、左端についてはbinary trieで条件を満たすような魔法のインデックスの最小値を求めて比較することで判定する、というもの。これは非常に面白く感じられる。binary trieというのはつまるところ必要な箇所しか作らないセグメント木であると見れて、そのとき当然区間minクエリに答えられるし、さらに全体にxorできる性質も変わらない。

ARCのコードゴルフをした。AはPerly/1//&1がいい感じ。Bはよくわからないが、とりあえずOctaveで解いておいた。Cは1 2 2 3 3 3 3 4...という出力をする解法が天才的。Rakuでmsbを使う。Eはぽかーん懐古DPさんの解が強い。僕のコンテスト中のACコードから頑張って変形してみたが、今何イテレーション目かによって答えの符号を変えることで累積和を単純なものに落とし込めるようで、そこからさらに和の取り方を変えると、区間の両端を持たなくてよくなったり累積和がいらなくなってpopしたstackの要素を足し合わせればよくなったりする。

ICPCアジア地区横浜大会 2020 参加記

2021/03/16-2021/03/17に行われたICPCアジア地区横浜大会に出場しました。チームはAobayama_dropoutで、メンバーは碧黴さん、ゆきのんさん、僕です。

今年は新型コロナウイルスの感染拡大の影響で、オンラインでの開催となりました。それに伴い、ネット上の情報を自由に参照できたり、事前に用意したコード片を使用してもよいことになっていました。

チーム内でのコミュニケーションはSlackのみを利用し、すべてテキストベースで行いました。音声通話をしようかとの案も出ましたが、なんとなく消極的になっているうちに立ち消えていました。

コンテスト前

Aobayama_sugarstepのチーム練に便乗する形で練習していました。ありがとうございました。

1日目(03/16)

生活リズムが前にずれていて困っていました。午前2時半に目を覚まして、そこから眠れなくなって布団でゴロゴロしていたのですが、結局午前7時半に再度寝てしまったようで、次に起きたのが正午でした。なんとかセーフ。

prefixがAobayama_であるチームが2つ存在したので、チームごとの行動の際に混じったことがあったようです。が、それ以外は特に問題なく、学生証のチェックが終了しました。

開会式が終わって、practiceが始まりました。碧黴さんがA、ゆきのんさんがBを読むので、僕はCとDを読みます。どうやら昨年と全く同じ問題のようです。Cは二重階乗のオーダーで探索することを覚えていましたが、Dはあんまり覚えていなかったので、Dから解くことにしました。最短経路だけ取り出したグラフを考えたとき、ある辺について、そこを迂回するような経路が存在するか判定できれば良いです。橋の検出ライブラリを貼れば楽だったようですが、言いかえが思いつきませんでした。今回は始点からの距離を並べた列を作り、imos法で辺に対応する区間に加算して、対応する区間が2本以上の辺で覆われているかどうかで判定することにしました。一発AC。Cも適当に書いてAC。この時点でAとBも通っていたので、全完です。

practiceで速さを求めて全完しても虚しさがすごいです。そのあと、適当にWAやTLEを出してみて、何となくジャッジの挙動を確認できた気持ちになります。例えばreturn 1;でREになること、longが64bit整数であることなどは重要でした。

practiceの後に少しZoomでお話があって、今日の予定は終了です。夜は2Dセグ木のライブラリを作ったりしていましたが、午後10時くらいに寝落ちしてしまいました。

2日目(03/17)

午前3時半くらいに目を覚まします。しばらく布団でゴロゴロしていたのですが、今日は二度寝するとまずいので、起きることにしました。朝は食事した後TechFULのイベント問題を解いたりして過ごしていました。

Zoomに入る時間を間違えてギリギリになりましたが、何とか最終連絡を聞くことができて、いよいよコンテストです。

問題文:http://icpc.iisf.or.jp/past-icpc/regional2020/problems-2020.pdf

順位表:https://icpcsec.firebaseapp.com/standings/

コンテスト

C問題

碧黴さんがA、ゆきのんさんがBを読みます。僕は残りの問題を適当に開いて訳す感じで動こうかなと思ったのですが、C問題の問題名が「Short Coding」だったので、これは解くしかあるまい、としばらく時間を使って考えることにしました。

しばらく唸っていると、右手法(あるいは左手法)が使えることに気づきます。つまり、右手法を実際に再現するようなプログラムを書けば、どんな盤面でも必ずゴールできることになります。おそらく、かなり短いプログラムで再現可能で、それより短いプログラムについては全探索するというのが問題の意図なのでしょう。実際に手でいろいろ試していると、次のような5行のプログラムが完成しました。

RIGHT
IF-OPEN 5
LEFT
GOTO 2
FORWARD

サンプル出力が最大で5行であることからも、これが最短っぽいです。それ未満の行数のプログラムを全探索するコードを書いてサンプルを試してみると、出力される行数が一致していることがわかります。よさそうなので提出しましたが、WA。配列外参照していることに気づいたので直しましたが、またもやWA。コードをじっくり見ていると、右に曲がるときと左に曲がるときで方向を表す変数に足す値が逆になっていることに気づきました。そこを修正するとAC。45分でした。

CのFAはonionsの43分なので、ギリギリ負けたことになります。改めて以前のサンプルに対する出力を確認してみると、サンプル1から正しくない解を出力していることに気づきます。行数だけじゃなくてちゃんと内容にまで気を配っていれば……と後悔することしきりでした。しばらくはこれが頭にこびりついて離れなくなりました。

G問題

僕がCを解いている間にBが通っていました。Aはちょっと炎上していそうですが、あんまり触れずに次の問題に進みます。Dを読んで概要を共有しました。シンプルな問題ですが、とっかかりがつかめないので、次の問題に進むことにします。この時点ではGとHが2チームに、Jが4、5チームに解かれていたと思います。ゆきのんさんがすでにJを読んでいるので、僕はGを読むことにしました。ゆきのんさんはそのままJを書き始めていました。

Gの概要を共有してからしばらく考えていると、あるしきい値に対してそれ以下の頂点の数x、連結成分の個数aと、それより大きな頂点の数y、連結成分の個数bが与えられたとき、a+b-1<=min(x,y)が必要条件であることに気づきます。通され具合からこれが十分条件でもあると決めつけることにして、とりあえず実装します。

2021/03/18追記:解説でもこの部分の証明は飛ばされていましたが、そのとき話していた熨斗袋さんに帰納法が回るとの指摘を頂いたことを思い出しました。a+b>=3のときは、2つ以上の頂点からなる連結成分が必ず存在することがわかるので、その連結成分を適当につなげることにします。そのあと使った頂点を無視することで、不等式の両辺から1引いた問題に帰着できます。

xyを求めるのは簡単です。abを求めるのには、しきい値をずらしながら一つのUFを更新するのではうまくいきませんが、しきい値以下の頂点としきい値より大きい頂点に分けてそれぞれ計算すればうまくいきそうです。そのようにして実装してみるとサンプルが合ったので提出、AC。78分でした。この数分前にJも通っていました。

H問題

Aのコードが共有されてきました。改めて以前のやり取りを読み返してみてもどういうロジックなのかよくわからなかったので、各座標(x,y,z)について3方向の影を調べてブロックの存在判定をし、最後に条件を満たしているかチェックする、という方針に書き換えてもらうことにします。入力される文字列と座標の対応がややこしいですが、座標軸に合わせて考えることにすると、それぞれどの方向に軸が存在するか描かれた図を使うことで比較的簡単に変換の式が得られます。

書き換えてもらっている間にIを読んで概要を共有します。数え上げですがすぐにはわかりません。ゆきのんさんがHを読んでいて、そちらの概要も共有されてきました。こっちはクエリに答える問題なので、とっかかりは楽そうです。Hをしばらく考えることにします。

素因数ごとに独立に考えるのは明らかです。103以下の素数の個数を数えると168個でしたが、168本くらいならセグメント木を持ってもよさそうな気分になります。素因数の指数を小さいほうから3つ持つようなセグメント木を書けば、実際に答えにおけるその素因数の指数を計算することができそうです。定数倍が怖いですが、TLが10secもあるので多分大丈夫だろうという気持ちになりました。

残るは103以上の素数についてです。これは、区間の先頭k+1項に含まれるような素数しか候補となりえないため、それぞれチェックしてよさそうです。チェックの方法についてですが、事前に103以下の素因数を持たないようにしておいた数列に対して区間==を計算するようなセグメント木を作ってその上で二分探索すれば、ある素因数が出現する区間を求めることができるので、k+1回繰り返せば間k個を抜いたような区間の右端が求まります。

この時点でAが通っていたと思います。解けたので書くことにします。サンプルが貧弱で、103以上の素数が必要となるケースが存在しなかったので、自分で適当に作って足しました。しかし依然貧弱なままだったようで、例えば等号付き不等号の等号が抜けていたり、l+i項目を見ようとしてi項目を見てしまったりなど残念なミスで2WAを重ねました。結局147分時点でAC。

I問題

E問題の概要が共有されて、見覚えがあるという話がされていました。確かに僕も見たことがある気がします。

後からTLで知りましたが、JAG夏合宿2018day1Eらしいです。これは確か、どこか海外のICPC予選セットだったと思います。なのでAOJを探しても収録されていないわけなんですね。

Eを解こうとして、円の半径をにぶたんすれば良いと分かったのですがWA、多角形が円の半分に偏るコーナーケースにゆきのんさんが気付いたのが残り15分時点で、実装できませんでした…。

JAG夏合宿・ACPC2018 参加記 - kotatsugameの日記

角度を足して1周ぶんになるかを見ること、円の片側に多角形が寄った時の処理が難しいこと、などが思い出されました。適当に立式して二分探索すれば解けそうであることが分かったので、ゆきのんさんに任せて、自分はIに挑みます。

まず、入退室が両方記録されているIDは無視してよいです。それ以外を考えます。

制約がn<=5000なので、1次元足したdpをするのだろうなという気持ちになります。入室の際にIDがわからない人にIDを割り振ってしまうと、入室と退室でそれぞれ1つずつ情報を持たなければならない気がします。ここで、退室のときに入室まで遡って割り振ることにしてみると、情報が1つだけでよいような気がします。まだIDが割り振られていない人が室内に何人いるか、の情報を足す1次元で持つことにして、実際に書いて様子を見ます。直感的に、それ以外に必要になるような値はすべて適切な前計算と組み合わせて導出できる気がします。

dp[i][j]で、今i番目の記録を処理していて、室内にIDが割り振られていない人がj人いる場合の通り数を表すことにします。まず入室処理についてですが、これは、IDが割り振られている人が入室するか(dp[i+1][j]+=dp[i][j])、そうでない人が入室するか(dp[i+1][j+1]+=dp[i][j])の違いになります。特に係数が掛かったりはしません。

次に退室処理についてです。退室する人のIDがわかっているときは、室内にいるIDが割り振られていない人のうち1人を選んでIDを割り振ることになるため、係数にjがかかってdp[i+1][j-1]+=dp[i][j]*jとなります。IDがわからないまま退室するときは幾分複雑で、

  • 室内にいるIDが割り振られている人が退室する

現時点での室内の人数kが前計算でわかるので、dp[i][j]+=dp[i][j]*(k-j)です。

  • 室内にいるIDが割り振られていない人が退室する

室内にいるIDが割り振られていない人のうち1人を選んでIDを割り振るのは、先ほどと同じです。ただ今回は割り振るIDにも自由度があります。入退室のどちらにも記録されていなかったIDの個数のうち、現在すでに使われているIDの個数(つまり、IDが割り振られていないまま入室して、IDがわからないタイミングで退室していった人数)を求めましょう。IDが割り振られていないまま入室して、現在すでに退室していった人の人数は(これまでに入室したIDが割り振られていない人)-j人です。IDがわかるタイミングで退室するときは、必ずIDが割り振られていないまま入室した人から選ばれることがわかりますから、IDがわからないタイミングで退室していった人数は先ほどの値からさらに引いて(これまでに入室したIDが割り振られていない人)-j-(これまでに退室したIDが割り振られている人)人です。

かっこで示した値や「入退室のどちらにも記録されていなかったIDの個数」は前計算でわかるので、割り振るIDの自由度rが求まり、dp[i][j-1]+=dp[i][j]*j*rです。

これでサンプルを試すと合いました。この問題のサンプルもかなり貧弱に感じられますが、とりあえず提出してみると、AC。189分でした。

E問題

円の片側に多角形が寄っているとき微妙に変な値が出る、とのことで、ゆきのんさんのコードが共有されていました。適当に口出ししながらK問題を読みます。適当なdpを考えて実装したらサンプルが合ったので、チームメイトに何も言わずに提出したのですが、WAでした。いくつか証明をしていない性質を仮定して解いたので、仮定が間違っていたんだなあとはわかりますが、具体的にどういうケースで壊れるのかはわかりません。K問題は頑張っても通りそうにないので、E問題を通すことに集中することにしました。

コードをコピペしてきて手元で動かしていろいろやっていたら、サンプルが合ったので提出しました。するとゆきのんさんもほとんど同時に提出していたらしく、どちらもACしました。239分でした。両方通ったからよかったものの、例えば僕のコードがWAで、しかも微妙に僕のほうが早く出していた、みたいなことになったら目も当てられません。ここははっきりとコミュニケーション不足が表れました。

ゆきのんさんは誤差に苦しんで、結局acosasinに変更したらサンプルが合ったそうです。僕はacosのままでしたが通ったので、よくわかりません。Heno Worldも誤差で苦しんだという話をしていたのですが、僕自身はそういう感じがしないので、どこかの実装方針が違ったんだろうと思っています。しかし自分のコードもよく見るとEPSとEPSを10倍した値の2種類を使い分けている箇所があるので、たまたま1回目の提出で当たりを引いただけなのかもしれません。

残り

K問題を解いていました。現在の方針は、文字列の先頭にTのprefixを繋げていくdpで、繋げるときのスコア計算をZ-algorithmで行うものです。つなげる先がどのような文字列かわからない状態でスコア計算をするのはかなり怪しいですが、Tが繰り返されていると考えて大丈夫だろうと思い実装していました。しかしWAが取れないので、どうやら大丈夫ではないようです。しかしどのようなケースで落ちるのかが全然わからないため、ojでランダムケースによるテストをしてみました。すると、うまく愚直解と異なる答えが出るものが見つかりました。

bbcbbbcc
8

とりあえず、Tが繰り返されていると考えるスコア計算が実際にダメであることがわかりました。ここで、先頭に繋げるprefixの長さは広義単調増加するだろうと考え、現在どの長さのprefixを繋げたかも持つ3乗のdpを書いてみました。今度は上のケースにも通りましたが、当然TLEしてしまい、高速化をしようにもうまくいかず、そのままコンテストが終了しました。

コンテスト後

Gather Townに集まって話しながら解説を聞きました。K問題はオートマトン上でdpするらしいです。そう言われると見たことあるなあという気持ちになってしまうのですが、次見たときに解けるかどうかはちょっと怪しいです。その後YesNoを見ました。自分のチームのKへの提出が通っていないのは知っているのですが、実際Noとなる瞬間を目にすると非常に残念になります。

途中送った顔写真が公開されるフェーズがあったのですが、僕は(ほとんど故意に)送り忘れていたので、いらすとやの画像に差し変わっていました。みんな提出していないものだと予想していたのですが、かなりの人数が自分の顔面を提出していて本当にびっくりしました。

YouTubeLiveの放送が終了した後は、Gather Townが閉まるまでずっと喋っていました。途中からピクトセンスを始めたのですが、通話しながら遊ぶのは非常に楽しかったです。小学生みたいな下ネタで笑うのも楽しいです。

結果

8完10位でした。例年と単純に比較すれば良い成績であると喜ぶところですが、今年は並列可能になったり海外チームがいなかったりネット検索が可能だったりといろいろ勝手が違うので、ちょっとモヤモヤはします。とりあえず3年間順位が単調減少しているので、来年は1桁順位を取れるよう頑張りたいです。