Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-06-20

[][] Codeforces Beta Round #74 Div.2 08:50 はてなブックマーク -  Codeforces Beta Round #74 Div.2 - 練習帳

問題一覧:Dashboard - Codeforces Beta Round #74 (Div. 2 Only) - Codeforces

結果:Standings - Codeforces Beta Round #74 (Div. 2 Only) - Codeforces

=.ABCDE
--0:070:19-3--
1410+0/-0486924---

部屋内4位(Room 12),全体150位

Rating:1541 → 1557 (+16)

 YandexやICPCなどのイベントが続きご無沙汰だったCodeforces.張り切って臨んだのですが気づいたら朝でした.レート下がらなくてよかったです.

A. Cableway

要約

 起点に赤,緑,青,赤,緑,青・・・のケーブルカーが1分ごとに到着する.ケーブルカーは30分で終点に達する.各々のケーブルカーには2人が乗れる.r, g, b人の大学生がおり,それぞれ赤,緑,青のケーブルカーにしか乗らない.全員が終点に達するのに要する時間を答えよ.r, g, bは0以上100以下.r+g+bは1以上.

方針

 赤,緑,青それぞれのケーブルカーが必要な個数を求め,その3倍の時間と,到着に要する時間と,補正項を足す.

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

using namespace std;

int main(){
  int r, g, b;
  while(cin >> r >> g >> b){
    int res = 0;
    int rr = (r+1)/2;
    int gg = (g+1)/2;
    if (rr <= gg) res = 1;
    int bb = (b+1)/2;
    if (rr<=bb && gg <= bb) res = 2;
    cout<<  (max(max(rr, gg), bb)-1)* 3  + res + 30 << endl;
  }
}

B. African Crossword

要約

 n * mのクロスワードがある.一つのマスには一つのアルファベットが書かれており,黒マスはない.このクロスワードから次の条件を満たす文字を除き,残った文字を一列に並べる.除外する条件は「自分と同じ列or同じ行に自分と同じ文字がある(自分自身は除く)」.また,一列に並べる順序は,もとのクロスワードでより上にあるものが先に,同じ行にある場合はより左にあるものが先になるようにする.n, mは1以上100以下.

方針

 全探索してもO(n*m*max(n, m))なので,愚直に調べれば良い.

解答

 初め(i, j)に対し,(ii, j), (i, jj) (0 <= ii < n, 0 <= jj < m, ii ≠ i, jj ≠ j)の中に重複があるかが条件かと勘違いしました.残念.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>

using namespace std;

typedef long long ll;

int main(){
  int n, m;
  while(cin >> n >> m){
    vector<string> s(n);
    for(int i = 0;i <n;i++){
      cin >> s[i];
    }
    string ans;
    for(int i = 0;i < n;i++){
      for(int j = 0;j < m;j ++){

	for(int ii = 0;ii < n;ii++){
	  if(i == ii ) continue;
	  if(s[i][j] == s[ii][j]){
	    goto next;
	  }
	}
	for(int jj = 0;jj < m;jj++){
	  if(j == jj) continue;
	  if(s[i][j] == s[i][jj]){
	    goto next;
	  }
	}
	ans+=s[i][j];
      next:;
      }
    }
    cout << ans << endl;
  }
}

C. Robbery

要約

 n個の金庫が一列に並んでおり,i番目の金庫の中にはa[i]個のダイヤが入っている.そこから泥棒がダイヤを盗む.まず,泥棒がダイヤを最大m回移動させる.移動のさせ方は次の3通りのどれかで,混在させても良い.

  • 任意の金庫から任意の金庫にダイヤを1個移動させる
  • 任意の金庫からポケットにダイヤを1個移動させる
  • ポケットから任意の金庫にダイヤを1個移動させる

 次に警備システムがダイヤの数をチェックする.隣接する2つの金庫に入っているダイヤの数の和を求めn-1個のordered tuple得てその値が初期状態から変わらないかをチェックする.

 以上の行動を1ターンとして合計kターン行う.kターン終了時,ポケットに入っているダイヤの数の最大値を求めよ.nは1以上10**4以下,m, kは1以上10**9以下.

方針

 nが偶数の場合,隣接する金庫内のダイヤの和を変えずにダイヤを移動させる事は出来ない.例えば,ダイヤの数が

6 5 4 3 2 1

なら,例えば一番左端をp個減らしつつ,和の条件を保とうとすると,

6-p 5+p 4-p 3+p 2-p 1+p

となり,合計は元と同じ.奇数の場合は合計を減らす事が出来る.

6 5 4 3 2

なら,

6-p 5+p 4-p 3+p 2-p

とすれば警備のチェックは通る.これには奇数番目の金庫からその右隣にある偶数番目の金庫にダイヤをp個移動させ,右端にある金庫からp個のダイヤを取れば良いので(n/2+1)*p回の操作が必要.つまりp < n/2+1ではダイヤを移動させる事は出来ない.また,奇数番目の金庫に入っているダイヤの数の最小値より多くのダイヤを取る事は出来ない.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>

using namespace std;

typedef long long ll;

const int inf = 1000000;

ll mn(ll a, ll b ){
  return a > b ? b :a;
}

int main(){
  ll n, m, k;
  while(cin >> n >> m >> k){
    vector<ll> a(n);
    for(int i = 0;i <n ;i++){
      cin >> a[i];
    }
    ll ans = 0; 
    if(n % 2 == 0){
      ans = 0;
    }else{
      if(n/2 >= m ){
	ans = 0;
      }else{
	ans = inf;
	for(int i = 0; i < n;i+=2){
	  ans = mn(ans, a[i]);
	}
	ans = mn(ans, k *( m /((n/2) + 1)));
      }
    }
    cout << ans <<endl;
  }
}