はじめに
- 本記事の内容は筆者自身の解釈による解法であり，必ずしも最も効率の良い解法であるとは限らない点をご容赦ください
- コンテストページ
目次
A. Edge Checker
B. Count Distinct Integers
C. Jumping Takahashi
D. Strange Balls
A. Edge Checker
| 正解者数/提出者数 | 7120/7188 |
|---|
問題文
下の画像で示す図において， $a$ 番の点と $b$ 番の点が線で直接結ばれているかを答えてください．
入力
$a \quad b$
- $1 \leq a \lt b \leq 10$
- $a,b$ は整数
解法
$a \lt b$ より，基本的には $a$ 番の点の次の点が $b$ 番の点であるかどうか，すなわち $a + 1 = b$ かどうかを判定すれば良いです．
ただし， 上の条件を満たさない $(a,b)$ の組の中で $(a,b) = (1,10)$ の場合のみ例外的に答えが "Yes" となります．
以上より，答えは
- $a + 1 = b$ または $(a,b) = (1,10)$ のとき "Yes"
- それ以外の場合 "No"
となります．
コード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
int a,b; cin >> a >> b;
if((a==1&&b==10) || (a+1==b)) cout << "Yes" << endl;
else cout << "No" << endl;
}
B. Count Distinct Integers
| 正解者数/提出者数 | 6920/7038 |
|---|
問題文
長さ $N$ の正整数列 $a=\left(a_{1}, a_{2}, \ldots, a_{N}\right)$ には何種類の整数が現れますか？
入力
$N$
$a_1 \quad \dots \quad a_N$
- $1 \leq N \leq 1000$
- $1 \leq a_{i} \leq 10^{9}(1 \leq i \leq N)$
- 入力は全て整数
解法
順序付き集合の set を利用します．
set は重複を許さない順序付き集合であり，既に集合内に存在する値を新たに追加しようとしても自動で削除されます．
そのため， set に正整数列 $a=\left(a_{1}, a_{2}, \ldots, a_{N}\right)$ の要素を順番に追加していくと，最終的には重複した値の存在しない集合となります．
よって，最終的に得られる集合の要素数が正整数列 $a$ に含まれる整数の種類の数となります．
コード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
ll n; cin >> n;
set<int> s;
rep(i,n){
int a; cin >> a;
s.insert(a);
}
cout << s.size() << endl;
}
C. Jumping Takahashi
| 正解者数/提出者数 | 4022/5492 |
|---|
問題文
高橋君は数直線上の座標 $0$ の位置にいます．
これから高橋君は $N$ 回のジャンプを行います． $i (1 \leq i \leq N)$ 回目のジャンプでは，正の方向に $a_i$ または $b_i$ 移動します．
$N$ 回のジャンプの後に座標 $X$ の位置にいるようにすることはできますか？
入力
$N \quad X$
$a_1 \quad b_1$
$⋮$
$a_N \quad b_N$
- $1 \leq N \leq 100$
- $1 \leq a_{i}<b_{i} \leq 100(1 \leq i \leq N)$
- $1 \leq X \leq 10000$
- 入力は全て整数
解法
問題文をそのままの意味で受け取ると， $N$ 個ある $a,b$ の組についてそれぞれいずれかを選択した場合の累積和が $X$ と等しい値になる場合があるかどうかを求めることになります．
ある1つの組 $a_i,b_i$ について考えると， $b_i$ を選んだ場合は， $a_i$ を選んだ場合よりも最終的な累積和が $b_i-a_i$ だけ多くなります．
よって，全ての組について $a$ を選択した場合の累積和を $sum_a$とすると，この問題は「 $N$ 個の値の集合 $(b_1-a_1, b_2-a_2, \dots, b_N-a_N)$から部分集合を選んでそれらの和を $X - sum_a$ にすることが可能かどうかを判定する部分和問題」と捉えることができます．
次に解法について考えると，まず思いつく方法として $N$ 個ある $a_i,b_i$ の組についてどちらを選ぶのかの $2$ 択をbit全探索を用いて全探索する方法が考えられます．しかし，この問題では $N$ は最大で $100$ をとる可能性があり，時間計算量が $O\left(N 2^{N}\right)$ であるbit全探索は計算量の面で利用できないことがわかります．
部分和問題を解くためのもう1つの方法として動的計画法を用いる方法があります．
部分和問題において一致するかどうか調べる対象を $K$ とすると，こちらの方法では時間計算量は $O(N K)$ で表されるため， $N$ の値が大きい場合でも利用することが可能です．
動的計画法を用いたアルゴリズムの詳細については下記の記事を参照していただくとわかりやすいかと思われます．
コード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
int n,x; cin >> n >> x;
vector<int> a(n),b(n);
rep(i,n) cin >> a[i] >> b[i];
int sum_a = 0;
// aの累積和と，b-aの値を記録
rep(i,n){
sum_a += a[i];
b[i] -= a[i];
}
if(sum_a > x){ // aの累積わがxを超えている場合は"No"
cout << "No" << endl;
return 0;
}
int K = x - sum_a;
// n個のb-aの部分集合の和をx-sum_aにできるかどうかdp
vector<vector<bool>> dp(n + 1, vector<bool>(K + 1, false));
// 初期化
dp[0][0] = true;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= K; ++j) {
dp[i+1][j] = dp[i+1][j] | dp[i][j];
if (j >= b[i]) dp[i+1][j] = dp[i+1][j] | dp[i][j-b[i]];
}
}
if (dp[n][K]) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
D. Strange Balls
| 正解者数/提出者数 | 3650/4530 |
|---|
問題文
高橋君は $2$ 以上の整数が書かれた $N$ 個のボールを持っており，これらを細長い筒の中に落としていきます． $i(1 \leq i \leq N)$ 回目には， $a_i$ が書かれたボールを落とします．
ボールは特殊な材質でできており，筒の中において $k(k \geq 2)$ が書かれたボールが $k$ 個連続すると，それら $k$ 個のボールは全て消えてしまいます．
各 $i(1 \leq i \leq N)$ について， $i$ 個目のボールを筒の中に落とした後，筒の中に何個のボールがあるか求めてください．
入力
$N$
$a_1 \quad \dots \quad a_N$
- $1 \leq N \leq 2 \times 10^{5}$
- $2 \leq a_{i} \leq 2 \times 10^{5}(1 \leq i \leq N)$
- 入力は全て整数
解法
stackを利用すると実装しやすいです．
今回はpairの要素を持つstackを使用します． $1$ つ目の値はstackのコンテナに格納されるボールに書かれた数字， $2$ つ目の値はその数字が現時点までに連続して同じ数字を持ったボールのいくつ目なのかを表すようにします．
具体的には，
$2,3,2,3,3$
のような数字の書かれたボールが筒に入っている場合，
$(2,1),(3,1),(2,1),(3,1),(3,2)$
という要素がstackに格納されていることになります．
そして，この筒に $3$ が書かれたボールを入れると
$(2,1),(3,1),(2,1),(3,1),(3,2)$ ← $(3,3)$
↓
$(2,1),(3,1),(2,1),(3,1),(3,2),(3,3)$
↓
$(2,1),(3,1),(2,1)$
というように $3$ つ連続した $3$ の書かれたボールが消えます．このように，stackに追加されるpairの $1$ つ目の値と $2$ つ目の値が等しい場合にその値と等しい個数のボールが消えることがわかります．
以上より，順番にpairをstackに追加していき，pairの $1$ つ目の値と $2$ つ目の値が一致したときにその値と等しい個数のボールをstackから取り除く操作を繰り返すことで答えを得ることが可能です．
コード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
ll n; cin >> n;
stack<pair<ll,ll>> A;
ll f1=1,f2=0,k=1,num=0; // f1:一つ前のボールの数字, f2:現在のボールの数字, k:現在のpairの2つ目の値
rep(i,n){
cin >> f2;
num++;
if(f1==f2){
k++;
}else{
k = 1;
}
A.push(make_pair(f2,k));
if(k==f2){
num -= k;
rep(j,k) A.pop();
if(A.empty()){
f1 = 1;
k = 1;
}else{
k=A.top().second;
f1 = A.top().first;
}
}else{
f1 = f2;
}
cout << num << endl;
}
}