AtCoder Beginner Contest #011
ooooで総合18th.やったぜ!
http://abc011.contest.atcoder.jp/
公式解説 http://www.slideshare.net/chokudai/abc011
解説ニコ生 http://live.nicovideo.jp/watch/lv183702185
A
C++03で提出してコンパイラエラーをもらう.ペナルティにはならないらしい.
int main(){ int n; while (cin >> n){ if (n == 12) cout << 1 << endl; else cout << n + 1 << endl; } }
B
#include<cctype>
が便利.Rubyにはcapitalize
というまんまそれなメソッドがあるが本番ではC++脳が先に回った
int main(){ string s; cin >> s; s[0] = toupper(s[0]); rep(i, s.size())if (i){ s[i] = tolower(s[i]); } cout << s << endl; }
puts gets.chomp.capitalize
C
問題にかかれているのとは逆に0から初めて足し算してもよい.
0から始めて1,2,3を足していき、NG数を踏まずにi
回以内の足し算でj
を作るための足し算の最小回数をdp[i][j]
とおく.
dp[i][]
の更新に必要なのはdp[i-1][]
だけなので,下のソースコードではdp[i+1]
をnext
,dp[i]
をcur
とおいている.
i
=0~350,j
=1~3で,cnt[i + j] = min(cnt[i + j], cnt[i] + 1)
の漸化式でcur[n]
までの最短手数を求め,最終的にcur[n]
が100以下になるか判定する.
貪欲でも解けるらしい.
typedef vector<int> vi; typedef vector<bool> vb; int main(){ int n; while (cin >> n){ vi cnt(400, inf); vb ng(400); rep(i, 3){ int x; cin >> x; ng[x] = true; } bool ok; if (ng[0]) ok = false; else { cnt[0] = 0; rep(i, 350){ if (cnt[i] == inf) continue; loop(j, 1, 4){ if (!ng[i + j]){ cnt[i + j] = min(cnt[i + j], cnt[i] + 1); } } } if (cnt[n] <= 100) ok = true; else ok = false; } if (ok) cout << "YES"; else cout << "NO"; cout << endl; } }
D
まずx
もy
もD
で割れない時は答えはNO
で,割れるときはx
,y
,D
を全てD
で割り,D
=1で考える.
漸化式を立てて普通にDPだが,DPテーブルの大きさをWHとしたとき,O(NH*W)だと微妙な定数倍高速化をしないと通らない.
double
の誤差を考え,答えの許容誤差の10^-9に影響しないような値は切る- 同様に誤差を考えてDPテーブルを縮める
- ループ展開する
で通った.個人的にはあまり好きではないけど,こういうテクニックを使わせる点で教育的なのかなと思った.
→これは想定解法ではないらしく、公式解説にもっと賢い方法があります.
int main(){ int n, d, x, y; while (cin >> n >> d >> x >> y){ double p; if (x%d == 0 && y%d == 0){ const int w = 350; const int h = 350; x /= d; y /= d; x += w / 2; y += h / 2; if (!in(x, y, w, h)) p = 0; else { vvd cur(h, vd(w, 0)); cur[h / 2][w / 2] = 1; int const dx[] = { 1, 0, 0, -1 }; int const dy[] = { 0, 1, -1, 0 }; rep(i, n){ vvd next(h, vd(w, 0)); rep(y, h)rep(x, w){ // ループ展開(dx[],dy[]をループで回るとTLE) int nx, ny; nx = x + 0; ny = y + 1; if (!in(nx, ny, w, h) || cur[y][x] < 1e-10) goto aaa; next[ny][nx] += cur[y][x] / 4; aaa:; nx = x + 0; ny = y + -1; if (!in(nx, ny, w, h) || cur[y][x] < 1e-10) goto bbb; next[ny][nx] += cur[y][x] / 4; bbb:; nx = x + 1; ny = y + 0; if (!in(nx, ny, w, h) || cur[y][x] < 1e-10) goto ccc; next[ny][nx] += cur[y][x] / 4; ccc:; nx = x + -1; ny = y + 0; if (!in(nx, ny, w, h) || cur[y][x] < 1e-10) continue; next[ny][nx] += cur[y][x] / 4; } swap(next, cur); } p = cur[x][y]; } } else { p = 0; } cout << fixed << setprecision(30) << p << endl; } }