CODE FESTIVAL 2016 Final
A問題
A: Where's Snuke? - CODE FESTIVAL 2016 Final | AtCoder
snuke
という文字列がある場所の列(アルファベット)と行(数字)を出力
コード
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; string s; int H, W; int main(void) { cin >> H >> W; REP(i, H) { REP(j, W) { cin >> s; if(s=="snuke") { char c = 'A'+j; cout << c << i+1 << endl; } } } }
Submission #991415 - CODE FESTIVAL 2016 Final | AtCoder
B問題
B: Exactly N points - CODE FESTIVAL 2016 Final | AtCoder
- 和が
N
になる重複のない自然数の集合で最大の数字が最も小さい集合を出力せよ
方針
m(m+1)/2 > N
となる最小のm
を取り、大きいものから順に除外できる数字を除外していって、ちょうどN
になる集合を作る
コード
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int N; cin >> N; int m = 1; for(int i=1; i<=N; ++i) { if(i*(i+1)/2 >= N) { m = i; break; } } int res = m*(m+1)/2 - N; vector<int> contain(m+1); contain.assign(contain.size(), 1); for(int i=m; i>0; --i) { if(res == 0) break; if(res-i >= 0) { res -= i; contain[i] = 0; } } for(int i=1; i<=m; ++i) { if(contain[i]) cout << i << endl; } }
Submission #992560 - CODE FESTIVAL 2016 Final | AtCoder
C問題
C: Interpretation - CODE FESTIVAL 2016 Final | AtCoder
N
人が話すM
種類の言語が与えられる。全員が意思疎通可能か答えろ
方針
N+M
個の頂点を持つ二部グラフを作って人を表すN
個の頂点が連結かどうか調べる- 連結判定はDFSでできる
コード
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; vector<vector<int> > edge; vector<bool> visit; void dfs(int v) { if(visit[v]) return; visit[v] = true; for(int i=0; i<edge[v].size(); ++i) { dfs(edge[v][i]); } } int main(void) { int N, M; int K, L; cin >> N >> M; edge.resize(N+M); REP(i, N) { cin >> K; edge[i].resize(K); REP(j, K) { cin >> L; L = N+L-1; edge[i][j] = L; edge[L].push_back(i); } } visit.resize(N+M); dfs(0); REP(i, N) { if(!visit[i]) { cout << "NO" << endl; return 0; } } cout << "YES" << endl; }
Submission #993138 - CODE FESTIVAL 2016 Final | AtCoder
D問題
通らず
E問題
部分点を狙ってt
秒でできる最大クッキー数を考えたが失敗
AOJ 1600: Entrance Examination
問題
Entrance Examination | Aizu Online Judge
codefestival前の肩ならし
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int m, nmin, nmax; while(cin >> m >> nmin >> nmax && m) { vector<int> p(m); REP(i, m) scanf("%d", &p[i]); sort(p.begin(), p.end(), greater<int>()); int gap = 0; int ans = 0; for(int i=nmin-1; i<nmax; ++i) { if(p[i]-p[i+1] >= gap) { gap = p[i]-p[i+1]; ans = i+1; } } printf("%d\n", ans); } }
CODE FESTIVAL 2016 qual C
A問題
A: CF - CODE FESTIVAL 2016 qual C | AtCoder
文字列がCF
を部分文字列として含むか判定せよ
方針
C
を見つけたらレベルへ、レベル1でF
を見つけたらクリアみたいなコード
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { string s; int k=0; cin >> s; for(int i=0; i<s.size(); ++i) { if(k==0 && s[i]=='C') k=1; if(k==1 && s[i]=='F') {k=2; break;} } if(k==2) cout << "Yes" << endl; else cout << "No" << endl; }
Submission #942379 - CODE FESTIVAL 2016 qual C | AtCoder
B問題
B: K個のケーキ / K Cakes - CODE FESTIVAL 2016 qual C | AtCoder
なるべく連続したケーキを食べないようにするとき、連続したケーキを食べる回数
方針
可能なら前回食べたケーキを食べないようにして、残りが一番多いケーキを食べる
コード
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int K, T; int a[101]; cin >> K >> T; REP(i, T) { cin >> a[i]; } int ans = 0; int max = 0, max_index=-1; REP(j, T) if(a[j] > max) {max = a[j]; max_index = j;} int before = max_index; a[max_index]--; REP(i, K-1) { max = 0, max_index=-1; REP(j, T) if(a[j] > max && j!=before) {max = a[j]; max_index = j;} if(max_index != -1) { before = max_index; a[max_index]--; } else { a[before]--; ans++; } } cout << ans << endl; }
Submission #943260 - CODE FESTIVAL 2016 qual C | AtCoder
C問題
C: 二人のアルピニスト / Two Alpinists - CODE FESTIVAL 2016 qual C | AtCoder
- 右から見てそこまでで一番高い山と左から見たそこまでで一番高い山の標高が与えられる
- 情報に矛盾があれば0、なければありえる山の高さの場合の数を出力
方針
- 各山についてあり得る標高の種類を記録しておいて後で掛ける
i
番目のデータで最高標高が更新されていたら1通りに確定- 確定しない場合はその時点での標高通りの組み合わせがある。右からと左からで低い方
- 左から確定した山の高さを使って、右から見たときの最高標高が確定値よりも低かったら矛盾
コード
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; ll T[100001], A[100001]; ll cand[100001], kaku[100001]; ll mod = 1000000007; int main(void) { int N; bool flag = true; cin >> N; REP(i, N) cin >> T[i]; REP(i, N) cin >> A[i]; if(T[N-1] != A[0]) { cout << 0 << endl; return 0; } cand[0] = 1; FOR(i, 1, N) { if(T[i] > T[i-1]) { cand[i] = 1; kaku[i] = T[i]; } else { cand[i] = T[i]; kaku[i] = -1; } } cand[N-1] = 1; for(int i=N-2; i>=0; --i) { if(kaku[i] != -1 && A[i] < kaku[i]) { flag = false; break; } if(A[i] > A[i+1]) cand[i] = 1; else cand[i] = min(cand[i], A[i]); } if(flag == false) { cout << 0 << endl; return 0; } ll ans = 1; REP(i, N) { ans = (ans*cand[i])%mod; } cout << ans << endl; }
Submission #944505 - CODE FESTIVAL 2016 qual C | AtCoder
D, E
解けない
CODE FESTIVAL 2016 qual A
来世に期待
A
A: CODEFESTIVAL 2016 - CODE FESTIVAL 2016 qual A | AtCoder
- 長さ12の文字列sの前半4文字と後半8文字の間に半角スペースを1つ挿入して出力せよ
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i=0; i<(int)(n); ++i) int main(void) { string s; cin >> s; cout << s.substr(0, 4) << " " << s.substr(4,11) << endl; }
Submission #890791 - CODE FESTIVAL 2016 qual A | AtCoder
std::string::substr()
の関数名を正確に覚えていなかったから検索してた。
B
B: 仲良しうさぎ / Friendly Rabbits - CODE FESTIVAL 2016 qual A | AtCoder
N
行の入力でうさぎi
がうさぎj
を好きという情報が与えられる。(i != j
)- うさぎ
i
がうさぎj
を好き かつ うさぎj
がうさぎi
を好きというペアの数を求めよ
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i=0; i<(int)(n); ++i) int R[100001]; int main(void) { int N, a; cin >> N; rep(i, N) { cin >> a; R[i] = a-1; } int ans = 0; rep(i, N) { if(R[R[i]] == i) ans++; } cout << ans/2 << endl; }
Submission #892907 - CODE FESTIVAL 2016 qual A | AtCoder
- 0-indexedにするために入力から1引く処理を入れた
- 配列サイズを間違えていて1WA
C
C: 次のアルファベット / Next Letter - CODE FESTIVAL 2016 qual A | AtCoder
- 文字列から1文字選んで次の文字(z
の次はa
)にする操作をK回まで行える。辞書順最小の文字列を作れ
さすがに余裕だと思っていたら、ここでハマって終了。
ACするコード (ジャッジ結果)
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i=0; i<(int)(n); ++i) int main(void) { string s; int K, n; cin >> s >> K; n = s.size()-1; rep(i, n) { int p = 'z'-s[i]+1; if(s[i] != 'a' && K >= p) { K -= p; s[i] = 'a'; } } s[n] = 'a' + (s[n]-'a'+K)%26; cout << s << endl; }
ACしないコード (ジャッジ結果)
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i=0; i<(int)(n); ++i) int main(void) { string s; int K, n; cin >> s >> K; n = s.size()-1; rep(i, n) { int p = 'z'-s[i]+1; if(s[i] != 'a' && K >= p) { K -= p; s[i] = 'a'; } } s[n] += K%26; if(s[n] > 'z') s[n] = 'a' + (s[n]-'z'-1); cout << s << endl; }
一度z
より大きい値を入れてから戻すという処理を書いたら、char型に入れられる値の範囲が-128から127(一般的な環境の話)なせいでif文が成立せず通らなくなっていたようだ。
ダメになる例
今までASCIIコードを操作する問題では数字(ASCIIコードで48〜57)しか扱ったことがなかったのでこういうハマり方をしたことがなかった。
以後気をつけよう。
D
D: マス目と整数 / Grid and Integers - CODE FESTIVAL 2016 qual A | AtCoder
- 任意の2x2の正方形が
左上+右下=右上+左下
を満たすようにRxC
のマス目に非負整数を書き込むことができるか
editorialにある通り実装したのに1時間かかった
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int R, C, N; vector<ll> w; struct E{ int to, cost; E(int t, int c): to(t), cost(c) {}; }; vector<vector<E> > edge; ll rmin, cmin; bool dfs(int v) { if(v < R) rmin = min(rmin, w[v]); else cmin = min(cmin, w[v]); REP(i, edge[v].size()) { E e = edge[v][i]; if(w[e.to] != -1) { if(w[v]+w[e.to]!=e.cost) return false; } else { w[e.to] = e.cost - w[v]; if(!dfs(e.to)) return false; } } return true; } int main(void) { int tr, tc, ta; cin >> R >> C >> N; edge.resize(R+C); REP(i, N) { cin >> tr >> tc >> ta; tr--; tc--; edge[tr].push_back(E(R+tc, ta)); edge[R+tc].push_back(E(tr, ta)); } w.resize(R+C); w.assign(R+C, -1); REP(i, R+C) { if(w[i] != -1 || edge[i].size() == 0) continue; w[i] = 0; rmin = numeric_limits<ll>::max(); cmin = numeric_limits<ll>::max(); if(!dfs(i) || rmin+cmin < 0) { cout << "No" << endl; return 0; } } cout << "Yes" << endl; }
Submission #899631 - CODE FESTIVAL 2016 qual A | AtCoder
- 解説中の「上側にR個の頂点を並べ,下側にC個の頂点を並べ」たグラフを、前の
R
個が上側・後ろのC
個が下側となる全体でR+C
個の頂点を持つグラフとして表現し、dfsで条件判定した rmin
とcmin
で非負になることを確認した- 重みは
long long int
でないとオーバーフローしてWA(それでハマってた)。
E
そのうち……
Codeforces Round #372 (Div. 2)
2回目のCodeforces。
A問題
http://codeforces.com/contest/716/problem/A
入力の間隔がcを超えたらリセット、そうでなければインクリメントという感じで数えていく
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i=0; i<(int)(n); ++i) int main(void) { int n, c, ans, t, before; cin >> n >> c; ans = 0; before = 0; rep(i, n) { cin >> t; if(t - before > c) ans = 1; else ans++; before = t; } cout << ans << endl; }
B問題
http://codeforces.com/contest/716/problem/B
入力文字列の長さ26の部分列がA〜Zを重複なく含むようにする。
長さ26の部分列を全て見て、2回以上出現するアルファベットがなければいい感じに埋めてつくれる。
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i=0; i<(int)(n); ++i) int main(void) { string S; cin >> S; bool none = true; if(S.size() < 26) { cout << -1 << endl; return 0; } char list[26]; rep(i, S.size()-25) { rep(j, 26) list[j] = 0; for(int j=i; j<i+26; ++j) { list[S[j]-'A']++; } bool flag = true; rep(j, 26) { if(list[j] > 1) flag = false; } if(flag) { int k = 0; for(int j=0; j<S.size(); ++j) { if(j >= i && j<i+26) { if(S[j] == '?') { for(; k<26; ++k) { if(list[k] == 0) { char c = 'A'+k; cout << c; list[k] = 1; break; } } } else { cout << S[j]; } } else { if(S[j] == '?') { cout << 'A'; } else { cout << S[j]; } } } cout << endl; none = false; break; } } if(none) cout << -1 << endl; }
C問題
http://codeforces.com/contest/716/problem/C
変なルールに従ってレベルアップするために何回ボタンを押せばいいか。
今のレベルと次のレベルの公倍数の平方になるまでボタンを押せばレベルアップできるので、各レベルの回数はO(1)で求まる。 全部用意しておいて入力に従って表示するだけ。
#include <bits/stdc++.h> using namespace std; typedef long long int ll; #define rep(i, n) for(int i=0; i<(int)(n); ++i) ll dp[100001]; int main(void) { dp[1] = 2; for(ll k=2; k<=100000; ++k) { dp[k] = (k+1)*(k+1)*k - (k-1); } int n; cin >> n; for(int i=1; i<=n; ++i) { cout << dp[i] << endl; } }
D問題, E問題
Dは?を1としてdijkstraで最短路を求めてから、最短路がLになるよう増やせばいいのかなと思っていろいろ試したがそれが最短路ではなくなってしまう場合を考慮してなくて時間内に解けず。 Eは開いてすらいない。
まだsystem test通っていないのでACかは不明。
AOJ 1181: Biased Dice
問題
Biased Dice | Aizu Online Judge
- サイコロがある場所に積まれていき、転がり落ちることができる場合は6, 5, 4という優先順位でその目の方向に転がる
- ルールに従ってサイコロを転がしていった時に見えるサイコロについて、1〜6の目がいくつずつ上を向いているか調べよ
- 入力として、積まれるサイコロの上面の目(t)と前面の目(f)の組がn個与えられる
方針
- 頑張ってシミュレーションする
- 6, 5, 4の目について[t][f]を与えたときにどちらの方向にあるかを求める配列を用意する
- 優先順位に従って転がしていき、各場所の高さとサイコロのt, fを更新していく
コード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i=0; i<(int)(n); ++i) #define NO 0 #define UP 1 #define RIGHT 2 #define LEFT 3 #define DOWN 4 int h[201][201], face[201][201]; const int six[7][7] = { {NO, NO, NO, NO, NO, NO, NO}, {NO, NO, NO, NO, NO, NO, NO}, {NO, UP, NO, LEFT, RIGHT, NO, DOWN}, {NO, UP, RIGHT, NO, NO, LEFT, DOWN}, {NO, UP, LEFT, NO, NO, RIGHT, DOWN}, {NO, UP, NO, RIGHT, LEFT, NO, DOWN}, {NO, NO, NO, NO, NO, NO, NO} }; const int five[7][7] = { {NO, NO, NO, NO, NO, NO, NO}, {NO, NO, UP, RIGHT, LEFT, DOWN, NO}, {NO, NO, NO, NO, NO, NO, NO}, {NO, LEFT, UP, NO, NO, DOWN, RIGHT}, {NO, RIGHT, UP, NO, NO, DOWN, LEFT}, {NO, NO, NO, NO, NO, NO, NO}, {NO, NO, UP, LEFT, RIGHT, DOWN, NO} }; const int four[7][7] = { {NO, NO, NO, NO, NO, NO, NO}, {NO, NO, LEFT, UP, DOWN, RIGHT, NO}, {NO, RIGHT, NO, UP, DOWN, NO, LEFT}, {NO, NO, NO, NO, NO, NO, NO}, {NO, NO, NO, NO, NO, NO, NO}, {NO, LEFT, NO, UP, DOWN, NO, RIGHT}, {NO, NO, RIGHT, UP, DOWN, LEFT, NO} }; int main(void){ int n; while(cin >> n && n) { int t, f; rep(i, 201) rep(j, 201) {h[i][j] = 0; face[i][j] = -1;} rep(i, n) { cin >> t >> f; t; f; int x = 100, y = 100; int nx, ny; h[y][x]++; bool fall = true; while(fall) { nx = x; ny = y; fall = false; if(six[t][f] == UP && h[y+1][x] < h[y][x]-1) { fall = true; ny = y+1; f = 7-t; t = 1; } else if(six[t][f] == RIGHT && h[y][x+1] < h[y][x]-1) { fall = true; nx = x+1; t = 1; } else if(six[t][f] == LEFT && h[y][x-1] < h[y][x]-1) { fall = true; nx = x-1; t = 1; } else if(six[t][f] == DOWN && h[y-1][x] < h[y][x]-1) { fall = true; ny = y-1; f = t; t = 1; } else if(five[t][f] == UP && h[y+1][x] < h[y][x]-1) { fall = true; ny = y+1; f = 7-t; t = 2; } else if(five[t][f] == RIGHT && h[y][x+1] < h[y][x]-1) { fall = true; nx = x+1; t = 2; } else if(five[t][f] == LEFT && h[y][x-1] < h[y][x]-1) { fall = true; nx = x-1; t = 2; } else if(five[t][f] == DOWN && h[y-1][x] < h[y][x]-1) { fall = true; ny = y-1; f = t; t = 2; } else if(four[t][f] == UP && h[y+1][x] < h[y][x]-1) { fall = true; ny = y+1; f = 7-t; t = 3; } else if(four[t][f] == RIGHT && h[y][x+1] < h[y][x]-1) { fall = true; nx = x+1; t = 3; } else if(four[t][f] == LEFT && h[y][x-1] < h[y][x]-1) { fall = true; nx = x-1; t = 3; } else if(four[t][f] == DOWN && h[y-1][x] < h[y][x]-1) { fall = true; ny = y-1; f = t; t = 3; } if(fall) { h[y][x]--; h[ny][nx]++; x = nx; y = ny; } else { } } face[y][x] = t; } int ans[6] = {}; rep(i, 201) rep(j, 201) {if(face[i][j] != -1) ans[face[i][j]-1]++;} cout << ans[0]; rep(i, 5) cout << " " << ans[i+1]; cout << endl; } }
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1956974
反省
- コードが汚い
AOJ 1174: Identically Colored Panels Connection
問題
Identically Colored Panels Connection | Aizu Online Judge
- 電気を流すと隣接した同じ色のパネルを含めて色が変わるパネルがある
- 隣接した同じ色のパネルは結合する
- 左上のパネルに5回電気を流したとき、指定された色で左上と結合している最大のパネル数を求めよ
方針
- dfsであらゆる変色パターンを試す (6の5乗なので間に合いそう)
- パネルの変色とパネル数カウントはbfsでやる
コード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i=0; i<(n); ++i) typedef pair<int, int> P; int p[10][10], visited[10][10]; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; int h, w, c; int dfs(int count) { if(count == 5) { int ret = 0; if(p[0][0] != c) return 0; rep(i, 10) rep(j, 10) visited[i][j] = 0; queue<P> que; que.push(P(0, 0)); while(!que.empty()) { P point = que.front(); que.pop(); if(visited[point.first][point.second] == 0) { visited[point.first][point.second] = 1; ret++; rep(i, 4) { int ny = point.first + dy[i]; int nx = point.second + dx[i]; if(nx >= 0 && nx < w && ny >= 0 && ny < h && visited[ny][nx] == 0 && p[ny][nx] == c) { que.push(P(ny, nx)); } } } } return ret; } int org[10][10]; int ret = 0; rep(i, h) rep(j, w) org[i][j] = p[i][j]; rep(color, 6) { int org_c = p[0][0]; rep(i, 10) rep(j, 10) visited[i][j] = 0; queue<P> que; que.push(P(0, 0)); while(!que.empty()) { P point = que.front(); que.pop(); p[point.first][point.second] = color+1; visited[point.first][point.second] = 1; rep(i, 4) { int ny = point.first + dy[i]; int nx = point.second + dx[i]; if(nx >= 0 && nx < w && ny >= 0 && ny < h && visited[ny][nx] == 0 && p[ny][nx] == org_c) { que.push(P(ny, nx)); } } } ret = max(ret, dfs(count+1)); rep(i, 10) rep(j, 10) p[i][j] = org[i][j]; } return ret; } int main(void){ while(cin >> h >> w >> c && h) { rep(i, h) rep(j, w) cin >> p[i][j]; cout << dfs(0) << endl; } }
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1920825
反省
- visitedの処理がうまく書けなくて重複カウントしていてハマった
- 遅い(1.7s)のは仕方ないのかなと思ったら、同じような解法でもvisitedの更新をしないで済むよう実装すれば0.02sで解けていた(これとか)