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時頃
コンテスト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; }
