rime + testlib で部分点の制約チェックをする

競プロ

TL;DR

validator で validator.group() を呼び出すことで subtask 名を取得できる。

はじめに

皆さんは先日行われた UTPC2024 に参加しましたか？ 参加していない方は問題を見ましたか？ とてもおもしろい問題ばかりなので、まだ問題を解いていない方は、今すぐこのページを閉じて UTPC2024 の問題を解きましょう。

私は UTPC2024 の運営の 1 人でした。 その中で、部分点のある問題のテスターを担当していたのですが、テストケースが部分点の制約を満たしているかどうかをチェックする方法がわからず困っていました。

UTPC では問題の準備に rime、validator に testlib を利用しています。 比較的メジャーな構成だと思うのですが、意外とネット上には明確な解決策が見当たりませんでした。 そこで、私が見つけた解決法をここに残しておこうと思います。

解説

解決策は冒頭に書いたとおりです。ここでは、どのようにしてこの方法にたどり着いたかを説明します。

rime は C++ で記述された validator を利用する場合、各 Subtask とテストケースの組に対して、<validator の実行ファイル> --group <Subtask名>のようにして validator を実行し、テストケースの中身を標準入力として与えます。 したがって、validator 内でどのような制約判定を行えばよいかは、引数として与えられた Subtask 名を取得すれば良いわけです。

testlib のコードをよく読むと、引数 --group で指定された文字列は validator.group() で取得できることがわかります。 よって、validator.group() で現在の Subtask を判定し、その内容に応じて制約チェックを切り替えればよいです。

終わりに

testlib のまとまったドキュメントが欲しい……。

ICPC 2023 Asia Yokohama Regional 参加記

競プロ ICPC

ICPC 2023 Asia Yokohama Regional にチームDELIAIRとして参加して8位でした！

順位表

大会前

対策としては，基本的に毎週 Universal Cup でチーム練習をしていました．あとは個人で精進をしていました．

実装で失敗した去年の反省から，実装の割り振りを工夫しました． 実装が速くて正確なtokusakuraiが８割，torisasamiが1.5割，僕が0.5割程度を担当する形です．

大会１日目

チームのメンバーと一緒に会場近くのお店でラーメンを食べてから会場に向かいました． 去年と同じ会場だったこともあり少し懐かしさを感じながら会場入りしました．

リハーサルでは，パソコンのセットアップ担当のtokusakuraiが真面目に話を聞いていなかったせいでCLionの立ち上げに苦戦していました． 問題は去年と同じだったのでそれ以外は特に問題なくこなすことができました． 余った時間はtokusakuraiがタイピングの練習をしていて僕はお菓子を食べることくらいしかすることがありませんでした． 海外チームの問題を解くスピードが速かったので結構強いチームなのではないかという話をしていました．

チーム紹介ではtokusakuraiが英語を暗記しきていて偉かったです．

解散後は中華街で食事をしました． tokusakuraiが問題を解くフローについて提案してきました． 僕が考察の大まかな指針を出して，torisasamiが詰めてtokusakuraiに伝えて，実装をすべてtokusakuraiに任せるというものです． 僕はそれほどうまく行かないと思ったのですが，本番は実際に結構この通りに動くことになりました．

それからお風呂に入って，ABCの問題を軽く見てからホテルで11時過ぎに就寝しました．

午前1時くらいに目が覚めてしまって，午前4時くらいまで寝付けませんした． 他の２人も途中で起きていたようですが午前2時以降はちゃんと寝ていたと思います．

大会2日目

コンテスト前

午前７時半くらいに起こされましたが，8時くらいまで布団から出られませんでした．

会場に近いホテルだったので会場には余裕で到着することができました． コンテスト前でしたがあまり緊張はしていませんでした．

コンテスト中

僕がA, torisasamiがBを見たあとに２人で残りを真ん中の方から手分けしてみていくことにしました． 以下時系列です．

A: 問題文が読みやすく，DPをやるだけのようにみえました．始点が任意であることだけを丁寧に確認してGへ行きました．

G: ぱっと見よくわかりませんでした．少し考えて複雑なFPSとかだとお手上げだなと思いながら次へ行きました．

