AtCoder ABC278 に向けた練習
ABC277でAB2完という惨敗を喫したので、ABC278に向けた練習（2022/11/19（土）より前の話）
大槻兼資「アルゴリズム的思考力が身につく! プログラミングコンテストAtCoder入門 単行本」 – 2022/8/1
の中級編の問題をやってみる。
ABC085C - Otoshidama
ABC085B - Kagami Mochi
は以下でも取り上げられていたのですでに終了済み。
ABC137C - Green Bin
アナグラム問題。文字列s1をソートしたものと文字列s2をソートしたものが一致すればアナグラム。mapで重複を数え、その組み合わせの数n(n+1)/2を出力。
PAST1F F - DoubleCamelCase Sort
PAST問題に行くには、AtCoder公式より
https://kenkoooo.com/atcoder/#/table
のPASTタブを見たほうが早い。
単純実装問題。一つの文字列から切り出してソートする。文字列を識別するのが先頭と末尾が大文字なことなので、その条件で切り出し、小文字に変換してソート、先頭と末尾を大文字に戻して出力。
PAST3E E - Sprinklers
単純実装問題。グラフをvector<vector<int>> graph(N+1);で保持して、クエリを処理していく。
ABC122 C - GeT AC
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, Q;
string s;
cin >> N >> Q >> s;
vector<int> v(N);
int cnt = 0;
for(int i = 1; i < N; i++){
if(s[i-1] == 'A' && s[i] == 'C'){
cnt++;
}
v[i] = cnt;
}
for(int i = 0; i < Q; i++){
int L, R;
cin >> L >> R;
cout << v[R-1] - v[L-1] << endl;
}
}
でACだったが、本の解説と累積和の取り方がずれている気がする。
AGC024 A - Fairness
AtCoder Grand Contest (AGC)でもAは結構簡単なのか。AGCの問題も、AtCoder ProblemsからAGCタブを選ぶのが早い。
高橋君の値をA、中橋君の値をBとしたときに、偶奇でA-BかB-Aを出力するだけ。答えの絶対値が10^18を超える場合Unfairを出力せよとあるが、そんな場合はない。
パリティ問題と呼ばれている。
ABC086 C - Traveling
ACした記憶があって、AtCoder ProblemsではACになっているが、AtCoderにはない。そんな不思議なお話。
マンハッタン移動の問題。パリティ問題らしい。時間の差分、xの差分、yの差分で、時間が間に合ってかつ時間と距離のパリティが一致すれば移動可能というもの。時間の差分、距離の差分で探索しても間に合ってACだった。
ABC125 D - Flipping Signs
言い換え問題と呼ばれている。問題を如何に簡単な問題に言い換えるかが非常に重要なことが本の5.9で解説されている。競技プログラミングにかなり重要な要素だと思う。
偶数個のマイナスは消せるのですべてプラスになり、マイナスが奇数個の場合に絶対値が最小になる数のみにマイナスをつけて、和を取る問題に帰着できる。
AGC030 A - Poisonous Cookies
ペアリングの例題（p. 232）。
算数問題。毒入りの美味しいクッキーC枚中、何枚食べれるかをcとすると、最後に毒入りのクッキーを食べて不調のまま終わってもよいから、cはA+B+1かCの小さい方。よって答えはB+c。
diverta 2019 Programming Contest C C - AB Substrings
AtCoder ProgramsのARC-Likeタブの、DIVERTA2019（DIVERTA2019-2じゃない方）。
算数問題。初サブミットで48問中46ACから、WAを抜け出せなかった私に以下の解説が響く。
少し考えただけでも大変複雑な問題であることがわかります。なるべく多くの"AB"が生成されるように考えたつもりでも、考え抜けがあるかもしれません。このような問題への1つのアプローチとしては、いろんな場合を試してみて、もっともらしい答えが見出せたらそれをコーディングして提出することが考えられます。場当たり的に説いたとしても、何度もWA判定を受けながら試行錯誤して最終的にACがとれるかもしれません。しかし、確実に一発でACをとりたいならば、「上界を見積もる」という方法が有効です。
この本は素晴らしい本だ。
大槻兼資「アルゴリズム的思考力が身につく! プログラミングコンテストAtCoder入門 単行本」 – 2022/8/1
