Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

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'について単調増加であることがわかります。これは(※)の式が成立している事を示します。

2011-09-12

[][] TopCoder Single Round Match 517 Div.1 22:56 はてなブックマーク -  TopCoder Single Round Match 517 Div.1 - 練習帳

結果

 コンテスト結果概要

 個人結果(要ログイン)

2500:21:35.186Challenge Succeeded170.71->0.00
6000:52:37.760Opented0.00
9000:51:19.312Opented0.00
Challenge..0.00

部屋(Room 1) 13位,全体 594位

Rating : 1504 → 1413 (-91)

 500どころか250も解けなかったという.

250 CompositeSmash

問題文

 問題文

要約

 整数nを適当に2つの数の積に分解する(分解の仕方は何通りかあるがそのうちの1つを適当に選ぶ),できた2つの数をそれぞれ同じ用に2つに分解する.以降これを可能な限り繰り返す.別の数targetが与えられているので,nをどのように分解しても,その分解途中にtargetが現れるかを判定せよ.n, targetは2以上100000以下の数.

方針

 nを1通りに分解できるなら"Yes"...とは限らず,さらにn%target==0の条件がつかないとならない.一方,分解できなかったら"No"...とも限らず,もしn==targetなら実際には"Yes"となる.などのように場合分けが煩雑になってしまいコーナーケースを潰しきれませんでした.

 今回の提出コードも(n, t)=(1024, 4)のケースで落とされてしまいました.

提出コード

(このコードは正しくありません)

class CompositeSmash {
public:
  string thePossible(int n, int target) {
    if(n % target != 0){
      return "No";
    }
 
    int cnt = 0;
    for(int i = 2; i*i <= n; i++){
      if(n%i==0){
        cnt++;
      }
    }

    if(cnt == 1){
      return "Yes";
    }else if(cnt == 0){
      if(n == target){
        return "Yes";
      }else{
        return "No";
      }
    }
 
    if(n == target){
      return "Yes";
    }
 
    int cntt = 0;
    for(int i = 2;i * i<=target;i++){
      if(target%i==0){
        cntt++;
      }
    }
    if(cntt == 0){
      return "Yes";
    }else{
      return "No";
    }
  }
};

 Sigmarさんの「KISSの原則」*1の話にもありましたが,コンピュータに探索を任せるように思考を変えられると,このような問題を解けるようになるのかな,と忸怩たる思いをしながら感じました.

