読者です 読者をやめる 読者になる 読者になる

たにしきんぐダム

プログラミングやったりアニメやゲーム見たり京都に住んだりしてます

CODE THANKS FESTIVAL A日程に参加してきました!

CODE THANKS FESTIVAL A日程に参加してきました!!

CODE FESTIVAL2014 | RECRUIT HOLDINGS -リクルートホールディングス

CODE THANKS FESTIVALは、予選に参加したけど本戦に参加できなかった人のためのオンサイトのコンテストで、東京のテレコムセンターで開催されました。

めちゃくちゃ楽しかった!
競技プログラミング自体CODE FESTIVAL予選がきっかけで始めたようなものだったけど来年は本戦に出場したい!と思えるくらいやる気を起こしてくれるイベントだった。
交通費だけでなくTシャツやら何やら頂いて、企業って凄いなぁと思った。

Tシャツ、かわいい。
f:id:tanishiking24:20141212200040j:plain:w300

コンテスト

コンテストは3時間で8問、問題は比較的易しめとなっていたそう(と言っても最後の方は全然難しかった…)

コンテスト問題はこちら
Welcome to code thanks festival 2014 A日程(オープンコンテスト) - code thanks festival 2014 A日程(オープンコンテスト) | AtCoder
特典として

  • 1位~5位には高級焼き肉招待
  • 6位~10位には焼き肉招待
  • 500点以上にはトートバッグプレゼント!
  • 各問題について一番最初にACした人にはAmazonギフトカード3000円分

が貰えるということで、僕はトートバッグを狙っていくことにしました。

結果は5完500点でギリギリトートバッグGET!!
f:id:tanishiking24:20141212215342j:plain:w300

嬉しいけど悔しかった。精進します。
コードは下の方にあります。

懇親会

何人かと仲良くなれたりchokudaiさんと一緒に写真撮って貰えたり、寿司にピザに食べれて最高だった。
書道コーディングもあったり
f:id:tanishiking24:20141212215735j:plain:w400
emacs vs vim戦争が起こってた。

DDRやらもありました。
f:id:tanishiking24:20141212215729j:plain:w300
踊ってるのはchokudaiさんです。

問題の難易度も丁度よくて凄く楽しかったです!
これを機に競技プログラミングどんどんやっていって来年は本戦出場したい…!

コード

A問題

2a*4b

B問題

ソートしてから大きい順に足していった。

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

int main(){
  int n;
  int machine[3];
  cin >> n >> machine[0] >> machine[1] >> machine[2];
  
  sort(machine,machine+3,greater<int>());
  int badges=0,i=0,ans=0;
  while(true){
    badges +=machine[i];
    if(i==2) i=0;
    else i++;
    ans++;
    if(badges>=n) break;
  }
  cout << ans << endl;
  return 0;
}

C問題

これも計算

#include <iostream>
using namespace std;

int main(){
  int n,m;
  cin >> n >> m;
  int point[n];
  int res=0;
  for(int i=0;i<n;i++) cin >> point[i];
  for(int i=0;i<m;i++){
    int s;
    cin >> s;
    s--;
    res+=point[s];
  }
  cout << res << endl;
  return 0;
}

D問題

グラフ問題かと思ったら違った。
中学校の数学の問題みたいな感じに定期券の区間と、駅同士の区間を比較した。

#include <iostream>
using namespace std;

int main(){
  int N,Q;
  cin >> N >> Q;
  int a,b,s,t;
  for(int i=0;i<Q;i++){
    cin >> a >> b >> s >> t;
    if(a <= s && b >= s && b <=t)
      cout << (t-b)*100 << endl;
      
    else if(a >= s && a <=t && b >=s && b <=t)
      cout << (a - s + t - b)*100 << endl;

    else if(a >= s && a <=t && b >= t)
      cout << (a-s)*100 << endl;

    else if(a <= s && b >= t)
      cout << 0 << endl;

    else
      cout << (t-s)*100 << endl;
  }
  return 0;
}

E問題

1.まずは手順通りにやった状態にして
2.それから各p番目の手順の反対の動作をし
 2.1.もし最終的に南を向いていた石像の数が一致したらフラグをたてる
 2.2.もとに戻す
3.pがNより小なら2に戻る。

計算量が何とか〜って言ってたけど何故かこれで通った。
計算量意識してもっとすっきりしたコード書きたい。
めちゃくちゃ汚い

#include <iostream>
#include <vector>
using namespace std;

int main(){
  int R,C,M,N;
  cin >> R >> C >> M;
  cin >> N;
  int statue[R][C];
  int r1[N],r2[N],c1[N],c2[N];
  vector<int> pos_proc;
  
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++) statue[i][j] = 0;
  }
  
  for(int p=0;p<N;p++){
    cin >> r1[p] >> r2[p] >> c1[p] >> c2[p];
    r1[p]--; r2[p]--; c1[p]--; c2[p]--; //0base
    for(int i=r1[p];i<=r2[p];i++){
      for(int j=c1[p];j<=c2[p];j++) statue[i][j]++;
    }
  }

  //何番目を忘れた?
  for(int p=0;p<N;p++){
    for(int i=r1[p];i<=r2[p];i++){
      for(int j=c1[p];j<=c2[p];j++) statue[i][j]--;
    }
    int sauth = 0;
    for(int i=0;i<R;i++){
      for(int j=0;j<C;j++){
        if(statue[i][j] % 4 == 0) sauth++;
      }
    }
    if(sauth == M) pos_proc.push_back(p+1); //1base
    
    //試したら元に戻す
    for(int i=r1[p];i<=r2[p];i++){
      for(int j=c1[p];j<=c2[p];j++) statue[i][j]++;
    }
  }
  
  for(int i=0;i<pos_proc.size();i++) cout << pos_proc[i] << endl;
  return 0;
}

F問題

bool d[i][j]というiはjより上位という表を作る。
 0列目(選手1が負けた相手についてはtrueになってる)を調べて上位陣リストupperに追加。
 追加した分だけrankを足して、追加した人についてはusedフラグをたてる。
上位陣リストからひとつとって、その列を調べる〜

みたいな事をやった。
グラフにして深さ優先,深さ優先で良かったみたいだけど思いつかなかった…

本番の時は下から9行目でuppers.insert(uppers.end(),i)にして、末尾から一つ前に挿入するつもりが、末尾に挿入するというアホなミスをしてて通らなかった…。

#include <iostream>
#include <vector>
using namespace std;

int main(){
  int n,m;
  cin >> n >> m;
  
  bool d[n][n]; //iはjより上位
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++) d[i][j] = false;
  }

  int a,b;
  for(int i=0;i<m;i++){
    cin >> a >> b;
    a--; b--;
    d[a][b] = true;
  }

  int rank = 1;
  vector<int> uppers;
  bool used[n];
  fill(used,used+n,false);
  used[0] = true;

  for(int i=0;i<n;i++){
    if(d[i][0] == true){
      rank++;
      uppers.push_back(i);
      used[i] = true;
    }
  }

  while(!uppers.empty()){
    int j = uppers.back();
    for(int i=0;i<n;i++){
      if(d[i][j] == true){
        if(used[i] == true) continue;
        rank++;
        uppers.insert(uppers.end()-1,i);
        used[i] = true;
      }
    }
    uppers.pop_back();
  }
  cout << rank << endl;
  return 0;
}

G,Hもそのうち解きます!!