ICPC2014 国内予選

ICPC

だめでした

チームC++2zとして参加しました。結果は2問だけ解いて75位でした。
http://icpc.iisf.or.jp/2014-waseda/domestic/results/

先輩の研究室チームがおそらく予選通過する様で何よりです。

また来年がんばります。

過程

@LazyMiiに突っ込みをもらいながら僕(@tubo28)が実装し、その間に@menphimに他の問題を読んでもらうという作戦でした。

開始前

チームメイト3人共14:30に授業が終わる。ディスプレイや本番中に食べるお菓子を会場に運ぶ。 院生チーム(Undefind Iketeru Methods)の先輩から差し入れのドーナツをもらう。

練習セッションのJ問題を終了30秒前にACする。

会場の準備は大方後輩がやっていてくれたが、プリンタの準備をしていたら開始時間ギリギリになった。

開始

@LazyMiiとAを読む。商品がたくさんあると勘違いしてA問題からDP？？？と焦ったが@LazyMiiに2つしか無いと訂正される。
制約が小さいので2つの商品の税抜き価格で全探索する。

A AC(12分)

Bの説明を聞く。消す操作と落とす操作を別々に実装し、消せなくなるまで無限ループを回す方針で解く。落とすときにqueueかstackを使うと楽そうだねという話をする。
2次元配列のインデックス[i][j]が逆になっていたりして詰まるけど無事AC。

B AC(38分)

@menphimにCの説明を聞く。二分探索するのが良さそう(思考停止)と初見で思い、幾何ライブラリも持ち込んでいたのでその方針で取り掛かる

具体的には、建物のてっぺんを下底として、高さが十分に大きい長方形で空の部分を敷き詰める。 円がその全ての長方形と共通部分を持たないような円の中心のy座標の最大値を二分探索する。

@LazyMiiにライブラリを読み上げてもらいながら円と長方形の当たり判定を実装する。が、自分の勘違いで写し間違えていたり、trueとfalseを逆にしていたりで盛大にバグる。

@LazyMiiといっしょにデバッグするも細かいバグが次々見つかり、更に初めに考えた方針自体が少し間違っていることに気づき、訳が分からなくなり、終了時間になってしまう。

デバックしている最中に@menphimがDが15分で解けるかもしれないし解けないかもしれない(?)と言ってくれたけど、苦手な文字列の問題だったので断ってしまった。

Eもグラフだから見てと言われて目を通したけど、1回しか通らない経路をどうにかして決めた後何かするんだろうなーと思いつつも大事な部分は分からなかったので、Cに集中したほうがいい気がして放置してしまった。

反省

コンテスト後のタイムラインで、Cの頭いい解き方を自称頭がついていないclimpetさんに教えてもらいほえーっとなる。(上位チームはみんなこれらしい)さらに、Dはよく考えたら正しくエンコードできたのをvectorに突っ込みながらbitで全探索して最後にソートする愚直な方法で十分だし、Eも初めだけ合ってたのでアイデアを説明して@menphimに詳しく考えてもらえばよかったなと思ったり、後悔ばかりだった。
変な解法に嵌って抜け出せなくなる負のスキルが発動して、それでもどうにか出来る実装力もなかった。精進します。

ソースコード

A

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

using namespace std;

#define loop(i,a,b) for(int i=(a); i<int(b); i++)
#define rep(i,b) loop(i,0,b)

int main(){
    int x,y,s;
    while(cin >> x>>y>>s && x|y|s){
        int ans=-1;
        for(int i=1;i<=1000; i++){
            for(int j=1;j<=1000; j++){
                if(i*(x+100)/100 + j*(x+100)/100 > s) break;
                if(i*(x+100)/100 + j*(x+100)/100 != s) continue;
                ans = max(ans, i*(y+100)/100 + j*(y+100)/100);
            }
        }
        cout << ans << endl;
    }
}

B

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define loop(i,a,b) for(int i=(a); i<int(b); i++)
#define rep(i,b) loop(i,0,b)

typedef vector<int> vi;
typedef vector<vi> vvi;

int erase(vvi& g){
    int h=g.size();
    int res=0;
    rep(y,h){
        for(int x=0; x<5; x++){
            int t=g[y][x];
            if(t==0) continue;
            int xx=x;
            for(;xx<5;xx++){
                if(g[y][xx]==t) continue;
                else break;
            }
            int w=xx-x;
            if(w>=3){
                for(int ix=x;ix<xx; ix++){
                    g[y][ix]=0;
                }
                res+=w*t;
            }
        }
    }
    return res;
}

void fall(vvi &g){
    int h=g.size();
    queue<int> gg[5];

    for(int i=h-1; i>=0; i--){
        for(int j=0; j<5; j++){
            if(g[i][j]==0) continue;
            gg[j].push(g[i][j]);
        }
    }
    
    vvi ng(h,vi(5));
    rep(j,5){
        int i=h-1;
        while(gg[j].size()){
            ng[i--][j]=gg[j].front();
            gg[j].pop();
        }
    }
    g=ng;
}

int main(){
    int h;
    while(cin>>h && h){
        vvi g(h,vi(5));
        rep(i,h)rep(j,5)cin>>g[i][j];
        int ans=0;
        while(1){
            int t = erase(g);
            ans += t;
            if(t==0) break;
            fall(g);
        }
        cout << ans << endl;
    }
}

はーーー…