F: 少し考えるとすぐに性質が見えたので，解けたことを報告しておきました．

E: 制約からbitDPかと考えましたが特に考察は進みませんでした．

D: 構文解析かと期待したがそうではありませんでした．制約も小さいので区間DPを適当にやるだけだと考えて解けた報告をしました．

C: 数え上げ多いな〜と思いながら少し考えましたが，わりと難しそうに思いました．

M: torisasamiが読めてなかったので読みました．雑に三分探索、二分探索でいけるとおもいましたが，円の探索に手数がかかることを見逃していました．合流してきたtorisasamiと解法を詰め直して考察を終えました．途中でAをtokusakuraiに説明しました．

そのあとは，torisasamiと問題の概要や考察を共有しました． FやDをtokusakuraiに説明することもしました．

Dでペナが出てしまったのですが，これは2桁以上の整数を使えるとして問題を解いていたからでした．僕がBNFをよく見ていなかったことが原因だったので申し訳なかったです．

途中で順位表を見てEやG，Hが解かれているのを確認したのですが強いチームだけだったので信用できませんでした．

Eの O(N^2 2^N) 解法をtorisasamiが思いついて更に O(N 2^N)に落とせないか相談しました． 詰まってGを見たところ，DPをしたときの状態がそれほど多くないことに気がつきました．

Eについては定数倍も軽いので O(N^2 2^N)でも通るのではないかと主張しておいて，僕は他の問題を考えることにしました． 最終的には O(N 2^N)に落としたらしくて偉いです．

Hを考えたのですが特に進捗を生めなかったところ，tokusakuraiにEを説明したtorisasamiが燃やす埋めるを提案して一気に進みました． 具体的なコスト関数を２人で計算して劣モジュラであることを確認したあと，詳細の詰めはtorisasamiに任せることにしました．

この時点で I, J は通されてたのですが J のほうがマシに見えたので J を考えていきました． 合流したtorisasamiとパスグラフの場合を考えていると貪欲が思い浮かびました． 木の場合に正当性の証明ができなかったのですが，反例の構築もできませんでした． HLD+遅延セグ木を使えば実装できることはすぐわかりました． 実装が重いので他に方法がないかも考えましたが他に思いつきませんでした． そのまま重めの未証明解法を，Hを解き終えたtokusakuraiに投げることになりました． しかし２ペナが出てしまいこれは嘘解法ではないかということになりました．

そこから３人でIを考えていきました． 行列で書いてみたり，双対を取ってみたりしたのですが全く解法が見えませんでした． 詰まっていたのでJに戻ったところ正当性の証明ができた気がしました． そこで実装を確認したところ実装が間違っていたことがわかり，Jを正解することができました．

そのあとは Iを考えたのですがよく分からず，時間ギリギリでtorisasamiが適当な解法を実装し始めたので僕はCを考えてみました． 結局 J は通すことはできませんでした．

Cはコンテスト終了後も考察をしてnが奇数のとき以外は方針が見えたのですがそこからがよくわかりませんでした．

コンテスト後

結果は８位でした． opt社から企業賞をいただきました．ありがとうございます． 去年よりよい結果ではあるものの，SPJやThe Raspberry Candiesに負けてしまい悔しかったです． 全体としてそこまで悪くはなかったと思うのですが，他のチームが強かったです．

Speed Star の4時間全完はさすがでした． WFに行くにはこのチームに勝たなければならなかったのですが，圧倒的実力の差を感じます．

Iは解法がとてもきれいで驚きました． ２種類の液体を混ぜたときに作ることが可能な溶液の濃度と量をもっと丁寧に考えることができていれば解けたかもしれません． チームの中では自分が一番得意そうな解法なだけあって解けなかったことがとても悔しいです．

懇親会ではコミュ障なりに少し交流を広げられたので良かったです．

最後に

３年間チームを組んでくれたtokusakurai, torisasamiにはとても感謝しています． ３人とも今年でICPCは引退になります． 僕があまり実力を伸ばせなかったことは申し訳なかったですが，このチームで最後までICPCに挑戦することができてよかったです．

最後になりましたが，このような楽しい大会を開いてくださったICPCの事務局やスポンサーなど運営に関わった方々，懇親してくれた参加者の方々にはとても感謝しています。とても楽しかったですありがとうございました！！！！！

