競プロ復帰戦（ABC175感想戦A～E）
大学の課題とかに追われていたのもあって，半年ほど完全にサボっていました． 夏休みに入って再び時間ができたので，これを期に復帰することにしました． 復習をサボらないように，あと備忘録的なものを兼ねて，ブログ形式で記録をつけることにしました．
ABC152以来の参戦です．いつの間にかABC175まできててびっくりしました．
レート変化
511→528に上がりました．正直誤差の範囲です・・・．冷えなかっただけマシですが・・・．
A：Rainy Season
'S'と'R'から成る文字列が与えられ，'R'が何文字連続しているか答える問題． 文字列の長さが3であることから，文字列のパターンは高々23=8パターンしかありません． 素直に場合分けすればよいです．
int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); string s; cin >> s; if (s == "RRR") { cout << "3" << endl; } else if (s == "RRS" || s == "SRR") { cout << "2" << endl; } else if (s == "RSS" || s == "SRS" || s == "SSR" || s == "RSR") { cout << "1" << endl; } else { cout << "0" << endl; } return 0; }
汚ねぇコードだなぁと思いながら書いてたけど，これが想定解らしい．
B：Making Triangle
棒の本数と長さが与えられて，その中から三角形を作ることができてかつ長さがそれぞれ異なる3本の棒の選び方の総数を求める問題． 選んだ棒の組み合わせに対して三角形の成立条件が成立し，かつ選んだ3本の棒の長さがそれぞれ異なるかを判定する，という流れをそのまま実装すればいけます． 棒の数の制約が$N\leq{}100$であることから，全探索しても間に合います．計算量は$O(N^{3})$です． あらかじめ棒の長さでソートしておけば，三角形の成立条件が簡単になるので条件式が書きやすくなります．
int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); vector <ll> stick; int n; int cnt = 0; cin >> n; rep(i, n) { ll tmp; cin >> tmp; stick.push_back(tmp); } sort(all(stick)); // stick.erase(unique(all(stick)), stick.end()); if (stick.size() < 3) { cout << 0 << endl; return 0; } for (int i = 0; i < SZ(stick) - 2; i++) { for (int j = i + 1; j < SZ(stick) - 1; j++) { for (int k = j + 1; k < SZ(stick); k++) { if (stick.at(i) + stick.at(j) > stick.at(k)) { if ((stick.at(i) != stick.at(j) && stick.at(j) != stick.at(k) && stick.at(k) != stick.at(i))) { cnt++; } } } } } cout << cnt << endl; return 0; }
最初同じ長さの棒は区別されないものだと勘違いしていて，テストケースと答えが合わず時間を溶かしたのは内緒です． これと後のC問題の2WAで足を引っ張られました・・・．
C：Walking Takahashi
高橋君をできるだけ数直線の原点に近づける問題． まず状況として，次の2パターンに分かれます．
- 移動可能回数が少なく，高橋君が最適解に近づく前に力尽きる場合
- 移動可能回数が十分に大きく，高橋君が最適解に到達できる場合
前者の場合，原点に向かってひたすら移動し，力尽きた地点が最適解となるので簡単です．
後者の場合，解の候補は以下の2点存在します．
- 高橋君の初期位置から$\frac{X}{D}$回移動した位置
- 高橋君の初期位置から$\frac{X}{D}+1$回移動した位置
原点からの距離が最短になる位置（最適解）は上2つのうちのどちらかになります． 以下，最適解を解1，もう一方の解を解2と呼びます．
以上のことを用いると，後者の場合は以下のように考えれば解が求まります．
- 高橋君を解1の位置まで移動させる
- 残り移動回数で解1と解2を交互にぴょんぴょんする
- 最後に止まったほうが解
3の「最後に止まる方」は，1が終了した時点での残り移動回数から求めることができます．
int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); ll x, k, d; cin >> x >> k >> d; ll preans1, preans2; ll idou1, idou2; idou1 = llabs(x / d); preans1 = llabs(llabs(x) - idou1 * d); preans2 = llabs(preans1 - d); idou2 = idou1 + 1; if (preans1 > preans2) { swap(preans1, preans2); swap(idou1, idou2); } if (idou1 > k) { cout << llabs(llabs(x) - d * k) << endl; // answer } else if ((k - idou1) % 2 == 0) { cout << preans1 << endl; } else { cout << preans2 << endl; } return 0; }
一ヵ所llabsを付け忘れていることに気づけず，2WAしました．くそっ． 本番中に解けたのはここまででした．
ここまでは安定して来れるんだけど，D以降はその日の問題の相性にもよるなぁって感じ． A～Cをノーミスで早く解けるようにならないとこの先中々厳しそう．
D：Moving Piece
ここからは本番では解けていません． 一夜明けて，解説を読んでから解いてみました．
最初見た時は全パターン洗い出すことを一瞬考えましたが，制約的に厳しいことにはすぐ気づけました．
有向グラフを描くとジャンプするマスが一定周期でループしていることが分かり，それを用いれば$O(N^{2})$で求まるようです． 知らないアルゴリズムが出てきているわけではないので，気づくことはできたかもしれないなぁ． 「順列ときたら閉路を考える」的な文をTwitterで見たけど，定石なんですかね？
コードはほぼ解説動画の写経なので載せません．
E：Picking Goods
平面を移動してアイテムを回収し，回収するアイテムの価値を最大化する問題．
典型的なDPなのでいけるのでは？と思いましたが， 同じ行でアイテムは最大3個までしか拾えないという条件を加味するというところで分からなくなりました．
既に$k$個拾ったという情報をdpテーブルに付け足すことで解決できるらしい． 解説を見たら確かにそうだとわかるんですけどね・・・． 本番で思いついて実装できるかって言われたら・・・，って感じです． DPをほとんど実装したことがないので，圧倒的経験値不足です． 精進します・・・．
F：Making Palindrome
まだ解説すら見ていません． Dijkstra法とかで解決できるみたいなので，時間あれば見てみます．
今後の目標
とりあえず年内緑を目指して頑張ろうと思います． しばらくサボってた間のABCの問題を解いて，力をつけていきます．
