CODEFESTIVAL2014 予選B

ブログの存在を忘れていた
スーパーコン本戦とかPCK予選(落ち)とか色々あったけど過去のことは忘れたな
コードフェスティバルの予選が合ったらしい(参加権ない)
予選Aは20位で1ページ目に乗ってて実力に見合わない

予選B

• 直前にキーボードの3(#)キーが壊れる
• 治らない
• なんにも準備してない
• スタート
• シャープ打てないとtweetしようとしたところで「しゃーぷ」を変換すれば出来る事が判明
• A問題FA狙うも9秒ACという人外が現れて引退
• MAXとるだけっぽい(A00:20AC)
• B問題
• 足すだけっぽい
• 書く
• ACやったね(B02:43AC)
• 順位表を確認
• D問題ACしてる人がいるからそっちを先に解こう
• Dが一番簡単という風潮??
• DP?
• 書く
• 問題誤読、なぜか増加部分列的な感じだと思ってた
• 書く
• 書けない
• 更に問題誤読
• 一瞬セグ木が頭の片隅に浮かぶけどオーダー大丈夫か？
• やめよう
• C問題読む
• 変な解法しそうだなあ
• どうせC問題
• 文字の数数えて使わないといけない数を求める
• 良い感じにやる
• 反例なんて考えられない頭だからこのまま提出
• 意外にもACしてる(C36:26AC)
• 順位逝ってしまうから保険欲しい
• 普通に数えるやつを書く(D38:59TLE部分点30)
• セグ木のやつO(nlog^2n)か
• O(10^8)くらい??
• んーー(関数電卓紛失)
• 書く
• にぶたんばぐる
• にぶたん世界一書けない
• にぶたんした後の微妙な足し算めんどい
• 番兵置こう(いらなかった)
• 提出(D63:21AC)
• 1.5sかかってる
• cinにしたらどうなるのだろう
• TLE
• 終わり(44位)

Code

A

#include<bits/stdc++.h>
using namespace std;
int main(){
  int a, b;
  cin >> a >> b;
  cout << max( a, b) << endl;
}

B

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
int main(){
  int n, k, a[100000];
  cin >> n >> k;
  int64 sum = 0;
  for(int i = 0; i < n; i++){
    cin >> a[i];
    sum += a[i];
    if(k <= sum){
      cout << i + 1 << endl;
      return(0);
    }
  }
}

C

#include<bits/stdc++.h>
using namespace std;
typedef pair< int , int > Pi;
int main(){
  string s1, s2, s3;
  cin >> s1 >> s2 >> s3;
  int cnt1[26] = {}, cnt2[26] = {}, cnt3[26] = {};
  for(int i = 0; i < 26; i++) cnt1[i] += count(s1.begin(), s1.end(), (char)('A' + i));
  for(int i = 0; i < 26; i++) cnt2[i] += count(s2.begin(), s2.end(), (char)('A' + i));
  for(int i = 0; i < 26; i++) cnt3[i] += count(s3.begin(), s3.end(), (char)('A' + i));
 
  
  int need1 = 0, need2 = 0;
  bool flag = true;
  for(int i = 0; i < 26; i++){
    if(cnt2[i] < cnt3[i]){
      need1 += cnt3[i] - cnt2[i];
      if(cnt2[i] + cnt1[i] < cnt3[i]) flag = false;
    }
  }
  for(int i = 0; i < 26; i++){
    if(cnt1[i] < cnt3[i]){
      need2 += cnt3[i] - cnt1[i];
    }
  }
  if(need1 > s1.size() / 2 || need2 > s2.size() / 2 || !flag)  cout << "NO" << endl;
  else cout << "YES" << endl;
}

D

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair< int , int > Pi;
int h[100002];
#define MAX 400000
int n, seg[MAX * 2 - 1];
const int INF = 1 << 30;
void update( int i, int x){
  i += n - 1;
  seg[i] = x;
  while(i > 0){
    i = ( i - 1 ) / 2;
    seg[i] = max( seg[i * 2 + 1], seg[i * 2 + 2]);
  }
}
int query( int a, int b, int k = 0, int l = 0, int r = n){
  if( r <= a || b <= l ) return -1;
  if( a <= l && r <= b ) return seg[k];
  int vl = query( a, b, k * 2 + 1, l, (l + r) / 2);
  int vr = query( a, b, k * 2 + 2, (l + r) / 2, r);
  return max( vl, vr);
}
void init( int& size){
  n = 1;
  while( n < size ) n *= 2;
}
 
int main(){
  int size;
  scanf("%d", &size);
  init(size);
  h[0] = -INF;
  for(int i = 1; i <= size; i++){
    scanf("%d", &h[i]);
    update( i, h[i]);
  }
  h[size + 1] = INF;
  for(int i = 1; i <= size; i++){
    int cost = 0;
    int row = 0, high = i - 1;
    while(high - row > 0){
      int mid = (high + row + 1) >> 1;
      if(query(mid, high + 1) > h[i]){
        row = mid;
      } else {
        high = mid - 1;
      }
    }
    cost += i - high - 1;
    
    row = i + 1, high = size + 1;
    
    while(high - row > 0){
      int mid = (high + row) / 2;
      if(query( row, mid + 1) > h[i]){
        high = mid;
      } else {
        row = mid + 1;
      }
    }
    
    cost += row - i - 1;
    
    printf("%d\n", cost);
  }
}