2023/11/29追記：本番で使っていたライブラリを公開しました。ご自由にお使いください。

競技プログラミングは大学生活の役に立つか？

結論：立った（立たないところもあった）

（本日はエイプリルフールです。そのためこの記事の中には嘘や誇張や矛盾が混じっていたり混じっていなかったりします。）

役に立ったところ

1. プログラミング能力

プログラムが書けると有利な場面は大学生活において結構あります。 プログラミング能力の獲得をメインターゲットに据えた授業で楽ができるのはもちろん、プログラミング能力の獲得をメインターゲットに据えていない授業でもプログラミングをしなければならない場面はあります。 そのような授業においてプログラミングという非本質的な作業に割くリソースが少ないことはよりよい授業理解につながるでしょう。 また、プログラミングが必要のない授業でも簡単なデータの分析や数値計算を素早く行えるのは便利な能力です。 比較的自由なテーマのレポートではそのような能力を活かして内容を組み立てることでオリジナリティが出やすくなることが期待できます。

2. 数学力

競技プログラミングに取り組む中で、それなりに高度な数学に触れてそれを問題の中で実践していくということはよくあります。 そのなかで着実に数学力は伸びていたようです。 （僕の所属していた学科では数学の要求度が低かったこともあり）おかげで（卒業に関わる単位において*1）数学で苦労したことはほとんどありませんでした。

3. その他

まずは競技プログラミングを通して友人ができたことはよかったと思います。 僕の所属していた学科は学生の仲がとても悪かったので友人の存在はとても貴重でした。

また、僕の場合は卒論のテーマは競技プログラミングの問題が元ネタになっています。 僕の卒論の単位は競技プログラミングのおかげ得ることができたといっても過言ではないでしょう。

役に立たなかったところ*2

1. 毎週末がつぶれる

AtCoderのコンテストは多くの場合土日の夜21時からです。 毎週コンテストに出ようとすると人生に支障が出たりそうでもなかったりします。

2. 生活習慣が壊れる

これは上記よりさらに深刻です。 Codeforcesのような海外のコンテストにしっかり参加しようとすると、深夜は活発に活動できる体を作らなければなりません。 午前の授業は出にくくなります。 それに普通に健康に悪いです。

3. 算数パズル能力

「役に立ったところ」では競技プログラミングを通して得た能力が役に立つところを紹介しましたが算数パズル能力は1ミリも役に立ちませんでした。 それどころか、この手のパズルに対する難易度評価が壊れるので気を付けないと無意識に他人を煽る発言をしてしまいます。（2敗）

4. 趣味として紹介して引かれる

え？家でパソコンをカタカタするのそんなに好きなの？（笑）

*1:他学部の某授業では泣かされましたが

*2:またの名を悪口コーナー

卒論で出会った latex のあれこれ

卒論の執筆を通して出会った latex の機能やお作法、トラブルについて備忘録もかねて記しておきます。 適宜更新します。

環境

Windows 11の WSL 2 上に TexLive2022 をインストールして使用しています。 texファイルから pdf の生成には platex + dvipdfmx を利用しています。

hyperref を使うと全体的に文書がずれる

hyperref パッケージは生成されるpdf にリンクを付けるものです。 このパッケージを使用すると全体的に文書が右下にずれた pdf が生成されるようになりました。 pxjahyper パッケージを利用することで解決しました。 pxjahyper パッケージは hyperref パッケージを日本語に対応させるパッケージです。 そもそも pxjahyper パッケージを利用しないと pdf の目次が文字化けするので日本語の文書で hyperref パッケージを使用する場合は pxjahyper パッケージは必須です。

pxjahyper を利用すると生成される pdf が白紙になる

pxjahyper は pdf にリンクを付けるパッケージである hyperref を日本語対応させるためのパッケージです。 pxjahyper を使ったところコンパイルしても白紙しか生成されなくなってしまいました。 原因は次のリンクに示してあるように pxjahyper パッケージのバグのようです。

okumuralab.org

対策はいろいろあるようですが今回は nomag オプションを付けることで対応しました。

pdf 中のリンクの囲みをなくしたい

