工事中。金曜日以降一部の記述は参加記のほうに切り出される可能性があります。
03/13(月)
午後1時半起床。1時間くらいスマホを触ってからようやく布団から脱出した。
準備して今日も5h。Muscatキャンプの今日のセットは将来的にUniversal Cupでも使われるらしいので、日本チームで示し合わせて別のセットを走ることにした。中国ICPCの2021 Finalらしい。
それにしても、キャンプに参加するからと言ってインターンの定例会をお休みさせてもらったのに実際に走っているのはただのバチャとなると、少し罪悪感がある。
Dashboard - The 7th China Collegiate Programming Contest, Finals (CCPC Finals 2021) - Codeforces
書く
感想戦を終えてからはずっと先週の週記を書いていた。CF一つと5h二つが書き終わらないまま体裁だけ整え、日付が変わる直前に投稿。その後朝までかけてCFと5h一つについては書き足した。
午前6時くらいに布団に入ってからはなろうを読んでいた。三章まで読み進めたが主人公の言動があまり好きになれず放棄することに決めた。一応ここに記録しておく。
https://ncode.syosetu.com/n6938fe/
午前8時半就寝。
03/14(火)
午後2時半起床。今日のMuscatキャンプのセットも昨日と同じ理由で回避し、中国ICPCのMianyangセットを走った。
Dashboard - 2022 China Collegiate Programming Contest (CCPC) Mianyang Onsite - Codeforces
書く
感想戦の後は今日のコンテストのupsolveをしていた。しかしDが全然通らない。そのうち椅子の上で寝てしまい、少し目を覚ましたタイミングで慌てて布団に移動しもう一度寝た。日付が変わったくらいだった。
午前4時前に起床。1時間くらいかけてようやくDを通した。double型の数A
とB
を等号付きで比較する際A<B+eps
としていたのをA<=B+eps
としたら通った。B
の値が大きすぎる場合にeps
を足しても値が変わらず、等号なしの比較になってしまっていたらしい。
朝まで先週の週記を書き足していた。何とか残っていた最後の5hについても書ききり、ようやく完成。完成といっても校正は行っていない。その合間になろうで「熾天使さんは傍観者」を読了した。
https://ncode.syosetu.com/n8651ia/
面白かった。設定が好みなのはもちろん、話のテンポもよくてストーリーがスイスイ進行していく。その中でも必要なイベントや見せ場はしっかりこなしていて満足。
午前9時頃布団に入り別のなろうを読んでいた。正午ちょっと前にようやく就寝。
03/15(水)
午後2時半起床で激烈に眠い。食事していざMuscatキャンプ最終日。
今日はe-judgeというジャッジシステムを使用するらしい。コンテスト直前になってサイトへのURLが共有されたが、最初に伝えられたものが間違っていたらしくログインできずに焦っていた。問題を報告するためTelegramのアプリをインストールしたところで正しいものが再度共有されているのに気付いた。
少し遅れてコンテストを開始すると、なぜか開始より前に5問解いている状態となっていた。ペナルティの値が負になっていて面白い。運営に連絡してしばらくしたら直っていた。
kotatsugame伝説
— heno (@heno_code) 2023年3月15日
コンテストページを開いた余波だけで5完 https://t.co/YgrBCugOLG
笑っていられたのはここまで。まだ言及禁止なので詳しく書けないが凄まじいコンテストだった。自分たちは5時間で1完。これでも参加チームの中では解けているほうである。
04/18追記:参加記を書いた。
コンテスト中に解法が出た問題を通し切るため午後11時頃まで粘着し、なんとかACをもぎ取った。その後解説を読んだがあまり理解できず苦しかった。
解説pdfは実はWhatsAppというSNSのキャンプ公式チャットにしか上がっていない。SNSへのログインのために電話番号が要求されるため入っていない人もいるので、今更だがダウンロードして日本チームに配った。
日本のUniversal Cup参加者が集まるDiscordサーバにプライベートチャンネルを作ってそこにアップロードしたら、実はそのサーバでは全員管理者になっていて実質誰でも見える状態になってしまった。必要な人に行き渡ったのを確認してすぐ消した。まあUCで使う予定のないセットだけ走ったので大丈夫だろう。
日記を書いて午前6時就寝。
03/16(木)
午後4時過ぎ起床。インターンの進捗としてなんとかドキュメントの体裁を整え、午後5時から1on1に臨んだ。
進捗報告として書き足したところを説明しつつ、曖昧な点について確認しつつ修正。もっと丁寧に書いたほうが良さそうなところが残っているもののひとまず完成という感じにはなった。ちょうどこのドキュメントを使う予定の方が明日から稼働されるようなので、ギリギリだった。
来週のタスクを設定したあと、ちょっと前に書いたAPIを叩くプログラムを実用する機会があったが、このタイミングで少し機能を追加したり対処が漏れていたケースで落ちるのを修正したりの作業が発生した。結果1on1終了は少し伸び、午後7時半になった。
疲れ果ててハーメルンを1作読了。「貴方はウマれ変わったのでトレセン学園で無双を希望しています。」。5話完結のほぼ短編だった。
「貴方は中央トレセン学園から追放されることを希望しています。」作者の別作品。面白そうだと気軽に読んだがラストがちょっと曇り気味で、身構えていなかったためそこそこ衝撃を受けた。面白かったことには変わらない。5話ではしっかり他人から見た主人公も描写されており健康に良い。
食事して午後9時頃からTCB56を解き始めた。今回は大変だった。
https://techful-programming.com/user/event/4032
1問目、2問目はよい。3問目は格子点を全探索すればよいことに気付くのに一瞬かかった。4問目は4方向を見るループを要求されて面倒。
5問目。文字ごとにそれが書かれたマスを数え降順に並べることでが復元できる。文字の置換は常に直前に置換されたマスの一部だけが対象になっているので、ある文字で一度置換されたマスを集めるためには、その文字より後ろに並んだ文字が書かれたマスを全部集めてくればよい。そうして集めたマスから座標の平均を求めることで、置換の際にどのマスがだったかわかる。そこから方向を特定して出力する。
このアルゴリズム自体はすぐ思い付けたのに、焦ってひたすらバグらせ盛大に時間をかけた。詰めずに書き始めたらソート順や出力順を間違えているし、座標の平均を取る対象が間違っているし、typoもいくつかあるし大変だった。17分かけたため-8pt。
6問目はマスを白にする場合と黒にする場合を両方試す。白にする場合はそこを避けるように貪欲に置いて置ききれるかチェックする。黒にする場合はとりあえず貪欲に置いてみて、どれだけずらせるかも加味し目的のマスを黒にできるか判定する。実際には1マス以上ずらせれば必ず可能だったが気づいていなかった。変数の初期化ミスで1WA、時間も16分半かかっており-13pt。
7問目は答えとなるを二分探索する。隕石から避難するためのマスとして考える必要があるのは私有地の「端」のみであり、具体的にはから上下左右にマス離れたマス、あるいはそのようなマスが存在しなければグリッドの端に行ってさらに別の方向に可能な限り向かったマスである。つまり候補が高々8マスしかないため受けるダメージの計算が十分高速に行える。
8問目はマスの情報をデータ構造のインデックスに置き、適切に係数を掛けながらの取得を頑張る。左上マスがの長方形領域に対して総和を取得できれば十分。係数はとなる区間、定数の区間、となる区間に分かれるので、それぞれデータ構造を用意して対応した。
9問目は難しかった。のケースから解いた。にしか存在しない要素、にしか存在しない要素、との両方に存在する要素の数をそれぞれ固定するとが計算できる。どの要素を選ぶかは単にcombinationで、との数え上げはあらかじめ包除原理でやっておけばよい。。
この考察を元にのケースを解いた。こちらは積の和典型で、に寄与する2要素を回重複あり・順番込みで選び、その要素たちを選べるような、を数え上げるのを目標にする。これまで選んだことのある要素を上の3種類に分類し、それぞれカウントしながらdpすることができる。ここまでの計算量はで、ただし遷移の定数倍がかなり重い。
その後、を数え上げる。使える要素が大量にあるうち個の要素を必ず含む必要があるという条件になるが、これもその「必ず含む要素」について包除を行うことで計算できる。41分かかって-20pt。
10問目は……苦行。ただし実装はそこそこ上手かったと思う。1列ずつ右に追加してチョコを作ることにし、これを状態間の遷移だと捉え行列累乗で高速化する。つまりやるべきことは状態の列挙と遷移の列挙である。
直前に追加した列のうちどのマスとどのマスが連結か、どのマスが空きマスか、どの空きマスがチョコの外に繋がっているか、また穴を作り終わったか・チョコを切り出し終わったかが分かれば遷移できる。最後の要素については適当に0、1、2で表しておく。それ以外の要素については列の各マスに番号を振っておくことにした。
空きマスもそうでないマスも連結成分として高々3種類を区別できればいいから、それぞれ0、1、2と3、4、5を割り振ることにする。同じ数字なら同じ連結成分に属していることになる。また特にチョコの外に繋がっている空きマスには番号0を割り当てることにした。
以上で個の整数が状態になる。列挙の際は、何もない状態だけからスタートして、一つ右に追加する列通りを全探索し新しい状態が見つかったらまた同様に計算するということを繰り返した。こうすると遷移についても同時に求まるため都合が良い。
最後に残ったのが、ある状態に1列追加して次の状態を求める関数の実装について。ここはUFを使い新しい列の各マスと連結成分に対する番号をマージするとまあまあ簡単だった。UFの連結成分をそれぞれ見て、追加した列のマスを含むなら番号を適切に割り当て、そうでないなら穴やチョコを作り終わったと判断してその情報を適切に更新、あるいは条件を満たさないと判定する。
でも380状態になり、行列累乗は十分間に合いそう。しかしTLEだった。行列を生配列に持ち、さらに行列累乗してから最初の状態を掛けるのではなく同時に行う(つまりをではなくと計算する)ことにしたら通った。69分1ペナで-58pt。
3時間弱かかり日付が変わるくらいの時間になってしまった。ここから明日のセミナーの準備を開始し4時間ほどかけて終わらせた。クラトフスキの定理の強さに感動。グラフのある性質がその部分グラフに遺伝するなら、やの細分という具体的な例についてのみ確かめることで、平面グラフでないもの一般がその性質を持つと証明できてしまう。
シャワーを浴びて布団に入ったあと、なぜかしばらくTLを眺めるのが止められなかった。午前5時半就寝。
03/17(金)
起きたら午前9時45分だった。ただでさえ遅刻しそうなのに布団で少しダラダラしていたため、午前10時を回ってから家を出ることになってしまった。
午前中は同級生のセミナー。今日はなんだかずっと詰まっていて補題一つの証明も終わらなかった。自分でも教科書を読んでみたがどこに困難があるのかいまいちわからない。詰まっている部分の周辺について自分の理解を説明しても納得行かなそうだったので、自分がなにか陥穽に気づいていないだけかもしれない。
昼食を摂りつつ正午からはオンラインで海外の方のセミナーを聞いた。博士課程の方の関係者らしい。自分たちがどのくらいのレベルにあるのかわからないようでかなり丁寧に説明していただけたが、今日扱っていたのがだったため十分理解できたものと思う。
環、特にからグラフを作るという話だった。が素数だと完全グラフになってしまうし、そうでなくてもかなり密に辺があって、それほど面白そうに見えない。また今のところ作ったグラフを調べて得られるような環の性質もないらしく、何がしたかったのか伝わらなかったという感想。
午後2時前からは自分の発表。そこそこ駆け足で説明したら1時間半ほどで終わった。発表について特に反省すべき点もないと考えている。
午後4時頃帰宅し、1時間半ほどかけて荷物をまとめオンサイトに向けて出発した。午後6時過ぎ発車の新幹線に乗ることにしたが東京まで2時間半ほどかかるらしく、着いてから夕食を摂る時間がなさそうだったので駅弁を食べた。
— こたつがめ (@kotatsugame_t) 2023年3月17日
新幹線の車内では日記を書いていた。ただし最後の20分ほどは寝ていたはず。今日はかなり混み合っていて、自由席車両では立ち乗りしている人も見られた。
東京駅に到着。乗り換えに手間取りつつ渋谷駅から池尻大橋駅と辿って、少し歩いたところが今日の宿だった。伝えていた時間から30分ほど遅れてしまったが無事チェックインできた。
部屋に入ったのが午後9時40分頃。即座にPCを開いてyukicoder 381に出た。
yukicoder contest 381 - yukicoder
電車に乗っている間にコンテストが開始してしまったので後ろの問題から読んでいた。その流れで今日は逆順に解いた。
Fは結構面白い。まず良い印の付け方に関する性質を考える。1行目は自由に付けて良い。2行目からは1マス決めると残りは一意になるが、具体的にどういう配置になるか調べてみると、なんと1行目と全く同じか完全に逆のどちらかになっていた。
つまり良い印の付け方は次のように定式化できる:0または1からなる数列とに対し、「マスに印が付いている」とした良い印の付け方が一対一対応する。
マスを、タイブレークを適当に決めて整数の降順に並べる。自分より前に並んだマスに印が付けられず、かつ自分に印が付けられるような、の選び方を数えると良い。やの同じ値になるべき要素をUFでマージしていくことで、その連結成分数として自由度が求まる。と決まっていることに注意。
E。最初の順列で転倒数に寄与しないペアは操作後も寄与しない。そうでないものについてそれぞれ操作後も寄与するような分割方法を数えれば転倒数の総和が求まる。
自分は寄与しないものを数えて全体から引いた。(ただし)について、との間に仕切りがなければ一緒にソートされて寄与しなくなる。そのような場合の数はで、適当にバラしてBITで記録すればに対してを一括で計算できる。
Dは頂点1を経由することで距離2での移動が必ず可能なので、距離1で移動できるペアを数える問題になる。つまりを求めればよい。ここでを取り除いているのは、だからといってペアを数えてはいけないからである。
あらかじめ107まで求めることができる。なので、最初とした列を用意し、素数を列挙しつつなる全てに対しと更新すればよい。最後に累積和を取る。計算量はエラトステネスの篩と同じ。
Cは最初すべての要素をにした後一番小さい要素から順に、と引き上げていき、毎回答えを更新する。最小値を固定しているとも思える。
Bはとりあえずの条件だけ満たし、後から余った0を先頭に近いところに、1を末尾に近いところに入れる。の条件を満たすには、先頭の文字を0と1両方試した上で回直前の文字と異なる文字を置くとよい。この過程で足りなくなったらアウト。の場合に余った0や1を入れる場所がなくてもアウト。
A。うしっぽい数の大小関係がの辞書順で決まっている。が36通りあるのでとわかり、を適当に求めた上で実際に整数を作ればよい。作ると言っても直接出力するだけだが。
コンテスト開始から1時間弱で全完、スコアは低めで16位。
シャワーを浴びて日記を書き、日付が変わってすぐ就寝した。
03/18(土)
午前5時前にうっかり目を覚ましてしまい、しばらく眠れず1時間ほど輾転反側していた。
午前7時15分に目覚ましで起床。同じホテルに止まっているへのkと一緒に朝食を摂った。一人2個までのパンとフリードリンクということで少し物足りない。時間帯の問題か全然人がいなかった。
— こたつがめ (@kotatsugame_t) 2023年3月17日
午前8時半頃出発し歩いて会場に向かった。開場を少し待ち、ほぼ一番乗りで入場。席に荷物を置いた後開会式までずっと懇親していた。Universal CupやMuscatキャンプでチームを組んでいただいたかっつさん・ぷらさんとお会いできて感激。
午前10時、開会式。10分弱chokudaiさんの話を聞いた後ヌルっとコンテストが開始した。
Toyota Programming Contest 2023 Spring Final - AtCoder
Aを開いたが解けない。ここで無理に粘着すると後々響くことが分かっていたので、同じ300点が付けられていたこともありBに進んだ。
Bはクイズの直後にクイズに回答するときとその逆でそれぞれ期待値の式を立て、比較してどちらを先に行うのがよいか調べるのが典型テク。整理すると見事にとが分離できての降順に行うのがよいと分かった。
ここまで式変形するのはちゃんと順序になっていることを確認するためであり、実際の比較関数ではを分母に持ってくる一歩手前の式を使えばゼロ除算に気を遣う必要がなくなる。REを出して腰を抜かしたが、よく見ると配列サイズが足りていなかった。
Aに戻らずCに進んだ。との最上位bitが等しいことは分かったがそれ以降特に進まなかったので実験してみたところ、条件を満たすは数をbitの集合と見たとき必ずを満たしていることが分かった。つまりとなるものだけ調べれば十分で、を全探索すればよい。
ようやくAに戻ってきた。長方形の高さと幅を固定すると、それ以外を固定しなくても内部の値の総和がきれいな形になるようだ。左上のマスを含むの長方形について、内部の値の総和はとなる。ここから1マス右にずらすと総和は増え、1マス下にずらすと増える。
つまり右にずらす回数を、下にずらす回数をとすると、総和がだけ増える。ここで、である。特にであることから、をで割った商とあまりによっての候補が高々一つに定まる。これだけチェックすればよい。
Dは実装が複雑な方針を取ってしまったようだがかなりスムーズに通せた。を固定してを動かすと、順列の初項にはが一度ずつ現れる。よって求める順列の初項はとして決まり、これを達成するはと一対一対応する。そこで以降はのみ考える。
2項目を考えてみたところ、その値は初項にをで足したものだと分かった。つまりを適切にソートすることでこれも決まる。同じ値となるが複数存在するなら、その中でをソートすればよい。以下同様。
このようなソートにはSuffix Arrayが使える。その順序の上での候補は常に区間となっており、それを管理しながらどんどん先の項を求めていった。単なる大小比較ではなく前の項に足してをした上での比較だからちょっとどころではなく面倒だが、二分探索を丁寧に行うことで対処できた。
1時間ちょっとでDまで通り、この時点では12位だったはず。その後順当にEに進んだものの30分くらい経っても何も見えなかったので別の問題に行くことにした。Fは面白そうだしやるべきことが明確。Gは1時間でFAが出ているが、木dpっぽいことを考えてみても全くうまくいかない。よってFを考えることにし、残り時間をそれに費やした。
部分列を数え上げるdpでは、次の文字を決めたら最も近い位置から取ることで重複を除いている。よってどのような文字ならそう取れるかを考えるのが、Fを解く際にやるべきことだと考えた。まず操作によって完全に削除できる文字列を求めた。これは実験してみるとすぐ/A(AA|BA|BB)*B/
だと分かる。
そこからいろいろ場合分けすることで、文字A
なら最も近い位置から取ってよいことが分かった。しかしB
の場合、特にBB
と続くときそうはいかないようだ。この辺りを考えているうちに時間切れとなった。正確にはここで考察を打ち切り、適当に条件をエスパーして実装を始めたが、サンプルが合わず終わった。
昼食は叙々苑の焼肉弁当だった。信じられないくらい美味しかった。冷え切っていても肉が柔らかいのはさすがと言うほかない。
— こたつがめ (@kotatsugame_t) 2023年3月18日
昼食後は同じ席でchokudaiさんによるトヨタ自動車でのアルゴリズム・ヒューリスティクス活用の事例を聞いた後、サブホールに移動してrngさんからの挑戦状を観戦した。ステージでは日本の自由色コーダーほぼ全員が一堂に会しており錚々たる顔ぶれであった。
この挑戦状についてrngさんは「いつもの」と表現されていたが、自分の記憶が正しければ前回は2018年のCODE FESTIVALだったはず。自分ですら2回目なのだから、これが「いつもの」になる人は少ないだろうなあと思いながら観ていた。内容的には自由色の圧倒的考察スピードを目の当たりにできて得難い体験となった。
一応どんなものがあったか記録しておきたい。7問あって、最初の4問はすぬけさがし・RGB値当て・自由色コーダーのユーザー名とカラーコードの対応当て・コンテストトップページの間違い探しと特に競プロチックではなかった。
5問目は今日のコンテストのA問題で、、としたときカウントされる長方形を一つ求めよというもの。yutaka1999さんが左上33・右下67という解をかなり高速に見つけておられた。と気づいて感動。AのFAは伊達ではなかった。
6問目はF問題にちなんでいて、空文字列にAB
、BA
、BB
のどれかを挿入することを繰り返して得られる長さ10の文字列を数え上げよというものだった。出来上がる文字列の条件が「A
の文字数がB
の文字数以下」になるのでが答えらしい。
7問目はE問題由来。からへ、両方の座標を正の数増やすことを繰り返してたどり着く方法を数え上げる問題だった。ここで座標が座標以下という条件はない。軸ごとにどの座標を踏むか考えるとが答えとなる。
片方の軸では「踏まない座標」を数えることにすると座標と座標から合わせて6個選ぶ問題になり、この値がと等しいことが言える。最近見た考え方なのでスッと取り出せてよかった。解答された方がどちらで計算されたのかは知らない。
といったところで全員参加のイベントはひとまず終了。これから表彰式まではサブホールでトークセッションや座談会が行われる一方、メインホールの一部が雑談コーナーとして開放されており、自分はそちらでずっと最近の5hでご一緒した人々と喋っていた。
話題は最近のMuscatキャンプや今日のE問題。夏の学生選手権もMulti-Universities Camp直後だったのでその話ばかりしていた記憶がある。話していたメンバーも大して変わらない。
E問題はの場合答えがカタラン数になることが実験から分かっていて、Rubikunさんによって格子状の経路数え上げとE問題のvalidな移動の間の対応が与えられ納得できた。
この時間自分からは一切動かなかったが、何人かの方に話しかけて頂けた。kotatsugame Tシャツは話題にこそできるが視認性はいまいちだから、恐らく自分の顔を知っている人経由で会いに来てくださったのだろう。
kotatsugame Tシャツを着ている kotatsugame さんに会いました! pic.twitter.com/fmQrZFT8PY
— てあ(競プロ) (@cpg_tea) 2023年3月18日
2時間ほどしこたま会話して、表彰式。4完時点で賞金圏外だったので特に希望もなかったがE以降が完全に焼け野原だったので思ったより惜しかったなという印象。Aを爆速で通せてBでペナを出さなければ10位くらいに滑り込めたのかもしれない。ただし実現可能性は低い。
懇親会はコロナ禍以前とほとんど変わらない形式の立食パーティーだった。一応食べ物を取るときには手袋を装着することになっていたのだろうか。自分は何も食べずずっと懇親していたのでよくわからない。山盛りのフルーツの写真だけ撮っておいた。
— こたつがめ (@kotatsugame_t) 2023年3月18日
この時間は自分からウロウロしていた。会話した中で特に覚えている方が二人いる。一人は高校の後輩だった。うっすら覚えている高校時代の印象では特にプログラミングしているとは思っていなかったが、大学生になってから始めたらしい。声をかけられてかなりびっくりした。
もう一人は、以前自分があーだこーだーでお薦めした本を読んでくださった方。他にお薦めの本はないですかと聞かれ、できれば短めとのことから複数巻前提のラノベを挙げるわけにもいかず、窮した結果読書記録を眺めて「11文字の檻」を見つけた。
青崎有吾氏の著作も好んで買うから、これをお薦めとして挙げることに抵抗感はない。自分は裏染天馬シリーズが好みだがこれには肌に合わない要素があったとのことだ。しかしその要素は他作品ではほぼ現れなかったはずだから、この作品も問題なく読んでいただけるものと思う。
この前のあーだこーだーで面白かった本として「儚い羊たちの祝宴」をお薦めしたら、読んでくださった方がいらっしゃったらしい。
週記(2022/05/23-2022/05/29) - kotatsugameの日記
午後7時半くらいに会場を出て、へのkと共にホテルに帰ってきた。午後8時からUniversal Cup 8回目。思ったよりギリギリで、せっかくコンビニに寄って夕食を買ったのに食べる暇がなかった。
ぞいぞいしてきた pic.twitter.com/7nXLfTMcDQ
— こたつがめ (@kotatsugame_t) 2023年3月18日
2022-2023 ICPC Central Europe Regional Contest - Dashboard - Contest - QOJ.ac
今日はSloveniaセット。通話を繋ぐためヘッドセットを持ってきてやる気は十分だったが、さすがに体がついてこず途中で意識を飛ばしそうになっていた。
書く
シャワーを浴び、TLを眺めながらゆったり食事して午前4時過ぎ就寝。
03/19(日)
午前9時過ぎ起床。かなり眠たい。