修正コード
(#include 省略)
using namespace std;

int memo[111111];
bool solve(int n, int t){
  if(n == t){
    return memo[n] = true;
  }
  if(memo[n] != -1){
    return memo[n];
  }

  bool dividable = false;
  bool ok = true;
  for(int i = 2; i*i<=n; i++){
    if(n%i != 0){
      continue;
    }
    dividable = true;
    ok &= (solve(n/i, t)|solve(i, t));
  }

  return memo[n] = (ok&dividable);
}

class CompositeSmash {
public:
  string thePossible(int n, int t) {
    memset(memo, -1, sizeof(memo));
    bool ok = solve(n, t);
    return ok ? "Yes" : "No";
  }
};

2011-09-03

[][] TopCoder SRM 516 Div.1 500 RowsOrdering (続き) 18:56 はてなブックマーク -  TopCoder SRM 516 Div.1 500 RowsOrdering (続き) - 練習帳

 前回のエントリで,500点問題の誤答の原因がわからないままでしたが,それが解決したので追記します.

500 RowOrdering

問題文

 問題文

方針

 問題を思い出すと,「1から50までを組み合わせてできるm文字の文字列達(全部で50**m個)にあるルールの範囲で適切に順番をつけ,与えられた文字列達の順位の合計が最小になるようにせよ」というものでした.そしてその順番は文字列内でのポジション(column)に1〜50のpermutationを与える事と,それらを統括する1個のpermutation(1〜m)を与える事で決まりました.前回前者は出来ましたが,後者が間違っていました.

 前回のpermutationの決定方法は以下のようなものでした

class comp{
public:
  // i, j は1から50までを動く
  bool operator<(int i, int j){
    // v[x][y]はx番目のcolumnに入っているyの個数
    // 条件:Σ_{y} v[i][y] = Σ_{y} v[j][y]
    sort(v[i].rbegin(), v[i].rend());
    sort(v[j].rbegin(), v[j].rend());
    return v[i] < v[j];
  }
};

 それぞれのcolumnでの順位の合計を計算し,それが小さい順に並べるのが正しいソート方法でした.

class comp{
public:
  // i, j は1から50までを動く
  bool operator<(int i, int j){
    // v[x][y]はx番目のcolumnに入っているyの個数
    // 条件:Σ_{y} v[i][y] = Σ_{y} v[j][y]
    sort(v[i].rbegin(), v[i].rend());
    sort(v[j].rbegin(), v[j].rend());
    long long ai = 0;
    long long aj = 0;
    for(size_t i = 0; i < v[i].size(); i++){
      ai += i * v[i];
      aj += j * v[j];
    }
    return ai < aj;
  }
};

 間違いの原因はこの2つが同じ結果になると思ってしまった事で.例えば次のような単純な例でも両者の結果はずれてしまいます.

v[i] = {1, 1, 0, 0, 0, 0, 0,...}
v[j] = {2, 0, 0, 0, 0, 0, 0,...}

 辞書式順序なら,v[i] < v[j]ですが,Σi*v[i] = 1, Σj*v[j] = 0なので,訂正した方の順序はv[i] > v[j]です.

2011-09-01

[][] TopCoder Single Round Match 516 Div.1 08:50 はてなブックマーク -  TopCoder Single Round Match 516 Div.1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:14:58.653Passed System Test200.11
5000:55:18.277Challenge Succeeded204.37->0
10000:04:24.523Opented0.00
Challenge..0.00

部屋(Room 37) 8位,全体 284位

Rating : 1450 → 1504 (+54)

 黄色復帰しましたが,500が恒常的に解けないと頭打ちなので,どうにかしないとならないです.

250 NetworkXOneTimePad

問題文

 問題文

方針

 aを鍵bで暗号化してcになるならば,aを鍵としてcに同じ処理を行えば鍵bが得られます(a xor b = c => c xor a = b).従って,cipher textの0番目がどのplain textを暗号化したものかを決めてしまえば,鍵の候補が得られます.その鍵を用いて他のcipher textを複合化して,もともとのplain textのうちのどれかが得られるかを調べます.

提出コード

 せっかく配列をソートしたのに,線型探索をしたのが残念です.

#include <string>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <algorithm>
 
using namespace std;
 
string gen(string& s, string t){
  string ans = "";
  for(int i = 0; i < s.size(); i++){
    char c;
    if(s[i] == t[i]){
      c = '0';
    }else{
      c = '1';
    }
    ans+=c;
  }
  return ans;
}
 
 
class NetworkXOneTimePad {
public:
  int crack(vector <string> p, vector <string> q) {
    int n = p.size();
    int m = q.size();
    sort(p.begin(), p.end());
    sort(q.begin(), q.end());
    int ans = 0;
 
    for(int i = 0; i < n; i++){
      string key = gen(q[0], p[i]);
      bool isans = true;
      for(int j = 1; j < m; j++){
        string input = gen(q[j], key);
        if(find(p.begin(), p.end(), input) == p.end()){
          isans = false;
        }
      }
      if(isans){
        ans++;
      }
    }
    return ans;
  }
};

500 RowsOrdering

問題文

 問題文

方針

 各columnに割り当てるpermutation(1~50)がそれぞれのcolumnに属する文字達だけから決められ,他のcolumnや,column同士の優先順序を決めるpermutation(1~M)に依存しないという点が,計算量を落とす時に重要なポイントだと思います.この事を説明する為に,columnの優先順序(1~Mのpermutation)と,各columnでの文字の優先順序(1~50のpermutation)が決まっていたとして,あるrowの順位がどのように決まるかを考えます.

 例えば各々のpermutationは1, 2, 3, ...という自明のものとして,rows ={"cbd", "dac", "bbb"}とします,例えばcbdの順位は

2(cの順位) * 50**2(倍率) + 1(bの順位) * 50**1(倍率) + 3(dの順位) * 50**0(倍率)

と計算できます.別の文字列も同じように足し算の形に直すと,

2(cの順位) * 50**2(倍率) + 1(bの順位) * 50**1(倍率) + 3(dの順位) * 50**0(倍率)
3(dの順位) * 50**2(倍率) + 0(aの順位) * 50**1(倍率) + 2(cの順位) * 50**0(倍率)
1(bの順位) * 50**2(倍率) + 1(bの順位) * 50**1(倍率) + 1(bの順位) * 50**0(倍率)

倍率をまとめあげます.

2(cの順位)                         1(bの順位)                          3(dの順位)
3(dの順位) * 50**2(倍率) + 0(aの順位) * 50**1(倍率) + 2(cの順位) * 50**0(倍率)
1(bの順位)                         1(bの順位)                          1(bの順位) 

 各columnに割り振るpermutation(1~50)は自由に決められます.従って,自分に割り振られる倍率がいくらだったとしても,それぞれのcolumnは倍率抜きでの合計(上図で縦に並んでいる値の合計)を最小化するようにpermutation(1~50)を決めれば良いです.そして,そのようなpermutation(1~50)はそれぞれの列での出現頻度が多い文字から高い順位を与えるものです.

 次にcolumnの優先順序の決め方を考えます(ただ,自分のコードは間違っていてそれを直せていないので,アイデアのみ紹介します)

 下のコードでは次のようにして優先順序を計算しています:まず,それぞれのcolumnについて,上と同じように文字の出現頻度を多い順に並び替え,次にそれぞれの列で求めた配列を辞書式順序(e.g [5, 4, 3, 2] > [5, 4, 3, 1])で大きい順に並び替えています.

提出コード

 同じ部屋の対戦者が自分の提出コードのバグを見つけて行った一斉攻撃に巻き込まれてChallengeされました.

(間違っています)

#include <string>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
 
typedef long long ll;
 
int getnum(char c){
  if(c >= 'a' && c<='z'){
    return c - 'a' + 1;
  }else{
    return c - 'A' + 27;
  }
}
 
vector<ll> stat;
vector<vector<int> > prestat;
 
bool comp(int i, int j){
  return stat[i] < stat[j];
}
 
bool comppre(int i, int j){
  return prestat[i] < prestat[j];
}
 
ll mod =  1000000007;
 
class RowsOrdering {
public:
  int order(vector <string> rows) {
    int m = rows[0].size();

    prestat.clear();prestat.resize(m, vector<int>(50, 0));
    vector<int> preind(m);
    for(int i = 0;i < m;i++){
      for(int j = 0;j < rows.size();j++){
        prestat[i][getnum(rows[j][i])]++;
      }
      preind[i] = i;
      sort(prestat[i].rbegin(), prestat[i].rend());
    }
    sort(preind.rbegin(), preind.rend(), comppre);    
 
    ll ans = 0;
    ll multiplier = 1;
    for(int i = m-1; i >= 0; i--){
      int ii = preind[i];
      stat.clear();stat.resize(50);
      vector<int> ind(50);

      for(int j = 0;j < 50;j++){
        ind[j] = j;
      }

      for(int j = 0;j < rows.size();j++){
        stat[getnum(rows[j][ii])]++;
      }

      sort(ind.rbegin(), ind.rend(), comp); 

      ll base = i == 0 ? 1 : 0;
      for(int j = 0; j < stat.size(); j++){
        ans = (ans + ( ( (stat[ind[j]] * base) + mod )%mod) + mod) % mod;
        base = (base + multiplier + mod)%mod;
      }
      multiplier = (multiplier * 50 + mod)%mod;
    }
    return static_cast<int>(ans);
  }
};

2011-07-26

[][] TopCoder Single Round Match 513 Div.1 01:08 はてなブックマーク -  TopCoder Single Round Match 513 Div.1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:39:19.218Passed System Test121.68
5000:35:26.558Opened0.00
10000:28:17.098Opented0.00
Challenge..0.00

部屋(Room 29) 15位,全体 530位

Rating : 1513 → 1450 (-63)

 プラスマイナス1のズレ恐怖症.

250 YetAnotherIncredibleMachine

問題文

 問題文

方針

 各プラットフォームの取りうる位置の個数を,すべて掛け合わせれば答えになるので,各プラットフォームを個別に考えます.マウントポイントの左右それぞれ最も近い位置に落ちるボールのみがプラットフォームの配置数に影響するので,まずそれらを求め,場合の数を(右側のボールの位置)-(左側のボールの位置)を元にして計算しました.

 場合の数を直接計算しなくてもプラットフォームの位置を全通り試し,落ちてくるボールにぶつかる事がない位置を数え上げる方法でも間に合います(計算量 O(プラットフォームの数 * プラットフォームの長さ * ボールの数)).

コード例

 意外と場合分けが面倒で,プラスマイナス1のズレを修正するのに苦労しました.

#include <string>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <cmath>
 
using namespace std;
 
int mod = 1000000009;
 
class YetAnotherIncredibleMachine {
public:
  int countWays(vector <int> mount, vector <int> length, vector <int> balls) {
    int n = mount.size();
    int m = balls.size();
    long long  ret = 1;
 
    for(int i = 0; i < n; i++){
      long long  count = 1;
      int leftmost = -50001;
      int rightmost = 50001;
      bool flag = false;
      for(int j = 0; j < m; j++){
        if(balls[j] == mount[i]){
          flag = true;
          break;
        }
        if(mount[i] < balls[j]){
          if(balls[j] < rightmost){
            rightmost = balls[j];
          }
        }else{
          if(leftmost < balls[j]){
            leftmost = balls[j];
          }
        }
      }

      if(flag){
        count = 0;
      }else if(rightmost - leftmost <= length[i]){
        count = 0;
      }else{
        int buf = min(rightmost - leftmost , length[i]+1);
        int right = min(mount[i], rightmost - 1 - length[i]);
        buf = min(buf, right - leftmost);
 
        int left = max(mount[i], leftmost + 1 + length[i]);
        buf = min(buf, rightmost - left);
        count = buf;
      }
      ret = (ret * count) % mod;
    }
    return (int)ret;
  } 
};