Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2012-07-01

[][] Google Code Jam Round3 Problem D small 01:36 はてなブックマーク -  Google Code Jam Round3 Problem D small  - 練習帳

問題文

 問題文

概要

  • 文字列sが与えられている.長さnで次の条件を満たす文字列が存在するような数nのうち,最小のものを答えよ.
  • 条件:文字列が,文字列sの「2-gram」及び「2-gramの一部分をleet変換して出来るすべての候補」を全て含む.
    • 文字列のN-グラムとは,長さNの部分列の事.例えば「abca」なら「ab」「bc」「ca」
    • leet変換とは特定のアルファベットを形の似ている数字や記号に変換する事.例えば「google」→「g00gle」など.この問題では,"o" → "0", "i" → "1", "e" → "3", "a" → "4", "s" → "5", "t" → "7", "b" → "8" "g" → "9"のleet変換のみ考える.
  • 制限:sの長さは1000以下

コード

 Practiceでの提出コード(gist):https://gist.github.com/2952584

考えた過程

方針1:時間のかかる解き方 → 失敗

最初に思いついた方法は,巡回セールスマン問題に帰着させる方法でした.sの2-gram及び2-gramのleet変換すべてを列挙し,それらをグラフの頂点とします.頂点aから頂点bへのコストは,aの後ろにいくつか文字を加えて,bが接尾辞となる為に必要な最小の文字数とします.すると,全ての頂点を1回ずつ訪問するコストは,解候補となる文字列の長さとなります.従ってそのような訪問コストのうち,最小のものをとれば答えが得られます.

しかし,sの長さが1000なので,部分文字列の個数は1000個,leet変換を施すと候補数は最悪2*2=4倍に増えるので,頂点数が4000の巡回セールスマン問題を解かなければならず,とても時間に間に合いません.

方針2 (その1):簡単な場合の問題に帰着させる

問題を簡単化する事を考えます.leet変換できるような文字がsの中に存在しないとします.例えばs="pqrp"などです.leet変換がない場合に,文字列を2-gramに分解してからごにょごにょするようなアルゴリズムで問題が解けるとします.すると,一般にleet変換がある場合は,同じように2-gramに分解した後,leet変換で拡張してから同じアルゴリズムを適用すれば問題が解けるはずです.まずはleet変換がない場合について考えてみようと思います.

(2-gramに分解せずに解くようなアルゴリズムを用いた場合,そのアルゴリズムをleet変換が含まれるケースに拡張できるかは分かりません.例えばppoの場合,含めるべき2-gramはpp, po, p0だけですが,もとの文字列ppoにp0を追加してしまうと,ppop0となり,含める必要のないopが入ってしまいます.)

方針2 (その2):leet変換がない場合を考える → 失敗

leet変換がない場合,答えはsの長さと同じになるかというと,そうとは限りません.例えば,s="pqppqp"は2-gramの種類としてpq, qp, ppしか持ちません.この3種類の部分列をすべて含む最短の文字列は,sよりも短い"pqpp"などの4文字です.もっと極端なのは,s="ppppppppppppppppppp"などは,"pp"が条件を満たします.

少し気になるのは,全2-gramをunique操作を残った2-gramから,元の文字列を復元する問題は,今解こうとしている問題と同程度に難しい事です.例えば,pqppqrから2-gramをとってunique操作をすると,pq, qp, pp, qrが取り出せます.これらを組み合わせて、もとの文字列のpqppqrを復元する問題は,今解きたい問題から最小性の条件を取り除いたものです.

条件を満たす文字列は可能性としては短くなる事しかあり得ません.そこで,どのような時に短くなるかを考えてみましたが,法則みたいなものは見つかりませんでした.

方針3:2-gramの別の表現方法を考える → うまくいく...らしい

この辺りで手詰まり感が出てきたので,別な方針を考える事にしました.これまではずっと,個々の2-gramを一つの頂点だと思ってきましたが,別の表現方法もありました.つまり,それぞれのアルファベットを頂点だと思って,xyという2-gramがあったら,xからyへ枝を貼るとしてグラフを作っても,2-gramを表現できます.このグラフの場合,最短の文字列を作るのは,すべての枝を通る,最短の一筆書き(重複を許す)を見つける問題に帰着されます.

