【AtCoder】黒〜緑のためのABC解説 | ABC306 A~D

コンテスト概要

ジャッジ遅れでUnratedになってしまいました...

問題	配点	Diff
A. Echo	100	?
B. Base 2	200	?
C. Centers	250	159
D. Poisonous Full-Course	400	596
E. Best Performances	475	1268
F. Merge Sets	525	1557
G. Return to 1	600	2563
Ex. Balance Scale	650	3335

問題解説

A. Echo

概要

長さ$N$の英小文字からなる文字列$S$が与えられます。
$S_1$, $S_1$, $S_2$, $S_2$, ... , $S_N$, $S_N$と並べた文字列を出力してください。

制約

• $1 \leq N \leq 50$
• $S$は長さ$N$の文字列

必要技術

• forループ
• stringのi文字目取得

方針

とりあえず、何も考えずS, Nを受け取りましょう。
その後、「『Sのi文字目を出力』を2回繰り返す」をN回繰り返せば良いです。
(一文字ずつ前から見ていって、それぞれを2回ずつ出力すればOKです)

コード

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  string S;
  cin >> N >> S;
  for(int i=0; i<N; i++) {
    cout << S[i] << S[i];
  }
  cout << endl;
}

endlは改行なので、最後に1回だけ(=ループ外で)するようにしています
(endlがなくてもACになりますが、基本「解答の最後には改行をつける」ことになっています)

もちろんcout << ...の行をfor(int j=0; j<2; j++) cout << S[i];としても良いですが...2会ループくらいならわざわざforを使わなくていいよね?

C++においてS[i]はchar型(文字型)ですが、これの正体はただの数字に過ぎないので、S[i]*2みたいな操作はできないです
また、S[i]+S[i]とかもバグると思います。真面目に一つずつ出力しましょう!

B. Base 2

概要

0/1からなる長さ64の数列A($A_0$~$A_{63}$)が与えられます。
$A_0 \times 2^0 + A_1 \times 2^1 + ... + A_{63} \times 2^{63}$を求めてください。

制約

• $A_i$は0か1

必要技術

• 巨大な数の扱い(unsigned long long)
• ビットシフト演算
• (2進数の感覚)
• (boost::multiprecision::cpp_int)

方針

入力が64個あるので、for文で入力を受け取りましょう。

普通に考えれば、ansという変数を作っておき、$x^y$を求めることができるpow(x, y)を使って$2^i$を求め、それをansに足していけばいいのですが...

今回は、答えが最大$2^0+2^1+...+2^{63}$、すなわち$2^{64}-1$となります。
これはかなり大きい数であり、そのせいでかなり難しい問題となっています。

intなどの型には「入れることのできる最大値/最小値」があります。これは以下のとおりです。

• intは±20億(-2,147,483,648～2,147,483,647、すなわち $-2^{31} \sim (2^{31}-1)$)
• long longは$-2^{63} \sim (2^{63}-1)$
• doubleは有効数字が(10進数で)約15桁

なので、これらの型を使うことはできません。
また、先ほど紹介したpow()という関数はdoubleを返すので、これも使えません。

C++で大きい数を扱うときは基本的にlong longを使っておけば十分なのですが、今回はlong longですら微妙に足りません。
そこで、long longを正の数のみを扱えるようにしたunsigned long longを使います。
これは$0 \sim (2^{64}-1)$を表すことができます。いけそうですね!

ただ、pow()が使えないという問題は解決していません。
ここでは、2のN乗という形しか出てこないことを使います。

2進数において、「2倍」は「桁を左に1個ずらす」、「$2^N$倍」は「桁を左にN個ずらす」と言い換えることができます。(10進法で1桁ずらせば10倍ですよね!)

コンピューターは2進数の世界で動いているので、「桁をずらす」という操作(ビットシフト)が準備されています。
N << 2で「Nを2進数で2桁左にずらす」という意味です。

B問題にしては要求知識がかなり多いような気がしますが...

コード

#include <bits/stdc++.h>
using namespace std;
int main() {
  unsigned long long ans = 0;
  for(int i=0; i<64; i++) {
    unsigned long long A;
    cin >> A;
    A = A << i;
    ans += A;
  }
  cout << ans << endl;
}

なお、Pythonでは数字に桁数制限がなく、また整数の冪乗操作で誤差が出ないようなので、ans += A * (2 ** i)のようなコードでACが取れてしまうようです。Pythonすごい...

余談: Boostライブラリを使った方法

