chigichan24に人権はあるだろうか,いやない

競技プログラミングやってます。

PCK2014予選敗戦記

こんばんは.chigichanです.

今日はPCK2014の予選に参加していました.
結果から行くと確実に本戦はないです.

問題とかを振り返ってみる.

1問目 椅子の総数

  • わたしが解いた.
  • やるだけ.
  • よく問題を読まなかったけど多分2つの積を出すだけだと分かる.
  • #includeを震えながら書く.
  • 余裕でsample通る -> AC
  • やったぜ.

コード

#include<cstdio>
using namespace std;
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d\n",a*b);
    return 0;
}

2問目 お財布メタボ診断

  • これも私が解いた.
  • やるだけ.
  • 適当に硬貨の配列をとってかけてやるだけ.
  • 1000以上だからif文は >= だよなとか思いながら書く.
  • sample通って提出 -> AC
  • お.いいねー.

コード

#include<cstdio>
using namespace std;
int a[]={1,5,10,50,100,500};
int main(){
    int b[10];
    for(int i = 0; i < 6; i++){
        scanf("%d",&b[i]);
        b[i] *= a[i];
    }
    int sum =0;
    for(int i = 0; i< 6; i++){
        sum += b[i];
    }
    if(sum >= 1000)puts("1");
    else puts("0");
    return 0;
}

3問目 残り物には福がある

  • 相方君が解いた.
  • 剰余算するだけ?らしい.
  • さくっと解いてAC
  • この時点で2位だったらしい(あとから聞いた).
  • この間に私は4の解法を考えて、紙にコーディングしていた.

コード

#include<cstdio>
using namespace std;
int main(void){
    int n,k,p; scanf("%d",&n);
    for(int i = 0;i < n;i++){
        scanf("%d%d",&k,&p);

        if(k%p != 0) printf("%d\n",k%p);
        else printf("%d\n",p);
    }
    return 0;
}

4問目 路線バスの時刻表

  • 私が解いた.
  • 時間が与えられるので(重複あり)早い順に並び替える.
  • 適当にpair作って解く.
  • 重複有りなのをすっかり忘れていたがsampleにあったので助かった.
  • 適当にmemoする.
  • sample通ってAC
  • やるだけ(とか言ってたら競技終了後ふざけんな的なことをある方から言われた).

コード

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define PB push_back
#define fi first
#define se second
#define mkpr make_pair
#define reps(i,j,k) for(int i = j; i <k; i++)
#define rep(i,j) reps(i,0,j)
typedef pair < int , pair < int ,int > > P;
bool memo[23*60+60];
int main(){
    int n;
    vector < P > M;
    scanf("%d",&n);
    rep(i,n){
        int a,b;
        scanf("%d %d",&a,&b);
        if(memo[a*60+b]++)continue;
        M.PB(mkpr(a*60+b,mkpr(a,b)));
    }
    int m;
    scanf("%d",&m);
    rep(i,m){
        int a,b;
        scanf("%d %d",&a,&b);
        if(memo[a*60+b]++)continue;
        M.PB(mkpr(a*60+b,mkpr(a,b)));
    }
    stable_sort(M.begin(),M.end());
    rep(i,M.size()){
        printf("%d:%02d%c",M[i].se.fi,M[i].se.se,i == M.size()-1?'\n': ' ');
    }
}
  • 今見るとコードが汚い.

5問目 鉄道路線

  • この時点では問題読んでいなかった.
  • 相方氏にこんな感じの関数書いてと言われて少し書いた.
  • 結局使わなかったらしい.
  • バグる.
  • バグった時は「n分ほしいです」と宣言してそれが認められたら、その時間だけデバッグをし

それでも直らなかった場合はこれを繰り返す.というように決めていたので彼は数字を宣言.

  • 直らなかったらしい&6問目は実装ゲーとわかったのでわたしと交代.

6問目 フロッピーキューブ

  • シミュレートするだけ.
  • 幅優先探索みたいなノリ.
  • memoしなくてよかったらしいが一応した.
  • キューブの遷移のルールをひたすら配列に書き込む.
  • これはバグったらつらいやつだとすぐに分かる.
  • コードを書いて実行したらバグった.
  • つらい><
  • デバッグのn分を宣言し、それでもわからなかったので、相方氏に交代.

5問目 鉄道路線

  • なんとかコードができたらしい.
  • 提出 -> WA
  • 初WA.
  • え(困惑)みたいになる.
  • 解法違うんじゃね?みたいになってとりあえず先に6問目を詰めようとなる.

6問目 フロッピーキューブ

  • 面が揃ったかどうかの判定が1ずつずれていた.
  • 側面の色を入れ替えるのを忘れていた.
  • の2つを気づいてsampleが通る -> 提出 -> AC
  • やったぜベイビー!
  • 順位表を見る.自分らが8位?(記憶が曖昧)で何個か上に久留米のチームがいる.
  • とりあえず7を見てみる.