hyperref パッケージのデフォルトの設定では下の写真のように pdf 中のリンクは赤枠で囲われます。

この設定が個人的に気に入らなかったので枠を消す方法を探しましたが見つかりませんでした。 結局以下のようにプリアンブルに書いて枠の色を白色にしました。

\hypersetup{ % ハイパーリンクの設定
  pdfborder={0 0 0},
}

コード中に数式を書きたい

lstlisting 環境で論文中にプログラムを載せたのですが、そのプログラムの中に数式を入れたくなりました。 プリアンブルのlstset中にescapechar=\@と書くことで@をエスケープ文字に指定し、@で囲まれた場所に数式環境を導入することでできました。 例えば

\begin{lstlisting}
#include <stdio.h>

int main() {
    double e = 0.0;
    double frac = 1.0;
    // @$e = \sum_{n = 0}^\infty{\frac{1}{n!}}$を利用しネイピア数を計算する@
    // @$n$を99で打ち切る@
    for (int n = 1; n <= 100; n++) {
        e += 1.0 / frac;
        frac *= n;
    }
    printf("%f\n", e);
}
\end{lstlisting}

と書くと、次のようになります。

数式中にいい感じに空白を作りたい

数式をの位置をそろえていい感じの見た目にするのに悪戦苦闘していたところ zkou君 のアドベントカレンダーの記事が出て、\phantomというコマンドを知りました。 とても助けられました。 qiita.com

数式中の文字列には\textitを使う

数式中の変数として長さが2文字以上の変数名を使いたくなることがあると思います。 そのときに変数名をそのまま数式環境中に書くと、変数中の文字はそれぞれ独立した変数名として扱われてしまいます。 （たとえばabcと書くとaとbとcの掛け算として扱われるということです） \textitで囲むと囲んだ文字全体で1つの変数として扱ってくれます。 小さな違いですが以下の写真のように囲まなかったほうは文字の間に微妙な空白が開いてしまうことがわかると思います。 毎回囲むのは面倒なのでマクロを活用するとよいと思います。

左がtextitで囲まなかったとき、右がtextitで囲んだとき

synctexファイルが生成されない

synctex は tex ファイルと pdf ファイルの間で対応する位置を教えてくれる便利な機能です。 使用しようとしたところコンパイル時に synctex ファイルが生成されず困りました。 原因はコンパイルオプションをつける位置を間違えていたことでした。 具体的にはplatex <ファイル名> -synctex=1ではなくplatex -synctex=1 <ファイル名>とすべきでした。

ICPC2022 Asia Yokohama Regional 参加記

ICPC 競プロ

ICPC2022 Asia Yokohama Regional に tokusakurai、torisasami とチーム DELIAIR で出場して12位でした！

順位表

前日まで

みんな卒論が忙しくてあんまり練習できていませんでした。 特に僕は卒論が絶賛炎上中で直前1週間くらいはあまり競プロができませんでした。(チームメイトの2人にはマジで申し訳ない)

写経用の記述量少なめライブラリは整備はしてチームで整備していました。チームのパソコン担当(諸説あり)なのでリポジトリの設定とかをがんばりました。

作戦としてはtokusakuraiの実装速度が高いのでほとんど実装を任せて行こうということになりました。

1日目

少し道に迷わないか心配でしたが無事会場に到着することができました。 registration からいきなり英語で焦りました。 会場は寒いと聞いていたのですが思ったよりも暖ったです。 コーチを引き受けていただいたさかなさんにご挨拶ができたのでよかったです．

チーム紹介の冊子を開くと"?"が大量にのっているチームがあってなんだと思ったら自分のチームですが チーム紹介には◼️と◻️でQRコードを書いたのですがフォントの問題？で全部"？"で表示されて悲しかったです。 来年はフォントの情報も教えていただけると……

リハーサルではCを書いて、そこそこの速度で通せたので少し安心しました。 モニターは2日目に動かしてはいけないので今日のうちに位置の調整をしてくださいというアナウンスがあったのですがそこでtorisasami がモニターを全部ひっくり返したらいいんじゃないかと言い出したのがおもしろかったです。

