はやし屋

競技プログラミングのメモ きたない

パソコン甲子園(PCK) 2013 予選 参加記

後輩と出場して
予選落ちしました。
問題は良問ばかりでしたが、緊張と困惑で 6AC + 4WAしました。


ソースは後から書き直したものです(考え方自体は変わってない)

方針は1~6が後輩が解いてその間に自分が後半を読むとかしてたけど、
お互い緊張しててgdgdだった...

テンプレート

#include<iostream>
#include<string>
#include<bitset>
#include<cctype>
#include<cstdlib>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<complex>
using namespace std;
 
// structure
typedef long long ll;
typedef pair < int , int > Pi;
typedef pair < int , Pi > Pii;
 
#define INF (1 << 28)
#define SQR(x) ((x)*(x))
 
//repetition
#define reps(i,j,n) for(int i = j ; i < n ; ++i)
#define rep(i, n) reps(i,0,n)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
 
// containar
#define ALL(v) (v).begin(), (v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define sz(z) (int)((z).size())
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define UNQ(s) {sort(ALL(s));(s).erase(unique(ALL(s)),(s).end());}
#define fr first
#define sc second
 
// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
 
/*
// < v > ^
const int dx[] = {-1,0,1,0,0};
const int dy[] = {0,1,0,-1,0};
 
// convert
string itos(int v) {stringstream ss;ss<<v;return ss.str();}
int stoi(string s) {int v; stringstream ss(s);ss>>v;return v;}
 
*/
 
// PROG START

1.
一週間の最高気温と最低気温を与えられての差を出す
絶対値などは気にしなくてよい

int main(){
  rep(i,7){
    int a ,b;
    cin >> a >> b;
    cout << a-b << endl;
  }
}

2.
4回チケットの種類と枚数が与えられてそれぞれの合計金額を出す
後輩ifで場合分けやってたけど添字の方が効率よくねと思いながらみていた

int main(){
  int lis[] = {6,4,3,2};
  rep(i,4){
    int a , b;
    cin >> a >> b;
    cout << lis[a-1]*1000*b << endl;
  }
}

3.
温泉チケット1枚の料金とプールチケット1枚の料金と
必要な温泉チケットの枚数とプールチケットの枚数が与えられる

条件は、
・温泉チケット5枚とプールチケット2枚で合計料金を2割引できる
・余分に買ってもよい

最低何円でいけるか

数十分かけて後輩WAした...

WAした後自分がみて場合分けめんどいからループで書いてっていって書いてもらってACした

この頃から予選落ちすんじゃねとか思い始めた

無駄ありすぎだけどまあいいか

int main(){
  int n;
   cin >> n;
   rep(i,n){
     int x , y , b , p;
     cin >> x >> y >> b >> p;
     int ret = INF;
     for(int i = 0 ; i <= 5 ; ++i){
       for(int j = 0 ; j <= 2 ; ++j){
	 int A = (b + i)*x, B = (p + j)*y;
	 if(b+i >= 5 && p+j >= 2){
	   A *=.8;
	   B *=.8;
	 }
	 ret = min(ret,A+B);
       }
     }
     
     cout << ret << endl;
   }
}

4.
景品の種類の数と
それぞれのガチャガチャの景品と個数が与えられて、
ガチャガチャやってかぶる時の最小回数をだせという問題
後輩悩んでて聞かれたけど、
自分も慌てていて頭いっぱいで悩んでしまった...
このころから頭真っ白になった

5を解いたあと解きました。

場合分けで適当にやる
後からみたら簡単ダナ〜と思った

int main(){
  int n;
  
  while(cin >> n && n){
    vector < int > v;
    rep(i,n){
      int a;cin >> a;
      if(a)v.pb(a);
    }
    sort(RALL(v));
    if(v.empty())cout << "NA" << endl;
    else if(v[0] == 1)cout << "NA" << endl;
    else {
      cout << v.size()+1 << endl;
    }
  }
}

5.
TDNシミュレーション
後輩が通した
queueを使ったらしい

int main(){
  int n;cin >> n;
  vector < int > hito(n,0);
  string v;
  cin >> v;
  int ba = 0;
  rep(i,100){
    if(v[i] == 'M'){
      hito[i%n]++;
    } else if(v[i] == 'S'){
      ba += hito[i%n]+1;
      hito[i%n] = 0;
    } else {
      hito[i%n]+=ba+1;
      ba = 0;
    }
  }
  
  sort(ALL(hito));
  
  rep(i,hito.size())cout << hito[i] << " ";
  cout << ba << endl;
}

6.
CとAとNの種類の人数が与えられて、
CCAとCANとCCCのどれかの組み合わせで1グループを作る
最大何チーム作れるか

dp書いてTLEして、
貪欲じゃん!!!となってぎりぎりにAC

あとでふるわら先輩と話して
「自明じゃん何ですぐ思いつかないの」とかいわれた

「は?」とそのときは思ったが
終わってみると自明と感じた

int main(){
  
  int n;cin >> n;
  
  rep(i,n){
    int ret = 0;
    int c , a , n;
    cin >> c >> a >> n;

    int mi = min(a,min(c,n));
    n -= mi;a -= mi;c -= mi;
    ret += mi;

    mi = min(c/2,a);
    a -= mi;c -= mi*2;
    ret += mi;

    ret += c/3;
    
    cout << ret << endl;
  }
}

7.
最初から読んでいたが真っ白でめっちゃバグらせた
コード書けなくて辛かった
僕が全て悪いです...


これも終わったあと先輩に聞いてみたが「やるだけじゃん」と言われた

これも「は?」ってなったけど家帰って書いたらそれなりに書けたので
お、そうかなって思った

終わってから適当に書いたので正誤わかんない
未だ悔やまれる><

Pi seg[1<<18];
int n , r , l;
int N;

void update(int id , int point){
  int k = id + N-1;
  seg[k].fr += point;
  seg[k].sc = -id;
  while(k){
    k = (k-1)/2;
    seg[k] = max(seg[2*k+1],seg[2*k+2]);
  }
}

void init(int size){
  N = 1;
  while(N < size)N <<= 1;
  rep(i,n)update(i,0);
}

int main(){
  cin >> n >> r >> l;
  init(n);
  int ID = 0 , t = 0;
  int sum[111111] = {};
  rep(i,r){
    int id , time , point;
    cin >> id >> time >> point;
    id--;
    update(id,point);
    sum[ID]+=time-t;
    t = time;
    ID = -seg[0].sc;
  }
  sum[ID] += l - t;
  int ret = 0;
  rep(i,n)if(sum[ret] < sum[i])ret = i;
  cout << ret+1 << endl;
}

8.9
これもうわかんない(また追加すると思われる)

追記
8:http://hayashiya.hatenablog.com/entry/2013/11/09/133755


反省会
・1~6までやるだけでは...
・7完できないとかさすがに許されない
・自分も緊張してたけど後輩それ以上にガチガチだったので、
 はやいうちにかわってもよかったなとおもった(後輩AOJ300問とか解いてて普段はめっちゃ強い)
・1年生だけチーム6完しててつえェ
・緊張に弱すぎ(絶望)
・めっちゃ悔しい
・JOIまでにはもっと頑張ります