もし一筆書きが出来るのならば,答えは単純に1+(枝の数)です.しかし,一般の場合には枝の本数より長くならなければなりません.早く提出している人の回答を見てみると,その答えは,1+(枝の数)+max( (Σ_{v} max(out_edge-in_edge, 0) )-1 , 0)となるようです.証明は,例えば節の数についての帰納法等で行えると思うのですが,もう少し直感的な説明が欲しいところです.

2012-06-24

[][] TopCoder TCO Round 2C Level2 (500) ThreePoints 20:09 はてなブックマーク -  TopCoder TCO Round 2C Level2 (500) ThreePoints - 練習帳

問題文

 問題文

概要

  • 2次元平面上にn点が与えられている。
    • どの2点をとってもx座標は等しくない。また、どの2点をとってもy座標は等しくない。
  • 次の条件を満たす3点の組(A, B, C)の個数を答えよ:条件「A[x] < B[x] < C[x]かつA[y] < C[y] < B[y]、ここでP[x], P[y]はそれぞれ点Pのx, y座標を表す」
  • 制限:n ≦ 300000, 点のx, y座標は0以上10**9未満の整数値

コード

 Practiceでの提出コード(gist):https://gist.github.com/2863529

 (SRM終了直後の感想戦とPracticeで解答例を見た後に作成しています)

考えた過程

方針

点vについて,vより右上にある点をR[v],左下にある点をL[v]とすると,答えはΣ_{v} R[v]*(R[v]-1)/2 - R[v]*L[v]となります.具体的には,x座標について点をソートし,(x座標が小さい点はy座標が何番目に小さいか)を計算します(上の提出コードではperm[i]で書いています).これの数え上げにはBITを用いています,

どうやって思いつこう

それぞれの点を上の条件の点Aに対応させ,各点Aに対してB, Cの組が何個あるかを考えます・・・(*).B, Cは両方とも必ず右上になければなりません.ただ,B, Cがすべての右上に全部が条件を満たす訳ではありません.なので(1)の問題の前に,B, Cの配置でどのようなものが条件を満たすかを考えてみます.そのために,まず2つの点の配置関係を考えてみます.すると,x, y座標が一致する点がないという条件があるので,/(一方が右上にある)という関係と\(右下にある)の関係しかない事が分かります.

うまく問題の条件を使って問題を簡単に出来たので,この方針は悪くなさそうです.

ナイーブな方法では数え上げられない

では,(*)の問題,すなわち,各Aに対して,B, Cが/の関係になっている組の数は何個あるかを計算します.これにはAより右上にあるそれぞれの点Bに対して,Bより右上にある点が何個あるかを求め,それをすべて足さなければなりません.すなわたい2重ループです.点が300000個あるので,n**2の計算はできません.これをどう解消するかがこの問題のポイントなのだと思います.それぞれの点について「自分より右上にある点の数」を保存しておく事は出来ます,これは後で使うかもしれないので念頭に置いておきます.

真ん中の点を用いて数え上げる

/の関係になっている3つ組全体の個数を数え上げるときにΣを2回計算しなければならないのは,左下の点について分類している為です。これを真ん中の点を用いて分類すると,前述のように(左上の点)*(右下の点)で数え上げられてしまいます.これは1重ループで計算できてしまいます.多分この部分に発想の飛躍がある所なのだと思います.後はそれぞれの点について右上にある点の個数だけではなく,左下にある点の個数も予めBITなどで計算しておけば、答えが得られます.

2012-06-04

[][] TopCoder SRM 543 Div.1 Level2 (500) EllysRivers 00:01 はてなブックマーク -  TopCoder SRM 543 Div.1 Level2 (500) EllysRivers - 練習帳

問題文

 問題文

概要

  • 複数の川が平行に並んでいて、川と川の間には直線の道路がある。川の幅は川ごとに異なる。
    • つまり2次元座標を適当に置くと、川はy軸に平行な帯状領域で、道路はy軸に平行な直線と思える。以降この座標系を用いる
  • 川と道路を移動する事で、左下のスタート地点(0, 0)から右上のゴール地点(W, L)まで移動したい。そのために要する最短時間を求めよ。
  • 川内では自由な方向に移動できるが、道路は細いためy軸方向のみ移動できる。
    • 道路を移動する速度はすべての道路で共通だが、川内を移動する速度は川ごとに異なる。
  • 川から道路への移動と道路から川への移動はy座標が整数の点でのみ行える。
    • スタート、ゴール地点は共に道路上の点
  • 制限:
    • 川の数(以下ではNと書く)は50以下、川と道路での移動速度は10**6以下、それぞれの川の幅は10**6以下でL, Wは整数で10**6以下

