#はじめに
drkenさんのAtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～を、本編記事で紹介されていないいろいろな方法で解いてみます。
実装は C++ です。
こんな別解が乗っていないよ！というご指摘があれば、ぜひお寄せください！
practiceA は別解がない(入力の方法を変えたりとかしかできない)ので割愛します。
第 1 問 : ABC086A - Product
元記事の解法は、$a \times b$ を計算してそれが偶数か判定するものです。
#include <iostream>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
int c = a * b;
if (c % 2 == 0) cout << "Even" << endl;
else cout << "Odd" << endl;
}
これは制約から、$1\leq a,b\leq10000\Rightarrow a\times b\leq100000000\leq \mathrm{\verb|INT_MAX|}=2147483647$となるので正しく動きます。（これが満たされない場合、オーバーフローをして正しい答えが出ない可能性があります。）
一方、$a$ と $b$ のどちらも奇数であるか？を判定するようなコードは別解になります。
この方法だと、制約がもう少し緩くても正解することができます。
#include<iostream>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
cout << (a & b & 1 ? "Odd" : "Even") << endl;
// if (a % 2 == 1 && b % 2 == 1) cout << "Odd" << endl;
// else cout << "Even" << endl;
// と書くのと同じです
}
ここで、cout の中身 (a & b & 1 ? "Odd" : "Even") を見慣れない人もいると思います。
パーツごとに見て行きましょう！
まず、偶数・奇数についての条件は、ビット演算を用いて表すことができることが多いです。
A が奇数であるという条件は、A & 1 == 1 であらわすことができます
（追記 : 2018/06/15）
(A & 1) == 1 であらわすことができます。
C++での演算子の優先順位は & より == のほうが高いので、A & 1 == 1 は A & (1 == 1) のように解釈されます。
今回の計算では 1 == 1 は true 、つまり 1 だったので偶然想定した動作になっていました。
以下も同様に修正しています。
a も b も奇数である$\iff$(a & 1) == 1 && (b & 1) == 1$\iff$(a & b & 1) == 1
です。
ところで、a & b & 1 は 0 か 1のどちらかです。
なので、(a & b & 1) == 1 は、bool(a & b & 1) と同じになります。
これが最初の a & b & 1 の部分です。
後半の ? "Odd" : "Even" では、**条件演算子（三項演算子）**というものを使っています。
条件演算子は、以下のような使い方をするものです。
(条件) ? (条件がTrueの時の値) : (条件がFalseの時の値)
よく似た処理をする構文で、if文があります。比較してみましょう。
if(条件) (条件がTrueの時の処理) else (条件がFalseの時の処理)
三項演算子は条件で値を、if文は条件で処理を、それぞれ選んでいます。
条件演算子は演算子なので、演算の結果としての値があります。
それに対してif文は文なので、値がありません(C++完全理解人類からマサカリが飛ばされそう…)。
たとえば、
cout << (if(a & b & 1) "Odd" else "Even") << endl;
のように書くことはできず、
cout << (a & b & 1 ? "Odd" : "Even") << endl;
や
if (a & b & 1) cout << "Odd" << endl; else cout << "Even" << endl;
と書くことができます。
cout << "Odd" << endl は ostream 型の値をもつ式なので、
a & b & 1 ? cout << "Odd" << endl : cout << "Even" << endl;
のように書くこともできます。
（追記 : 2018/06/15）
さらに、偶数か奇数かには下一桁しか関係ないことを考えると、$a,b<10^{100000}$ などでも正解できる次の別解が考えられます。
#include <iostream>
using namespace std;
int main() {
string A, B;
cin >> A >> B; // 文字列として数字を読み込む
int a = A.back() - '0', b = B.back() - '0'; // 下一桁は最後の一文字が表す数
cout << (a & b & 1 ? "Odd" : "Even") << endl;
}
1 問目は他に別解が見つけられなかったので次に行きましょう。
第 2 問 : ABC081A - Placing Marbles
元記事では、最初から見ていって '1' が出たらカウンターを進めています。
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
cin >> s;
int counter = 0;
if (s[0] == '1') ++counter;
if (s[1] == '1') ++counter;
if (s[2] == '1') ++counter;
cout << counter << endl;
}
たとえば、C++ には accumulate 関数という、範囲の合計を求めてくれる関数があります。これを用いると、例えば次のような別解を書くことができます。
#include<iostream>
#include<string>
#include<numeric>
using namespace std;
int main() {
string s;
cin >> s;
cout << accumulate(s.begin(), s.end(), 0) - 3 * '0' << endl;
// sの最初から最後までの合計(?)から、 3*'0' を引くと '1' の個数が出てくる...!?
}
文字の合計をとったり、- 3 * '0' がかなり不思議なおまじないに見えて、なぜこれで正しい答えが出てくるのかわからないかもしれません。
これは、文字一文字を現す char 型の変数に秘密があります。
実は char 型は整数型の一つで、多くの場合 ASCII コードという整数と文字の対応規則に沿って文字への変換が行われています。
そのため、整数でできる四則演算などは当然 char 型でも行うことができます。
さらに、ASCIIコードはわかりやすく作られていて、例えば '7'-'3'=7-3 などが成り立つように、'0', '1', ...,'9' が連続する整数に対応しています。
なので、数字一文字が入っている char 型の変数が、なんの数字を表しているかを知りたいとき、c - '0' とすると求めたい値が手に入るなど、いろいろ便利なことができます。
今回のコードでは、'1' = '0' + 1 が成り立つことから、合計と 3 * '0' の差が '1' の数を表すようになっています。
この問題にはさらに別解があります。
与えられる文字列は、3 桁の数字だと考えることができます。
求める数は、3 桁の数字の各桁の和ですが、今回の条件ではこれは 9 未満なので、与えられる 3 桁の数字を 9 で割ったあまりが求める数と等しいことになります。
（証明も有名で、$100a+10b+c=a+b+c+9\times(11a+b)$ が成り立つため、$a+b+c<9$ のとき $100a+10b+c$ を $9$ で割ったあまりは $a+b+c$ と等しくなります。）
#include<iostream>
using namespace std;
int main() {
int a;
cin >> a;
cout << a % 9 << endl;
}
今回は与えられる文字列が 3 文字なのでこれで正しい答えが出ますが、文字数が 9 文字以上になったりすると正しい答えが出なくなります。
次の問題に行きましょう。
第 3 問 : ABC081B - Shift only
この問題は、公式で一つ別解が示されています。
AtCoder Beginners Collection記事(元記事)で紹介されている解法
#include <iostream>
using namespace std;
int N;
int A[210]; // 最大 200 個なので余裕を持って 210 に --- 200 以上ならなんでもよいです
int main() {
cin >> N;
for (int i = 0; i < N; ++i) cin >> A[i];
int res = 0;
// 操作が行える限り操作を繰り返す
while (true) {
bool exist_odd = false; // A[i] がすべて偶数かどうかを判定するフラグ
for (int i = 0; i < N; ++i) {
if (A[i] % 2 != 0) exist_odd = true; // 奇数があったらフラグを立てる
}
if (exist_odd) break; // 奇数があったら break
// 操作を行えるなら操作を実際に行う
for (int i = 0; i < N; ++i) {
A[i] /= 2;
}
++res; // 操作回数をインクリメント
}
cout << res << endl;
}
と、線形探索記事で紹介されている解法
#include <iostream>
using namespace std;
const int INF = 10000000; // 十分大きな値に
int N;
int A[210]; // 最大 200 個なので余裕を持って 210 に
int main() {
cin >> N;
for (int i = 0; i < N; ++i) cin >> A[i];
int res = INF;
for (int i = 0; i < N; ++i) {
int count = 0; // 何回 2 で割れるか
while (A[i] % 2 == 0) {
A[i] /= 2;
++count;
}
// 最小値を更新
if (res > count) res = count;
}
cout << res << endl;
}
です。
そして、もう少し考察を進めるとさらに別解があることがわかります。
「2で割る」という操作は、その数のビットをすべて1ずつずらすことです。
そして、ある数について、立っている一番下のビットが $2^i$の位のとき、その数は $i$ 回2で割れることになります。
つまり、答えは全体の中で、少なくともどこか一つで立っている一番下のビットの位置です。
なので、全体で見てどこかで立っているビットをまとめてしまっても答えを出すのに支障はありません。
複数の数で、どれか一つでも立っているビットを立たせる演算はbitwise or(|)演算だったので、$N$ 個全ての整数のbitwise orをとったあと、それが何回割れるか計算すればいいです。
これを実現するコードは以下のようになります。
#include<iostream>
using namespace std;
int N, a, b;
int main() {
cin >> N;
for (int i = 0; i < N; ++i) {
cin >> a;
b |= a; // 立っているビットをor演算でまとめる
}
int count = 0; // bが何回2で割れるかを確かめればOK
while (b % 2 == 0) {
b /= 2;
++count;
}
cout << count << endl;
}
この問題は、どの方法でプログラムを書いても大きく計算量は変わりませんが、考察によって実装量を減らせるいい例だと思います。
（競技プログラミングの問題で実装が重いと言われている問題の一部に、このように考察の方向性で実装量が大幅に変わったりするものがあります。よりよい実装方針がないか心がける習慣をつけるといいかもしれません。）
次の問題です。
第 4 問 : ABC087B - Coins
元記事では、3重ループによる全探索が解法として挙げられています。
#include <iostream>
using namespace std;
int main() {
int A, B, C, X;
cin >> A >> B >> C >> X;
int res = 0;
for (int a = 0; a <= A; ++a) {
for (int b = 0; b <= B; ++b) {
for (int c = 0; c <= C; ++c) {
int total = 500*a + 100*b + 50*c; // 合計金額
if (total == X) ++res; // 合計金額が X に一致したら答えをインクリメント
}
}
}
cout << res << endl;
}
これは$O(ABC)$の解法で、今回の制約では$ABC\leq4624$なので十分間に合います。
ですが、この解法には無駄な探索があり、それを減らすことで別解を作ることができます。(この節の内容は第 8 問: ABC 085 C - Otoshidamaでする内容とかなり重なっていますけど…)
まず、500円玉を $a$ 枚、100円玉を $b$ 枚使うことにした時点で、残りいくらを50円玉で払う必要があるかは決まっているので、50円玉を払う枚数を探索することは無駄です。
500円玉を $a$ 枚、100円玉を $b$ 枚で $X$ 円を上回る場合や、$C$ 枚の50円玉で残り金額が払いきれない場合を除いて、50円玉の支払い方はただ1通りだけです。
この処理を実装すると、次の別解になります。
#include <iostream>
using namespace std;
int main() {
int A, B, C, X;
cin >> A >> B >> C >> X;
int res = 0;
for (int a = 0; a <= A; ++a) {
for (int b = 0; b <= B; ++b) {
int part = a * 500 + b * 100; // ここまでの合計金額
if (X >= part && X - part <= C * 50) ++res;
}
}
cout << res << endl;
}
この解法は$O(AB)$の解法で、$A+B+C\leq10^4$程度でも間に合うはずです。
もう少し数学的な考察をすることで、さらに高速な別解も作ることができます。
上の解法をもう少し深く考えると、500円玉を $a$ 枚使うことを決めたとき、「500円玉を $a$ 枚、100円玉を $b$ 枚で $X$ 円を上回らないし、$C$ 枚の50円玉を使って残り金額が払いきれる」ような $b$ の個数が500円玉を $a$ 枚使う時の支払い方の通り数になります。
このような $b$ は区間になるので、区間の上の端と下の端を持っておくと答えを出すことができます。
このような区間に含まれているものの数を数え上げるとき、半開区間で区間を持っておくといいことが多いです。
この問題も、半開区間 $[b_1, b_2)$ を $b_1:=$ 残り金額を50円玉 $C$ 枚以下を使って払うことができる最小の $b$ 、$b_2:=500a+100b>X$ を満たす最小の $b$ と決めて、計算した後に $b_1,b_2$ を $[0,b+1]$ の数に収めると、$b_2-b_1$が求める通り数になります。
この処理を実装すると以下のような別解になります。
#include <iostream>
using namespace std;
int main() {
int A, B, C, X;
cin >> A >> B >> C >> X;
int res = 0;
for (int a = 0; a <= A; ++a) {
int rem = X - a * 500; // 残金
res += max(0, min(rem / 100 + 1, B + 1)) // 区間の上端
- max(0, min((rem - (C - 1) * 50) / 100, B + 1));// 区間の下端
}
cout << res << endl;
}
区間の下端が少し複雑な形ですが、これは $X$ に50円単位の端数がある時のための処理になります。
複雑な形の式はミスがあっても発見しにくいので、$X$ に50円の端数があるときははじめに $X$ から50円を引いて $C$ を一枚減らしておくといいかもしれません。
（追記 : 2019/06/06）
(1年越しの更新です！)
この問題には $O(1)$ での解法があります。
直前の $O(A)$ の解法で、max(0, min(rem / 100 + 1, B + 1)) - max(0, min((rem - (C - 1) * 50) / 100, B + 1)) を計算しています。これの第1項と第2項を別々に計算することにしましょう。
これは、どちらも公差 $5$ の数列を、$0$ 以上 $B+1$ 以下に制限したものと考えることができます。
「$0$ 以上 $B+1$ 以下に制限する」という処理は簡単ではないですが、高校数学で行うような丁寧な計算を行うことで式を立てることができます。
#include <iostream>
using namespace std;
int sum_truncated_seq(int a, int A, int B) {
int upper = max(0, min((a - B + 3) / 5, A + 1)), lower = max(0, min((a + 4) / 5, A + 1));
return (2 * a - 5 * (lower - 1 + upper)) * (lower - upper) / 2 + (B + 1) * upper;
}
int main() {
int A, B, C, X;
cin >> A >> B >> C >> X;
cout << sum_truncated_seq(X / 100 + 1, A, B) - sum_truncated_seq((X - (C - 1) * 50) / 100, A, B) << endl;
}
初項 $a$, 公差 $5$, 項数 $A+1$ の等差数列を $[0,B+1]$ の範囲に収めた数列の和を計算する関数 sum_truncated_seq を定義しています。
中身は複雑ですが、等差数列の和を少し変形した形です。これで、この問題を $O(1)$ で解くことができました。
次の問題です。
第 5 問 : ABC083B - Some Sums
元記事では全探索が紹介されています。
#include <iostream>
using namespace std;
// 各桁の和を計算する関数
int findSumOfDigits(int n) {
int sum = 0;
while (n > 0) { // n が 0 になるまで
sum += n % 10;
n /= 10;
}
return sum;
}
int main() {
int N, A, B;
cin >> N >> A >> B;
int total = 0;
for (int i = 1; i <= N; ++i) {
int sum = findSumOfDigits(i); // i の各桁の和
if (sum >= A && sum <= B) { // i の各桁の和が A 以上 B 以下かどうか
total += i;
}
}
cout << total << endl;
}
このような桁ごとに分解して考える問題には桁DPという手法が有効なことがあります。
桁DPでは、各桁を順に見て再帰関数を呼び出していくものが多いです。
#include <iostream>
using namespace std;
long long int D[5], cdp[5][37][2], sdp[5][37][2];
long long int C(int d, int s, int f) { // 下d桁の合計がs以下になるようなものの個数を数える
if (s < 0) return 0;
if (d < 0) return 1;
if (cdp[d][s][f] >= 0) return cdp[d][s][f];
long long int cnt = 0;
if (f) {
for (int i = 0; i <= 9; ++i) {
cnt += C(d - 1, s - i, f);
}
return cdp[d][s][f] = cnt;
} else {
for (int i = 0; i <= D[d]; ++i) {
cnt += C(d - 1, s - i, i != D[d]);
}
return cdp[d][s][f] = cnt;
}
}
long long int pow10(int n){ // 必要になるので10の累乗を計算します
int ret = 1, a = 10;
while(n){
if(n & 1){
ret *= a;
}
a *= a;
n /= 2;
}
return ret;
}
long long int S(int d, int s, int f = 0) { // 下d桁の合計がS以下になるようなものの合計を数える
if (s < 0) return 0;
if (d < 0) return 0;
if (sdp[d][s][f] >= 0) return sdp[d][s][f];
long long int sum = 0;
if (f) {
for (int i = 0; i <= 9; ++i) {
sum += S(d - 1, s - i, f) + i * C(d - 1, s - i, f) * pow10(d);
}
return sdp[d][s][f] = sum;
} else {
for (int i = 0; i <= D[d]; ++i) {
sum += S(d - 1, s - i, i != D[d]) + i * C(d - 1, s - i, i != D[d]) * pow10(d);
}
return sdp[d][s][f] = sum;
}
}
int main() {
fill(cdp[0][0], cdp[5][37], -1);
fill(sdp[0][0], sdp[5][37], -1);
int N;
cin >> N;
for (int i = 0; i < 5; ++i) {
D[i] = N % 10;
N /= 10;
}
int A, B;
cin >> A >> B;
cout << S(4, B) - S(4, A - 1) << endl; // 桁和がB以下のものからA未満のものを引いたのが答え
}
桁DPは強力な方法で、この問題の制約が $N\leqq10^{18}$ になっても多分通りますが、実装が重くて苦手です…（主観）
次の問題です。
第 6 問 : ABC088B - Card Game for Two
元記事では大きい順にソートしてから数を交互に変数AliceとBobに加えています。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N;
int a[110]; // 最大 100 個ですが余裕をもたせます
cin >> N;
for (int i = 0; i < N; ++i) cin >> a[i];
sort(a, a + N, greater<int>()); // a[0:N] を大きい順にソート
int Alice = 0;
int Bob = 0;
for (int i = 0; i < N; ++i) {
if (i % 2 == 0) { // Alice のターン
Alice += a[i];
}
else { // Bob のターン
Bob += a[i];
}
}
cout << Alice - Bob << endl;
}
ここで、答えansを持っておいて、交互に足したり引いたりすることで別解を作ることができます。
これは、Aliceがansに数を足し、Bobがansから数を引いて、Aliceはansをなるべく大きく、Bobはansをなるべく小さくするように行動すると考えることができます。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N;
int a[110];
cin >> N;
for (int i = 0; i < N; ++i) cin >> a[i];
sort(a, a + N, greater<int>()); // a[0:N] を大きい順にソート
int ans = 0;
for (int i = 0; i < N; ++i) {
if (i % 2 == 0) { // Alice のターン
ans += a[i];
}
else { // Bob のターン
ans -= a[i];
}
}
cout << ans << endl;
}
この言い換えでは、ほとんど処理は変わりませんが、これと逆の考え方（Aliceが最大に、Bobが最小にするように行動するものを、二人が自分のスコアを最大化すると言い換えること）で見通しが立ちやすい問題があります。
覚えておくといいことがあるかもしれません。
また、計算式を観察することで条件分岐をなくすこともできます。
$N=5$ のとき、aを小さい順にソートすると、答えは $a[4]-a[3]+a[2]-a[1]+a[0]=a[4]-\Bigl(a[3]-\bigl(a[2]-(a[1]-a[0])\ \bigr)\ \Bigr)$ のように変形できるので、aを小さい順にみていって
$\mathrm{ans}\gets a[i]-\mathrm{ans}$ としてもいいことがわかります。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N;
int a[110];
cin >> N;
for (int i = 0; i < N; ++i) cin >> a[i];
sort(a, a + N); // a[0:N] を小さい順にソート
int ans = 0;
for (int i = 0; i < N; ++i) {
ans = a[i] - ans;
}
cout << ans << endl;
}
ここまではソートに $O(N\log N)$ をかけて計算する解法ばかりでしたが、この問題はソートをしない、次の問題(ABC 085 B - Kagami Mochi)で扱ったバケット法をうまく使った $O(N)$で解く別解があります。
$c[i]:=$ 値 $i$ のカードが何枚あるか
とするのが直感的ですが、よく考えると、同じ値のカードが偶数枚あっても結果に影響はないことがわかります。
結局、
$c[i]:=$ 値 $i$ のカードが奇数枚あるか
とするといいです。
このとき、$i=1,2,\dots,100$ について、$c[i]$ がtrueならば$\mathrm{ans}\gets i-\mathrm{ans}$を実行すると答えが出ます。
#include <iostream>
using namespace std;
int N, a, ans;
int c[101];
int main() {
cin >> N;
for (int i = 0; i < N; ++i) {
cin >> a;
c[a] = !c[a];
}
for (int i = 0; i <= 100; ++i) {
if (c[i]) ans = i - ans;
}
cout << ans << endl;
}
次の問題に行きましょう。
第 7 問 : ABC085B - Kagami Mochi
この問題も元記事で複数の解法が紹介されています。
バケット法を用いた解法と、
// バケット法による解
#include <iostream>
using namespace std;
int main() {
int N;
int d[110];
cin >> N;
for (int i = 0; i < N; ++i) cin >> d[i];
int num[110] = {0}; // バケット
for (int i = 0; i < N; ++i) {
num[d[i]]++; // d[i] が 1 個増える
}
int res = 0; // 答えを格納
for (int i = 1; i <= 100; ++i) { // 1 <= d[i] <= 100 なので 1 から 100 まで探索
if (num[i]) { // 0 より大きかったら
++res;
}
}
cout << res << endl;
}
順序つき集合std::setを使った解法です。
// std::set を用いた解
#include <iostream>
#include <set>
using namespace std;
int main() {
int N;
int d[110];
cin >> N;
for (int i = 0; i < N; ++i) cin >> d[i];
set<int> values; // insert するときに重複を取り除いてくれます
for (int i = 0; i < N; ++i) {
values.insert(d[i]); // 挿入します
}
// set のサイズを出力します
cout << values.size() << endl;
}
まず、別解ではないですがstd::setと同様の機能をもった(hashを使って高速な)std::unordered_setでの実装を書きます。
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
int N;
int d[110];
cin >> N;
for(int i = 0; i < N; ++i)cin >> d[i];
unordered_set<int> s(d, d + N);
// 宣言するときに配列を渡せば自動的に重複を消してくれます(std::setでもそう)
cout << s.size() << endl;
}
次に、std::unique関数を使った実装を紹介します。
std::unique関数は、隣り合った同じ値を削除してその分後ろを詰めてくれます。
返り値は詰め終わった後の一番後ろなので、ソートした後unique関数の結果と先頭との差をとると答えがでます。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N;
int d[110];
cin >> N;
for(int i = 0; i < N; ++i)cin >> d[i];
sort(d, d + N); //ソートする
cout << unique(d, d + N) - d << endl;
}
バケット法については、計算中に答えを出していく方法があります。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N, d;
int num[110];
fill(num, num + 110, 0); // 0で初期化をしないとたいへんなことになります
cin >> N;
int ans = 0;
for(int i = 0; i < N; ++i){
cin >> d;
if(!num[d])++ans; // num[d]が0のときだけansを1増やす
++num[d]; // num[d]をふやす
}
cout << ans << endl;
}
また、バケット法を使った解法で、accumulate関数を使う方法もあります。(えびさんに教えてもらいました、ありがとうございます！)
#include <iostream>
#include <numeric>
using namespace std;
int main() {
int n;
cin >> n;
int x[101] = {}; // 初期化
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
x[a] = 1; // 出てきた数字は1に
}
cout << accumulate(x, x + 101, 0) << endl;// 合計は1がいくつあるかと同じ
}
この問題もバケット法では $O(N)$、ソートやstd::setを使う方法では $O(N\log N)$です。
次の問題へいきましょう。
第 8 問 : ABC085C - Otoshidama
問題概要は第 4 問 : ABC087B - Coins と大きく変わらないので別解の方針もあまり変わりません。
元記事の解法は第 4 問の$O(AB)$解法とほとんど同じです。
#include <iostream>
using namespace std;
int main() {
int N, Y;
cin >> N >> Y;
int res10000 = -1, res5000 = -1, res1000 = -1;
for (int a = 0; a <= N; ++a) { // 10000円の枚数を 0 〜 N で調べる
for (int b = 0; b + a <= N; ++b) { // 5000円の枚数を 0 〜 N-a で調べる
int c = N - a - b; // 1000円の枚数は決まる
int total = 10000*a + 5000*b + 1000*c;
if (total == Y) { // 答えが見つかったら
res10000 = a;
res5000 = b;
res1000 = c;
}
}
}
// 答えを出力 (見つかっていなくても -1 -1 -1 になるので OK です)
cout << res10000 << " " << res5000 << " " << res1000 << endl;
}
ところで、第 4 問に線形オーダー( $O(A)$ )の解法があったということは、こちらにもあることが予想できます。
そのために、10000円の枚数 $a$ 枚を決めたら残り $N - a$ 枚をうまく1000円と5000円にして $Y$ 円にできるかを高速に判定する方法を考えましょう。
これは、
\begin{cases}
\hphantom{5000}\ b+\hphantom{1000}\ c=N-a\\
5000\ b+1000\ c=Y-10000a
\end{cases}
という連立方程式を解くことと同じで、鶴亀算のような考え方で実装すると簡単に解くことができます。
つまり、$N-a$ 枚をとりあえず全て1000円で払い、足りない分を5000円で払ってうまく払えれば成功です。
#include <iostream>
using namespace std;
int main() {
int N, Y;
cin >> N >> Y;
int res10000 = -1, res5000 = -1, res1000 = -1;
for (int a = 0; a <= N; ++a) { // 10000円の枚数を 0 〜 N で調べる
int c = N - a; // とりあえず全部 1000円で
int b = (Y - a * 10000 - c * 1000) / 4000; // 足りない分
if (a * 10000 + b * 4000 + c * 1000 == Y && b >= 0 && b <= c) {
res10000 = a;
res5000 = b;
res1000 = c - b;
}
}
cout << res10000 << " " << res5000 << " " << res1000 << endl;
}
もちろん、連立方程式の解 $b=\dfrac{Y-1000N-9000a}{4000},c=\dfrac{5000(N+a)-Y}{4000}$ が正の整数であるかを判定するコードを書いても構いません。
整数であるかを判定するには分子が分母で割り切れるかを判定すればいいです。
#include <iostream>
using namespace std;
int main() {
int N, Y;
cin >> N >> Y;
int res10000 = -1, res5000 = -1, res1000 = -1;
for (int a = 0; a <= N; ++a) { // 10000円の枚数を 0 〜 N で調べる
int b = Y - 1000 * N - 9000 * a; // 連立方程式の解の分子
int c = 5000 * (N + a) - Y;
if (b >= 0 && c >= 0 && b % 4000 == 0 && c % 4000 == 0) { // 正で、割り切れたら
res10000 = a;
res5000 = b / 4000; // 分母で割って正しい値にする
res1000 = c / 4000;
}
}
cout << res10000 << " " << res5000 << " " << res1000 << endl;
}
ところで、この問題は解を一つ見つければいいので、一つ見つかった時点で答えを出力して終了してしまっても構いません。
こうすることで、最悪の場合(-1 -1 -1のとき)の計算量は変わりませんが、多くの場合でちょっぴり早くなることが期待できます。
#include <iostream>
using namespace std;
int main() {
int N, Y;
cin >> N >> Y;
int res10000 = -1, res5000 = -1, res1000 = -1;
for (int a = 0; a <= N; ++a) { // 10000円の枚数を 0 〜 N で調べる
int c = N - a; // とりあえず全部 1000円で
int b = (Y - a * 10000 - c * 1000) / 4000; // 足りない分
if (a * 10000 + b * 4000 + c * 1000 == Y && b >= 0 && b <= c) {
res10000 = a;
res5000 = b;
res1000 = c - b;
cout << res10000 << " " << res5000 << " " << res1000 << endl;
return 0; // 見つかったので出力して終了
}
}
cout << res10000 << " " << res5000 << " " << res1000 << endl;
}
そして、この問題にはなんと定数時間 $O(1)$ 解法があります！
ポイントは5000円札の枚数です。
5000円9枚(45000円)を10000円4枚と1000円5枚に、枚数を変えずに変換することを繰り返せば、
「条件を満たす配り方があるとき、5000円札を8枚以下しか使わない条件を満たす配り方が必ずある」ことがわかります。
なので、5000円の枚数について調べれば、0枚から8枚の9回の計算をすれば必要十分であることがわかります。
あとは、1000円と10000円について上と同様の計算をすればいいので、これは定数回の計算で答えが求まる $O(1)$ 解法です。
#include <iostream>
using namespace std;
int main() {
int N, Y;
cin >> N >> Y;
int res10000 = -1, res5000 = -1, res1000 = -1;
for (int b = 0; b <= 8; ++b) { // 5000円の枚数を 0 〜 8 で調べる
int c = N - b; // とりあえず全部1000円で
int a = (Y - 5000 * b - 1000 * c) / 9000;
if (Y == a * 9000 + b * 5000 + c * 1000 && a >= 0 && a <= c) {
res10000 = a;
res5000 = b;
res1000 = c - a;
cout << res10000 << " " << res5000 << " " << res1000 << endl;
return 0;
}
}
cout << res10000 << " " << res5000 << " " << res1000 << endl;
}
（追記 : 2018/06/15）
この問題は、なんとforループすら使わずに解くことができます！
Otoshidama、mod9で考えると5000円札の枚数は一意に決まるからループはいらないことはあまりに有名
- かならい(@sugarknri) さん 9:49 - 2018年6月15日
$\bmod9$ で問題を考えると、$a,b,c$ は次の連立一次合同式を満たします。
\begin{cases}
a+\hphantom{5}\ b+\ c\equiv N\\
a+5\ b+\ c\equiv Y
\end{cases}
これを変形すると、 $b\equiv2N+7Y\pmod9$ が成り立つことがわかります。
$0\leqq b<9$ としてよかったので、これで $b$ の値が決まりました。
$b$ の値を決めたら残りの値は決まったので、これは $O(1)$解法です。
#include <iostream>
using namespace std;
int main() {
int N, Y;
cin >> N >> Y;
int res10000 = -1, res5000 = -1, res1000 = -1;
int b = (2 * N + 7 * Y) % 9; // 連立合同式の解
int c = N - b; // とりあえず全部1000円で
int a = (Y - 5000 * b - 1000 * c) / 9000;
if (Y == a * 9000 + b * 5000 + c * 1000 && a >= 0 && a <= c) {
res10000 = a;
res5000 = b;
res1000 = c - a;
cout << res10000 << " " << res5000 << " " << res1000 << endl;
return 0;
}
cout << res10000 << " " << res5000 << " " << res1000 << endl;
}
次の問題にいきましょう。
第 9 問 : ABC049C - 白昼夢 / Daydream
この問題は元の記事中で複数の別解に言及されています。
後ろから見ていくもの（元記事のコードです）や、
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string divide[4] = {"dream", "dreamer", "erase", "eraser"};
int main() {
string S;
cin >> S;
// 後ろから解くかわりにすべての文字列を「左右反転」する
reverse(S.begin(), S.end());
for (int i = 0; i < 4; ++i) reverse(divide[i].begin(), divide[i].end());
// 端から切っていく
bool can = true;
for (int i = 0; i < S.size();) {
bool can2 = false; // 4 個の文字列たちどれかで divide できるか
for (int j = 0; j < 4; ++j) {
string d = divide[j];
if (S.substr(i, d.size()) == d) { // d で divide できるか
can2 = true;
i += d.size(); // divide できたら i を進める
}
}
if (!can2) { // divide できなかったら
can = false;
break;
}
}
if (can) cout << "YES" << endl;
else cout << "NO" << endl;
}
DP(動的計画法)、
$dp[i]:=i$文字目までをうまく切る(divide する)ことができれば $1$、できなければ $0\ $ となるように定めると、うまく遷移をすることができます。
#include <iostream>
#include <string>
using namespace std;
string divide[4] = {"dream", "dreamer", "erase", "eraser"};
bool dp[100010];
int main() {
string S;
cin >> S;
dp[0] = 1;
for(int i = 0; i < S.size(); ++i){
if(!dp[i])continue; // そこまでで矛盾があったらとりあえず無視
for(string s : divide){
if(S.substr(i, s.size()) == s){ // うまく切れたら先に進む
dp[i + s.size()] = 1;
}
}
}
cout << (dp[S.size()] ? "YES" : "NO") << endl;
return 0;
}
幅優先探索、
幅優先探索ではキュー（queue, 待ち行列）というデータ構造がよく使われます。
キューを使うと、あるものをためておいて、入れた順に取り出していくことができます。
この解法ではキューを使って文字列をうまく切ることができるところを管理しています。
#include <iostream>
#include <queue>
using namespace std;
string divide[4] = {"dream", "dreamer", "erase", "eraser"};
int main() {
string S;
cin >> S;
queue<int> BFS;
bool can = false;
BFS.push(0);
while(!BFS.empty()){ // キューが空になるまで続ける
int t = BFS.front();
BFS.pop();
if(t == S.size()){ // 最後まで切れたら成功
can = true;
break;
}
for(string s : divide){
if(S.substr(t, s.size()) == s){ // 切れたらとりあえず切ったことにしてみる
BFS.push(t + s.size());
}
}
}
cout << (can ? "YES" : "NO") << endl;
return 0;
}
ちょっと先までみる貪欲、
後ろから解法と比べて注意しないといけないのは、一回切れたらもう一回divideの最初から切れるか試さないといけないところです。(たとえばerasereraserだと、eraserを消した後にeraseの判定がきてしまってうまくいきません)
#include <iostream>
using namespace std;
string divide[3] = {"dream", "eraser", "erase"};
int main() {
string S;
cin >> S;
bool can = true;
for (int i = 0; i < S.size();) {
bool can2 = false; // 4 個の文字列たちどれかで divide できるか
for (int j = 0; j < 3; ++j) {
string d = divide[j];
if (S.substr(i, d.size()) == d) { // d で divide できるか
can2 = true;
i += d.size(); // divide できたら i を進める
if (j == 0) {
if (i == S.size())break;
if (S.substr(i, 3) == "ere" || S.substr(i, 3) == "erd" ||
(S.size() - i == 2 && S.substr(i, 2) == "er")) { // dreamerの場合、erの後に続くのはeかdだけ(かdreamerで終わりか)です
i += 2;
}
}
break;
}
}
if (!can2) { // divide できなかったら
can = false;
break;
}
}
cout << (can ? "YES" : "NO") << endl;
}
がありました。
他にも別解があります。
幅優先探索でできるものは原理的には（計算が間に合うなら）深さ優先探索を使って解くことができます。
深さ優先探索をするときは再帰関数を使うと実装が楽ですが、再帰関数は少し発展的なテーマです。実装自体はシンプルに出来上がるのが嬉しいところです。
#include <iostream>
using namespace std;
string divide[4] = {"dream", "erase", "eraser", "dreamer"};
string S;
bool DFS(int n) { // n文字目以降の文字がうまく切れるかを計算します
if (n == S.size()) return true; // 最後まできたら成功
for (string i : divide) {
if (n + i.size() <= S.size() && S.substr(n, i.size()) == i) {
if (DFS(n + i.size())) return true; // とりあえず切ってみて成功だったらうれしい
}
}
return false; // どうやっても切れなかったら失敗
}
int main() {
cin >> S;
cout << (DFS(0) ? "YES" : "NO") << endl;
}
C++11から新しく標準に追加された機能として、正規表現を扱うregexがあります。
正規表現についてはいろいろと説明するところが多いので調べてみてください。（とりあえずとても文字列処理が便利になるものと覚えておくといいです）
新機能regexを使うと、この問題の別解を作ることができます。
dream、dreamer、erase、eraserの繰り返しでできた文字列は、正規表現で(dream|dreamer|erase|eraser)*と書くことができるので（(a|b|c|...)が「a,b,cの中のどれか」、*が「直前のものを繰り返す」を表しています）、この問題は次のように解けます。
#include <iostream>
#include <string>
#include <regex>
using namespace std;
int main() {
string S;
cin >> S;
cout << (regex_match(S, regex("(dream|dreamer|erase|eraser)*")) ? "YES" : "NO") << endl;
}
（追記 : 2018/06/15）
正規表現(dream|dreamer|erase|eraser)*は(dream(er)?|eraser?)*とするとさらにシンプルに書くことができます。
?は直前のものがあってもなくてもいいとするものです。
#include <iostream>
#include <string>
#include <regex>
using namespace std;
int main() {
string S;
cin >> S;
cout << (regex_match(S, regex("(dream(er)?|eraser?)*")) ? "YES" : "NO") << endl;
}
いろいろな解法があるこの問題ですが、実は 嘘解法 もあります。
嘘解法とは、正答が出力されない（かもしれない）ケースがある解法（つまり間違った解法）で、テストケースが不十分であることによってACになってしまうようなものです。
この問題では、次のアルゴリズムが嘘解法になります。
入力された文字列 $S$ について、次のことをする。
- もし $S$ の中に文字列
"eraser"があれば、それを削除する。- もし $S$ の中に文字列
"erase"があれば、それを削除する。- もし $S$ の中に文字列
"dreamer"があれば、それを削除する。- もし $S$ の中に文字列
"dream"があれば、それを削除する。
以上が終わったとき、 $S$ が空文字列になっていれば
"YES"、なっていなければ"NO"を出力する。
C++で実装すると以下のようになります。(C++には単純置換がなさそうなのでregex_replace関数を使っています)
#include <iostream>
#include <string>
#include <regex>
using namespace std;
int main() {
string S;
cin >> S;
S = regex_replace(S, regex("eraser"), "");
S = regex_replace(S, regex("erase"), "");
S = regex_replace(S, regex("dreamer"), "");
S = regex_replace(S, regex("dream"), "");
cout << (S == "" ? "YES" : "NO") << endl;
}
この解法は、一見良さそうに見えます。(実際前からの貪欲で正しい答えが出ないdreameraserなどに対しても正しい答え"YES"を返します。)
この解法のいけないところは、たとえば"dream"の途中に"erase"を追加してできた文字列"dreraseeam"を考えるとわかります。
この文字列は、"dream"の後に"erase"を追加することでは作ることができないので、出力するべき答えは"NO"ですが、このアルゴリズムだと、
$S=$
"dreraseeam"
- $S$ の中に
"eraser"はないので何もしない。- $S$ の中に
"erase"があるので削除して、$S=$"dream"となる。- $S$ の中に
"dreamer"はないので何もしない。- $S$ の中に
"dream"があるので削除して、$S=$""となる。
$S$ が空文字列なので、答えは
"YES"！
となって、間違えてしまいます。
しかしこのコードは提出すると正解になってしまうので、これは嘘解法です。
このアルゴリズムは、削除をしたときにもともと繋がっていない文字列が繋がってしまうために間違えてしまいます。
なので正解にするためには、削除するのではなく一回"dream","dreamer","erase","eraser"に使われていない文字(たとえば"!"とか"0"とか)で隙間を支えておいて、最後にまとめて消すといいです。
#include <iostream>
#include <string>
#include <regex>
using namespace std;
int main() {
string S;
cin >> S;
S = regex_replace(S, regex("eraser"), "0"); // 使われていない文字("0")に置換
S = regex_replace(S, regex("erase"), "0");
S = regex_replace(S, regex("dreamer"), "0");
S = regex_replace(S, regex("dream"), "0");
S = regex_replace(S, regex("0"), ""); // "0"を消す
cout << (S == "" ? "YES" : "NO") << endl;
}
次の問題に行きましょう。
第 10 問: ABC086C - Traveling
元の記事では「 $t_1$ にある地点にいて、$t_2$ に目的地に行くことができる」ための条件を考えて実装しています。
#include <iostream>
using namespace std;
int main() {
int N;
int t[110000], x[110000], y[110000];
cin >> N;
t[0] = x[0] = y[0] = 0; // 初期状態
for (int i = 0; i < N; ++i) cin >> t[i+1] >> x[i+1] >> y[i+1]; // 1-index にしておく
bool can = true;
for (int i = 0; i < N; ++i) {
int dt = t[i+1] - t[i];
int dist = abs(x[i+1] - x[i]) + abs(y[i+1] - y[i]);
if (dt < dist) can = false;
if (dist % 2 != dt % 2) can = false; // dist と dt の偶奇は一致する必要あり！
}
if (can) cout << "Yes" << endl;
else cout << "No" << endl;
}
ところで問題の制約に $1\leqq t_1<t_2<\dots<t_n\leqq10^5$ という条件があります。
現在位置と次の目的地が決まったら、「とりあえず目的地に近づいて、時間が余ったらうろつく」のが最適なので、各秒ごとに動きをシミュレーションしても解くことができます。
#include <iostream>
using namespace std;
int main() {
int N;
cin >> N;
int nowt = 0, nowx = 0, nowy = 0; // 現在時刻と位置
bool can = true; // 旅行プランが実行可能？
for (int i = 0; i < N; ++i) {
int x, y, t;
cin >> t >> x >> y; // 目的時刻と目的地
for (; nowt < t; ++nowt) { // 一秒ずつシミュレーション
if (x != nowx) {
nowx += x < nowx ? -1 : 1; // xがずれていたらx方向に近づく
} else {
nowy += y < nowy ? -1 : 1; // xがずれていないのでy方向に近づく
}
}
if (x != nowx || y != nowy) { // 目的地にたどりつけなかったら実行不可能
can = false;
}
}
cout << (can ? "Yes" : "No") << endl;
}
おわりに
競技プログラミングの問題は難易度問わずいろいろな別解があることが多いです！
その中には想定解法とは全く違った視点から問題を見たものや別のきれいな構造を見出したもの、本質的に速度が早いものなどがあって、別解を味わうのは楽しいです！
みなさんも、想定解だけではない競技プログラミングの世界を楽しみましょう！
最後になりましたが、精選10問を作り上げてABSのきっかけになった(すごい)けんちょんさん、いくつかの別解を私に教えてくれたTwitterのみなさん(えびさん、ミドリムシさんほか)、ありがとうございました！
以上です。(読んでいただいてありがとうございました！)