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; }
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問目 フロッピーキューブ
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チームという制約にひっかかるので
予選敗退です.
テスト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; }