AtCoder Beginner Contest 302 に参加しました＆反省会
AtCoder Beginner Contest 302 の振り返り
- A問題しか解けず。
- A問題：
が
で割り切れる場合
、そうでない場合は
と出力する
- B問題：全探索にしたが、斜め方向の探索に失敗した
- C問題：配列のあり得る並び替えを愚直に走査するが、8ケースでWAになった
- D問題：全探索ではTLEになる
A問題
方針
解説*1から
- 正整数
に対して、
と等しいため、この式を計算することで求めることができます
B問題
解説*2から
- 出発点から8方向を調べ
snukeの文字があるかどうかを調べます - 8方向への展開、マス目の文字が
snukeのいずれかの文字に等しいかをfor文を使ってまとめます
実装例
int di[] = {-1, -1, -1, 0, 0, 1, 1, 1}; int dj[] = {-1, 0, 1, -1, 1, -1, 0, 1}; int main() { int h, w; cin >> h >> w; vector<string> s(h); for (int i = 0; i < h; i++) cin >> s[i]; string T = "snuke"; for (int si = 0; si < h; si++) { for (int sj = 0; sj < w; sj++) { for (int v = 0; v < 8; v++) { int i = si, j = sj; for (int k = 0; k < 5; k++) { if (i < 0 || j < 0 || i >= h || j >= w) break; if (s[i][j] != T[k]) break; if (k == 4) { for (int nk = 0; nk < 5; nk++) { printf("%d %d\n", i+1, j+1); i += di[v]; j+= dj[v]; } return 0; } i += di[v]; j+= dj[v]; } } } } return 0; }
C問題
方針
- 与えられた文字列を並び替えるすべてのパターンを調べます
- このとき
next_permutation関数を利用します - 比較する
つの文字列が一文字だけ一致しない場合問題文の条件を満たします
実装例
int main() { int n, m; cin >> n >> m; vector<string> s(n); for (int i = 0; i < n; i++) cin >> s[i]; sort(s.begin(), s.end()); do { bool ok = true; for (int i = 0; i < n-1; i++) { int d = 0; for (int j = 0; j < m; j++) if (s[i][j] != s[i+1][j]) d++; if (d != 1) ok = false; } if (ok) { cout << "Yes" << endl; return 0; } } while(next_permutation(s.begin(), s.end())); cout << "No" << endl; return 0; }
D問題
解説*3から
int main() { int n, m; long long d; cin >> n >> m >> d; vector<long long> a(n), b(m); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < m; i++) cin >> b[i]; sort(b.begin(), b.end()); long long ans = -1; for (int i = 0; i < n; i++) { long long l = a[i]-d, r= a[i]+d; int j = upper_bound(b.begin(), b.end(), r) -b.begin(); if (j > 0) { long long x = b[j-1]; if (l <= x) ans = max(ans, a[i]+x); } } cout << ans << endl; return 0; }
