Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-03-14

[][] Manthan 2011 01:08 はてなブックマーク -  Manthan 2011  - 練習帳

問題一覧:Dashboard - Manthan 2011 - Codeforces

結果:Standings - Manthan 2011 - Codeforces

=.ABCDE
--2:382:24---
574+0/-0150424---

部屋内18位,全体249位

Rating:1608→1637

上がるとは思わなかったです

A. Partial Teacher

要約

 長さ n-1 の文字列 s が与えられている。次の条件を満たすような数列 a のうち,合計が最小となるものを求めよ。

  • すべての i で a[i] > 0 ( i = 0, 1, .. n-1)
  • s[i] == '=' なら a[i] == a[i+1]
  • s[i] == 'L' なら a[i] > a[i+1]
  • s[i] == 'R' なら a[i] < a[i+1]

 nは 2 以上 1000 以下,条件を満たす a の存在は保証されている。

方針

 例えば s = "L===R" の時の真ん中部分のように,左右どちらを見ても自分より大きい数が入る場合,その部分は取りうる値のうち最小の 1 を割りあてます。しかしa[i] が 1 で s[i] が R のときに a[i+1] は 2 とは限りません。例えば s = "=RLL" のときは a = 1321 です。1 と 1 に挟まれた部分は

a 1 ? ? ? ? ? ? 1
s  R R R R L L L 

のように左側に R ,右側に L が揃っているという形かこれに = がいくつか挿入された形になっているので,R と L の数うち大きい方がこの区間での最大の数です。

コード (c++)
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(){
  int n;
  while(cin >> n){
    string s;cin >> s;
    vector<int > a(n);
    for(int i = 0; i < n; i++){

      // 左側から探索する
      int countl = 0;
      for(int j = 0; j < i; j++){
	if(s[j] == 'L') countl =0;
	else if(s[j] == 'R') countl++ ;	
      }

      // 右側から探索する
      int countr= 0;
      for(int j = n-1; j >= i ; j--){
	if(s[j] == 'R') countr =0;
	else if(s[j] == 'L') countr++ ;	
      }

      cout << max(countl, countr) + 1 << " ";
    }
    cout << endl;
  }
  return 0;

 提出されたコードを見ると,全ての数が 1 の状態からスタートして,「条件を満たしていない部分を修正する」という操作を,すべての部分が条件を満たすまで繰り返すというアルゴリズムが多かったです。

コード(c++,コンテスト外)
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

int main(){
  int n;
  while(cin >> n){
    string s;cin >> s;
    vector<int> a(n,1);
    bool flag = true;
    while(flag){
      flag = false;
      for(int i = 0; i < n-1; i++){
	if(s[i] == '=' && a[i] != a[i+1]){
	  a[i] = a[i+1] = max(a[i], a[i+1]);
	  flag = true;
	}else if(s[i] == 'R' && a[i] >= a[i+1]){
	  a[i+1] = a[i] + 1;
	  flag = true;
	}else if(s[i] == 'L' && a[i] <= a[i+1]){
	  a[i] = a[i+1] + 1; 
	  flag = true;
	}
      }
    }
    for(int i = 0; i < n; i++){
      cout << a[i] << " ";
    }
    cout << endl;
  }
  return 0;
}

 ただ,これでも flag を true にした所で一緒に break もしてしまうと,L が999個並ぶケース(test case 6)で TLE を起こしてしまいます。実際それで A 問題が落ちた人も多いようです。

B. Restoration of the Permutation

要約

 長さ n の数列 A と n 以下の正数 k から長さ n の数列 B が B[i] = #{j | 1<= j <= n , i + k <= a[j]} として作られている。n, k, B が与えられている。条件を満たす A のうち,辞書式順序で最小のものを答えよ。

 n は 1 以上 1000 以下,k は 1 以上 n 以下,条件を満たす A は存在する事は保証されている。

方針

 自分よりも大きい数同士の前後関係がもし決まっていたら,自分自身を差し込める位置の候補が決まるので,候補中の一番左側の部分に差し込みます。その後自分よりも小さな数をどこに差し込んでも条件が崩れる事はないので。条件を満たすように大きい数から順に数列に差し込んでいけば良いです。例えば,最初のテストケースならば A を次のように作れます。

5
4 5
4 5 3
4 5 2 3
4 1 5 2 3
コード(c++)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
  int n;
  while(cin >> n){
    int k; cin >> k;
    vector<int> b(n);
    for(int i = 0; i < n; i++){
      cin >> b[i];
    }
    vector<int> ans;
    for(int i = n-1; i >= 0; i--){
      if(b[i] == 0){
	ans.insert(ans.begin(), i + 1);
	continue;
      }
      for(int j = 0;j < n; j++){
	if(ans[j] >= i + 1 + k) b[i]--;
	if(b[i] <= 0 ){
	  ans.insert(ans.begin() + j + 1, i + 1);
	  break;
	}
      }
    }
    for(size_t i = 0; i < ans.size(); i++){
      cout << ans[i] <<  " ";
    }
    cout << endl;
  }
  return 0;
}