AtCoderのC++では、Boostライブラリというライブラリが使用可能になっています。 このライブラリの`cpp_int`という型は「多倍長整数」と呼ばれ、Pythonのように無限の桁数を扱うことができます。 (ただ、演算は多少遅いそうです) includeの周りが多少複雑になりますが、知っておくとどこかで使えるかもしれません。

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::multiprecision::cpp_int;
int main() {
  cpp_int ans = 0;
  for(int i=0; i<64; i++) {
    cpp_int A;
    cin >> A;
    ans += A * pow(2, i);
  }
  cout << ans << endl;
}

C. Centers

概要

長さ3Nの配列Aが与えられます。
i=1,2,...,Nについて、「Aの中で2番目に出てくるi」はAのどこにありますか?

制約

$1 \leq N \leq 10^5$
$1 \leq A_j \leq N$

必要技術

• 配列
• 計算量

方針

まずは入力を受け取ります。
その後、問題文の通りに「Aの中で2番目に出てくるi」を1~Nに対してそれぞれ求めることを考えてみます。
Aの中で2番目に出てくるiはどのようにして探せば良いでしょう?
今回、Aは順番にソートされているわけでもないので、一つずつ見ていく以外にありません。

こうすると、あるiに対して「Aの中で2番目に出てくるi」を求めるのに、最悪3N回程度の探索が必要です。
これを「『Aの中で2番目に出てくるi』の検索の計算量は$O(3N)$である」と表現します。
全体としては、これを1~NのN回繰り返さなければならないので、計算量は$O(3N^2)$となります。

今回、Nは最大$10^5$であるので、$3N^2$は最大$10^{10}$程度まで膨らんでしまいます。
コンピューターは1秒間に$10^7$回程度の計算しかできないので、これを実行するのは厳しいです。(TLEとなります)

高速化しましょう。
先ほどの方法では、「前から後ろまで見る」という操作を何回も行っているのが問題です。
そこで、countという配列を作成し、count[i]に「iがこれまで出てきた回数」を入れるようにすれば、1回の探索で1~Nまでのすべての値に対して、2番目に出てくるときに気づくことができます。
(count[i]を増やそうとした時、count[i] == 1ならば今処理中のものが2個目ということです)
その結果を配列ansに入れることにします。

これにより、計算量を$O(3N)$まで減らすことができました。
何を出力するかに気をつけながら書いてみましょう。

コード

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  vector<int> A(3*N);
  for(int i=0; i<3*N; i++) {
    cin >> A[i];
    A[i]--;
  }
  vector<int> count(N);
  vector<int> ans;
  for(int i=0; i<3*N; i++) {
    if(count[A[i]] == 1) {
      ans.push_back(A[i]+1);
    }
    count[A[i]]++;
  }
  for(int i=0; i<N; i++) {
    cout << ans[i] << " ";
  }
  cout << endl;
}

このコードでは、cin、count、coutと3つのfor文を分けています。
もちろん、cinとcountをくっつけて一つのforにしても構いません。

cinなどのあたりで+1や-1をしています。
これは、入力が1始まりであるのに対し、配列は0始まりだからです。
この操作をしなければ、count[A[i]]あたりで配列外参照を起こしてREとなるでしょう。
「今1始まりの値を扱っているのか、0始まりの数字を扱っているのか」は常に意識しておくようにしてください。
(面倒臭ければ、配列の長さをNでなくN+10くらいにすればOKです)

coutの部分については、空白区切りでの出力が求められているため、「値 << 空白」をセットにして出力しています。
このままでは最後に無駄な空白がついてしまいますが、AtCoderのジャッジは賢いので無視してくれます。
(気になる人はif書いて場合分けしましょう)

D. Poisonous Full-Course

概要

毒/解毒剤のどちらかが含まれている料理がN個出てきます。
高橋くんは毒を食べるとお腹を壊してしまい、その状態で毒を食べると死にます。
解毒剤を食べると、健康な状態に戻ります。
高橋くんは、それぞれの料理に対して「食べる」「食べない」を選ぶことができます。
N個の料理について、「毒/解毒剤のどちらが含まれているか($X_i$)」および「料理のおいしさ($Y_i$)」が与えられるので、「高橋くんが生きて帰れる」という条件のもと、「食べられる料理のおいしさの和の最大値」を求めてください。

制約

$1 \leq N \leq 3 \times 10^5 $
$X_i = 0$ または $1$
$-10^9 \leq Y_i \leq 10^9$

必要技術

• DP
• pair

方針

はじめに、「おいしさが負なら食べない」「今から食べようとしているものが解毒剤である、または『毒だが今はお腹を壊していない』場合は食べる」というふうに考えてみます。
しかし、これでは例えば、「おいしさ1、毒」「おいしさ-100、解毒剤」「おいしさ100000、毒」のように、一瞬おいしさ-100を食べて損になるけれど、後でおいしさ100000を食べられるので結果的に特になるような場合にうまく判定できなさそうです。

