東京工業大学プログラミングコンテスト2015 P問題 - Dancing stars on regular expession!

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 の意味でも使います。

重要なこと

f:id:JAPLJ:20150531020925p:plain

容量無限の辺は

  • a が E なら b も E
  • b が F なら a も F

を意味する(切ってしまうとカットが無限になる)。

E を含めば +1

f:id:JAPLJ:20150531021202p:plain

たとえば 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 日目の記事です。

まとめ

Q. この記事を読めば動的計画法が分かるようになりますか?

A. なりません。

はじめに

プログラミングコンテストの問題の題材として DDR (DanceDanceRevolution) が出題されることは少なくありません *1。しかし、活動時間の全てをオンラインジャッジにつぎ込む生活では、DDR を想像することができず、問題の理解に困ってしまうこともあるでしょう。一分一秒を争うこの世界では、致命傷となりかねません。本記事は、そのような状況への対策として執筆されています。*2

問題

あるゲームには図 1 のような 8 つの矢印パネルがついた台があり、図 2 のような譜面が流れてきます。このゲームの遊び方は単純で、矢印が判定エァリアに重なるタァーイミングでパァーノゥを踏む *3 というルールです。

※4 つのパネル(←、↓、↑、→ を 1 セット)を用いるプレースタイルを SP (Single Play) と言い、今回のように 8 つのパネル (上下左右 2 セット) を用いるプレースタイルを DP (Double Play) と言います。この記事はこれがやりたかっただけです、ここまで読んで頂いてありがとうございました。明日の記事は uwitenpen さんで「CodeRunnerの裏側」です。楽しみですね。


f:id:JAPLJ:20141213221531p:plain

図1

f:id:JAPLJ:20141213221646p:plain

図2

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 のような譜面を考えましょう。

f:id:JAPLJ:20141213221819p:plain

図3

これは「アフロ踏み」と呼ばれる典型的なステップのひとつです。これはどのように踏むのが最適と言えるでしょうか?すこし考えてみましょう。

この配置の踏み方にはいろいろと考えられますが、距離や速さを優先するなら次のような踏み方になるかと思います。

f:id:JAPLJ:20141213221835p:plain

図4

こうすれば左足も右足も、最も近い 2 パネル間の移動だけで済んでいるので、前節の指標であればかなり良いと言えそうです。

しかし、この踏み方では同じ足を連続して使うことが多い点に注意してください。一般に同じ足を連続して動かしてパネルを踏むことをスライドといい、距離や体勢を考えると有用なことも多いですが、同じ足を連続して使うことにより大きな負荷がかかるのはもちろん、動かしていない方の足にも体重が大きくかかり負担となります。そこで、次のような踏み方を考えましょう。

f:id:JAPLJ:20141213221853p:plain

図5

このような踏み方をすると左右の足を交互に使うことができます。

さて、それでは左右に交互に踏むことが最適なのか?というと必ずしもそうではありません。スライドを使った方が足の移動距離が短くなることは多いですし、たとえば先ほどの「アフロ踏み」で交互に踏んだ図 5 を見ると、途中 (丸印を付けた箇所) で身体が横向きになってしまうことがわかります (実際に図 5 に従ってステップを踏んでみましょう)。

「スライド」を多用するのが得意という人もいれば、スライドは苦手なので交互踏みを優先するという人もいるわけです。そういったことも考えた上で、個人の得手不得手も考慮してそれぞれに合った最適な踏み方を導き出すにはどうすればよいでしょうか?

この問題の先ほどと比べて難しいところは、踏み方の良さを考えるにあたって 2 つの評価軸 (スライドの回数と足の移動距離) があるという点に尽きます。このせいで、ある状態へ至るための最良コストを決定することができません。スライドが多くても足の移動距離を節約したい人もいれば、交互に踏めるところはできるだけ交互に踏むという人もいるからです。

今回は状態を拡張することで乗り切ります。これまで状態は「k 個目の矢印を踏んだ後、それぞれの足が置かれている場所」で表現していましたが、これを「k 個目の矢印を踏むまでにスライドを使った回数が s 回で、k 個目の矢印を踏んだ後にそれぞれの足が置かれている場所」とします。つまり、本来評価値であったはずの値 (スライドの回数) を状態に組み込んでしまいます。こうすると、改めて考える評価値は先ほどと同じ移動距離に関するもののみとなり、同じようにして問題を解くことができます。

これができれば、スライドの得意な人にはスライドを多く使った状態へ至るための最適な踏み方を、苦手な人にはスライドをあまり使わない状態へ至るための最適な踏み方を、といった風に個人差を考慮した踏み方を計算することができます。

このように、評価軸が 2 つ以上あるときに、いくつかの評価値を状態に入れてしまうという方法は多くの (動的計画法を用いる) 問題で使うことができます。

奥深き DP の世界

この節は元の問題から少し離れて発展的なトピックです。

図 6 に示す 2 つの譜面パターンを見てみましょう。このように左から右(あるいは逆)に渡り歩くような譜面を「渡り」と言います。

