ICPC のチーム戦略について
この記事は Competitive Programming Advent Calendar 2015 - Adventar の1日目の記事です。
はじめに
私 (JAPLJ) は今年の 5 月にモロッコで開催された ACM-ICPC の世界大会で（世界大会出場は 2 回までのルールにより）現役選手を引退となったので、ICPC についてなにかを書いておこうと思いました。
ICPC といえば特筆すべきルールはやはり 3 人で 1 台の PC を使うチーム戦というところで、これまでにも様々なチーム戦略に関する記事が書かれています：
- ICPCに向けたUECodersの戦略 - とどの日記
- ~shiokawaのICPCに向けたチーム練習、コンテスト直前の準備について - しおしおたのブログ
- ICPC のチーム体制について - (iwi) ｛ 反省します - TopCoder部
（少し探して見つけたものと覚えていたものを順不同に挙げただけなので他にも探せばあるかもしれません）
そういうわけでチーム戦略についての記事を書こうと思いますが、一般的な話をしても仕方がない（というより iwi さんの記事がたいへん役に立ちます）ので、自分の経験に基づいたチーム戦の話をしたいと思います。つまり、特殊な例についての記録ということになるので、これがそのまま他のチームの戦略に役立つことはあまりなさそうですが、一部でも参考になれば幸いです。
対象
この記事で対象になるチームは以下の条件を満たしているようなチームです。
- チームメンバーにりんごさん (rng_58) がいる。
おっと、りんごさんも既に現役選手を引退となったので、対象チームがなくなってしまいました。ここまで読んで頂いてありがとうございました。明日の記事は 1_000_000_007 さんで「悪問の具体的事例とどうすればその問題をよりよくできるか」です。楽しみですね。
というわけにもいかないので、粛々と続きを書きます。
チーム構成
ここからは基本的にモロッコへ行った際のチームをもとにします。
- rng_58 (りんごさん)
チームの司令塔です。問題の概要をいち早く把握し、迅速に解法を導き、それら解法の複雑さや現在の順位表をもとにどの問題から手をつけるべきかを判断し、適切なコーダーに仕事を割り振ります。
- semiexp (準急)
コーダー 1 です。圧倒的なデータ構造力とタイピング速度、自身も TopCoder の target である強みを活かして、序盤の簡単な問題・データ構造を活用する問題・複雑な DP の問題などを担当することが多くありました。
- japlj
コーダー 2 です。TopCoder のレーティング等では上 2 人に遠く及ばないところがあるので、その分を練習量でカバーし、幾何・探索・複雑な実装を要する問題を多く担当しました。
チーム戦略
とにかく、実際のコンテストでどういう戦略をとるかについて書きます。
開始時
計算用紙を 1 枚使って、現状の記録を行います。10問のコンテスト (A問題からJ問題まで) の場合は、まず大きく A から J までのアルファベットを紙に書きます。
コンテスト中は、問題の簡単な分野や内容を表す語句、既に担当コーダーが決まった場合はその名前 (うちの場合は s か j)、解き終えた場合にはそのアルファベットに大きく丸を書いていきます。この問題はどういう解法で時間がかかる、この問題をまずやって次はこれ、などといった相談はこの紙を使って行います。
最序盤
ICPC において最序盤の問題選択は非常に重要です。最初の 1 問を解くまでに余計な時間を 5 分かけてしまうと、その後解く全ての問題に +5 分ぶんのペナルティがかかることになってしまい、これは無視できない量です。特に World Finals のように問題の並び順と難易度に関係がない場合、簡単な問題を迅速に探しだす必要があります。
タイピング速度のある準急にテンプレートの準備などを行ってもらっている間、急いで問題文を読んでいきます。ここでは明らかに幾何のような図がある問題や問題文が長すぎる問題は一旦放っておいて、短くて単純そうなものを直感的に選んで読んでいきます（この辺の選択は経験がモノを言う場面でもあります）。準急が一通りの準備を終えた段階で、簡単な問題を渡すことができればベストです。
また、りんごさんは問題文の短いもの、数学の要素が強そうなものを優先して読みます。数学の問題は解法は難しくとも実装が容易であることが少なくなく、またりんごさんは数学の問題が非常に得意なので最序盤にこういった問題を通すことも多くありました。
序盤
開幕が落ち着いたら、序盤の比較的容易な問題を片付ける作業に入ります。ここをいかに滞り無く行えるかがかなり大切です。
この段階では、基本的に semiexp, japlj のどちらか片方が PC 前で実装を行い、もう片方がまだ読めてない問題文を読んで概要（とすぐに分かれば解法）をりんごさんに伝えていきます。りんごさんは自分で読んだり受け取ったりした問題概要から、次にどの問題をやるべきかを判断します。このあたりではまだ問題が比較的容易なためコーダーがどちらでも大差なく、また効率の観点からいっても同じコーダーが連続しないようにします。
あまりに簡単な問題という場合を除いて、りんごさんが問題を担当コーダーに任せるときには「何分ぐらいかかりそうですか？」という質問をします。これに正確に答えるのは非常に難しいですが、5 分や 10 分ぐらいの単位で大まかな値を申告します。解法がわかっている複数の問題のうちどれを優先して解くかを考えるときに、同じコーダーが連続しないことに加え、この申告時間の短い方を優先することになります。（この申告が間違っていることももちろん往々にしてありますが、申告より短く終わった場合はそれでよし、申告より長くかかった場合はその時点で戦略を考えなおして交代するなりの処置をとります）
中盤
だいたい全問題の概要がわかり、容易な問題が片付いたあたりです。コンテストの難易度にもよりますが、この時点で開始から 1〜2 時間程度、解いた問題数が 5〜6 問であることが多かったと思います。
このあたりに来ると、コンテスト終了時の順位表の推測が行えます。「この問題はまずどこのチームも解かない」「上位の間ではこれを解けるかどうかが重要になる」といったことから、「あとはこの 4 問にこういう順で挑戦して時間内に全て解ければベストで、5 位以内には入れる」のようにコンテスト終了までの大まかな見通しを立てます。
semiexp, japlj はそれぞれ担当する（わりと重めの）問題があってそれに取り組むという状態になっています。りんごさんは、難しい数学の問題があってそれに取りかかっているという状態になると良いですが、問題セットによってはこの時点ですでに暇になっている（残った問題はとても解けるものではない or コーダーが考えるべきことしか残っていない）ことも多くなります。
終盤
コンテストの残りが 1〜2 時間ほどになってくると、WA が出てしまってとれないといった問題も出てきます（中盤までにこういう問題を出すとかなりまずい）。このときデバッグに印刷は積極的に行いますが、コーダー交代は比較的慎重に行います。printf デバッグ等明らかに PC を使ったほうがデバッグが捗ること、コーダーの交代は頻発するとそれによる時間のロスも無視できなくなってくることが理由です。
手元で WA が出るケースを探して、見つけたら printf デバッグ等の結果も含めて全部を印刷し、それについて吟味している間はコーダーを交代する、といったケースが多かったように思います。手元でどうしたも WA になるケースが見つからずどうしようもない（もはやソースとにらめっこするしかなく、PC を使うメリットがない）と判断した場合もコーダーを交代します。
コンテスト後
コンテストが終わったあとは反省会を行います。
まず全問題を振り返って、それぞれについて吟味します。このとき、コーダーはもう一方のコーダーが担当した問題を（概要も含めて）全く知らない状態が良いです。これはりんごさんの采配と、その後のコーダーによる実装が詰まらず上手くいったということを意味しているためです。逆にバグが出て詰まってしまい印刷などをした場合、デバッグに協力するためにもう一方のコーダーにも問題概要と解法が伝えられる、といったことが起きてしまいます。
また、全問題のアルファベットを大きく書いた紙を使って全体の流れを確認します。解く問題の選択ミスはなかったか、順番は正しかったかの確認や、実装に申告より長い時間がかかってしまった問題についての検討などを行います。
練習について
個人練習
このチームの戦略は、それぞれの人がどういった能力を発揮するかが分かりやすくなっています。たとえばりんごさんは 5 時間の間、PC には全く触れません。一方僕や準急はふつうのコンテストと比べ、問題の解法を考える時間というのが圧倒的に少なく、ひたすらコーディングに偏った時間を過ごすことになります。
そのため個人としての練習もわかりやすく、たとえば僕は AOJ-ICPC の問題を全て（当時）埋めるなどの練習をしていました。
チーム練習
このチームの戦略はやはり明快で、コンテスト中の各人の動きはかなり分かりやすくなっています。そのためチーム練習に特別に時間を割くことはほとんどありませんでした（JAG の開催する模擬大会に出る程度）。
しかしモロッコに行ったときだけはチーム練習を行いました。序盤の戦略で「容易な問題をいかに滞り無く片付けられるかが重要」と言いましたが、りんごさんの分析により「序盤で詰まったコンテストでは最終的な成績も悪く、序盤がスムーズにいった場合最終的な成績もよい」ことがわかったためです（これはあくまでもこのチームの話です）。
確かに、これまでに調子の良かったコンテストを振り返ると、序盤の容易な問題を片付けた段階で 2 位に 2, 3 完の差をつけて 1 位ということが少なくありませんでした。一方、調子の悪かったコンテストでは、序盤にそこまで他チームをぶっちぎることが出来ていなかったように思われます。
そこで、モロッコにて「5時間コンテストの最初の1時間だけ練習」を行いました。これはその名の通り、5時間コンテストの過去問をひとつ選んできてそれで練習をするのですが、開始1時間が経った時点で終了とします。もちろん、戦略としては 5 時間コンテストに挑むつもりで行います。
つまり、直前になって 5 時間フルで使って難しい問題に取り組んだところで、いまからそういった実力を底上げするのには無理がある。だったら、コンテストに重要な序盤の動きだけを集中的に鍛えればよいし、そういった立ち回りなら直前からでも改善できる、という発想です。5 時間の練習で得られる成果を 1 時間で得ようという最高の練習です。効率 5 倍、スゴイ！
東京工業大学プログラミングコンテスト2015 P問題 - Dancing stars on regular expession!
Looksery Cup 2015 B. Looksery Party
リンク: http://codeforces.com/contest/549/problem/B
こういうのどういう思考過程で思いついたのかメモしておこう。
問題
人が n 人いて、それぞれ互いの電話番号を知っていたり知っていなかったりする。
パーティに人を呼ぶと、呼ばれた人は知っている電話番号すべてに電話をかける。自分の電話番号は知っているので自分にもかける。
数列 a1, a2, ..., an が与えられる。パーティに呼ぶ人をうまく選んで、人 i が電話をかけられた回数が ai にならないようにできるか。できる場合は呼ぶ人の集合を具体的にひとつ求めよ。
思考
（最初、「自分の電話番号は知っているので自分にもかける」ことを読み落とす）
結局、行列 P とベクトル a があって Px と a がどの要素も異なるような x ∈ {0, 1}^n があるかを判定する問題。でもこんなの解けるはずがない。
（問題文を読み直して「自分の電話番号は知っているので自分にもかける」ことを知る）
あからさまに怪しいのでこれの意味について考える。
人 i が電話をかけられた回数が ai に一致してしまったら、人 i を呼ぶ/呼ばないをひっくり返せば、少なくとも人 i については大丈夫。
でも他の人がやばくなるかもしれない。その時は他の人もひっくり返せばいいかと思いきや、また人 i がだめになってしまって、循環するかもしれない。
落ち着いて自明なパターンから考える。誰も呼ばないと ai = 0 の人がやばい。そういう人がいたら、とりあえず呼ぶとする（他の人を呼ぶ手もあるけど、あからさまに怪しい制約を活かすとしたら、その人自身を呼ぶことにするのがよさそう）。
その結果やばい人が現れたら、その人も呼ぶことにする。とやっていくとどうなるか？いやさっきと同じで循環するのでは？
よく考えると循環はしない。最初誰も呼んでいなくてやばい人がいたらその人を呼ぶ、をやると電話された回数は増えるだけで減らない。だから、一度やばくなって呼ばれた人がまたやばくなることはない。
GCJ 2015 Round 2 C - Bilingual
グラフと睨めっこしなくてもわりと機械的に作れますという話。
なので、「準備」までは分かっていて最小カットにしたいところまでは前提。
コンテスト中はすぐ作れたので機械的にできると思ってたけど記事を書いてみるとそうでもない気がしてきた。
問題
文章（単語の列）が N 個ある。各文章は英語かフランス語のどちらかである。
英語の文章に出てくる単語はすべて英語の単語で、フランス語の文章に出てくる単語はフランス語の単語である。
文章 1, 2 がそれぞれ英語、フランス語であることが分かっている。
文章 3 … N は分からないが、英語とフランス語で共通する単語の個数を最小にするように文章の言語を決めるとき、その最小値はいくらか。
準備
面倒なので英語、フランス語を E, F と書く。N 個の文章を S_1, S_2, ..., S_N と書く。S_1 = E, S_2 = F で、S_3 … S_N は E, F のどちらか。
入力に出てくる単語 w について、その単語がどの文章に出てきたかを考える。
- 文章 1, 2 の両方に出てくるなら、どうやっても E, F 共通の語（どうでもいいやつ）
- 文章 1 (E) に出てくるが文章 2 (F) に出ないなら、S_3 から S_N のうち w を含むような文章の中に F があれば共通の語（E, F が逆の場合も同じ）
- 文章 1, 2 の両方に出てこないなら、S_3 から S_N のうち w を含むような文章の中に E, F が両方あれば共通の語
やることは、S_3 から S_N までを E のグループと F のグループに分ける。文章の部分集合がいくつかあって、それぞれに対して条件がある。部分集合 A について
1. A が E グループの文章を含めば +1
2. A が F グループの文章を含めば +1
3. A が両グループの文章を含めば +1
のいずれかの形で条件が決まる。
グラフの作り方
※以下では E, F をそれぞれフローの source と sink の意味でも使います。
重要なこと
容量無限の辺は
- a が E なら b も E
- b が F なら a も F
を意味する（切ってしまうとカットが無限になる）。
E を含めば +1
たとえば a, b, c のうち誰かが E なら +1 というコストをつけたいときは
- a, b, c のうち誰かが E なら必ず E になる点(☆)を作って
- ☆から F に容量 1 の辺を張る
☆の作り方は「重要なこと」を使うと簡単。
F を含めば +1 も同じようにできる。
両方含めば +1
文章の部分集合が空でないから E か F のどちらか片方は少なくともあるので
- E を含めば +1
- F を含めば +1
の両方をやって、答から 1 を引く。
CodeFestival 2014 上海 コンテスト感想
CodeFestival 2014 上海のコンテストは僕 (JAPLJ) ときゅうり (kyuridenamida) で writer/tester をしていました。
全体的には、セット前半は
- 落ち着く、焦らない
- 気づく
- しっかり実装する
あたりが試される感じで、セット後半はこれといった難問こそないものの、どの問題もそこそこの手応えがあるという感じを目指していました。
2 人で 3 時間 10 問のセットを準備する (しかも参加者は皆かなりの熟練者) ということでかなり大変ではありましたが、その分思い入れも強いセットになったので、ここで各問題について振り返ってみます。(解説をするわけではありません、オフィシャルな解説がそのうち出るはず？もう出てる？)
僕の書いた writer/tester 解も載せます。テンプレを略しているので謎の関数が出てきますが in() は整数入力、chmax(a, b) は a = max(a, b) で chmin も同様です。ライブラリとかも略。
続きを読む競技プログラマのための DP 入門
この記事は Competitive Programming Advent Calendar 2014 - PARTAKE の 13 日目の記事です。
はじめに
プログラミングコンテストの問題の題材として DDR (DanceDanceRevolution) が出題されることは少なくありません *1。しかし、活動時間の全てをオンラインジャッジにつぎ込む生活では、DDR を想像することができず、問題の理解に困ってしまうこともあるでしょう。一分一秒を争うこの世界では、致命傷となりかねません。本記事は、そのような状況への対策として執筆されています。*2
問題
あるゲームには図 1 のような 8 つの矢印パネルがついた台があり、図 2 のような譜面が流れてきます。このゲームの遊び方は単純で、矢印が判定ｴｧﾘｱに重なるﾀｧｰｲﾐﾝｸﾞでﾊﾟｧｰﾉｩを踏む *3 というルールです。
※4 つのパネル（←、↓、↑、→ を 1 セット）を用いるプレースタイルを SP (Single Play) と言い、今回のように 8 つのパネル (上下左右 2 セット) を用いるプレースタイルを DP (Double Play) と言います。この記事はこれがやりたかっただけです、ここまで読んで頂いてありがとうございました。明日の記事は uwitenpen さんで「CodeRunnerの裏側」です。楽しみですね。
DDR では同時踏みやフリーズアロー（長押し）といった要素もありますが、簡単のためとりあえず考えないことにします。
それぞれの矢印を右足か左足で踏むわけですが、譜面が与えられたときに、どの矢印をどちらの足で踏むことにすれば最も楽に踏めるでしょうか？という問題を考えます。
もちろん「最も楽」の定義がわからない以上、この問題には答えようがないわけですが、以下ではこの「最も楽」の定義を色々と考えてみて、その上でこの問題を解くことを考えます。
「状態」と「遷移」
まずは分かりやすい「最も楽」の指標として次のようなものを考えます。
- 足を動かすときには、距離が長いほど疲れる。
- 足を動かすときには、速さが大きいほど疲れる。
- そこで、足を動かすたびにその距離×速さだけの疲れがたまることにして、最も疲れない踏み方を目指す。
単純な方法として「各矢印について右足で踏むか左足で踏むかをすべて試す」というやり方が考えられますが、これが無駄であることは直感的にもわかると思います。
「100 個目の矢印を踏む足を決めるときに、10 個目とか 20 個目の矢印をどっちの足で踏んだかなんて関係ないのでは？」と感じるのは自然です。この考え方をもう少し進めると
- 100 個目の矢印を踏む足を決めるときに考えないといけないのは、99 個目の矢印を踏んだときに左足と右足がどこのパネルの上にあるかである。
と言えます。ここからが重要なのですが、この考えを逆に
- 99 個目の矢印を踏んだときに左足と右上がどこのパネルの上にあるかさえ分かっていれば、99 個目以前の矢印をどう踏んだかには関係なく 100 個目の矢印を踏む足を決めることができる。
と言ってしまえれば、効率のよい解法への道筋が見えてきます。少し一般的に言うと、「ほげほげさえ分かっていれば、それ以前の詳しいことが分からなくても、その後の選択に何も影響がない」という考え方です。この「ほげほげ」がいわば「状態」を表すのですが、「状態」は今後に影響を及ぼす最小限の要素だけ覚えておけば良いということが大切です。今回の問題の場合「状態」は「ある矢印を踏んだ後に、それぞれの足がどのパネルの上にあるか」です。
dp[k][left][right] を「k 個目の矢印を踏んだ後に、左足が left、右足が right の場所にある」という状態に至るまでの最小の疲れ として、状態間の関係、つまり遷移を考えます。k+1 個目の矢印が pos という場所に流れてくる場合
# 左足を動かして k+1 個目の矢印を踏む場合、その直前に左足があった場所 (left) を全部見て、一番良いものを選ぶ
dp[k+1][pos][right] = min { dp[k][left][right] + 疲れ(left → pos) }
# 右足を動かすときも同様
dp[k+1][left][pos] = min { dp[k][left][right] + 疲れ(right → pos) }
という漸化式が立ちます。あとは k が小さい方からこの式に従って計算を進めていけば問題を解くことができます。この解法のポイントは
- 「それさえ分かっていれば、それ以外の要素はその後の選択に影響を及ぼさない」という最小限の「状態」を見出す
- 「ある状態へ至るまでの最小コスト」を考え、状態間の関係 (ある状態から別の状態へうつる遷移) から漸化式を立てる
でした。
「状態」の拡張
前節で単純な「疲れ」による最適な踏み方の定義をしました。しかし、単に距離や速さによって踏み方の良さを定めるのには限界があります。図 3 のような譜面を考えましょう。
これは「アフロ踏み」と呼ばれる典型的なステップのひとつです。これはどのように踏むのが最適と言えるでしょうか？すこし考えてみましょう。
この配置の踏み方にはいろいろと考えられますが、距離や速さを優先するなら次のような踏み方になるかと思います。
こうすれば左足も右足も、最も近い 2 パネル間の移動だけで済んでいるので、前節の指標であればかなり良いと言えそうです。
しかし、この踏み方では同じ足を連続して使うことが多い点に注意してください。一般に同じ足を連続して動かしてパネルを踏むことをスライドといい、距離や体勢を考えると有用なことも多いですが、同じ足を連続して使うことにより大きな負荷がかかるのはもちろん、動かしていない方の足にも体重が大きくかかり負担となります。そこで、次のような踏み方を考えましょう。
このような踏み方をすると左右の足を交互に使うことができます。
さて、それでは左右に交互に踏むことが最適なのか？というと必ずしもそうではありません。スライドを使った方が足の移動距離が短くなることは多いですし、たとえば先ほどの「アフロ踏み」で交互に踏んだ図 5 を見ると、途中 (丸印を付けた箇所) で身体が横向きになってしまうことがわかります (実際に図 5 に従ってステップを踏んでみましょう)。
「スライド」を多用するのが得意という人もいれば、スライドは苦手なので交互踏みを優先するという人もいるわけです。そういったことも考えた上で、個人の得手不得手も考慮してそれぞれに合った最適な踏み方を導き出すにはどうすればよいでしょうか？
この問題の先ほどと比べて難しいところは、踏み方の良さを考えるにあたって 2 つの評価軸 (スライドの回数と足の移動距離) があるという点に尽きます。このせいで、ある状態へ至るための最良コストを決定することができません。スライドが多くても足の移動距離を節約したい人もいれば、交互に踏めるところはできるだけ交互に踏むという人もいるからです。
今回は状態を拡張することで乗り切ります。これまで状態は「k 個目の矢印を踏んだ後、それぞれの足が置かれている場所」で表現していましたが、これを「k 個目の矢印を踏むまでにスライドを使った回数が s 回で、k 個目の矢印を踏んだ後にそれぞれの足が置かれている場所」とします。つまり、本来評価値であったはずの値 (スライドの回数) を状態に組み込んでしまいます。こうすると、改めて考える評価値は先ほどと同じ移動距離に関するもののみとなり、同じようにして問題を解くことができます。
これができれば、スライドの得意な人にはスライドを多く使った状態へ至るための最適な踏み方を、苦手な人にはスライドをあまり使わない状態へ至るための最適な踏み方を、といった風に個人差を考慮した踏み方を計算することができます。
このように、評価軸が 2 つ以上あるときに、いくつかの評価値を状態に入れてしまうという方法は多くの (動的計画法を用いる) 問題で使うことができます。
奥深き DP の世界
この節は元の問題から少し離れて発展的なトピックです。
図 6 に示す 2 つの譜面パターンを見てみましょう。このように左から右（あるいは逆）に渡り歩くような譜面を「渡り」と言います。
図 7 のようにどちらの足で踏むかを決めてみると、わりと自然と両方とも交互に踏むことができるのが分かると思います。
この 2 つのパターンはどちらも交互に踏めている (スライドが 0 回) うえ、足の移動距離も左端近くから右端近くまでとほとんど同じです。ということは、この 2 パターンの譜面の難易度はほぼ同じだと言えるのでしょうか？
実はこの 2 つのパターンでは、A に比べて B の方が難しいとされています。その理由は図 7 の踏み方において囲って示した中央付近のパネルの踏み方にあります。B の譜面では中央あたり (丸印を付けた箇所) で→を右足、←を左足で踏んでいます。実際にステップを踏んでみるとわかりますが、前を向いたままこれを踏もうとすると中央で足が交差します。こういったパターンは交差渡りと呼ばれ、A のようにずっと前を向いたまま自然に踏めるもの (こちらはカニ歩きなどと呼ばれます) に比べて難しいとされているのです。
さらに、交差渡りと一口に言っても、たとえば B の譜面で中央の → を右足で踏んでから左足を交差させて ← を踏みにいくとき、右足の前から交差させていくか後から交差させていくかでも身体の向きが変わります。B のパターンの場合は左足が直前では ↑ パネルにあり、前から交差させていくと身体の向きが渡りの進行方向と合うので、前交差が良い踏み方であると言えます。
こういった配置も考慮に入れて踏み方を考えるときはどのようにすればよいでしょうか？交差するか否かだけであれば、そのときの足の位置から分かりますが、交差するとき前交差か後交差かといった問題は足の位置だけからでは分かりません。状態に新たな要素 (1 歩前だけでなく、2歩前にどの辺に居たか等) を加えるか、あるいは譜面に対して何らかの前処理 (事前に身体の重心の流れを計算しておいて渡りの方向を把握しておく等) をしておくか、などなど、工夫の余地は沢山あると思います。
余談
DDR にはグルーヴレーダーという機能があり、各譜面ごとにその属性 (矢印の密度や、同時踏みの量、長押しの長さなど) が計算されてレーダーチャートで表示されています。このグルーヴレーダーにより難易度や大まかな譜面傾向がつかめる、というわけです。
ところが、8 つのパネルを使う DP では矢印の密度や速さよりも、その配置が何よりも重要になってきます。グルーヴレーダーでは配置に関する情報が何も分からないので、左右に激しく振り回す譜面かどうかといった重要な要素もレーダーからは見て取れません。
そこで、仮に DP の要素に特化したグルーヴレーダーを考えるとしたら、どういった評価軸があって、どういう計算方法がよいかなあと考えていたところ、まさにこの記事に書いたような DP を使って色々な計算ができるのでは？という発想に至り、アドベントカレンダーもそういうネタで書くことに、
決めた、と言いたかったのですが、よく考えると全然 DP 特有の配置の難しさを考えるようなことを記事に書いていないし、なんで書こうと思ったのかよくわからなくなってきました。というかこの記事のほとんどが余談じゃん。皆さん DDR をやりましょう楽しいですよ。
AOJ2427 -- ほそながいところ
問題文: hosonagaitokoro | Aizu Online Judge
こういう系 (適切な方針を選ぶと非常に楽になる系) は結構好きです。以下白文字。
馬車 u が馬車 v (u > v) を抜かす場所 (あるいは抜かさない) を全探索すると、各馬車の出発時刻 x[u] に不等式制約が立つので牛をやる。ただし、同時に同じ場所で追い抜きができないので、ある馬車が同じ場所で 2 回以上追い抜きインシデントに遭遇するのは NG とする。O((n(n-1)/2)^(m+1) * n^3)
という方針でやると全然混乱せず実装も楽に一発 AC 出来てよかった。ソースは続き。
続きを読む