このように、「1列に並んでいるものを選んでいく」「単純な戦法(貪欲)ではうまくいかない」場合には、「動的計画法(DP)」を使うことが多い気がします。
(D問題あたりでDPが出ることが多いので、「DはDPのD」などと言われたりもします)

このような表を考えてみます。

状態	毒・100	毒・300	解毒・-200	毒・500	毒・300
健康	-	-	-	-	-
瀕死	-	-	-	-	-

この表を、「その食べ物を処理した(食べた/食べなかった)とき、今までの美味しさの総和として考えられる最大値」ということにして、埋めていこうと思います。

まず1つ目の食べ物です。食べた/食べていない、の2つを考えると、こうなります。

状態	毒・100	毒・300	解毒・-200	毒・500	毒・300
健康	0	-	-	-	-
瀕死	100	-	-	-	-

次に2つ目を考えます。毒が含まれているので、お腹を壊した状態では食べることはできません。
そこで、「健康→食べた」「健康→食べなかった」「瀕死→食べなかった」の3通りを考えます。

状態	毒・100	毒・300	解毒・-200	毒・500	毒・300
健康	0	0	-	-	-
瀕死	100	100 or 300	-	-	-

この表は「最大値」を表しているので、値は一つに定まります。

状態	毒・100	毒・300	解毒・-200	毒・500	毒・300
健康	0	0	-	-	-
瀕死	100	300	-	-	-

これをひたすら繰り返すと、表が完成します。

状態	毒・100	毒・300	解毒・-200	毒・500	毒・300
健康	0	0	100	100	100
瀕死	100	300	300	600	600

よって、答えは右端の二つの数字のうち大きいほう、すなわち600となります。

このように、「表を使って」「漸化式的に」「結果をメモりつつ」考える方法が動的計画法(DP)です。

DPの各マスに対して一度ずつ更新を行うので、計算量は$O(2N)$です。OKそうですね。

一つ気にしなければならないことは、DPに入る値のサイズです。もし全てのおいしさが最大値の$10^9$であり、全て無毒だった場合、最終的にDPに入る値は$3 \times 10^{14}$になります。
このため、9桁程度しか入らないintではなく、18桁程度入るlong longを使います。

コード

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
  int N;
  cin >> N;
  vector<pair<int, ll>> XY(N);
  for(int i=0; i<N; i++) {
    cin >> XY[i].first >> XY[i].second;
  }
  vector<vector<ll>> dp(N, vector<ll>(2, 0));
  dp[0][XY[0].first] = max(0LL, XY[0].second);
  for(int i=1; i<N; i++) {
    // まずはひとつ前を引き継ぎ (食べない)
    dp[i] = dp[i-1];
    // 以下、食べた場合を考える
    if(XY[i].first == 0) {
      dp[i][0] = max(dp[i][0], dp[i-1][0] + XY[i].second); // 健康→健康 (食べた)
      dp[i][0] = max(dp[i][0], dp[i-1][1] + XY[i].second); // 瀕死→健康 (食べた)
    } else {
      dp[i][1] = max(dp[i][1], dp[i-1][0] + XY[i].second); // 健康→瀕死 (食べた)
      // 瀕死→瀕死、はない
    }
  }
  cout << max(dp[N-1][0], dp[N-1][1]) << endl;
}

毎回long longと書くのが大変なので、llと書けばlong longを意味するようにしています。
(#defineの行です)

X、Yの保存に、2つの数字を束ねて一つとして扱えるpair<>を使っています。まあまあ便利です。
.first、.secondで値を出し入れできます。

DP部分は、表なので2次元配列で表現しています。
dp[i][0]が「i個目まで食べて健康な時のおいしさの最大値」、dp[i][1]が「i個目まで食べて瀕死な時のおいしさの最大値」を表すことにしました。
(一つ目の[]が表の横、二つ目の[]が表の縦の座標を表しているイメージです)
また、表は全て初期値0にしています。

DPの値を入れる時、dp[0][?]だけは手動で入れて、dp[1][?]以降はforで漸化式的に入れているのがポイントです。
(DPの横の長さをN+1みたいにすれば全部漸化式でできるかも?)

もしバグったら、dpの中身をcoutに出力させて、手元のメモと見比べてみましょう。

E. Best Performances

疲れたのでここで終了です(すみません...)

まとめ

C++の人はBに詰まった人も多いのではないでしょうか? (僕もその一人なんですが)
アルゴリズムというよりプログラミングの知識が問われましたね。

Dで使ったDPは、D~Eあたりでかなり出題されてる気がします。ぜひやってみてください。(ナップサックDPとかが有名ですね)