コード

 Practiceでの提出コード(gist):https://gist.github.com/2793235

考えた過程

問題を簡単にする

まず、道路を移動するスピードはどこでも同じなので、徒歩での移動するのは一番右端の道路でのみ行うことにします。本当にこの簡単化が効果的かはわかりませんが、とりあえずやっておきます。

動的計画法なのはすぐわかるけれど

dp[i][a]を、i番目の川を渡り終え、y座標がaの位置に達するのに要する最短時間とします。dp[i][*]達からdp[i+1][*]達が計算でき、また求めるべき答えはdp[N][L]なのでこのdpを更新する動的計画法で答えが求まります。しかし、問題なのはdpの更新をナイーブに行うと時間がかかってしまう点です。dp[i+1][y]は、y以下の非負整数aに対してdp[i][a]+(aからyまで川を移動する)を計算し、その最小値を取れば計算できます。しかし、この方法ではdp[i+1][*]達の計算にはO(L**2)です。Lが10**6程度なので、1回の更新だけでも制限時間を超えてしまいます。

高速の高速化を考える

そこで、この更新をもっと速くできないかと考えます。自分が探した範囲だと少なくとも2通りの方法が有りました。1つ目の方法は最小値を達成できない可能性を分割統治法を用いて枝狩りし、2つ目の方法は目的関数の凸性を用いて探索範囲を狭めています。最初に挙げた自分の提出コード(と入っても他の方の回答のほぼ丸写しですが...)は前者の方法を用いています。以下ではその方法を解説します。

後で良く使うので、以下の記号を用います。

  • i:以下の文脈では定数と思います
  • dp[i][a]:i番目の川を渡り終えて、y座標がaの位置に達するまでに要する最短時間
  • f(a, b) = 川の左端でy座標がaの点から、右端でbの点まで泳ぐのに要する時間。
    • つまり、dp[i+1][y]はf(a, y)をaの変数と見た時の最小値です。
  • a-bライン:川の左端でy座標がaの地点から、川の右端でy座標がbの地点までを結んだ直線
更新の高速化

y座標が丁度真ん中の点、つまりdp[i+1][L/2]を計算した結果、f(y, L/2)の最小値をy=a0で達成したとします。すると、次のことがわかります:「左端がy ∈ [0, a0]の地点から右端がz ∈ [L/2, L]の地点に泳いで移動する方法ではdp[i+1][z]の最小値を達成できない」。つまり今L/2に到達するために泳いだ直線を横切るような泳ぎ方は最適ではありません。これの証明は後で行います。

同様にして、a0-L/2のラインを逆向きに横切る方法(つまり、川の左端でy座標がy ∈ [a, L]の点からから川の右端でy座標がz ∈ [0, L/2]に移動する方法)も最適な経路でないことがわかります。すると、dp[i][L/2]を計算してしまえば、後は[0, a]→[0, L/2]の移動と[a, L]→[L/2, L]の移動だけを調べれば十分となります。つまり、分割統治法です。

証明

以下の事を証明します: 「dp[i+1][y] = min_{b} dp[i][b]+f(b, y) の最小値がb=aで達成される時、b < a、y < zとなるb, zに対して、dp[i][a]+f(a, z) < dp[i][b]+f(b, z)が成立する」

(証明)

dp[i][y]の最小値を取る経路の中にb-yラインを泳ぐ経路も含まれているので、dp[i+1][y] = dp[i][a]+f(a, y) ≦ dp[i][b]+f(b, y) が成立します。これと証明したい式を見比べると、f(b, y)-f(a, y) < f(b, z)-f(a, z) ・・・(※)を示せば十分です。

fは具体的な式でわかっていて、 f(a, y) = sqrt( (y-a)**2+w**2)/sです。ここで、sqrtは平方根、wは川幅、sは泳ぐ速度です。従って、f(b, y)-f(a, y) = (sqrt( (y-b)**2+w**2) - sqrt( (y-a)**2+w**2) )/sです。この式をs倍して変形してsqrt( ( (y-a)+(a-b) )**2+w**2) - sqrt((y-a)**2+w**2)とし、y'=y-aの関数だと思います。ここで、a-b > 0を用いると、この関数がy'について単調増加であることがわかります。これは(※)の式が成立している事を示します。