解散になったあとは中華を食べました。とても美味しくて満足したのでこのまま帰っていい気分になりました。(いいえ) ホテルで一泊しました。不眠がちなのでちゃんと寝られるか心配でしたがしっかり寝られてよかったです。

2日目

6時半に起きました。 会場に着いたところでホテルにぬいぐるみを忘れたことに気がついて悲しかったです。

コンテスト中

以下大体時系列順です。（結構記憶があやふやなので記憶違いのところがあるかもしれません）

tokusakurai がテンプレートの写経、他2人が問題文を読む担当でスタートしました。AとBは簡単でtokusakuraiに解法を伝えてやってもらいました。

後ろから見ていったのですが難しそうだったり実装がきつそうな問題ばかりで困りました。AB通した時点で順位表を見ても他の問題は解かれていませんでした。

いろいろな問題を眺めているとFが通されていたのでtorisasamiとtokusakuraiがFの相談をしてなんか通していました。(すげー)

その間にGが解けそうに見えたのでtokusakuraiに投げたら嘘解法でした。(ごめん) でもなんか解けそうと主張していたらtokusakuraiが上手いこと修正してくれて通してくれました。（天才）

torisasamiがEの解法がわかったらしいのでGの実装の間にEの解法を聞くと嘘でした。 いろいろ整理して2Dセグ木使えばできるよね～ってなっていたら、必要な分だけBIT作ればいいことに気が付きました。 これもtokusakuraiに投げたら少し時間がかかりましたが通してくれました。

Dもコインをどれを動かすかを全探索して適当ハッシュ取ればいけるみたいなことを主張しました。 これが地獄の始まりでした。 他が解けてなかったのでtokusakuraiに考察をさせるために僕が実装に回ったのですが実装が非常に難解で回転したあとの位置関係の管理が難しく、書けたはいいのですがサンプルが全く会いませんでした。 結局1時間半くらいかけてもダメだったので、別解法を思いついたtorisasamiにパスしました。 ですが、それも嘘であることが残り10分で判明してそのままコンテストは終了しました。

コンテスト終了後

凍結した順位表でtonosamaが8完していて驚きました。 最終結果でも Time Manipulators,と tonosama は一つ頭がとびぬけていて格の違いを実感しました。 2人しかいないはずの Give us sociability に負けてしまったのは悔しかったです。

表彰式が終わったあとはいろいろな人と話しました。 とはいっても東大のチームとばかり交流してしまったのはよくなかったかもしれません。 なんとかコミュ力の方を......。 ともかく楽しくてよかったです。

反省

振り返ると本番中ほとんどチームの力になれなかったのは非常に悔しいです。 来年も同じチームで出れそうなのでそれまでなんとか力をつけれたらと思います。 目標としてはまずは予選突破になりそうです。（国内予選だったら今回の順位だと落ちるので......）

最後に

最後になってしまいましたがチームを組んでくれた2人、コーチを引き受けてくれたさかなさん、そしてICPCのスポンサー、事務局など運営に関わった方々および参加者の方々にはとても感謝しています。 とても楽しかったです。 ありがとうございました！！！

ICPC2022国内予選参加記

競プロ ICPC

ICPC2022国内予選に torisasami、tokusakurai とチーム DELIAIR として出場して7位（学内4位）を取ることができました！ 正式発表はまだですが何もなければ予選突破です！！！ 僕個人としては ICPC 3回目の出場で初めて予選突破をすることができたのでとても嬉しいです！

正式に予選突破が決まりました。また他の2人の参加記はこちら tokusakurai、torisasami (2022/07/15追記)

順位表

予選前日まで

4年生になってから少し忙しいことが多くチーム練の頻度は減っていました。 今年は東大から強いチームがたくさん出るようで不安だったのですが、模擬国内はそこそこの順位を取ることができて少し安心しました。

僕が構文解析を毎回担当していたのですが2年連続出題されていることもあり、構文解析の書き方を2人と共有しました。

直前の土日に、本番はチームでどこかに集まってはどうかという話になって、指導教官に相談したところ大学の教室を借りることに成功したので*1チームで集まって参加することになりました。 対面で練習をしたことがなかったのでこれが吉と出るか凶とでるか読めませんでしたが、より円滑にコミュニケーションがとれたので結果的にはよかったと感じています

