chigichan24のお気持ち表明

おきもちを表明している

PCK2014もうひとつの本選

みなさんこんばんは~、chigichanです。

 
今日は、パソコン甲子園プログラミング部門の本選の日でした。
私は予選おちだったので、もうひとつの本選という本選の問題を5分遅れで予選落ちerで
とこうというコンテストにでていました。

結果だけ先にいうと

4AC/1WAで5位

でした。

ペアは、でした。
なるべく、時系列順に私の今日の様子を振り返りたいと思います。

include類はこちら

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cctype>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
#include <numeric>
#include <string>
#define INF 1e10
#define EPS 1e-15
const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
#define PB push_back
#define fi first
#define se second
#define rep(i,j) for(int i = 0; i < (j); i++)
#define reps(i, j, k) for(int i = j; j < k; j++)
using namespace std;
typedef long long ll;
typedef pair<int, int> Pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

12時頃

  • 昨年同様、もうひとつの本選のURLがわからない。
  • なぜか顧問から連絡が来てなかったし、当日になってURL知らないことを思い出した。
  • 昨年と同じなら予選の時と同じURLなはずなのに403が返ってきて不安になる。
  • pck2014の前にanother-とかつけてみたけど、そんなのないよと言われて不安になる。
  • 昨年はゆうくんが教えてくれたが、今年は彼も知らないらしい。
  • 沖縄のこのコンテストに出そうな人にtwitterで聞いてみる。
  • M教授が教えてくれた。
  • "圧倒的感謝"とかくだけた言葉でお礼を言いたいけど、しっかりとお礼をいう。

コンテスト10分前

  • 一度はログインできたは良かったがページにアクセスできなくなる。
  • きっと本選erの云々かんぬんで一時的にアクセス出来ないだけだろう。
  • 教室にいた後輩君が不安そうな声を上げている。

