ABC176感想戦A～E
復帰後2回目のABC参戦です．一夜明けた今日，とりあえず解説動画を見ずにEまで自力で通しました（文の解説は見ましたが・・・）．備忘録がてら感想等残しておきます．
レート変化
528→511です．無事に冷えました！！！！前回511→528だったので，元に戻った感じですね()
今回はCまで特に悩むことなく通せていたので期待できそうだと思ったのですが，皆余裕でCまで通していたみたいで相対的に自分の順位が落ちてしまったみたいです．レート冷やすとモチベーション下がるなぁ．
A：Takoyaki
「1脚6人掛けの椅子に25人座らせるためには何脚の椅子が必要ですか？」的な問題ですね．小中学校の算数数学で嫌ほど見た記憶があります．
まとめて焼き切れずに残ったたこ焼きを最後処理するのに，一回分の時間が余計にかかってしまうというのがこの問題のポイントです． 先述の椅子の問題でいうと，24人座らせるには椅子を4脚用意すればいいけれど，残り1人を座らせるために余分に1脚必要になる，といったところです．
この問題の場合，$\frac{N}{X}$にあまりが生じるかどうかで場合分けをし，あまりがなければ$\frac{N}{X}\times{}T$を出力し，あまりがあるなら$(\frac{N}{X}+1)\times{}T$を出力すれば解になります．
int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); int n, x, t; cin >> n >> x >> t; if (n % x == 0) { int num = n / x; cout << t * num << endl; return 0; } else { int num = n / x + 1; cout << t * num << endl; return 0; } return 0; }
本番中はなぜか綺麗に書こうとして場合分けの代わりにceilを使ってしまい，沼にハマりました． 綺麗さを求めて変に一般化しようとして失敗する典型例ですね． 結局通すのに8分ぐらいかかった気がします．そりゃ冷えるよなぁ．
B：Multiple of 9
与えられた数が9の倍数か判定する問題です． 制約が$N\leq{}10^{200000}$なので，数値として読み込むとオーバーフローします． だから文字列として読み込んで倍数判定法使ってね，っていう趣旨の問題です． （”たばいちょうせいすう”なるものを使うと数値として読み込んでもできるらしい．はえーすっごい．）
int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); char num_str[1000000]; scanf("%s", num_str); char *num_ptr = num_str; int count = 0; int sum = 0; while (*num_ptr != '\0') { int tmp = num_str[count] - 48; sum += tmp; num_ptr++; count++; } if (sum % 9 == 0) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; }
まぁそのままやるだけです． そのままやるだけなんですけど，文字列を1文字づつ分離するところで結構時間かかってます． これも今回の冷えの原因です．
C：Step
人が1列に並んでおり，それぞれの人の身長が与えられます． 前の人よりも身長を高く，ないしは同じになるように人に踏み台を与えていきます． この時トータルで踏み台を最低いくつ与えればよいでしょう，という問題です．
なんかこの問題どっかで見た気がします・・・．
1～$i$人目まで見た時，その中で一番身長が高かった人の身長を$max$という変数に保持します． この時$i+1$人目の身長が$max$以下であれば，$max$とその人の身長の差分だけの高さの踏み台を与えます． $i+1$人目の身長が$max$より高ければ，$max$を$i+1$人目の身長で更新し，次の人を見ます． これを最後まで繰り返し，与えた踏み台の総和を出力すれば解となります．
int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); int n; cin >> n; vector <int> a(n); rep(i, n) cin >> a[i]; ll max = a[0]; ll ans = 0; for (int i = 1; i < SZ(a); i++) { if (max < a[i]) { max = a[i]; continue; } else { ans += max - a[i]; } } cout << ans << endl; return 0; }
これについては3分ぐらいでACした気がします．
D：Wizard in Maze
迷路探索の応用です． 迷路の探索はやったことがあるので方針はすぐ浮かびましたが， 実装がまずくオーダーが落としきれずにTLEしました．
単に最短経路を求めるだけなら普通のBFSで終了ですが， 今回はワープのコストという概念があるのでそれだけでは無理です．
今回の場合，0-1BFSという手法でうまくいきます． 通常のBFSと異なるのは， deque（前後どちらからもpush，popできるqueue）を用い， ワープせずに移動した移動先を前にpushし，ワープを用いて移動した移動先を後にpushするというところです． これによってコストが低いもの（＝ワープ回数が少ないもの）から優先的に探索が行えます．
char mp[1005][1005]; int cost[1005][1005]; int h, w; deque <tuple <int, int, int, int, bool> > deq; int ch, cw; int dh, dw; bool end_fg = false; void bfs(int x, int y, int cst) { if (end_fg) { return; } if (x < 0 || y < 0 || h <= x || w <= y) { return; } if (mp[x][y] == '#' || cost[x][y] != -1) { return; } else { cost[x][y] = cst; } if (x == dh && y == dw) { end_fg = true; return; } for (int i = -2; i < 3; i++) { for (int j = -2; j < 3; j++) { if (i == 0 && j == 0) { continue; } else if ((i == -1 && j == 0) || (i == 1 && j == 0) || (i == 0 && j == -1) || (i == 0 && j == 1)) { tuple <int, int, int, int, bool> tmp = make_tuple(i, j, x, y, false); deq.push_front(tmp); } else { tuple <int, int, int, int, bool> tmp = make_tuple(i, j, x, y, true); deq.push_back(tmp); } } } } int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); cin >> h >> w; cin >> ch >> cw; ch--; cw--; cin >> dh >> dw; dh--; dw--; rep(i, 1005) { rep(j, 1005) { cost[i][j] = -1; } } rep(i, h) { char tmp[1005]; cin >> tmp; rep(j, w) { mp[i][j] = tmp[j]; } } bfs(ch, cw, 0); while (deq.size() != 0) { tuple <int, int, int, int, bool> next = deq.front(); deq.pop_front(); if (get <4>(next)) { bfs(get <0>(next) + get <2>(next), get <1>(next) + get <3>(next), cost[get <2>(next)][get <3>(next)] + 1); } else { bfs(get <0>(next) + get <2>(next), get <1>(next) + get <3>(next), cost[get <2>(next)][get <3>(next)]); } } /*rep(i, h) { rep(j, w) { cout << cost[i][j]; } cout << endl; }*/ cout << cost[dh][dw] << endl; return 0; }
解説記事を読んだときは少し感動しました．面白いですね．
E：Bomber
爆破できる爆破対象の数を最大化する問題です．
爆弾と同じ行，列にある爆破対象が爆破できるので， 単純に爆破対象が一番多い行と列を探し，その行と列の交点に爆弾を置けば， (行にある爆破対象)＋(列にある爆破対象)が爆破され解になるのでは？ と本番中は思ったのですが， 爆弾を置いた場所に爆破対象があった場合その限りでないことにすぐ気づきました． （交点の爆破対象が2重に計上されるため，実際は1つ減ってしまいます．）
本番中はなんかめんどくさそうだなぁと思ってスルーしました． （実際Dの方がめんどくさかった．）
爆破対象が最大になる行および列は複数ある可能性があります． 爆破対象が最大になる行の数を$hctr$，爆破対象が最大になる列の数を$wctr$とすると， 爆弾を置く候補地は$hctr\times{}wctr$となります．
もしこの候補地全てに爆破対象が存在した場合， どこに爆弾をおいたとしても(行にある爆破対象)＋(列にある爆破対象)-1の爆破対象しか爆破できず，これが解となります． 逆に爆破対象のない候補地が存在した場合， そこに爆弾を設置することで，(行にある爆破対象)＋(列にある爆破対象)の爆破対象が爆破できます．
int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); int h, w, m; cin >> h >> w >> m; vector <int> hbomb(h, 0); vector <int> wbomb(w, 0); vector <pair <int, int> > bomb(m); rep(i, m) { int tmp1, tmp2; cin >> tmp1 >> tmp2; tmp1--; tmp2--; bomb[i] = make_pair(tmp1, tmp2); hbomb[tmp1]++; wbomb[tmp2]++; } int hmax = -1; int wmax = -1; int hctr = 1; int wctr = 1; rep(i, h) { if (hmax == hbomb[i]) { hctr++; } else if (hmax < hbomb[i]) { hctr = 1; hmax = hbomb[i]; } } rep(i, w) { if (wmax == wbomb[i]) { wctr++; } else if (wmax < wbomb[i]) { wctr = 1; wmax = wbomb[i]; } } int cross = 0; int pattern = hctr * wctr; rep(i, m) { if (hbomb[bomb[i].first] == hmax && wbomb[bomb[i].second] == wmax) { cross++; } } if (!(pattern - cross)) { cout << hmax + wmax - 1 << endl; } else { cout << hmax + wmax << endl; } return 0; }
なんとなく本番中にもこんな感じのことは考えたのですが， ここまでシンプルにまとまるとは思っていませんでした．
F：Brave CHAIN
なんかTwitterで赤diffなのを見たのでとりあえず放置します()
最後に
アルゴリズムの知識がそれほどない状態でも茶にはなれましたが， これ以上レートを伸ばすためには基本的なアルゴリズムをしっかり勉強して，それを実装する練習をある程度詰まないと厳しそうだなぁと感じました・・・．特に実装の経験が全然足りないです．過去問をひたすら解いて勉強します・・・．