本番開始まで

1時間くらい前には全員集まることができて、院試の話をしたり、他のチームを今から闇討ちするにはどうすれば良いか考えたり、誰がどこを担当するかを決めたりしました。 相談の結果 A が僕、B がtokusakurai、C 以降を torisasami が見ていくことになりました。

僕と torisasami が蟻本を忘れてしまったのですが tokusakurai だけしっかり持ってきていました。*2

個人的には去年より落ち着いていて良い状態で本番に入ることができたと思っています。

本番中

↓問題 icpc.iisf.or.jp

A は見た感じ簡単そうでしたが模擬国内で1ペナを出した前科があるので慎重にいきました。 端っこは考えなくてよく$v_i \neq v_{i+1}$なので特にコーナーケースはなさそうです。 少し入力でバグらせてしまいましたが無事正解することができました。

torisasami が C の実装を始めているようだったので D 以降を見ていくことになりました。 D が数え上げ、E が構築、Fが構文解析を含む最適化でしたが問題を読んでいる内に C を通してしまったようでした。 数え上げなら torisasami の方が得意なはずと考えて D を押しつけて自分は E に取り組むことにしました。

tokusakurai が B で悲鳴を上げていたのでデバッグのフォローに入ろうとしたらなぜか gdb が tokusakurai の PC に入っておらずキレそうになりました。 コードを送ってもらって自分の手元で gdb を走らせて無事バグを発見することができ B を AC しました。

少しして E がわかった気がしたので実装を始め、並行して手が空いた tokusakurai に E の構築成功か判定するコードを書いてもらいました。

tokusakurai は torisasami と D に取り組み、気がついたら通していました*3。

torisasami は F に行って、 tokusakurai には E の解法を聞いてもらいました。 すると tokusakurai が穴を発見してくれて解法を修正することができました。感謝。 最終的には解法は以下の通りです。

  1. 帰還可能な行/列の最初と最後をそれぞれ1と0にする*4。
  2. 帰還可能な行/列の残りの交差点は + と - の市松模様で埋める。
  3. 帰還可能な行/列それぞれについてできるだけ + が前に来るよう貪欲に埋めていく。ここで失敗するならこれは構築不能。
  4. 残りのマスは乱択する。

完全に証明した訳ではなかったですが、帰還可能な行/列だけを考えればこれで構築可能であること、残りも解空間が大きいので乱択で大体大丈夫であること、確実に構築不能なものははじけているのでコーナーケースがあっても恐らく個別に処理できることからこの解法で押し通しました。 結果的に特にコーナーケースもなく正解することができました*5。 順位表を確認するとかなり良い位置に付けていて安心しました。

F は tokusakurai と torisasami で相談して解法が見えているようだったので僕は G, H を見ていきました。 最近永続データ構造を勉強して H がその応用でできそうに見えたのでしばらく考えましたがよくわかりませんでした。

G も幾何だしよくわからないしで、F でバグが出ているようなので F のフォローに入りました。 愚直を書いてないみたいだったので、とりあえず僕が書いていったのですがバグを出してしまい苦しんでいる間に3ペナを出しながらも正解してしまいました。（悲しいね）

6完時点で残り10分くらいで、さすがに今からGHをやるのは厳しいのでお祈りタイムに突入しました。 順位表を見る限り6完は少ないものの5完はそこそこ出ており、自分のチームはペナを結構付けてしまったので心配でした。 コンテストが終了してドキドキで順位表をリロードすると6完のチームはほとんど増えておらず見事7位に入ったことが確認できました。（やったね） tonosama が全完していてびっくりしました。（すげー）

問題の担当（諸事情により一部画像を加工しています）

本番後

本番後は勝ったのでサイゼで豪遊しました*6。 サイゼリヤのメニューとしては高かったですがプロシュートがとてもおいしかったです。 デザートを食べ逃したのでまた行きたいです。 サイゼリヤといえば間違い探しですが最後の一個の間違いを結局見つけられることができず悔しかったです。