2012-05-28

[][] Codeforces Round #120 : E. Counter Attack 01:18 はてなブックマーク -  Codeforces Round #120 : E. Counter Attack - 練習帳

問題文

 問題文

概要

  • 無向グラフが与えられている。
  • このグラフの補グラフを連結成分に分解せよ。
    • グラフG=(V, E)の補グラフG'とは、節がGと同じで、枝は(v, w)∉E(v, w∈V)となるグラフのことである。つまり、もとのグラフの枝の有無を反転させたグラフのこと。
  • 条件:節:n ≦ 5*10**5、枝:m ≦ 10**6

コード

 Practiceでの提出コード(解1):http://codeforces.com/contest/190/submission/1715799

 Practiceでの提出コード(解2):http://codeforces.com/contest/190/submission/1715764

 UnionFindはライブラリから使用:https://github.com/delta2323/algorithm_library

考えた過程

第一歩

一般の場合n**2≫mなので、補グラフはほぼ完全グラフになってしまっています。

nが小さければ、深さ優先探索なりUnion Findなりを使って連結成分分解は簡単にできます。しかし今回はn**2が大きいためにこれらの方法をそのままは使えません。何か飛び道具のようなうまい方法がないかと考えたのですが、結局思いつきませんでした。そこで、ベタに連結成分を計算する方法をうまく工夫して軽くできないかを検討しました。

未決定集合を持つ→失敗

最初に考えたのは、データの持ち方の方での工夫でした:まだどの連結成分に属するかが決まっていない節の集合(未決定集合)を持っておきます。深さ優先探索である節から隣接する節に移動する時には、その節が未決定集合に入っているかを調べ、すでに未決定集合から除かれている場合には移動しない事で枝狩りします。計算量的には問題ないと思うのですが、書き方が下手でRuntime Errorになってしまいました(後述のNG解の1つ目がそれです)。setをiteratorで回しながらstd::set::erase(iteraotr)でその要素を削除しているのでiteratorが無効になっています。

クラスタの数を少なくして連結成分分解

節の数がn個ある完全グラフを深さ優先探索すると、枝の持ち方を工夫しないと計算にO(n**2)だけかかってしまい、これがこの問題のネックになっています。そこで次の方法として、節を予めまとめあげて節の数を減らしてから、深さ優先探索ができないかを考えました。具体的には、二段階に分かれます。第一段階では、節達のうち距離1でつながっているもの達をある程度つなげることでクラスタにまとめ上げ、第二段階でクラスタに対して(ナイーブな)連結成分分解を行います。どちらの段階も最悪O(n**2)だけかかるのですが、今回の(補)グラフが密である事を用いると第一段階では相当な枝狩りが期待でき、第二段階ではクラスタ数が少なくなることが期待できます。実際うまく制限時間に収まりました(解1)。

無効なiteratorを用いないようにしながらtraverseする

Editorialを読んでみると、どうやら節同士をまとめてクラスタにするような事をしなくても、NG解1で考えていた、未決定集合を保持しながら幅優先探索で解答が得られるようです。ただ、setから単純に値を削除してしまうとiteratorが無効になってしまうので、実装の方法を少し工夫が必要でした。その工夫方法がこちらなどで紹介されていました。この方法を用いたのが(解2)です。

NG集

2012-05-20

[][] Codeforces Round #119 : C. Weak Memory 18:56 はてなブックマーク -  Codeforces Round #119 : C. Weak Memory - 練習帳

問題文

 問題文

概要

  • 無向連結グラフが与えられている(節:n個、枝:m本)
  • グラフのうちk個の節に印がついている
  • スタート地点とゴール地点が与えられている
  • 次の条件を満たす正数qのうち、最小の値を求めよ。条件を満たすqがない場合には-1と答えよ。
    • 条件:「スタートからゴール地点への経路のうち、次の条件を満たすものが存在する。スタート地点からqステップ以内に印つきの節がある、さらにその印つきの節からqステップ以内に印つきの節がある...これを繰り返してゴール地点までたどり着ける。」
  • 制限
    • n ≦ 10**5, m ≦ 2*10**5, k ≦ n, 実行時間2秒以内

コード

 Practiceでの提出コード:Submission #1683870 - Codeforces

 UnionFindはライブラリから使用:GitHub - delta2323/algorithm_library: A library for competitive programming