C. Sequence of Balls

 未解決です

D. Optical Experiment

要約

 1 から n までの置換が 2 組与えられている。2 つを横書きにして上下に並べ,同じ数同士を直線で結ぶ(n 本の直線が引ける)。n 本の直線の部分集合で条件「どの直線もその部分集合に属する自分以外のすべての直線と交わっている」を満たすものを考える。この条件を満たす部分集合のうち要素数の最大のものの要素数を答えよ。

 n は 1 以上 10^6 以下。

方針

 「2 本の光線が交差する <=> 2点間で枝が伸びている」として無向グラフを描くと最大クリークを求める問題になりますが,これはNP困難なので n が大きい今の問題では使用できません。

 一方の置換を逆順にすると最長共通部分列問題そのものになります。そのままのアルゴリズムでは O(n^2) かかってしまいますが,これを最長増加部分列問題に帰着させると,O((n+r) log n ) ( r = # {(i,j) | a[i] = b[j] } ) のアルゴリズムとなり,今考える数列が置換なので,さらに O(nlog n) にまで落ち,制限時間に間に合います。

コード(c++,コンテスト外)
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>

using namespace std;

int main(){
  int n;
  while(cin >> n){
    vector<int> a(n);
    vector<int> b(n);
    for(int i = 0; i < n; i++){
      int x; cin >> x; x--;
      a[x] = i; // look up table : a[p] = q => p は最初の数列で q 番目
    }
    for(int i = 0; i < n; i++){
      int x; cin >> x; x--;
      b[i] = a[x]; // ref : b[p] = q => a[p] は2番目の数列で q 番目
    }
    reverse(b.begin(), b.end());    
    vector<int > dp(n,INT_MAX);

    // 最長増加部分列問題を解く
    for(int i = 0; i < n; i++){
      *lower_bound(dp.begin(), dp.end(), b[i]) = b[i];
    }
    cout << lower_bound(dp.begin(), dp.end(), INT_MAX) - dp.begin() <<endl;
  }
  return 0;
}

E. Save the City!

 読んでいません


コンテスト中

 A 問題を始め 7 分くらいで提出できた。意気揚々と B 問題に進むも,詰まってしまう。全探索はできないから適当なルールを決めて大きい方 or 小さい方から数を挿入していくのだろうと漠然とは思うものの,具体的な方法にまで帰着できない。その時点で D 問題を提出していた人がいたので D 問題も読んでみる事にする。「2 本の光線が交差する <=> 2点間で枝が伸びている」として無向グラフを描けば,最大クリーク問題に帰着できるので調べてみる・・・NP困難?と言う事は何か使ってない条件から問題を簡単にするのかな。でもそもそも頂点の数が 10^6 だから 2 本の光線を選んで全探索するだけでも TLE になる,この方針ダメなのか。少し考えた後で残りの問題も見てみる。C 問題,編集距離,正確に実装できる自信がない。E 問題,図がたくさんあり禍々しい雰囲気を感じる。B, D を解く事方針に決める。

 開始 30 分頃に A 問題を Hack される。提出した解答では隣同士の生徒がもらえるタフィーの差は高々 1 個となっているけれど,これには例えば

9
L=LR=LL=

のような反例がある事に気づく。 部屋の様子を見ると他の人もかなり落とされていている。「Harry Potterの再来か?」と怖じ気づき A 問題には触れない事を決める。

 その後 1 時間半程度 B と D を半々ずつ考えて, B を試行錯誤しながら完成させる。自分の実力では残り 30 分で D を解くのは難しいだろうと考え A 問題に戻る。ハックされた後ぼんやりと考えたアイデアで組み提出する。

 A, Bをロックする。他の人の A 問題のコードを見ると一番多かったのが上記の 2 つ目のコードだった。これは自分にはない発想だった。結局 1 個もハックできずにそのまま終了。自信はなかったが A, B 両方通っていた。