近くで東大でICPCに出た人々が何人も集まっているようだったので、サイゼリヤを出た後に合流しました。 最後に会ったのが約3年前の非競プロerの友達がいて驚きました。 他にもサークルの後輩が2人もいてびっくりしました。 noimi 君や SPJ、The Raspberry Candies、seguramu の皆さんと交流することができて楽しかったです。 ずっと競い合っていて、大学も同じなのに会うのが初めてなのは不思議な気分でした。

反省

個人的な心残りとしては最後1時間以上を何もできずに終っているところです。 Gの考察は後でじっくりやってみると（たぶん）できたのでこのあたりの選択を間違えたかなと思っています。

また、僕は他人と解法の相談するのが苦手で1人で突っ走りがちです。 今回も E で始めにちゃんと tokusakurai と解法の共有ができていればもっと速く E を正解できたのかなと思っています。 これから練習していきたいですね。

最後に

最後になりましたが、一緒にチームを組んでくれた2人、コーチを引き受けてくれた enjapma さん、教室の貸し出しの許可していただいた指導教官、審判団のみなさん、その他大会運営に関わるすべての方々には感謝を申し上げたいと思います。

時間が無くて参加記の執筆ができませんでしたが模擬国内の運営をしていただいたICPC OB/OG の会のみなさんにもこの場で感謝を申し上げたいと思います。

World Final を目指すのはかなり厳しい戦いになると思いますが、アジア大会に向けて精進していくので応援よろしくお願いします......！*7

*1:競プロに理解がある研究室最高！

*2:結局使いませんでしたが

*3:なんか畳み込みとか統治分割とか言っていましたが難しく考えすぎていたみたいです

*4:初めの解法では0にするのを忘れていました

*5:これは運がよかったと思います

*6:負けても豪遊するつもりでした

*7:卒論！

Alien DP をざっくり理解する

競プロ

Alien DP という名前は Twitter でたまに見かけますが、その詳しい内容を調べようとしてもなかなか大変だったので備忘録もかねてここに書いておきます。

Alien DP は ABC で出題されており、その解説で詳しい説明がなされているのでネタバレをされてもよい方はそちらも参照すると良いでしょう。

数理的な詳しい解説は Monge グラフ上の $d$-辺最短路長を計算するアルゴリズム | Kyopro Encyclopedia of Algorithms になされているので、本記事では正当性の証明などは避けて直感的にどのようなアルゴリズムであるかを理解することを目標とします。

Alien DPで解ける問題

Alien DPは次のようなことができるアルゴリズムです。

x = 0, 1, 2,\dots, Nとする。 f(x)が下に凸である。つまり任意の x\le N-2に対して f(x+1) - f(x) \ge f(x+2) - f(x+1)が成立するとする。 もし任意の定数 cに対して \min_{x = 0, 1, 2,\dots, N}{(f(x) - cx)}が \Theta(\alpha)で計算できるなら 任意の k = 0, 1, 2,\dots, Nに対して f(k)を \Theta(\alpha\log max(f(x+1) - f(x)))で計算できる。

f(k)より \min_{x = 0, 1, 2,\dots, N}{(f(x) - cx)}を高速に計算できる場面がぱっと思いつかないかもしれません。 例えば、長さ Nの配列に対し、そのうち k個の要素を使った最適化をするために dp[i][j] = \{i番目までにj個の要素を使ったときの最適値\}とするようなdpをしたいがそのままでは \Theta(N^2)で間に合わないときが考えられます。*1

アルゴリズム

\min_{x = 0, 1, 2,\dots, N}{(f(x) - cx)}を求める操作は y = f(x)のグラフと傾き cの直線が接するときの接点を求める操作に対応します。 これは傾き cの直線の式を y = cx + bとおいて、 y = f(x)との交点をもつようにしながら bを最小化していると考えるとよいです。

この接点の x座標は cに対して単調増加なので、接点が (k, f(k))に来るような cの値を二分探索すればよいです。 接点が cの右か左かは cを少しずらして計算することで判定することが可能です。

注意すべきこと

下の図のように y=f(x)のグラフと直線の交点は1点とならない場合があります。 そのため二分探索の分岐条件を考えるときは気をつけなければなりません。

更新履歴

2022/05/30 @noshi91さんからのご指摘を受け一部修正しました

*1:このように多くの場面ではdpによってこれをなしているのでAlien "dp"ですね