f:id:JAPLJ:20141213221926p:plain

図6

図 7 のようにどちらの足で踏むかを決めてみると、わりと自然と両方とも交互に踏むことができるのが分かると思います。

f:id:JAPLJ:20141213221947p:plain

図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 出来てよかった。ソースは続き。

続きを読む

ICPC ひとり地区大会 NEERC 2011

ひとりで地区大会練習をした。(LiveArchiveで)

LiveArchive: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=527

問題PDF: http://neerc.ifmo.ru/past/2011/neerc-2011.pdf

I 問題がインタラクティブで LiveArchive はジャッジに対応していないので、あらかじめ手元ジャッジできるようにしておいた。(しかし普通にミスってて今回も手動ジャッジに手間取ってしまった)

AC Penalty A B C D E F G H I J K L
8 1204 5+0 41+0 167+0 264+1 63+0 - 231+0 - 216+0 - 137+3 -

("-" は提出なし、"+n" は n 回誤答を提出、"m+n" は n 回誤答を提出した後に m 分の提出で AC)

本番順位表だと 11 位だった。9 完は 2 チームで、11 位は 8 完下位というところ。ひとりなのでペナルティで負けるのはしょうがないね。

問題概要(感想は下)

A

グリッド上に / \ で書かれた多角形があるので面積を求める。

B

0 〜 m-1 の整数を 01 列でエンコードする。 m ≦ 2n なる最小の n をとってくる。

エンコード先の 01 列は長さ n-1 か n のどちらかで、

  • 小さい数の方が 01 列が短い(または同じ長さ)
  • 小さい数の方が 01 列が辞書順で小さい

を満たすようにする。エンコード後のビット数を最小にせよ。具体的な 01 列も求めること。

m ≦ 10,000。

C

面倒に面倒を加えて面倒でアレンジした面倒な問題。説明する気が起きない。解法自体は簡単なので……。

D

n 個の文字列 s1, ..., sn が与えられる。以下の文字列を含む辞書を作る。

  • s1, ..., sn
  • si の空でない prefix と sj の空でない suffix を連結したもの(i = j でも良い)

辞書に含まれる文字列は何種類あるか。

n ≦ 105 で各文字列の長さは 40 以下。

E

雌雄の区別があるとある種の個体 1, ..., n がいる。どれが雄でどれが雌かも与えられる。

m 個の情報が時系列順に与えられる。各情報は

  • a, b から性別 s の子が生まれる。(a, b の性別は異なり、生まれた子の番号はまだ使われてない最小の番号)
  • a が死ぬ。

のいずれか。また、「個体 a の DNA 番号は x」という形式の情報が k 個与えられる。

子は雌親の DNA 番号をそのまま受け継ぐとしたとき、m 個の情報が与えられた後で生きている個体について

  • すべての DNA 番号が同じであるか
  • 異なる DNA 番号の個体がいるか
  • 与えられた情報からでは判定できないか

を求める。

n, m, k それぞれ 105 ぐらい。

F

時刻 t = 1, ..., n に点 (p[t], 0) から、(x[t], y[t]) を頂点とするような放物線を描いてミサイルが発射される。

m 個の航空機の情報が与えられる。各情報は、時刻 a から時刻 b の間に x 座標が x1 から x2 の間を飛ぶという形式。

それぞれの航空機について、飛んでいる時間に発射されるようなミサイルの軌道と交わらないためには高度いくつを飛ぶ必要があるかを求めよ。

n, m は 105 ぐらいだったと思う多分。

G

1 以上 n 以下の秘密の整数がある。

1回のクエリでは 1 以上 n 以下の整数 x を指定して、秘密の整数と x の最大公約数を知ることができる。

秘密の整数を特定するために最悪ケースで必要なクエリの回数を求めよ。

n は 104 以下。

H

2 点 p1, p2 と 2 直線 l1, l2 が与えられる。

直線 l であって、p1 を l に関して対称移動すると l1 上に動き、p2 を l に関して対称移動すると l2 上に動くようなものがあれば求めよ。

I

リアクティブ問。

n 要素の秘密の順列がある。

1 回のクエリでは n 要素の順列を指定して、秘密の順列との最大共通部分列の長さを知ることができる。

5n2 回以内のクエリで秘密の順列を特定せよ。

J

前進命令、右回転命令、左回転命令と関数定義、関数呼び出しからなるプログラムに従って動くロボットがいる。

ロボットが停止するまでの間に通った座標のうち |x| + |y| の最大値を求めよ。いくらでも大きくなる場合は Infinity と出力。

関数定義は 100 個以下。各関数の命令数は 100 以下。

K

n 頂点の木が与えられる。辺をいくつか追加して、以下の条件を満たすようにしたい。

  • 条件: どの辺を取り除いてもグラフが連結である。

最低いくつの辺を足す必要があるか?また、足す辺の具体例をひとつ出力せよ。

n は 105 以下。

L

読む気起きず。

続きを読む