考えた過程

方針1:印つき節のみのグラフを作れるか?

 もし印つき節だけ取り出し、節間の距離を元のグラフでの最短距離とするグラフを作れれば、その上でダイクストラに近いことを行えば、与えられた課題を解くことができそうです(各節の上で、通常の「その節までの最短距離」の代わりに「その節に到達するまでにたどった枝のコストの最大値」を覚えます)。すると問題はそのような最短距離を結んだグラフが作成可能に帰着できます。でもそれは難しそう。一番嬉しいのは2つの印つき節間の距離がすべて求まる事ですが、それにはワーシャルフロイドを行う必要がありますが、印つき節の最大数は10**5なので、計算量的に無理で、仮にできたとしてもメモリが足らなさそうです。印つき節間の距離を全部は計算しないで計算が間に合うようにするということも考えられるけれど、必要不必要の判断をどのように行うかがパッとは思いつかないです。とりあえずこの方針ではこの先に思いつきませんでした。

方針2:qについて2分探索

 次に考えたアイデアはqの値について2分探索が出来る事です。つまり、ある値qでスタートからゴールまでたどり着くことが可能なら、qより大きい値でもたどり着くことは可能なので2分探索が使えます。qが3なり4なりある特定の定数になってしまえば、今いる印つきの節からqステップ以内にある印つきの点を深さ優先的に探索することで、ゴールに辿り着けるか調べられます。つまり、「ある印つき節移動する→その点を始点とするダイクストラを実行し、qステップ以内の印つき節を見つける→それらを順番に訪問する→・・・」とすれば良いです。でもダイクストラは無駄な計算をものすごくしているような気がする。ダイクストラの計算量がO(m+nlogn), 印つき節の深さ優先探索でO(k)なので、合計の計算量は大雑把にO(k(m+nlogn))。やっぱり計算量的に難しそう。

 ただ、qについて2分探索の方はそれなりに良さそうな気がしていて、印つきの2つの節について「枝が貼られている」⇔「qステップで移動可能」でグラフを作れば、求める条件は新しく作ったグラフの上でスタート地点とゴール地点が連結であるというところまで問題を簡単にできます。連結かどうかを調べるのは、深さ優先探索でもUnionFindでもできるので、この部分はあまり気にする必要がなさそうです。ただ、この場合も方針1の時と同じように、すべての印つき節のペアについてqステップで移動可能かを考えていたら時間は足らなくなってしまう。

解答

 ここまでで良くわからなくなりギブアップ。他の方の回答を見ていたのですが、以下の方針がしっくり来ました。以下のSubmissionを参考にさせていただきました。

「qステップで移動可能か」という条件のチェックがナイーブな方法では全く時間が足らないですが、この部分を工夫して計算量を減らすのがポイントだと思います。方針は次のとおりです。各節(印つきとはかぎらない)で「最も近い印つき節」と「その印つき節までの距離」の2つを覚えておきます。節vに対するこれらの値をv.n(neighbour), v.d(distance)と置く事にすると、印つき節をつなげるための規則は枝(v, w)に対して「v.d+1+w.d <= qならばv.nとw.nをつなげる」となります。キューに(v.n, v.d)を入れて、順番にこの規則を適用します。(v.n, v.d)の情報に更新があったら、その更新情報をキューに追加します。

最初に挙げた自分の提出コードに対して、次のテストケースを与えた場合を考えます。このテストケースはT字型をしたグラフでTの先端3箇所にvolunteerがいます。T字の上棒の左端が1, 右端が42, T字の下端が27番の節です。連結部分は26番で1-26間の距離は25, 26-27間の距離は15, 26-42間の距離は30です。答えとなるq=45のケースでは、T字を遠回りしなければゴールにつけません。気になるのはq=55の時で。この場合スタートからゴールまで直接移動できるのですが、自分の提出アルゴリズムでは、やはりT字を遠回りする道を選択しています。つまり、印つき節に対し「枝が貼られている」⇔「qステップで移動可能」となっているグラフよりも少ない枝を張っている事で計算量が抑えられているのだと思います。各節に対して覚えておくのは最も近い印つき節だけで覚える事でそれを達成しています。

不安になるのは、節のつなぎ漏れがないかということです。実を言うと自分でも何故これで正しくできるかをきちんとは理解できていないですのですが、今回の提出コードではそれで十分だったようです。