コンテスト開始

  • アクセスできないじゃないか(半ギレ
  • キレそう(キレそう
  • 鯖貧弱すぎでしょ(キレてる
  • 大体予選の時はこんなことなかったじゃないか(キレキレ
  • 後輩君が不安そうな声を上げている。
  • あ、今のうちにテンプレート書いちゃえばいいじゃん(名提案
  • ペアの子はめちゃくちゃタイプが早いので任せる
  • 15分くらいして後輩君の「入れた」という声を聞き私達のチームもアクセスする。
  • 入れた(歓喜
  • しかし、ログインした時点ですでに2完しているチームがあったりして、圧倒的に不利

1問目

  • 問題をざっくり読む。
  • 軽めの幾何かなとか思ったけど、読み進めていくともはややるだけ。
  • 私が書き始める。
  • その間にペアには2問目を読んでもらう。
  • 何度かバグらせたが、sampleが通る。
  • コードがくっそ汚い。
  • 提出->AC (00:33:00)
  • やったぜ。
//problem1
int main() {
	int n;
	scanf("%d",&n);
	int rad[] = {0,30,60,90,120,150,180};
	int dist[] = {0,100,200,300,400,500};
	rep(i,n){
		int r,t;
		scanf("%d%d",&r,&t);
		int index_t = 0;
		rep(i,7){
			if(rad[i]==t){
				index_t = i;
				break;
			}
		}
		int sub = 5*index_t + r/100;
		if(r % 100 == 0 && t % 30 == 0){
			printf("%d\n",sub);
		}	
		else if(r%100 == 0){
			int index = 0;
			rep(i,7){
				if(rad[i]>t){
					index = i;
					break;
				}
			}
			printf("%d %d\n",5*(index-1)+r/100,5*index+r/100);
		}
		else if(t%30 == 0){
			int index = 0;
			int index_t = 0;
			rep(i,7){
				if(rad[i]==t){
					index_t = i;
					break;
				}
			}
			rep(i,6){
				if(dist[i]>r){
					index = i;
					break;
				}
			}
			printf("%d %d\n",5*index_t+dist[index-1]/100,5*index_t+dist[index]/100);
		}
		else{
			int index1 = 0;
			int index2 = 0;
			rep(i,7){
				if(rad[i]>t){
					index1 = i;
					break;
				}
			}
			rep(i,6){
				if(dist[i]>r){
					index2 = i;
					break;
				}
			}
			printf("%d %d %d %d\n",5*(index1-1)+dist[index2-1]/100,5*(index1-1)+dist[index2]/100,5*(index1)+dist[index2-1]/100,5*(index1)+dist[index2]/100);
		}
	}

	return 0;
}

2問目

  • ペアに2問目がどんな感じだったかを聞くがよくわからなかったとの返答。
  • 自分も問題を読む。
  • 全探索で行けそうだが枝刈り頑張らなきゃいけない感じ。
  • なんか規則性とかありそうと示そうとするが示せない。
  • ペアは全探索が腑に落ちないらしく規則性を探し、その間に私は全探索のコードを書く。
  • 自明な枝刈りをしつつコードが出来る(01:00:00)
  • やっぱり最大ケースだと遅すぎる。
  • ペアが規則性的なものを見つけたらしい(40近くまでパターンを列挙していた)
  • この規則性のやりとりを3回くらいして最も良いと思われる規則性の発見をした。
 1  0  0  0 | 1
-1  3  0  0 | 2
 0  3  0  0 | 3
 1  3  0  0 | 4
-1 -3  9  0 | 5
 0 -3  9  0 | 6
 1 -3  9  0 | 7
-1  0  9  0 | 8
 0  0  9  0 | 9

いま1~9までのパターンを列挙した。
この時1の値は(1,-1,0)が順にループしていて、3は(3,3,3,-3,-3,-3,0,0,0)でループをしている。
これを40近くまで列挙すると、見えるのが3^nの数字は3^(n+1)周期でループをしていて、
その数字は(正,負,0)となっていることがわかる。
これをコードに起こすことで、O(logw)となった。

  • という考察に行き着くまでかなりの時間をようした。
  • さらに私がコードに起こすのを微妙にバグらせて辛かった。
  • 何度か手直しをしていたら、後輩君が2完(1WA)をしている。
  • 私達は0WAでACしないと後輩君に勝てないという恐怖と戦っていた。
  • ペアの神的なデバッグのお陰でsampleは全部とおり、手元のケースを幾つか試し、

全部通ったので提出 -> AC (02:00:00)

  • 疲れるなぁ。
//problem2
int mod[] = {3,9,27,81,243,729,2187,6561,19683,59049,177147,531441};
int start[] = {1,2,5,14,41,122,365,1094,3281,9842,29525,88574,265721};
int main() {
	int w;
	scanf("%d",&w);
	int num;
	int index = 0;
	rep(i,13){
		if(start[i]>w){
			num = start[i-1];
			index = i;
			break;
		}
	}
	string ans = "";
	rep(i,index){
		int sub = w-start[i]+1;
		sub %= mod[i];
		if(i == 0){
			if(sub == 0){
				ans += "0";
			}
			else if(sub == 1){
				ans += "+";
			}
			else{
				ans += "-";
			}
		}
		else{
			if(0 < sub && sub <= mod[i-1]){
				ans += "+";
			}
			else if(mod[i-1] < sub && sub <= mod[i-1]*2){
				ans += "-";
			}
			else{
				ans += "0";
			}
		}
	}
	reverse(ans.begin(),ans.end());
	cout << ans << "\n";

	return 0;
}

4問目

  • 私が2問目を書いている間に4問目を読んでいてくれた。
  • 2問目を解いている途中に問題の説明をしてくれたが半分くらいしか頭に入ってなかった。
  • もう一度聞くとDAGを検出するだけらしい。
  • まじかよ
  • そんなにすんなり行くはずがないんだよなぁ
  • グラフは私のほうがいいだろうということで相談されたが、DAGを求めるだけとか...
  • DPでも求められるのは知っていたが考えるのが面倒に
  • 手元に強連結成分分解のコードがある。
  • これでノード数が変化したか否かで判断すればよくね(内心なげやり)と思いタイプの早いペアにコードを写してもらう。
  • その間にうさみみのカチューシャをつけた。
  • コードが写し終わった時、すでに頭のなかでコードは書き上がっていた。
  • それを適当にタイプしていく。
  • コードが完成。->ミスってる->修正->sample全部通る。
  • これでACだったらクソモンではとか言い合う。
  • ペルきゅんたちもいいそう。
  • じゃくしぃがハマってなければいいなと思う。
  • 提出 -> AC (02:24:00)
  • 笑った & ハイタッチ!
  • この時に1桁代まで浮上したと思う。
  • うさみみ強い
//problem4
int V;
vector<int> G[MAX_V];
vector<int> rG[MAX_V];
vector<int> vs;
bool used[MAX_V];
int cmp[MAX_V];
void add_edge(int from, int to) {
	G[from].push_back(to);
	rG[to].push_back(from);
}

void dfs(int v) {
	used[v] = true;
	rep(i, G[v].size()) {
		if(!used[G[v][i]]) dfs(G[v][i]);
	}
	vs.push_back(v);
}
void rdfs(int v, int k) {
	used[v] = true;
	cmp[v] = k;
	rep(i, rG[v].size()) {
		if(!used[rG[v][i]]) rdfs(rG[v][i], k);
	}
}
int scc() {
	memset(used, 0, sizeof(used));
	vs.clear();
	rep(v, V) {
		if(!used[v]) dfs(v);
	}
	memset(used, 0, sizeof(used));
	int k = 0;
	for(int i = vs.size() - 1; i >= 0; i--) {
		if(!used[vs[i]]) rdfs(vs[i], k++);
	}
	return k;
}
bool memo[256];
int main() {
	int n;
	scanf("%d",&n);
	int cnt = 0;
	rep(i,n){
		int a,b;
		char state[128];
		scanf("%d %s %d",&a,state,&b);
		b += 100;
		V  = 200;

		if(strcmp(state,"lock") == 0){
			add_edge(b,a);
		}
		else{
			add_edge(a,b);
		}
	}
	printf("%d\n",(V-scc())>0);
	return 0;
}

3問目

  • 一度問題文をよんではいたが、ぱっとした解法が浮かばなかったので飛ばしてた。
  • だらだらと話しながら解法を考える。
  • シミュレーションでオーダー間に合うじゃんとなる。
  • 別の人が2問目ではなく先にこっちをACしたらしい。
  • 考えれば考えるほどわけがわからなくなる。
  • うさみみつけてる人と真剣に会話するペアはどんな気持ちなんだろうとか考える。
  • この問題を解きながら他のほとんどの問題に目は通してみたものもやっぱりこれを最初に解こうとなる。
  • 一応出来たコードは予想通りの動きをしないので++を+=2にしたらsample通った。
  • これで通ったらガバガバじゃねとかいいながら提出 -> WA
  • 知ってた。
  • こんなんで通るはずがない。
  • いろいろ話しながら、互いの意見を共有しコードを完成形に近づけていく。
  • 正直アイデアのほとんどがペアの案なので曖昧な感じでコードを書いていく。
  • 後輩君がいろいろ嘆いている。
  • vectorとかmapとかを使って瞑想していたら、ペアが一気にコードを書き上げた。
  • sample通る -> 提出 -> AC (03:42:00)
  • 神かよ ハイタッチ!
  • 4位まで浮上。
  • 順位表の凍結はないらしい。
  • そのあとひとつ順位をおとして終了。
//problem3
int main() {
	int N,R,T;
	int mem[128]={0};
	int v[128];
	int stage[1024]={0};
	
	scanf("%d%d%d",&N,&R,&T);
	rep(i,N){
		scanf("%d",&v[i]);
	}
	rep(i,T){
		if(i == 0){
			rep(j,N){
				mem[j]+=v[j];
				mem[j]%=R;
			}
		}
		else{
			vi next (1024,0);
			rep(j,N){
				mem[j]+=v[j];
				mem[j]%=R;
				next[mem[j]]++;
			}
			rep(j,N){
				if(stage[mem[j]] < next[mem[j]]) stage[mem[j]] = next[mem[j]];
			}
		}
	}
	int cnt = 0;
	rep(i,R){
		cnt += stage[i];
	}
	printf("%d\n",cnt+N);

	return 0;
}

まとめ

  • M教授に圧倒的感謝
  • ペアプロ楽しい!!!!!!!!!
  • 糞コード量産
  • ペアがバグ取り+タイプのプロだった
  • はやしや君に負けてくやしい
  • 本選に福島から地域枠ででた人たちよりも予選落ちの上の人たちが本選にいくべk(自主規制
  • 4位なら図書券だったかもなので若干悔しい
  • 本選にいった毛ガニよりも総合成績は良かった模様
  • やっぱり場の空気ってあるんだろうな
  • ペアに圧倒的圧倒的感謝
  • 6問目解きたかったなぁ
  • うさみみとトイレは神

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

テスト1日目+誰か教えてください

一つ前の記事のちょっとした続き.


例のICT Summer Contest 2014 Day1(Hard)の問題の最後の問題を解いてみた.

I - Family's Kyoto-Custom Experience Tour(hard edition)

  • 他の人の解法を見てみたら、全く違ったのでこわい><
  • 割と強めの枝狩り全探索で通りました.
  • 初めてです.こういう体験.
  • ひょっとして嘘解法?
  • 本来の解法は逆元とか使うようだ(人のコードを見た限りでは)
  • と見せかけて、実はこれが想定解?なのかは不明なので,誰か教えてください!

コード

class data{
    public:
    int ay,ax;
    int by,bx;
    int cnt;
    data(){};
    data(int a,int b,int c,int d,int _cnt){
	ay = a;
	ax = b;
	by = c;
	bx = d;
	cnt=_cnt;
    }
};
int main(){
    int h,w,y,x;
    cin >> h >> w >> y >> x;
    h--;w--;
    queue < data > Q;
    Q.push(data(0,0,h,w,0));
    int ans=0;
    int path = max(abs(h-y)+abs(w-x),x+y);
    while(!Q.empty()){
	data d = Q.front();Q.pop();
	if(path == d.cnt && d.ay == y && d.ax == x && d.by == y && d.bx == x){
	   ans++;
	   continue;
	}	   
	if(path <= d.cnt)continue;
	rep(i,2){
	    int ny = d.ay+dy[i];
	    int nx = d.ax+dx[i];
	    if(ny > y || nx > x)continue;
	    Q.push(data(ny,nx,d.by,d.bx,d.cnt+1));
	}
	reps(i,2,4){
	    int ny = d.by+dy[i];
	    int nx = d.bx+dx[i];
	    if(ny < y || nx < x)continue;
	    Q.push(data(d.ay,d.ax,ny,nx,d.cnt+1));
	}
	rep(i,2){
	    int ny = d.ay+dy[i];
	    int nx = d.ax+dx[i];
	    if(ny > y || nx > x)continue;
	    reps(j,2,4){
                int nny = d.by+dy[j];
	        int nnx = d.bx+dx[j];
		if(nny < y || nnx < nx)continue;
		Q.push(data(ny,nx,nny,nnx,d.cnt+1));
	    }
	}
    }
    printf("%d\n%d\n",path,ans);
    return 0;
}