1. はじめに
こんにちは、ryusuke です。
今回の記事は「paiza x Qiita コラボキャンペーン」で、レベルアップ問題集から選ばれた $D$ ランクから $S$ ランクの各ランク $5$ 問（計 $25$ 問）を徹底解説するものとなっております。
当初はどれか１問を解説しようと考えていましたが、「せっかくなら全部解説しちゃうか！」のノリで始めたら結構地獄を見ました。
paiza は レベルアップ問題集 の問題言及・解説等のアップロードは問題ありませんが、スキルチェック の問題は SNS 上での言及が禁止となっていますのでご気をつけください。
自分は $2021$ 年から $1$ 年間ほどですが、paiza のアルバイトとして問題・解説コード作成などの業務に携わっていました。
詳しく気になる方はこちらをご覧ください。
そんな中、このようなキャンペーンを目撃したので参加してみようと決めました。
全てを書き終わった後の追記ですが、想像の $10$ 倍くらい時間がかかりめちゃめちゃ大変でした...
単純に $1$ 問解説する記事を作る量の $25$ 倍はかかるのでとても疲れました。何かしら読んでいただき得られるものがあれば幸いです。
それでは早速解説に入っていきます。
今回は紹介する問題が $25$ 問とかなりの問題数なので一つずつは折りたたんでいます。興味のある問題を開いてご覧ください。
2. D ランク
最初は $D$ ランクの問題 $5$ 選です。
$D$ ランクは以下のような対象者が個人的には勉強にオススメです。
-
アルゴリズムとデータ構造を今後勉強していきたい
-
競技プログラミングを始めたいが何から始めれば良いかわからない
-
書きたいプログラミング言語の標準入出力や if 文 for 文の書き方が分からない
標準入出力について
以下、解説していく問題には全て 標準入出力 の処理が必要不可欠となります。
ここに関しては過去の自分が Python での標準入出力の受け取り方について解説した記事がありますので初めての方はまずはこちらをご覧ください。
D1. N倍の文字列
問題概要
この問題は入力として $N$ を受け取り、* を $N$ 個繋げたものを出力する問題となっています。
例えば、
-
$N = 3$ の時、答えは
*** -
$N = 10$ の時、答えは
**********
のようになります。
解説
Python では文字列に対して 掛け算を行うことができます。
例えば Hello に $3$ を掛けたい場合は "Hello"*3 とすることで "HelloHelloHello" になります。
これを入力として受け取った $N$ に置き換えることでこの問題を解くことが出来ます。
解答例(Python)
# 入力を受け取る
N = int(input())
# ans という変数に * を N 個繋げた文字列を格納する
ans = '*'*N
# 答えを出力する
print(ans)
解答例（C++）
#include <iostream>
#include <string>
using namespace std;
int main() {
// 入力を受け取る
int N;
cin >> N;
// ansという変数に*をN個繋げた文字列を格納する
string ans(N, '*');
// 答えを出力する
cout << ans << endl;
return 0;
}
D2. Eメールアドレス
問題概要
メールアドレスの「ローカル」部分 $s$ と「ドメイン」部分 $t$ が $1$ 行ずつ与えられるのでこれらを 「ローカル」, @, 「ドメイン」 の順に繋げた文字列を出力する問題です。
例えば、
$s = $ paiza$, t = $ example.com の時の答えは paiza@example.com となります。
解説
文字列同士（str 型同士）の足し算は + 演算子を用いて処理することが可能です。
したがって、s + '@' + t のように記述することでこの問題を解くことが出来ます。
Python では文字列を処理する際には '' もしくは "" のいずれかで囲う必要がありますが、どちらを使用しても違いはないため好みで使用してください。
解答例（Python）
# 入力を受け取る
s = input()
t = input()
# ローカル・@・ドメインの順に繋げる
ans = s + '@' + t
# 答えを出力する
print(ans)
解答例（C++）
#include <iostream>
#include <string>
using namespace std;
int main() {
// 入力を受け取る
string s, t;
cin >> s >> t;
// ローカル・@・ドメインの順に繋げる
string ans = s + "@" + t;
// 答えを出力する
cout << ans << endl;
return 0;
}
D3. 足し算
問題概要
$a$ と $b$ の $2$ つの整数が与えられるのでこれらを足し合わせた値を出力する問題です。
解説
この問題は $a$ と $b$ が同じ行に $1$ 行で与えられる点が厄介です。
これは以下のように map 関数を用いることで処理することが可能です。
a, b = map(int, input().split())
したがって、後はこれらの $2$ つの値を足し合わせて出力することで、この問題を解くことが出来ます。
解答例（Python）
# 入力を受け取る
a, b = map(int, input().split())
# a と b を足し合わせた値を出力する
print(a + b)
解答例（C++）
#include <iostream>
using namespace std;
int main() {
// 入力を受け取る
int a, b;
cin >> a >> b;
// a と b を足し合わせた値を出力する
cout << a + b << endl;
return 0;
}
D4. 一番小さい値
問題概要
$5$ つの整数が与えられるのでこれらのうち最も小さい値を出力する問題です。
解説
この問題はある程度プログラミング言語を扱えるようになると解法がいくつかありそうな問題です。
ここではよくある解法（個人調べ）を $2$ つ紹介します。
1. list で受け取って min 関数で最小値を取得する
$5$ つの整数を list 型で受け取ることを考えます。
Python では内包表記を使用して以下のように受け取ることが出来ます。
n = [int(input()) for _ in range(5)]
見慣れないかもしれませんが for 文（繰り返し処理）を $5$ 回行い、ループの度に整数を受け取り配列に格納します。
list の中の最小値を取得する場合は min 関数を使用することで取得することが出来ます。
配列 n の中の最小値を出力する
print(min(n)
2. if 文を用いて最小値を取得する
for 文を用いて $1$ 行ずつ整数を受け取ります。
受け取る度に if 文を用いて現状の最小値と比較し、$n$ の方が小さい場合は答えを更新します。
解答例（Python）
- list で受け取り min 関数で最小値を取得する
# 入力を受け取る
n = [int(input()) for _ in range(5)]
# ans に配列 n の最小値を格納する
ans = min(n)
# 答えを出力する
print(ans)
- if 文で最小値を求める
# 入力を受け取る
ans = 100
for _ in range(5):
# 入力を受け取る
n = int(input())
# 現状の最小値よりも n の方が小さければ ans を更新する
if n < ans:
ans = n
# 答えを出力する
print(ans)
解答例（C++）
- list で受け取り min 関数で最小値を取得する
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
// 入力を受け取る
vector<int> n(5);
for (int i = 0; i < 5; ++i) {
cin >> n[i];
}
// ans に配列 n の最小値を格納する
int ans = *min_element(n.begin(), n.end());
// 答えを出力する
cout << ans << endl;
return 0;
}
- if 文で最小値を求める
#include <iostream>
using namespace std;
int main() {
// 初期値を設定する
int ans = 100;
for (int i = 0; i < 5; ++i) {
// 入力を受け取る
int n;
cin >> n;
// 現状の最小値よりも n の方が小さければ ans を更新する
if (n < ans) {
ans = n;
}
}
// 答えを出力する
cout << ans << endl;
return 0;
}
D5. 文字の一致
問題概要
文字列 $a$ と $b$ が与えられるのでこれらが同じ文字列であるかどうかを判定する問題です。
解説
文字列が一致しているかどうかは if 文を用いることで判定することが出来ます。
したがって、$2$ つの文字列を比較することでこの問題を解くことが出来ます。
解答例（Python）
# 入力を受け取る
a = input()
b = input()
# a と b が同じかどうかを判定する
if a == b:
print("OK")
else:
print("NG")
解答例（C++）
#include <iostream>
#include <string>
using namespace std;
int main() {
// 入力を受け取る
string a, b;
cin >> a >> b;
// a と b が同じかどうかを判定する
if (a == b) {
cout << "OK" << endl;
} else {
cout << "NG" << endl;
}
return 0;
}
3. C ランク
続いては $C$ ランクの問題解説となります。
$C$ ランクは以下のような対象者が個人的には勉強にオススメです。
-
基礎的な文法は理解できたので演習を積んでいきたい
-
競技プログラミングの問題に慣れたい
C1. 残り物の量
問題概要
質量 $m$ の物体があります。
このうちの $(100 - p)$ % の物体を $m^{\prime}$ とします。
さらに $m^{\prime}$ の $(100 - q)$ % を求めてください。
解説
$m$ の $(100 - p)$ % は $m \times \dfrac{100 - p}{100}$ で求めることが出来ます。
さらにその $(100 - q)$ % は $m \times \dfrac{100 - p}{100} \times \dfrac{100 - q}{100}$ で求めることが出来ます。
解答例（Python）
# 入力を受け取る
m, p, q = map(int, input().split())
# 売れ残ったお惣菜
ans = m * (100 - p) / 100
# 売れ残った量
ans = ans * (100 - q) / 100
# 答えを出力する
print(ans)
解答例（C++）
#include <iostream>
using namespace std;
int main() {
// 入力を受け取る
int m, p, q;
cin >> m >> p >> q;
// 売れ残ったお惣菜
double ans = m * (100 - p) / 100.0;
// 売れ残った量
ans = ans * (100 - q) / 100.0;
// 答えを出力する
cout << ans << endl;
return 0;
}
C2. Fizz Buzz
問題概要
いわゆる FizzBuzz 問題というものです。
https://ja.wikipedia.org/wiki/Fizz_Buzz
初めて聞いたという方は wikipedia を貼ってみたので読んでみてください。
エンジニアを目指す方であれば流石に知っていてほしい典型的なコーディング試験に出題される問題です。
解説
FizzBuzz 問題では整数 $N$ に対して $M$ で割った 余り を求める必要があります。
大半のプログラミング言語では % 演算子を用いることで余りを求めることが出来ます。
今回は $3$ で割り切れる、もしくは $5$ で割り切れるかの判別が必要になります。
if 文の条件分岐は前の問題でも触れたように、条件の厳しいもの から絞り込んでいく必要があります。
今回は $3$ でも割り切れる かつ $5$ でも割り切れるような数字を求めるというのが最も厳しい条件になるのでこれを最初の条件分岐に持ってきます。
あとは適切に条件分岐をしていくことでこの問題を解くことが出来ました。
FizzBuzz は典型問題なので。知らなかった・解けなかったという方は必ず抑えるようにしましょう。
解答例（Python）
# 入力を受け取る
N = int(input())
# 1 から N を for 文でループさせる
for i in range(1, N + 1):
if i % 3 == 0 and i % 5 == 0:
# 3 でも 5 でも割り切れる場合
print("Fizz Buzz")
elif i % 3 == 0:
# 3 で割り切れる場合
print("Fizz")
elif i % 5 == 0:
# 5 で割り切れる場合
print("Buzz")
else:
# いずれにも該当しない場合は数字を出力する
print(i)
解答例（C++）
#include <iostream>
using namespace std;
int main() {
// 入力を受け取る
int N;
cin >> N;
// 1 から N を for 文でループさせる
for (int i = 1; i <= N; ++i) {
if (i % 3 == 0 && i % 5 == 0) {
// 3 でも 5 でも割り切れる場合
cout << "Fizz Buzz" << endl;
} else if (i % 3 == 0) {
// 3 で割り切れる場合
cout << "Fizz" << endl;
} else if (i % 5 == 0) {
// 5 で割り切れる場合
cout << "Buzz" << endl;
} else {
// いずれにも該当しない場合は数字を出力する
cout << i << endl;
}
}
return 0;
}
C3. みかんの仕分け
問題概要
自然数となる $N$ の倍数ごとに箱があります。
あるみかんの重さは $w [g]$ です。
このみかんと重さの絶対値の差が最も小さい箱にみかんを入れたいです。このようなみかんが複数ある場合にはより大きい箱に分類します。
$M$ 個のみかんを正しく分類してください。
解説
この問題は実装量自体は少ないですが、考察や数学的な思考力が必要となるような問題です。
まずは、$w$ 以下の最大の $N$ の倍数 $d_1$ を求めます。
これは $w$ を $N$ で割った商を $p$ としたとき、$d_1 = pN$ として求めることが出来ます。
次に $w$ より大きい最小の $N$ の倍数 $d_2$ を求めます。
これは先ほど求めた $d_1$ に $N$ を加算することで答えを求めることが出来ます。
あとはこれらの値と $w$ との絶対値の差が大きい方が答えとなります。
しかし、この際 $d_1$ が $0$ となってしまう場合があるので正であるかの確認と、不等号の有無に気をつける必要があります。
このようにしてこの問題を解くことが出来ました。
解答例（Python）
# 入力を受け取る
N, M = map(int, input().split())
for _ in range(M):
w = int(input())
# w 以下の最大の N の倍数
d1 = (w // N * N)
# w より大きい最小の N の倍数
d2 = d1 + N
if abs(w - d1) < abs(w - d2) and d1 > 0:
print(d1)
else:
print(d2)
解答例（C++）
#include <iostream>
using namespace std;
int main() {
// 入力を受け取る
int N, M;
cin >> N >> M;
for (int i = 0; i < M; ++i) {
int w;
cin >> w;
// w 以下の最大の N の倍数
int d1 = (w / N) * N;
// w より大きい最小の N の倍数
int d2 = d1 + N;
if (abs(w - d1) < abs(w - d2) && d1 > 0) {
cout << d1 << endl;
} else {
cout << d2 << endl;
}
}
return 0;
}
C4. 野球の審判
問題概要
$N$ 球の野球ボールが投げられます。
各球は「ストライク」か「ボール」のいずれかであり、ストライクカウントが $3$ つ溜まると「アウト」、ボールカウントが $4$ つ溜まると「フォアボール」になります。
各球が投げられる度にどれに該当するのか対応した文字列を出力してください。
解説
この問題は条件分岐の多い if 文の処理を行う問題になります。
まずはストライクとボールの数をカウントするための「ストライクカウント」、「ボールカウント」を集計する変数 strike と ball を用意します。
その後、投げられた球がストライクならば strike を $1$ 増やし、ボールなら ball を $1$ 増やします。
最後に、strike が $3$ つ溜まったならば out!、ball が $4$ つ溜まったならば fourball!、そうでなければ対応する球の strike! もしくは ball! を出力することで、この問題を解くことが出来ます。
解答例（Python）
# 入力を受け取る
N = int(input())
s = [input() for _ in range(N)]
ball = 0 # ボールカウント
strike = 0 # ストライクカウント
for i in range(N):
# ボール・ストライクカウント判定
if s[i] == "ball":
ball += 1
if s[i] == "strike":
strike += 1
if ball == 4: # フォアボール
print("fourball!")
elif strike == 3: # アウト
print("out!")
elif s[i] == "strike": # ストライク
print("strike!")
else: # ボール
print("ball!")
解答例（C++）
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
// 入力を受け取る
int N;
cin >> N;
vector<string> s(N);
for (int i = 0; i < N; i++) {
cin >> s[i];
}
int ball = 0; // ボールカウント
int strike = 0; // ストライクカウント
for (int i = 0; i < N; i++) {
// ボール・ストライクカウント判定
if (s[i] == "ball") {
ball += 1;
}
if (s[i] == "strike") {
strike += 1;
}
if (ball == 4) { // フォアボール
cout << "fourball!" << endl;
break; // フォアボールでゲームが終了するのでループを終了
} else if (strike == 3) { // アウト
cout << "out!" << endl;
break; // アウトでゲームが終了するのでループを終了
} else if (s[i] == "strike") { // ストライク
cout << "strike!" << endl;
} else { // ボール
cout << "ball!" << endl;
}
}
return 0;
}
C5. 宝くじ
問題概要
宝くじの当選番号 $b$ と $n$ 枚の購入した宝くじの番号 $a_i \enspace (1 \leq i \leq n)$ が与えられます。
当選しているかどうかは以下のルールに基づきます。
| 賞 | 条件 |
|---|---|
| $1$等 | 当選番号（$b$）と一致する |
| 前後賞 | 当選番号 $\pm 1$ の番号と一致する |
| $2$等 | 当選番号の下 $4$ 桁と一致する |
| $3$等 | 当選番号の下 $3$ 桁と一致する |
| ハズレ | 上記のいずれにも満たさない |
購入した宝くじそれぞれについてどれに該当するか判別してください。
解説
この問題は複雑な if 文の問題となっています。
if 文の条件が複数ある場合は一般に 条件の厳しいもの から絞っていくのが重要です。
例えばこの問題であれば、$1$ 等の条件を満たしていれば $2$ 等の条件も満たしていますが、$2$ 等の条件を満たしていても $1$ 等の条件を満たしているとは限りません。
したがって、条件の厳しいものから絞っていくことが重要になってきます。
ここで各賞の判別に「下◯桁が一致する」というものがあります。これは余りを取ることで解決します。
例えば下 $3$ 桁が一致するかどうかに千の位よりも大きい桁については考える必要がありません。
したがって、$1000$ で割った余りが一致するかどうか を判定することで解決します。
このように丁寧に条件分岐を行うことでこの問題を解くことが出来ました。
前後賞の場合は adjacent と出力しますが、このように決められた文字列を出力する場合は、手打ちせずにコピー & ペーストすることを推奨します。
手打ちで合ってると思ってもタイピングミスなどにより不正解となってしまうと勿体無いですからね。
解答例（Python）
# 入力を受け取る
b = int(input())
n = int(input())
a = [int(input()) for _ in range(n)]
for i in range(n):
if b == a[i]: # １等であるかどうか
print("first")
elif (a[i] + 1 == b) or (a[i] - 1 == b): # 前後賞であるかどうか
print("adjacent")
elif b % 10000 == a[i] % 10000: # ２等かどうか
print("second")
elif b % 1000 == a[i] % 1000: # ３等かどうか
print("third")
else: # ハズレ
print("blank")
解答例（C++）
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 入力を受け取る
int b, n;
cin >> b >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
if (b == a[i]) { // １等であるかどうか
cout << "first" << endl;
} else if ((a[i] + 1 == b) || (a[i] - 1 == b)) { // 前後賞であるかどうか
cout << "adjacent" << endl;
} else if (b % 10000 == a[i] % 10000) { // ２等かどうか
cout << "second" << endl;
} else if (b % 1000 == a[i] % 1000) { // ３等かどうか
cout << "third" << endl;
} else { // ハズレ
cout << "blank" << endl;
}
}
return 0;
}
4. B ランク
ここからは $B$ ランクの問題解説となります。
$B$ ランクは以下のような対象者が個人的には勉強にオススメです。
-
基礎文法は完璧だが、実装が重かったり if, for 文が組み合わさる複雑な処理を苦手としている
-
計算量を少しずつ意識して高速なコードを書く練習をしていきたい
B1. 名刺バインダー管理
問題概要
$1$ 枚のファイルに $n$ 個のポケットが横に並んでおり、裏表で名刺を入れられるバインダーがあります。
例えば $n = 3$ の時は以下のようになります。
1 枚目
表 1 2 3
裏 (6) (5) (4)
2 枚目
表 7 8 9
裏 (12) (11) (10)
3 枚目
表 13 14 15
裏 (18) (17) (16)
整数 $m$ の裏（裏の場合は表）の数字を求めてください。
例えば上記の例で $m = 8$ の時の答えは $11$ になります。
解説
これは実験をすると見えてくる問題です。
競技プログラミングでは考察・実験をして具体的な値を代入することで規則が見えるということが多々あります。
これはその典型的な例です。
まずは裏表を足した値について着目します。
すると、（上記の例では） $1$ 枚目の裏表の合計は $7$、$2$ 枚目の裏表の合計は $19$、$3$ 枚目の合計は $31$ になっていることがわかります。
この数を数列とみなしていくと、$12$ ずつ増えている ことから以下のように続いていくことが予想できます。
7 19 31 43 55 67 79 91 ...
これは高校数学で習う初項が $7$、公差が $12$ の等差数列であることがわかります。
上記の例では $n = 3$ の例ですが、一般に $n$ の場合は初項が $2n + 1$、公差が $4n$ の等差数列になります。
したがって、初項と公差がわかったので残りは項数が必要になってきます。
項数は $2n$ ずつ次のファイルに増えていくので $ \displaystyle \lceil \dfrac{m}{2n} \rceil$ となります。
一般に $\dfrac{b}{a}$ の切り上げは $\dfrac{a + b - 1}{a}$ の切り捨てで求めることができるので、今回の場合は $\dfrac{2n + m - 1}{2n}$ の切り捨てで求めることが出来ます。
これで項数が分かったので後は公式に代入し、総和から $m$ を引いた値が答えになります。
計算量は $O(1)$ で高速に動作します。
解答例（Python）
# 入力を受け取る
n, m = map(int, input().split())
# 1 枚のファイルに並べられる名刺の個数
card = 2*n
# 前から何枚目のファイルに探したい名刺があるか
num = (card + m - 1) // card
# 2 枚目以降から何枚あるのか + 1枚目のファイルの合計は card + 1
sum_ = (card*2*(num - 1)) + (card + 1)
# 答えを出力する
print(sum_ - m)
解答例（C++）
#include <iostream>
using namespace std;
int main() {
// 入力を受け取る
int n, m;
cin >> n >> m;
// 1 枚のファイルに並べられる名刺の個数
int card = 2 * n;
// 前から何枚目のファイルに探したい名刺があるか
int num = (card + m - 1) / card;
// 2 枚目以降から何枚あるのか + 1枚目のファイルの合計は card + 1
int sum_ = (card * 2 * (num - 1)) + (card + 1);
// 答えを出力する
cout << sum_ - m << endl;
return 0;
}
B2. 長テーブルのうなぎ屋
問題概要
時計回りに座席番号が $1, 2, 3 \dots, n - 1, n, 1, 2 \dots$ と円形に並んだ席があります。
$m$ 組のグループがこの席に座ろうとしており、$i \enspace (1 \leq i \leq m)$ 組目は $a_i$ 人の客で座席番号が $b_i$ から時計回りに詰めて座ります。
どこか $1$ 人の席でも既に埋まっている場合は座りません。
全部で何人の客が座れるか求めてください。
解説
$n, m$ の制約が共に小さいので全探索することを考えます。
前から順に調べ上げていきますが、既に座席番号 $i \enspace (1 \leq i \leq n)$ に人が座っているかどうかを管理する bool 型の変数 is_ok を定義します。
全ての席が条件を満たす場合は再度二重 for 文で is_ok を更新します。
このようにしてこの問題は $O(nm)$ で解くことが出来ました。
解答例（Python）
# 入力を受け取る
n, m = map(int, input().split())
a, b = [0]*n, [0]*n
for i in range(m):
a[i], b[i] = map(int, input().split())
# is_ok[i] := 座席番号 i に人がいるかどうか
is_ok = [False]*n
ans = 0 # 座れる合計人数
for i in range(m):
check = True # i 番目のグループが座れるかどうか
for j in range(a[i]):
# 既に人がいる場合は i 番目のグループは座れない
if is_ok[(b[i] + j - 1) % n]:
check = False
# 座れる場合
if check:
# a[i] 人の席を True にする
for j in range(a[i]):
is_ok[(b[i] + j - 1) % n] = True
# 答えに a[i] を加える
ans += a[i]
# 答えを出力する
print(ans)
解答例（C++）
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 入力を受け取る
int n, m;
cin >> n >> m;
vector<int> a(m), b(m);
for (int i = 0; i < m; ++i) {
cin >> a[i] >> b[i];
}
// is_ok[i] := 座席番号 i に人がいるかどうか
vector<bool> is_ok(n, false);
int ans = 0; // 座れる合計人数
for (int i = 0; i < m; ++i) {
bool check = true; // i 番目のグループが座れるかどうか
for (int j = 0; j < a[i]; ++j) {
// 既に人がいる場合は i 番目のグループは座れない
if (is_ok[(b[i] + j - 1) % n]) {
check = false;
break;
}
}
// 座れる場合
if (check) {
// a[i] 人の席を True にする
for (int j = 0; j < a[i]; ++j) {
is_ok[(b[i] + j - 1) % n] = true;
}
// 答えに a[i] を加える
ans += a[i];
}
}
// 答えを出力する
cout << ans << endl;
return 0;
}
B3. みんなでしりとり
問題概要
しりとりを $N$ 人でします。
ルールが $4$ つあります。
- 発言は、単語リストにある $K$ 個の単語のうちのいずれかの単語でなければならない。
- 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
- 今までに発言された単語を発言してはならない。
-
zで終わる単語を発言してはならない。
$M$ ターンしりとりを行い最後まで残っている友達の人数を求めてください。
ただし、最低一人はしりとりに最後まで残ることが保証されます。
解説
この問題は個人的には 今回の $B$ 問題で最難関 です。
というのも実装量がとても多く、バグ無しにコード書く技術は高い実装力が必要となります。
$1$ つずつルールを見ていきましょう。
ルール $1$
- 発言は、単語リストにある $K$ 個の単語のうちのいずれかの単語でなければならない。
これは collections ライブラリの defaultdict モジュールを使用することで簡潔に実装することが出来ます。
Python では defaultdict を競技プログラミングで使用することが多々あるので初めて知ったと言う方は必ず抑えましょう。
Python では標準実装されている dict を用いると key が存在するかどうかを調べないと存在しない場合にエラーとなってしまいます。
しかし defaultdict はエラーを吐かずに自分で設定した初期値が返ってきます。
今回は key を文字列、value を使用したかどうかの bool 値で持つことを考えます。
初期値は全て使用していないので False にしますが、それ以外の単語（$K$ 単語以外）は既に使用したことと看做したいので初期値は True とします。
ルール $2$
- 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
これは $i \enspace (1 \leq i \leq M)$ ターン以降の時に $i - 1$ ターン目の単語の末尾と比較することで判定を行うことが出来ます。
ルール $3$
- 今までに発言された単語を発言してはならない。
これは defaultdict を用いて、word[s[i]] が True となっていれば脱落になります。
ルール $4$
-
zで終わる単語を発言してはならない。
これは $s_i$ の末尾が z であるかどうかを判定すれば良いです。
以上を全て実装すると中々な記述量となりますが、$O(NM \log(\max(|d_i|)))$ となります。
defaultdict を使用した場合は $O(1)$ ではなく、操作に $O(\log(|d_i|))$ かかってしまいます。
この問題のように $N, M$ が小さい場合は問題ありませんが、大きい場合は工夫するか使用せずに実装する必要があります。
解答例（Python）
from collections import defaultdict
# 入力を受け取る
N, K, M = map(int, input().split())
d = [input() for _ in range(K)]
s = [input() for _ in range(M)]
# word[d[i]] := d[i] を既に使用したかどうか
word = defaultdict(lambda : True)
for i in range(K):
word[d[i]] = False
# survival[i] := 友達 i が脱落したかどうか
survival = [False]*N
now = 0 # 現在のターンが誰なのか
for i in range(M):
# 誰のターンなのかを調べる
for j in range(N):
# 脱落している場合はスキップする
if survival[(now + j) % N]:
continue
# 脱落していない友達を見つけたら for 文を抜ける
now = (now + j) % N
break
check = False # このターンの友達が脱落するかどうか
# ルール 1. K 個の単語のいずれかでなければならない
# ルール 3. 既に発言していた場合は発言禁止
if word[s[i]]:
check = True
# ルール 4. z で終わってはいけない
if s[i][-1] == 'z':
check = True
# ルール 2. 直前の人の発言の末尾と一致する必要がある
# 初回のターンは前のプレイヤーがいない
if i != 0:
# 前のターンに友達が脱落していればルール 2. は適用されない
if last != s[i][0] and not last_friend:
check = True
# 末尾の文字
last = s[i][-1]
# s_i を使用済みにする
word[s[i]] = True
# このターンに友達が脱落したかどうか（2 ターン目以降のルール 2. で必要）
if check:
survival[now] = True
last_friend = True
else:
last_friend = False
# ターンを進める
now += 1
# 答えを出力する
print(survival.count(False))
for i in range(N):
# 脱落している友達は出力しない
if survival[i]:
continue
print(i + 1)
解答例（C++）
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
// 入力を受け取る
int N, K, M;
cin >> N >> K >> M;
vector<string> d(K);
vector<string> s(M);
for (int i = 0; i < K; ++i) {
cin >> d[i];
}
for (int i = 0; i < M; ++i) {
cin >> s[i];
}
// word[d[i]] := d[i] を既に使用したかどうか
unordered_map<string, bool> word;
for (int i = 0; i < K; ++i) {
word[d[i]] = false;
}
// survival[i] := 友達 i が脱落したかどうか
vector<bool> survival(N, false);
int now = 0; // 現在のターンが誰なのか
string last = "";
bool last_friend = false;
for (int i = 0; i < M; ++i) {
// 誰のターンなのかを調べる
for (int j = 0; j < N; ++j) {
// 脱落している場合はスキップする
if (survival[(now + j) % N]) {
continue;
}
// 脱落していない友達を見つけたら for 文を抜ける
now = (now + j) % N;
break;
}
bool check = false; // このターンの友達が脱落するかどうか
// ルール 1. K 個の単語のいずれかでなければならない
// ルール 3. 既に発言していた場合は発言禁止
if (word[s[i]]) {
check = true;
}
// ルール 4. z で終わってはいけない
if (s[i].back() == 'z') {
check = true;
}
// ルール 2. 直前の人の発言の末尾と一致する必要がある
// 初回のターンは前のプレイヤーがいない
if (i != 0) {
// 前のターンに友達が脱落していればルール 2. は適用されない
if (last != s[i].front() && !last_friend) {
check = true;
}
}
// 末尾の文字
last = s[i].back();
// s_i を使用済みにする
word[s[i]] = true;
// このターンに友達が脱落したかどうか（2 ターン目以降のルール 2. で必要）
if (check) {
survival[now] = true;
last_friend = true;
} else {
last_friend = false;
}
// ターンを進める
now += 1;
}
// 答えを出力する
int remaining = 0;
for (int i = 0; i < N; ++i) {
if (!survival[i]) {
remaining++;
}
}
cout << remaining << endl;
for (int i = 0; i < N; ++i) {
// 脱落している友達は出力しない
if (survival[i]) {
continue;
}
cout << i + 1 << endl;
}
return 0;
}
B4. 神経衰弱
問題概要
$N$ 人で神経衰弱を行います。
$L$ ターン行われ、各ターンで引いたカードが一致すればその手番のプレイヤーは $2$ 点を獲得し、そうでない場合は手番を交代します。
最終的に各プレイヤーの獲得した点数を出力してください。
解説
これはシミュレーションを行う問題です。
計算量的に愚直にシミュレーションを行っても特に問題はありません。
このレベル層の方々で躓きそうなポイントをいくつか列挙して解説していきます。
まずは手番が $1, 2, 3, \dots, N, 1, 2, \dots$ とループしていく点です。
これは現在の手番を表す変数 turn を用意し、手番が次のプレイヤーに変わったタイミングで turn の値を $1$ 増やします。その後、この値を $N$ で割った余りを取れば常に $0$ から $N - 1$ の範囲で手番を扱うことが出来ます。
次に手番の点数を扱う場合、 point という長さ $N$ の配列を用意しておき、同じ数字のカードを捲った場合、point[turn] の値を $2$ 増やすことで答えを求めることが出来ます。
計算量は $O(N + L)$ で十分高速です。
解答例（Python）
# 入力を受け取る
H, W, N = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(H)]
turn = 0 # どのプレイヤーの手番か
# point[i] := プレイヤー i の点数
point = [0]*N
L = int(input())
for _ in range(L):
# 入力を受け取り、同時に 0-indexed に変換する
a, b, A, B = map(lambda x: int(x) - 1, input().split())
# 同じ数字カードか判別する
if t[a][b] != t[A][B]:
# 違う場合は手番が次に回る
turn += 1
turn %= N
else:
# 同じ場合は 2 点入る
point[turn] += 2
# 答えを出力する
for i in range(N):
print(point[i])
解答例（C++）
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 入力を受け取る
int H, W, N;
cin >> H >> W >> N;
vector<vector<int>> t(H, vector<int>(W));
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
cin >> t[i][j];
}
}
int turn = 0; // どのプレイヤーの手番か
vector<int> point(N, 0); // point[i] := プレイヤー i の点数
int L;
cin >> L;
for (int i = 0; i < L; ++i) {
int a, b, A, B;
cin >> a >> b >> A >> B;
// 0-indexed に変換する
a--; b--; A--; B--;
// 同じ数字カードか判別する
if (t[a][b] != t[A][B]) {
// 違う場合は手番が次に回る
turn = (turn + 1) % N;
} else {
// 同じ場合は 2 点入る
point[turn] += 2;
}
}
// 答えを出力する
for (int i = 0; i < N; ++i) {
cout << point[i] << endl;
}
return 0;
}
B5. 3Dプリンタ
問題概要
$3$ 次元に積まれたブロックがあります。これを $X$ 軸方向から見た時（次元は $Y \times Z$ の二次元になる）、のブロックの見え方を求めてください。
解説
三次元配列の問題です。実装自体は少ないですが、三次元でイメージが難しいため、中々慣れていないと入力の受け取り方や答えの求め方に苦戦するかと思います。
まずは入力の受け取り方についてです。
入力の与えられ方に着目すると、$X + 1$ 行の二次元配列を $Z$ 回受け取ることで三次元配列を実現しています。
また $X$ 回目のループでは -- が与えられるので、これは答えを求めるのには不要なので条件分岐を行う必要があります。
続いて答えの求め方についてです。
$X$ 軸方向から見ると言うことは、答えは $Y \times Z$ の二次元配列になります。したがって、$Y \times Z$ の二次元配列 ans を定義します。
各セル（$ans_{i, j}$） には入力で受け取ったブロック $S$ のうち、$S_{k, i, j}$ の $i$ 成分を全探索し（入力例の画像の奥に進むイメージ）、一つでもブロックがあれば、$ans_{k, j}$ を # に更新することで解くことが出来ます。
計算量は $O(XYZ)$ となり十分高速です。
解答例（Python）
# 入力を受け取る
X, Y, Z = map(int, input().split())
S = []
for _ in range(Z):
s = []
for i in range(X + 1):
if i != X:
s.append(input())
else:
input()
S.append(s)
ans = [['.']*Y for _ in range(Z)]
for k in range(Z):
for j in range(Y):
# X が大きい順に見ていく
for i in reversed(range(X)):
if S[k][i][j] == '#':
ans[k][j] = '#'
# 答えを出力する
for i in reversed(range(Z)):
print(*ans[i], sep="")
解答例（C++）
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
// 入力を受け取る
int X, Y, Z;
cin >> X >> Y >> Z;
vector<vector<string>> S(Z, vector<string>(X));
// データを入力する
for (int k = 0; k < Z; ++k) {
for (int i = 0; i < X + 1; ++i) {
string line;
cin >> line;
if (i != X) {
S[k][i] = line;
}
}
}
// 初期化
vector<vector<char>> ans(Z, vector<char>(Y, '.'));
// 判定と更新
for (int k = 0; k < Z; ++k) {
for (int j = 0; j < Y; ++j) {
for (int i = X - 1; i >= 0; --i) {
if (S[k][i][j] == '#') {
ans[k][j] = '#';
break;
}
}
}
}
// 答えを出力する
for (int i = Z - 1; i >= 0; --i) {
for (int j = 0; j < Y; ++j) {
cout << ans[i][j];
}
cout << endl;
}
return 0;
}
5. A ランク
ここからは $A$ ランクの問題解説となります。
$A$ ランクは以下のような対象者が個人的には勉強にオススメです。
- 高度なアルゴリズムを駆使して問題を解けるようになりたい
- 愚直なコードでは実行時間制限に間に合わないので、工夫して高速なコードを実装する練習がしたい
A1. お菓子の詰め合わせ
問題概要
$N$ 個のお菓子があります。
これらから $X$ 円を超えず、買った個数が最大となる組み合わせの中でお釣りを最小化せよ。
解説
この問題は 制約に着目する ことが重要です。
競技プログラミングでは特徴的な制約から解法を考察する場面も多々あります。
今回の場合は $N$ が高々 $20$ なのでそれぞれのお菓子を買うか買わないかの $2$ 通りを全探索した場合、全ての組み合わせは $2^{20} = 1024^3 ≒ 10^6$ 程度しかありません。
したがって全探索することが可能です。
このように買う、買わないの $2$ 通りを全探索する方法を bit全探索 と言います。
bit全探索のアルゴリズムを簡潔に下に示します。
- $2^N$ 通りを for 文でループさせる
- 二重 for 文で各組み合わせに対してビットが立っているかどうかを判定する
- ビットが立っている場合、$j$ 番目の商品を購入する処理を行う
このような処理を行うことでこの問題を解くことが出来ました。
計算量は $O(N2^N)$ となります。
解答例（Python）
N, X = map(int, input().split())
x = [int(input()) for _ in range(N)]
ans = [10**10, 0] # 答えとなる（金額, 個数）
for bit in range(1 << N): # 2^N 通りを全探索する
money = 0 # 購入したお菓子の金額
cnt = 0 # 購入したお菓子の個数
for j in range(N): # ビットが立っているかどうかを判定する
if (bit >> j) & 1:
# ビットが立っている時にお菓子を購入する
money += x[j]
cnt += 1
# お菓子の総額が X を超えている場合はスキップ
if money > X:
continue
if cnt < ans[1]:
# 購入したお菓子の個数が現状の答えよりも小さい場合はスキップ
continue
elif cnt == ans[1]:
# 個数が現状の最大値と同じ場合はお釣りを最小化する
ans[0] = min(ans[0], X - money)
else:
# 個数の方が大きい場合は答えを全て更新する
ans = [X - money, cnt]
print(ans[0])
解答例（C++）
#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
using namespace std;
int main() {
int N, X;
cin >> N >> X;
vector<int> x(N);
for (int i = 0; i < N; ++i) {
cin >> x[i];
}
pair<int, int> ans = {numeric_limits<int>::max(), 0}; // 答えとなる（金額, 個数）
for (int bit = 0; bit < (1 << N); ++bit) { // 2^N 通りを全探索する
int money = 0; // 購入したお菓子の金額
int cnt = 0; // 購入したお菓子の個数
for (int j = 0; j < N; ++j) { // ビットが立っているかどうかを判定する
if (bit & (1 << j)) {
// ビットが立っている時にお菓子を購入する
money += x[j];
cnt += 1;
}
}
// お菓子の総額が X を超えている場合はスキップ
if (money > X) {
continue;
}
if (cnt < ans.second) {
// 購入したお菓子の個数が現状の答えよりも小さい場合はスキップ
continue;
} else if (cnt == ans.second) {
// 個数が現状の最大値と同じ場合はお釣りを最小化する
ans.first = min(ans.first, X - money);
} else {
// 個数の方が大きい場合は答えを全て更新する
ans = {X - money, cnt};
}
}
cout << ans.first << endl;
return 0;
}
A2. じゃんけんの手の出し方
問題概要
$N$ 回じゃんけんをします。
出した手の指がポイントとなり、グーを出したら $0$ ポイント、チョキを出したら $2$ ポイント、パーを出したら $5$ ポイントになります。
$N$ 回のじゃんけんの合計が $M$ ポイントになるように手を出す時、勝つ回数の最大値を求めよ。
解説
これは典型的な 動的計画法（Dinamic Programming） と呼ばれるアルゴリズムですね。英語の頭文字を取って良く dp と呼ばれることもあります。
まずは次のような
$\begin{aligned} {\mathrm dp}[i][j] &= i 番目までのじゃんけんでポイントが j 点の時の勝つ回数の最大値 \end{aligned}$ と定義します。
このように定義することで、答えは $\begin{aligned} {\mathrm dp}[N][M] \end{aligned}$ となります。
次に初期値です。
遷移できない箇所は $-1$ と今回は考えたいため、全てのセルの初期値は $-1$ とします。
ただし、${\mathrm dp} [0][0]$ は $0$ とします。
また、実装を楽にするため $2$ つの辞書型の変数 win, point を定義します。
win[i]
win[i] は $i$ に勝てる手を返します。
win['G'] = 'P'win['C'] = 'G'win['P'] = 'C'
となります。
point[i]
point[i] は $i$ を出した時の点数を返します。
win['G'] = 0win['C'] = 2win['P'] = 5
となります。
続いて、遷移です。
まずは相手の出した手 $S_i$ に対して勝つ手を出した場合について考えます。
例えばパーを出して来たならチョキ、グーを出して来たならパー、といった具合です。
$S_i$ に勝てる手は win[S[i]] であり、これを出した時の点数は、 point[win[S[i]]] となるため、前に紹介した $2$ つの変数が活きてきます。
遷移は以下のようになります。
$\begin{aligned} {\mathrm dp}[i + 1][j] = \max\left( {\mathrm dp}[i + 1][j], {\mathrm dp}[i][j - point[win[s[i]]]] + 1 \right) \end{aligned}$
次に相手の出した手 $S_i$ に対して、引き分け、もしくは負けの場合について考えます。
この時、勝つ回数は更新されませんが、ポイントは増えるので、ポイントのみを考慮した遷移を行います。
$\begin{aligned} {\mathrm dp}[i + 1][j] = \max\left( {\mathrm dp}[i + 1][j], {\mathrm dp}[i][j - point[k]] \right) \end{aligned}$
ここで $k$ は引き分けの手のポイントを表します。
全体の計算量は $O(NM)$ となります。
解答例（Python）
N, M = map(int, input().split())
s = input()
# dp[i][j] := i 番目までで指の合計が j 本の時の勝つ回数の最大値
dp = [[-1]*(M + 1) for _ in range(N + 1)]
dp[0][0] = 0
win = {'G': 'P', 'C': 'G', 'P': 'C'}
point = {'G': 0, 'C': 2, 'P': 5}
for i in range(N):
for j in range(M + 1):
for k in "GCP": # 出す手を全探索
if k != win[s[i]]: # 負ける手を出した場合の処理
if j - point[k] >= 0:
# 遷移元の組み合わせがあり得ない場合はスキップ
if dp[i][j - point[k]] == -1:
continue
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - point[k]])
else: # 勝つ手を出した場合の処理
if j - point[win[s[i]]] >= 0:
# 遷移元の組み合わせがあり得ない場合はスキップ
if dp[i][j - point[win[s[i]]]] == -1:
continue
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - point[win[s[i]]]] + 1)
# 答えを出力する
print(dp[N][M])
解答例（C++）
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
string s;
cin >> s;
// dp[i][j] := i 番目までで指の合計が j 本の時の勝つ回数の最大値
vector<vector<int>> dp(N + 1, vector<int>(M + 1, -1));
dp[0][0] = 0;
// 勝つための手を表現するマップ
char win_map[256];
win_map['G'] = 'P';
win_map['C'] = 'G';
win_map['P'] = 'C';
// 各手の指の本数
int point_map[256];
point_map['G'] = 0;
point_map['C'] = 2;
point_map['P'] = 5;
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= M; ++j) {
for (char k : {'G', 'C', 'P'}) { // 出す手を全探索
if (k != win_map[s[i]]) { // 負ける手を出した場合の処理
if (j - point_map[k] >= 0) {
// 遷移元の組み合わせがあり得ない場合はスキップ
if (dp[i][j - point_map[k]] == -1) continue;
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - point_map[k]]);
}
} else { // 勝つ手を出した場合の処理
if (j - point_map[win_map[s[i]]] >= 0) {
// 遷移元の組み合わせがあり得ない場合はスキップ
if (dp[i][j - point_map[win_map[s[i]]]] == -1) continue;
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - point_map[win_map[s[i]]]] + 1);
}
}
}
}
}
// 答えを出力する
cout << dp[N][M] << endl;
return 0;
}
A3. ハノイの塔
問題概要
ハノイの塔をシミュレーションせよ。
$n$ 個のブロックをシミュレーションした際の $t$ 番目の状態を求めよ。
ハノイの塔に関しては知っているていで説明をしていきます、
初めて聞いたという方は調べてみてください。
解説
この問題は個人的には今回解説する全 $25$ 問のうち最後に解説する $S5$ の十億連勝の次に難しいと感じます。
他の問題は使用するアルゴリズムを知っていれば解ける、というものが多いですが、この問題は特別高度なアルゴリズムが必要というわけでもなく考察・実装力が試されるので $S$ ランクに位置付けられていても何も不思議には思いません。
そんなわけで解説していきます。
このようなゲームのシミュレーションは再帰で書くと綺麗にかける場合が多いです。
まずハノイの塔のアルゴリズムは $3$ つある棒のうち、これから移す棒 from、移動先の棒 to、それ以外の棒 other と定義します。
また、これらをプログラム上では $0, 1, 2$ とインデックスを振ることにします。
dfs の開始は $n$ 個のブロックを左から右に移すので再帰関数 $f$ は $f(n, 0, 2, 1)$ となります。
そして、次に再帰を呼び出す際には $n$ 個のうち、上の $n - 1$ 段は other に移したいので $f(n - 1, from, other, to)$ を呼び出します。
これらの処理が終わったあと、一番下の本来 $n$ 段目にあったブロックを移動させます。
これは目的地に移せば良いので $f(1, from, to, other)$ となります。
最後に other に移していた $n - 1$ 個のブロックを目的地に移すので $f(n - 1, other, to, from)$ を呼び出します。
後はブロックを移すとき、移すブロックが $1$ つであれば配列の要素を移します。
このようにしてこの問題を解くことが出来ました。
解答例（Python）
def f(n: int, from_: int, to: int, other: int):
global cnt
if n == 1:
# 目的地に出発地の末尾を追加する
towers[to].append(towers[from_][-1])
# 出発地の末尾を削除する
towers[from_].pop()
cnt += 1
# t 回試行が終わったら答えを出力する
if cnt == t:
for i in towers:
if len(i) == 0:
print('-')
else:
print(" ".join(map(str, i)))
exit()
else:
# n - 1 段の塔を other に移動させる
f(n - 1, from_, other, to)
# 一番下の土台を移動させる
f(1, from_, to, other)
# other に移動させた 1 つ低い塔を目的地に移動させる
f(n - 1, other, to, from_)
n, t = map(int, input().split())
cnt = 0 # 試行回数
# 各塔の初期配置
towers = [[n - i for i in range(n)], [], []]
# n 個のブロックを左（0） から右（2）に移動させる
f(n, 0, 2, 1)
解答例（C++）
#include <iostream>
#include <vector>
using namespace std;
int cnt = 0; // 試行回数
int t; // 目標の試行回数
vector<vector<int>> towers; // 各塔の状態
void f(int n, int from_, int to, int other) {
if (n == 1) {
// 目的地に出発地の末尾を追加する
towers[to].push_back(towers[from_].back());
// 出発地の末尾を削除する
towers[from_].pop_back();
cnt += 1;
// t 回試行が終わったら答えを出力する
if (cnt == t) {
for (const auto& tower : towers) {
if (tower.empty()) {
cout << '-' << endl;
} else {
for (size_t i = 0; i < tower.size(); ++i) {
if (i > 0) cout << " ";
cout << tower[i];
}
cout << endl;
}
}
exit(0);
}
} else {
// n - 1 段の塔を other に移動させる
f(n - 1, from_, other, to);
// 一番下の土台を移動させる
f(1, from_, to, other);
// other に移動させた 1 つ低い塔を目的地に移動させる
f(n - 1, other, to, from_);
}
}
int main() {
int n;
cin >> n >> t;
// 各塔の初期配置
towers = {{}, {}, {}};
for (int i = n; i > 0; --i) {
towers[0].push_back(i);
}
// n 個のブロックを左（0） から右（2）に移動させる
f(n, 0, 2, 1);
return 0;
}
A4. 山折り谷折り
問題概要
$1$ 枚の紙を左に左にひたすら折っていく。
$N$ 回折った後紙を戻した時、谷折りなら $0$、山折りなら $1$ を出力せよ。
解説
このような問題は紙さえあれば実験が手軽にできるのでまずはやってみるのが大切です。
以下に実験結果を載せます。
| 試行回数 | 文字列 |
|---|---|
| $1$ | $0$ |
| $2$ | $001$ |
| $3$ | $0010011$ |
| $4$ | $001001100011011$ |
| $5$ | $0010011000110110001001110011011$ |
| $6$ | $001001100011011000100111001101100010011000110111001001110011011$ |
| $7$ | $001001100011011000100111001101100010011000110111001001110011011000100110001101100010011100110111001001100011011100100111001101$ |
| $8$ | $001001100011011000100111001101100010011000110111001001110011011000100110001101100010011100110111001001100011011100100111001101100010011000110110001001110011011000100110001101110010011100110111001001100011011000100111001101110010011000110111001001110011011$ |
| $9$ | $0010011000110110001001110011011000100110001101110010011100110110001001100011011000100111001101110010011000110111001001110011011000100110001101100010011100110110001001100011011100100111001101110010011000110110001001110011011100100110001101110010011100110110001001100011011000100111001101100010011000110111001001110011011000100110001101100010011100110111001001100011011100100111001101110010011000110110001001110011011000100110001101110010011100110111001001100011011000100111001101110010011000110111001001110011011$ |
| $10$ | $001001100011011000100111001101100010011000110111001001110011011000100110001101100010011100110111001001100011011100100111001101100010011000110110001001110011011000100110001101110010011100110111001001100011011000100111001101110010011000110111001001110011011000100110001101100010011100110110001001100011011100100111001101100010011000110110001001110011011100100110001101110010011100110111001001100011011000100111001101100010011000110111001001110011011100100110001101100010011100110111001001100011011100100111001101100010011000110110001001110011011000100110001101110010011100110110001001100011011000100111001101110010011000110111001001110011011000100110001101100010011100110110001001100011011100100111001101110010011000110110001001110011011100100110001101110010011100110111001001100011011000100111001101100010011000110111001001110011011000100110001101100010011100110111001001100011011100100111001101110010011000110110001001110011011000100110001101110010011100110111001001100011011000100111001101110010011000110111001001110011011$ |
| $11$ | $0010011000110110001001110011011000100110001101110010011100110110001001100011011000100111001101110010011000110111001001110011011000100110001101100010011100110110001001100011011100100111001101110010011000110110001001110011011100100110001101110010011100110110001001100011011000100111001101100010011000110111001001110011011000100110001101100010011100110111001001100011011100100111001101110010011000110110001001110011011000100110001101110010011100110111001001100011011000100111001101110010011000110111001001110011011000100110001101100010011100110110001001100011011100100111001101100010011000110110001001110011011100100110001101110010011100110110001001100011011000100111001101100010011000110111001001110011011100100110001101100010011100110111001001100011011100100111001101110010011000110110001001110011011000100110001101110010011100110110001001100011011000100111001101110010011000110111001001110011011100100110001101100010011100110110001001100011011100100111001101110010011000110110001001110011011100100110001101110010011100110110001001100011011000100111001101100010011000110111001001110011011000100110001101100010011100110111001001100011011100100111001101100010011000110110001001110011011000100110001101110010011100110111001001100011011000100111001101110010011000110111001001110011011000100110001101100010011100110110001001100011011100100111001101100010011000110110001001110011011100100110001101110010011100110111001001100011011000100111001101100010011000110111001001110011011100100110001101100010011100110111001001100011011100100111001101110010011000110110001001110011011000100110001101110010011100110110001001100011011000100111001101110010011000110111001001110011011000100110001101100010011100110110001001100011011100100111001101110010011000110110001001110011011100100110001101110010011100110111001001100011011000100111001101100010011000110111001001110011011000100110001101100010011100110111001001100011011100100111001101110010011000110110001001110011011000100110001101110010011100110111001001100011011000100111001101110010011000110111001001110011011$ |
すみません、作ってて楽しくつい $N$ が大きくなった結果も書いてしまいました...
実はこの結果を見るよりも手元で実験をするとわかるのですが、前の文字列の間に $0101 \dots$ という文字列が順番に繋がっていることがわかります。
なので後はこれを順番に処理していくことで答えの文字列を構築することが出来ます。
計算量は $O(N2^N)$ となります。
解答例（Python）
N = int(input())
s = "0"
for i in range(1, N):
next_s = ""
for j in range(2**i):
# 0,1,0,1 を順に追加する
next_s += str(j % 2)
# 1 個前の文字列を順番に追加する
if j != 2**i - 1:
next_s += s[j]
s = next_s
print(s)
解答例（C++）
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main() {
int N;
cin >> N;
string s = "0";
for (int i = 1; i < N; ++i) {
string next_s = "";
for (int j = 0; j < (1 << i); ++j) { // 2^i を (1 << i) に変換
// 0,1,0,1 を順に追加する
next_s += to_string(j % 2);
// 1 個前の文字列を順番に追加する
if (j != (1 << i) - 1) {
next_s += s[j];
}
}
s = next_s;
}
cout << s << endl;
return 0;
}
紙って $20$ 回も折れなくないですか？
あと $20$ 回くらい折れれば月に届きそうですね＾＾
A5. 本の整理
問題概要
本がバラバラに並んでいる。
先頭から順に本を正しく並び替える場合、操作は何回かかるか？
解説
愚直にソートすることを考えると、これはバブルソートと呼ばれ $O(N^2)$ かかってしまい今回のような制約では間に合いません。
そこで工夫することを考えます。
ここでは本の位置 pos という list 型の変数を用意します。
これを用いて先頭から順に本が正しい位置にあるかどうかを確認していきます。
$i$ 番目のループで本 $i$ が既に正しい位置にある場合は操作を行わず、そうでない場合は本 $i$ と今先頭から $i$ 番目にある本を入れ替えます。
このようにしてこの問題を $O(N)$ で解くことが出来ます。
解答例（Python）
N = int(input())
a = list(map(int, input().split()))
# pos[i] := 本 i が先頭から何番目にあるか
pos = [0]*N
# 本の初期配置を求める
for i in range(N):
pos[a[i] - 1] = i
# 先頭から順に調べていく
ans = 0
for i in range(N):
# 既に本が正しい位置にあればスキップ
if pos[i] == i:
continue
# 正しくない本の番号・位置
num1 = a[i] - 1
pos1 = pos[num1]
# 正しい本の番号・位置
num2 = i
pos2 = pos[i]
# 本自体を入れ替える
a[pos1], a[pos2] = a[pos2], a[pos1]
# 本の位置を入れ替える
pos[num1], pos[i] = pos[i], pos[num1]
# 本を入れ替える
ans += 1
print(ans)
解答例（C++）
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> a(N);
vector<int> pos(N);
// 入力を受け取る
for (int i = 0; i < N; ++i) {
cin >> a[i];
}
// pos[i] := 本 i が先頭から何番目にあるか
for (int i = 0; i < N; ++i) {
pos[a[i] - 1] = i;
}
// 先頭から順に調べていく
int ans = 0;
for (int i = 0; i < N; ++i) {
// 既に本が正しい位置にあればスキップ
if (pos[i] == i) {
continue;
}
// 正しくない本の番号・位置
int num1 = a[i] - 1;
int pos1 = pos[num1];
// 正しい本の番号・位置
int num2 = i;
int pos2 = pos[i];
// 本自体を入れ替える
swap(a[pos1], a[pos2]);
// 本の位置を入れ替える
swap(pos[num1], pos[i]);
// 本を入れ替える
ans += 1;
}
cout << ans << endl;
return 0;
}
おまけ
こちらの発展問題として AtCoder に以下のような問題があります。
興味のある方はぜひ挑戦してみてください。
6. S ランク
ここからは $S$ ランクの問題解説となります。
$S$ ランクは以下のような対象者が個人的には勉強にオススメです。
- $A$ ランク以下の問題は $9$ 割以上解けてもっと高度な勉強がしたい！
正直 $S$ ランクは青天井です。
記事を今回書いている自分でも解けない $S$ ランクの問題は多数存在します。
スキルチェックで解けずに悲しむ時も多々ありますが、解けた時の喜びが大きいので日々努力しているつもりではあります。
なので競技プログラミングの更なる高みを目指したい！という方にオススメです（正直、このレベルの適正者は自分で分かってると思います）。
S1. 村人の友好関係
問題概要
$N$ 人の村人が $Q$ 個のクエリに対して「同好会」に加入したり脱退したりする。
各村人間には「友好度」が設定されており、同好会に加入している人としていない人の友好度の最大値を出力せよ。
解説
まずは友好度が大きい順に与えられた $M$ 個の関係をソートします。
これらをクエリの度にそれぞれの村人同士が同好会に属しているかどうかをチェックします。
これは前処理を行うことで $O(1)$ で求めることが出来ます。
$2$ 人ともに同好会に属している、もしくは $2$ 人ともに同好会に属していない場合は友好度の最大値の候補としては有り得ないのでスキップします。
そうでない場合はソートしているためそれが最大値となりクエリを終了します。
見かけは $O(QM)$ になりますが、適切に枝刈り（break）することで高速に動作します。
解答例（Python）
N, M, Q = map(int, input().split())
edge = []
for _ in range(M):
a, b, f = map(int, input().split())
a -= 1
b -= 1
edge.append((f, a, b))
# 友好度が大きい順にソートする
edge.sort(key=lambda x: x[0], reverse=True)
group = [False]*N # group[i] := 村人 i がグループに存在しているかどうか
for _ in range(Q):
op, q = input().split()
q = int(q) - 1
if op == "+":
group[q] = True
elif op == "-":
group[q] = False
for f, a, b in edge:
# 2 人ともグループに所属 or 2 人とも未所属の場合は調べない
if group[a] == group[b]:
continue
print(f)
break
else: # グループが 0 人または N 人の場合は人気度が 0
print(0)
解答例（C++）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N, M, Q;
cin >> N >> M >> Q;
vector<tuple<int, int, int>> edge(M); // (f, a, b) を保持するタプルのベクトル
for (int i = 0; i < M; ++i) {
int a, b, f;
cin >> a >> b >> f;
a -= 1;
b -= 1;
edge[i] = make_tuple(f, a, b);
}
// 友好度が大きい順にソートする
sort(edge.begin(), edge.end(), [](const tuple<int, int, int>& x, const tuple<int, int, int>& y) {
return get<0>(x) > get<0>(y);
});
vector<bool> group(N, false); // group[i] := 村人 i がグループに存在しているかどうか
for (int i = 0; i < Q; ++i) {
char op;
int q;
cin >> op >> q;
q -= 1;
if (op == '+') {
group[q] = true;
} else if (op == '-') {
group[q] = false;
}
bool found = false;
for (const auto& e : edge) {
int f, a, b;
tie(f, a, b) = e;
// 2 人ともグループに所属 or 2 人とも未所属の場合は調べない
if (group[a] == group[b]) {
continue;
}
cout << f << endl;
found = true;
break;
}
if (!found) {
// グループが 0 人または N 人の場合は人気度が 0
cout << 0 << endl;
}
}
return 0;
}
S2. 島探し
問題概要
$N \times M$ のグリッドが与えられる。
これらのうち、黒色で塗られたマスが島である。
島同士が上下左右のいずれかに隣接していれば同じ島として扱う場合、島は全てでいくつあるか？
解説
この問題は DFS（深さ優先探索） や BFS（幅優先探索） のアルゴリズムを用いることで求めることが出来ます。
ここでは DFS（Depth First Search） を使用して解説します。
まずはじめに seen という二次元配列を用意します。
初期値は全て False にしておき、探索済みになれば True とします。
各マスに全探索し、今見ているマスが 未探索かつ島である 場合はそのマスから dfs を行います。
dfs では現在見ているマスの上下左右の隣接した $4$ マスに対して島であるかどうかを判定します。
これは bfs や dfs の処理で頻繁に出てくる手法です。
今いるマスが $(i, j)$ である場合探索する候補は $(i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)$ の $4$ マスとなります。
したがって、これらの変化量を tuple の変数 d に格納することで簡潔に処理することが出来ます。
詳しくは解答例の中に注釈を細かく入れているのでそちらをご覧いただくか、コメントでその旨を教えていただければ対応します。
解答例（Python）
def dfs(now_y: int, now_x: int):
# 今いるマスを探索済みにする
seen[now_y][now_x] = True
# 上下左右の 4 方向に対する変化量
d = ((1, 0), (-1, 0), (0, 1), (0, -1))
for dy, dx in d:
next_y = now_y + dy
next_w = now_x + dx
# 配列外参照なら探索を行わない
if not (0 <= next_y < H and 0 <= next_w < W):
continue
# 島でなければ探索を行わない
if S[next_y][next_w] == 0:
continue
# 既に探索済みの島であれば探索を行わない
if seen[next_y][next_w]:
continue
seen[next_y][next_w] = True
dfs(next_y, next_w)
W, H = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(H)]
# seen[i][j] := マス (i, j) を既に探索したかどうか
seen = [[False]*W for _ in range(H)]
ans = 0 # 島の数
for i in range(H):
for j in range(W):
# 島でなければ探索を行わない
if S[i][j] == 0:
continue
# 既に探索済みの島であれば探索を行わない
if seen[i][j]:
continue
dfs(i, j)
ans += 1
print(ans)
解答例（C++）
#include <iostream>
#include <vector>
using namespace std;
// 幅と高さ
int W, H;
vector<vector<int>> S;
vector<vector<bool>> seen;
// 深さ優先探索(DFS)関数
void dfs(int now_y, int now_x) {
// 今いるマスを探索済みにする
seen[now_y][now_x] = true;
// 上下左右の4方向に対する変化量
int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int i = 0; i < 4; ++i) {
int dy = d[i][0], dx = d[i][1];
int next_y = now_y + dy;
int next_x = now_x + dx;
// 配列外参照なら探索を行わない
if (!(0 <= next_y && next_y < H && 0 <= next_x && next_x < W)) {
continue;
}
// 島でなければ探索を行わない
if (S[next_y][next_x] == 0) {
continue;
}
// 既に探索済みの島であれば探索を行わない
if (seen[next_y][next_x]) {
continue;
}
// 再帰的に探索を続ける
dfs(next_y, next_x);
}
}
int main() {
cin >> W >> H;
S.assign(H, vector<int>(W));
seen.assign(H, vector<bool>(W, false));
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
cin >> S[i][j];
}
}
int ans = 0; // 島の数
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
// 島でなければ探索を行わない
if (S[i][j] == 0) {
continue;
}
// 既に探索済みの島であれば探索を行わない
if (seen[i][j]) {
continue;
}
dfs(i, j);
ans += 1;
}
}
cout << ans << endl;
return 0;
}
S3. mod7占い
問題概要
$N$ 枚のカードから異なる $3$ 枚のカードを選び、これらの和が $7$ で割り切れる組み合わせの個数を求めよ。
解説
愚直に全探索をすると、$O(N^3)$ となり、間に合いません。
こういうのは $2$ つの場合だとソートして片方を二分探索して $O(N \log N)$、みたいな問題もよくありますが今回はそうでもないようです。
着眼点としては 和が $7$ になる という条件に着目します。
$a_i$ の $7$ で割った余りは $7$ 通りしかないため、mod を取って、余りの個数で全探索することを考えます。
まずは $0, 1, 2, \dots, 6$ までで $3$ つを選んで和が $7$ になる組み合わせを列挙します。
このような組み合わせは列挙すると以下のようになります。
0 0 0
0 1 6
0 2 5
0 3 4
1 1 5
1 2 4
1 3 3
2 2 3
2 6 6
3 5 6
4 4 6
4 5 5
例えば $0, 1, 6$ の組み合わせの場合 $a_i$ のうち、$7$ で割った余りが $0, 1, 6$ の個数をそれぞれ $i, j, k$ 個とすると、答えの組み合わせは $i \times j \times k$ 通りあります。
また、$1, 1, 5$ の組み合わせの場合 $a_i$ のうち、$7$ で割った余りが $1, 1, 5$ の個数をそれぞれ $i, j, k$ 個とすると、答えの組み合わせは $\dfrac{i \times (i - 1)}{2} \times k $ 通りあります。
これは重複を許す場合の組み合わせの個数となります。
これらに注意して慎重に場合分けを行いつつ、答えを求めることでこの問題を解くことが出来ます。
解答例（Python）
N = int(input())
a = [int(input()) for _ in range(N)]
cnt = [0]*7
# a[i] を 7 で割った余りに置き換えそれぞれの個数を数える
for i in range(N):
cnt[a[i] % 7] += 1
mod7 = []
# (i + j + k) が 7 の倍数となるような組み合わせを全列挙する （i ≤ j ≤ k）
for i in range(7):
for j in range(i, 7):
for k in range(j, 7):
if (i + j + k) % 7 == 0:
mod7.append((i, j, k))
ans = 0
for i, j, k in mod7:
if i == j == k: # cnt[i]_C_3
ans += cnt[i]*(cnt[i] - 1)*(cnt[i] - 2) // 6
elif i == j: # cnt[i]_C_2 * cnt[k]
ans += (cnt[i]*(cnt[i] - 1) // 2) * (cnt[k])
elif i == k: # cnt[j]_C_2 * cnt[j]
ans += (cnt[j]*(cnt[j] - 1) // 2) * (cnt[j])
elif j == k: # cnt[k]_C_2 * cnt[i]
ans += (cnt[k]*(cnt[k] - 1) // 2) * (cnt[i])
else: # cnt[i] * cnt[j] * cnt[k]
ans += cnt[i]*cnt[j]*cnt[k]
print(ans)
解答例（C++）
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> a(N);
for (int i = 0; i < N; ++i) {
cin >> a[i];
}
vector<int> cnt(7, 0);
// a[i] を 7 で割った余りに置き換えそれぞれの個数を数える
for (int i = 0; i < N; ++i) {
cnt[a[i] % 7] += 1;
}
vector<tuple<int, int, int>> mod7;
// (i + j + k) が 7 の倍数となるような組み合わせを全列挙する （i ≤ j ≤ k）
for (int i = 0; i < 7; ++i) {
for (int j = i; j < 7; ++j) {
for (int k = j; k < 7; ++k) {
if ((i + j + k) % 7 == 0) {
mod7.emplace_back(i, j, k);
}
}
}
}
long long ans = 0;
for (auto [i, j, k] : mod7) {
if (i == j && j == k) { // cnt[i]_C_3
ans += cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6;
} else if (i == j) { // cnt[i]_C_2 * cnt[k]
ans += (cnt[i] * (cnt[i] - 1) / 2) * cnt[k];
} else if (i == k) { // cnt[j]_C_2 * cnt[i]
ans += (cnt[i] * (cnt[i] - 1) / 2) * cnt[j];
} else if (j == k) { // cnt[k]_C_2 * cnt[i]
ans += (cnt[j] * (cnt[j] - 1) / 2) * cnt[i];
} else { // cnt[i] * cnt[j] * cnt[k]
ans += cnt[i] * cnt[j] * cnt[k];
}
}
cout << ans << endl;
return 0;
}
S4. 文字列収集
問題概要
$N$ 個の文字列それぞれに価値 $P_i$ が定められている。
$M$ 個のクエリが与えられる。各クエリでは文字列 $Q_i$ が与えられ $N$ 個の文字列のうち、$Q_i$ と接頭辞が同じものはスコア $P$ が加算される。
クエリで与えられる文字列のスコアを求めよ。
解説
どんな問題でもまずは愚直に実装するとどれくらいの計算量がかかるのか見積もります。
一つのクエリでは $N$ 個の文字列それぞれに接頭辞が一致しているか試す必要があるので $O(NM \max(|S_i|) \max(|d_i|))$ になります。
これは流石に間に合わないので改善する必要があります。
一つ目のポイントとして、$|S_i|, |Q_i|$ が $100$ 以下ということに着目します。
これらはかなり制約が小さくなっているので、$S_i$ を先頭から $1$ 文字ずつ追加していくことを考えます。
例えば、$S_i =$ algo の場合、$4$ 回ループを行い、連想配列（defaultdict）を用いて a, al, alg, algo という文字列にポイント $P$ 加算します。
これを $N$ 個全ての文字列に適応するのは $O(N \max(|S_i|))$ となります。
$S_i$ が $100$ 以下であるため、これは十分高速に動作します。
ここまでの処理をクエリの前に行っておくことで、後はクエリの文字列にアクセスするだけでこの問題を解くことが出来ました。
制約から発想を導く典型的な競プロのテクニックが必要となる問題で個人的にはとても好きな問題でした。
解答例（Python）
from collections import defaultdict
N, M = map(int, input().split())
# 辞書型の変数を用意する
d = defaultdict(int)
for _ in range(N):
S, P = input().split()
P = int(P)
s = ""
for i in range(min(100, len(S))):
s += S[i] # 1 文字ずつ増やす
d[s] += P # S の先頭から i 文字目までの部分文字列の価値を +P にする
for _ in range(M):
Q = input()
print(d[Q])
解答例（C++）
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
// 辞書型の変数を用意する
unordered_map<string, int> d;
for (int i = 0; i < N; ++i) {
string S;
int P;
cin >> S >> P;
string s = "";
for (int j = 0; j < min(100, (int)S.length()); ++j) {
s += S[j]; // 1 文字ずつ増やす
d[s] += P; // S の先頭から i 文字目までの部分文字列の価値を +P にする
}
}
for (int i = 0; i < M; ++i) {
string Q;
cin >> Q;
cout << d[Q] << endl;
}
return 0;
}
S5. 十億連勝
問題概要
$N$ 個のステージがる。
$i$ 番目のステージでは $A_i$ 試合行われる。
この全ての試合の中で ちょうど $X$ 連勝する組み合わせの個数を求めよ。
ただし、ステージの途中で負けた場合はそのステージでは、以降試合を行わない。
解説
さあ遂に最後の問題となりました。
これは個人的には圧倒的に全ての問題の中で難しく感じました。$SS$ ランクあって良い問題だと思います。
それでは解説をしていきます。
この問題の厄介な点として、普通の dp では $X, A_i$ が大きすぎるため dp テーブルを作ってそれを更新していく、ということが出来ない点にあります。
このような dp は難しい問題になると定期的に出てくるのですが、dp の key を連想配列のような形で持つことで解決できる場合があります。
この問題では dp のキーに $i$ 試合目までが終わった時点で何連勝していて、既に $X$ 連勝したかどうかの bool 値を管理しておきます。
初期値は $dp[(0, false)] = 1$ となります。
その後、for 文の中でこれまでのキーを全て見ていきます。
まずは場合分けが必要になります。
これまでの勝利数が win の時、win + A_i が $X$ 以下かどうかで場合分けをする必要があります。
まずは win + A_i ≤ X の時についてです。
これは全てに勝っても $X$ 連勝はできないので、全勝するか、どこかで負けるかで場合分けをします。
全勝する場合は単に更新すれば良いのでこれまでの勝利数を $v$ としたときに dp[(win + A[i]), bool] に $v$ を加えます。全勝しても bool 値に変更はない（$X$ 連勝していないため）ので第二引数はそのままとなります。
次にいずれかで負けた場合についてです。
いずれかで負ける場合は負けるタイミングが $A_i$ 通りあるので、dp[(0, bool)] に $v \times A_i$ 通りを加えます。
負けるので連勝数は $0$ になります。
続いて、win + A_i ≥ X の時についてです。
まずはちょうど $X$ 連勝した場合についてです。
この時は $X$ 連勝を達成したことになるので bool を $true$ に変更します。
組み合わせはそのまま $v$ 通りを加算すれば良いです。
次に $X$ 連勝できずに負ける場合です。
この時連勝数は $0$ に修正され、組み合わせは $v \times (X - win)$ 通りとなります。
X - win は現在の勝利数 win から $X$ に達するまでの通り数を表しています。
以上の遷移を行うことで個の問題を解くことが出来ました。
計算量は $O(N^2)$ となります。
知り合いの競プロer から $O(N)$ でも解けそうと言われました。
自分はまだ解法がわからないのでもし分かった方がいればぜひ教えてください！
解答例（Python）
from collections import defaultdict
N, X = map(int, input().split())
A = [int(input()) for _ in range(N)]
dp = defaultdict(tuple)
dp[(0, False)] = 1 # 連勝数, X 連勝したかどうか
for i in range(N):
new_dp = defaultdict(int)
for k, v in dp.items():
win, bool_ = k # 連勝数, X 連勝したかどうか
if win + A[i] <= X:
# A[i] 試合全てに勝つ場合
new_dp[(win + A[i], bool_)] += v
# A[i] 試合のいずれかで負ける場合
new_dp[(0, bool_)] += v*A[i]
elif win + A[i] > X:
# X 連勝ちょうどで負ける場合
new_dp[(0, True)] += v
# X 連勝未満で負ける場合
new_dp[(0, bool_)] += v*(X - win)
dp = new_dp
ans = 0
mod = 10**9
for k, v in dp.items():
win, bool_ = k # 連勝数, X 連勝したかどうか
if bool_ or win == X:
ans += v
ans %= mod
print(ans)
解答例（C++）
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
int main() {
int N, K, M;
cin >> N >> K >> M;
vector<string> d(K);
vector<string> s(M);
for (int i = 0; i < K; ++i) {
cin >> d[i];
}
for (int i = 0; i < M; ++i) {
cin >> s[i];
}
// word[d[i]] := d[i] を既に使用したかどうか
unordered_map<string, bool> word;
for (int i = 0; i < K; ++i) {
word[d[i]] = false;
}
// survival[i] := 友達 i が脱落したかどうか
vector<bool> survival(N, false);
int now = 0; // 現在のターンが誰なのか
char last = '\0'; // 前のターンの末尾の文字
bool last_friend = false; // 前のターンの友達が脱落したかどうか
for (int i = 0; i < M; ++i) {
// 誰のターンなのかを調べる
for (int j = 0; j < N; ++j) {
// 脱落している場合はスキップする
if (survival[(now + j) % N]) {
continue;
}
// 脱落していない友達を見つけたら for 文を抜ける
now = (now + j) % N;
break;
}
bool check = false; // このターンの友達が脱落するかどうか
// ルール 1. K 個の単語のいずれかでなければならない
// ルール 3. 既に発言していた場合は発言禁止
if (word.find(s[i]) == word.end() || word[s[i]]) {
check = true;
}
// ルール 4. z で終わってはいけない
if (s[i].back() == 'z') {
check = true;
}
// ルール 2. 直前の人の発言の末尾と一致する必要がある
// 初回のターンは前のプレイヤーがいない
if (i != 0) {
// 前のターンに友達が脱落していればルール 2. は適用されない
if (last != s[i].front() && !last_friend) {
check = true;
}
}
// 末尾の文字
last = s[i].back();
// s[i] を使用済みにする
word[s[i]] = true;
// このターンに友達が脱落したかどうか（2 ターン目以降のルール 2. で必要）
if (check) {
survival[now] = true;
last_friend = true;
} else {
last_friend = false;
}
// ターンを進める
now += 1;
}
// 答えを出力する
int survivors = 0;
for (int i = 0; i < N; ++i) {
if (!survival[i]) {
survivors++;
}
}
cout << survivors << endl;
for (int i = 0; i < N; ++i) {
// 脱落している友達は出力しない
if (!survival[i]) {
cout << i + 1 << endl;
}
}
return 0;
}
7. 最後に
ここまで読んでくださった方々、本当にありがとうございました！！
当初の予定では $10$ 時間程度で仕上げるつもりでしたが、全ての問題を解く / C++ で解き直す / 問題概要を書く / 解説を書く、としていたら想像の $3$ 倍ほど時間がかかってしまいました。
この記事は競技プログラミングをやっているどの層にも何かしら得られるものがあれば嬉しいなという思いで書き上げました。ただ、分量がとても多い分、間違っていることもあると思いますのでぜひご指摘いただければありがたく思います。
また、今回のコードは Github にも公開しているので、興味のある方はぜひご覧ください。
それではまた次の記事でお会いしましょう。