コード(閲覧注意)

#include<cstdio>
#include<algorithm>
#include<vector>
#include <iostream>
#include <map>
#include <queue>
using namespace std;
#define PB push_back
#define fi first
#define se second
#define mkpr make_pair
#define reps(i,j,k) for(int i = j; i <k; i++)
#define rep(i,j) reps(i,0,j)
typedef pair<int,int> Pii;
class data{
    public:
    int cnt;
    int state[32];
    data(){}
    data(int _cnt,int _state[32]){
        cnt = _cnt;
        rep(i,32){
            state[i] = _state[i];
        }
    }
};
string getIndex(int array[32]){
    string str="";
    rep(i,30){
        str += (array[i]+'0');
    }
    return str;
}
vector <Pii> chenge[4];
bool check(int array[32]){
    rep(i,8){
        if(array[i] != array[i+1])return false;
    }
    reps(i,9,11){
        if(array[i] != array[i+1])return false;
    }
    reps(i,12,14){
        if(array[i] != array[i+1])return false;
    }
    reps(i,15,17){
        if(array[i] != array[i+1])return false;
    }
    reps(i,18,20){
        if(array[i] != array[i+1])return false;
    }
    reps(i,21,28){
        if(array[i] != array[i+1])return false;
    }
    return true;
}
int main(){


    chenge[0].PB(Pii(0,23));
    chenge[0].PB(Pii(3,26));
    chenge[0].PB(Pii(6,29));
    chenge[0].PB(Pii(9,20));
    chenge[0].PB(Pii(15,17));

    chenge[1].PB(Pii(2,21));
    chenge[1].PB(Pii(5,24));
    chenge[1].PB(Pii(8,27));
    chenge[1].PB(Pii(11,18));
    chenge[1].PB(Pii(12,14));

    chenge[2].PB(Pii(0,27));
    chenge[2].PB(Pii(1,28));
    chenge[2].PB(Pii(2,29));
    chenge[2].PB(Pii(14,15));
    chenge[2].PB(Pii(20,18));

    chenge[3].PB(Pii(6,21));
    chenge[3].PB(Pii(7,22));
    chenge[3].PB(Pii(8,23));
    chenge[3].PB(Pii(12,17));
    chenge[3].PB(Pii(9,11));

    int n;
    scanf("%d",&n);
    while(n--){
        map < string , int >  memo;
        int ini[32]={0};
        rep(i,30){
            scanf("%d",&ini[i]);
        }
        int ans = -1;
        queue < data > Q;
        Q.push(data(0,ini));
        while(!Q.empty()){
            data d = Q.front();Q.pop();
            if(check(d.state)){
                ans = d.cnt;
                break;
            }
            rep(i,4){
                rep(j,5){
                    Pii a = chenge[i][j];
                    swap(d.state[a.fi],d.state[a.se]);
                }
                if(memo[getIndex(d.state)]==0){
                    memo[getIndex(d.state)] = 1;
                    Q.push(data(d.cnt+1,d.state));
                }
                rep(j,5){
                    Pii a = chenge[i][j];
                    swap(d.state[a.fi],d.state[a.se]);
                }
            }
        }
        printf("%d\n",ans);
    }

    return 0;
}

7問目 バトンリレーゲーム

  • よくわからない.単純にシミュレートしたら落ちそう.
  • 5を解こうとなる.

5問目 鉄道路線

  • わたしがグラフの問題に落とす(嘘解法).
  • 書いたあとにやっぱりダメじゃんとなる.
  • 順位表がこのあたりで凍結.
  • 自分らは11位になっていた.
  • 上で灘が3チームいたのでギリ10位入っていたので勝ったか?となる.
  • 結局、はじめの方針は間違っていたことが判明する.
  • 他の部内のチームに抜かれる.


競技終了

Ω\ζ°)チーン 5AC (1WA)

  • 予想だが、部内3位(県内3位(九州3位)).
  • 全体順位は多分15前後でしょう.
  • 地域枠狙える順位だったが、同じ学校から2チームという制約にひっかかるので

予選敗退です.

まとめ

  • つらい.
  • けど去年とはまったく違う悔しさ.
  • Pelkiraくんの予想どおり部内戦となった.
  • JOIの夏季セミの人たちと本戦で会いましょうと言っていたのに果たせない.
  • 本当に申し訳ない.
  • わがままなわたしとペアを組んでくれたひのきくん、本当にありがとう.
  • 去年よりは問題は良かったと思います.
  • 本戦行く人は予選落ちの人の分も頑張ってください.
  • もうひとつの本戦では上位を狙います.
  • また、テスト勉強ががんばります.
  • それと競技プログラミングはもちろん続けます.できなくても楽しいので.
  • またいろんな人と会えるように精進します.
  • 様々な形でわたしと関わってくれた方々ありがとうございました.