【AtCoder】黒〜緑のためのABC解説 | ABC307 A~E

コンテスト概要

Cがとても難しく、難易度はA<B<D<E<C<F<G<Exとなりました。

問題	配点	Diff
A. Weekly Records	100	10
B. racecar	200	70
C. Ideal Sheet	300	1307
D. Mismatched Parentheses	400	666
E. Distinct Adjacent	475	1240
F. Virus 2	550	2139
G. Approximate Equalization	550	2330
Ex. Marquee	650	2754

難易度降下はこんな感じです。(横軸=AC時間、縦軸=相当レート)

Cが暴れ回っているのが見えますね。

問題解説

A. Weekly Records

概要

高橋くんは$7N$日間歩きました。
各週の歩数を求めてください。

制約

$1 \leq N \leq 10$
$0 \leq A_i \leq 10^5$

必要技術

• for

方針

入力される個数が不定なので、for文で受け取ります。
その後、「7個づつ足す」をN回行えば良いです。

コード

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  for(int week=0; week<N; week++) {
    int week_sum = 0;
    for(int day=0; day<7; day++) {
      int today;
      cin >> today;
      week_sum += today;
    }
    cout << week_sum << endl;
  }
}

B. racecar

概要

文字列がN個与えられます。
どれか2つを繋げることで回文を作ることはできますか?

制約

$2 \leq N \leq 100$
$1 \leq S_i$の長さ$\leq 50$

必要技術

• for
• vector
• 文字列操作

方針

Sが最大100個しかないので、Sを好きに2つ選んで($100 \times 99$通り)、繋いでみて回文になっているかを確かめることにしましょう。

回文判定は色々やり方がありますが、例えば、長さがAの文字列に対して「i文字目と(A-i+1)文字目が同じか?」を$1 \leq i \leq A$について確かめてみて、全てOKなら回文と言えそうです。

もちろん、文字列を逆順にして等しいかどうか調べるという方法でもOKです。

コード

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  vector<string> S(N);
  for(int i=0; i<N; i++) cin >> S[i];
  for(int first=0; first<N; first++) {
    for(int second=0; second<N; second++) {
      if(first == second) continue;
      string merged = S[first] + S[second];
      bool ok = true;
      for(int i=0; i<merged.size(); i++) {
        if(merged[i] != merged[merged.size()-1-i]) ok = false;
      }
      if(ok) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
}

S[first]、S[second]をこの順に繋げる、と考えます。
ただし、first == secondとなる場合に気をつけましょう。

文字列の結合は+で可能です。

その後、条件を満たしているかどうかをokという変数で管理しておき、もし回文であればYesと出力しつつプログラムを終了します。

回文判定を「逆順にして等しいか」で行う方法

reverse(S.begin(), S.end())で、Sが「Sを逆順にしたもの」で置き換えることができます。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  vector<string> S(N);
  for(int i=0; i<N; i++) cin >> S[i];
  for(int first=0; first<N; first++) {
    for(int second=0; second<N; second++) {
      if(first == second) continue;
      string merged = S[first] + S[second];
      string reversed = merged;
      reverse(reversed.begin(), reversed.end());
      if(merged == reversed) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
}

C. Ideal Sheet

概要

黒と透明からなるシートA, B, Xが与えられます。
透明で広いシートC上にA,Bを配置することで、Xと同じ模様にすることはできますか?
(ただし、Xの模様以外を描いてはいけません)

制約

$1 \leq $(A,B,Xの一辺の長さ)$\leq 10$

必要技術

• for
• 2次元配列
• 長くて複雑なコードを早く正確に書く能力

方針

この問題は、実はそこまで難しいテクニックが必要なわけではないのですが、非常に長いコードを正確に書き上げる必要があります。
そのため、D、E問題よりも難しかったようです。

まず入力受け取りです。
シートの様子は、vector<string>として受け取っておくと、A[i][j]と書くことで「上から(i+1)行目、左から(j+1)番目」を取得することができます。
vectorで1重配列なのになぜ[]が2つ?と思われるかもしれませんが、A[i]はstringであり、その後stringに対して[j]を行っている感じです。
stringがvector<char>のようなものであると考えるとわかりやすいかもしれません。

その後、A、Bを用いてXを再現します。
Cは無限に広いようなので、先に「X予定地」があるとしておきましょう。
地面にうっすらとXが描かれている感じです。

これにぴったりと当てはまるようなA,Bのおき方があるか、という話となります。

今回、制限も緩いので、「Aのx/y座標」「Bのx/y座標」を全て全探索しましょう。
ただし、A,Bの周りのあたりが透明な時は注意しなければいけません。少しはみ出す事も許されるからです。
(例えば、入力例1では、Aの左端はXから飛び出ています)

とりあえず、「A/Bの位置」は「A/Bの左上の座標」、Xの左上を(x,y)=(0,0)、下向きをx軸、右向きをy軸に取ることにします。
(vector<string>で[x][y]と取得できるようにこの向きにしています)

この時、Aのx座標は「Aの下端がギリギリXと重なる時」に最小値を取り、「Aの上端がギリギリXと重なる時」に最大値を取ります。
つまり、$1-H_A \leq x_A \leq H_X$というわけです。
$y_A, x_B, y_B$についても同じように表すことができるので、これを全探索します。

もし「Xの予定地内でXを完璧に再現できている」場合、次は「Xの予定地外で無駄な黒を配置していないか」をチェックしなければいけません。
この時、もちろん$1-H_A \leq x \leq H_X + H_A - 1$かつ$1-W_A \leq y \leq W_X + W_A - 1$の部分、および$1-H_B \leq x \leq H_X + H_B - 1$かつ$1-W_B \leq y \leq W_X + W_B - 1$の部分を全探索して見つけても良いのですが、今回は「Aの内部、かつX予定地の外部」、「Bの内部、かつX予定地の外部」を全探索することにしてみます。

コード

#include <bits/stdc++.h>
using namespace std;
int main() {
  // A入力
  int H_A, W_A;
  cin >> H_A >> W_A;
  vector<string> A(H_A);
  for(int i=0; i<H_A; i++) cin >> A[i];
  // B入力
  int H_B, W_B;
  cin >> H_B >> W_B;
  vector<string> B(H_B);
  for(int i=0; i<H_B; i++) cin >> B[i];
  // X入力
  int H_X, W_X;
  cin >> H_X >> W_X;
  vector<string> X(H_X);
  for(int i=0; i<H_X; i++) cin >> X[i];

  for(int X_A = 1-H_A; X_A <= H_X; X_A++) {
    for(int Y_A = 1-W_A; Y_A <= W_X; Y_A++) {
      for(int X_B = 1-H_B; X_B <= H_X; X_B++) {
        for(int Y_B = 1-W_B; Y_B <= W_X; Y_B++) {
          // Xと一致しているか調べる
          bool ok = true;
          for(int x=0; x<H_X; x++) {
            for(int y=0; y<W_X; y++) {
              bool is_black = false;
              if(0 <= x-X_A && x-X_A < H_A)
                if(0 <= y-Y_A && y-Y_A < W_A)
                  if(A[x-X_A][y-Y_A] == '#') is_black = true;
              if(0 <= x-X_B && x-X_B < H_B)
                if(0 <= y-Y_B && y-Y_B < W_B)
                  if(B[x-X_B][y-Y_B] == '#') is_black = true;
              if((X[x][y] == '#') != is_black) ok = false; 
            }
          }
          if(ok) {
            // 「X内部の模様は一致していた」場合
            bool ok_2 = true;
            // 「A内部、かつX外部」のチェック
            for(int x=0; x<H_A; x++) {
              for(int y=0; y<W_A; y++) {
                // 「A内での(x,y)」が、「Xを原点とした座標」でどこなのか
                int global_x = X_A + x;
                int global_y = Y_A + y;
                if(global_x < 0 || H_X <= global_x
                    || global_y < 0 || W_X <= global_y) {
                  if(A[x][y] == '#') ok_2 = false;
                }
              }
            }
            // 「B内部、かつX外部」のチェック
            for(int x=0; x<H_B; x++) {
              for(int y=0; y<W_B; y++) {
                // 「B内での(x,y)」が、「Xを原点とした座標」でどこなのか
                int global_x = X_B + x;
                int global_y = Y_B + y;
                if(global_x < 0 || H_X <= global_x
                    || global_y < 0 || W_X <= global_y) {
                  if(B[x][y] == '#') ok_2 = false;
                }
              }
            }
            if(ok_2) {
              cout << "Yes" << endl;
              return 0;
            }
          }
        }
      }
    }
  }
  cout << "No" << endl;
}

長いですが、そこまで特殊なことはやっていないはずです...
ちなみに、計算量は約$O(20^4 \times (2 \times 10^2)) = O(32 \times 10^6)$くらいになりそうなので、多分間に合うでしょ、ぐらいです。

実装がしんどいですね...この長さを爆速で、かつバグなしで書く、というのは結構大変です。

D. Mismatched Parentheses

概要

英小文字および(、)からなる文字列が与えられます。
(と)の間に英小文字のみが含まれている((,)は含まれていない)ような部分を消去する、という操作を繰り返した場合、最終的に文字列はどうなりますか?

制約

$1 \leq N \leq 2 \times 10^5$

必要技術

• 文字列操作
• stack

方針

基本的には、「)がくれば、一つ前の(からそこまでを全部消す」の繰り返しです。
しかし、「一つ前の(」を毎回検索していては時間に間に合いません。

ここで、stackというデータ型があります。
データが縦に(床に雑誌を置いているように)並んでいるようなイメージで使えるものです。
一番上の要素を消したり、取り出したり、要素を上に積んだり、といったことができます。
(が登場するたびにstackに新しい段を追加し、)が出てきたら一段取り除けばいけそうですね。
(つまり、(によって「消えるかもしれない」部分を一つの段として扱う)

つまり、前から順に一文字ずつ見ていき、

• a~zなら一番上の段に書き足す
• (ならstackに新しい段を追加し、(を書き足す
• )なら、
  • stackに2つ以上段があるなら、一番上の段を取り除く
  • 1つしか積まれていないなら、1段目に)を書き足す

ということになります。

コード

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  string S;
  cin >> N >> S;
  stack<string> st;
  st.push("");
  for(int i=0; i<N; i++) {
    if(S[i] == '(') {
      st.push("(");
    } else if(S[i] == ')') {
      if(st.size() == 1) {
        st.top().push_back(')');
      } else {
        st.pop();
      }
    } else {
      st.top().push_back(S[i]);
    }
  }
  string ans = "";
  while(!st.empty()) {
    ans = st.top() + ans;
    st.pop();
  }
  cout << ans << endl;
}

st.top()をそのまま順に出力すると逆順になってしまうので、一度ansにまとめてから出力しています。
stringに対して.push_back(char)で文字を追加できるのがポイントです。

E. Distinct Adjacent

概要

N人が円形に並んでいるので、それぞれに0以上M未満の整数を渡します。
どの隣り合う二人も異なる整数を持っているようにする方法は何通りありますか?

制約

$2 \leq N \leq 10^6$
$2 \leq M \leq 10^6$

必要技術

• DP
• modint
• (数学?)

方針

まず、人1に渡す整数は$M$通りです。
その次に、人2には人1と違うもの、すなわち$M-1$通りの選び方があります。
同様に、人3にも$M-1$通り...と考えていくといけそうですが、実は最後に罠があります。
人Nは人N-1、人1のどちらとも異なる整数を持っていなければならないので、$M-2$通りとなる...わけではありません!
もし人N-1、人1が同じ数字を持っている場合、人Nが選べる数字は$N-1$通りなのです。

しかし、(前から決めていくとして)人N-1が人1と同じ整数を持つことができるか、というのは、人N-2が人1と同じ整数かどうか、ということに左右されます。人N-2が人1と同じ整数を持つことができるか、というときも同様です。
なんか「人1と同じ整数を持っているか」に左右されそうな気がしますね...

というわけで、「どの人まで整数を渡したか」「人1と同じ整数を持っているか」を使ったDPとなります。
(数学が好きな人なら、確率漸化式を思い浮かべたかもしれません。漸化式≒DPなので、やってることは同じです)

あと、結果を998244353で割ったあまりで答えないといけません。これは、結果が非常に大きくなる(long longにも入らないレベル)ということです。ただ、計算ごとに% 998244353すればOKです。
(mod 998244353でも、足し算や引き算、掛け算は成立します。割り算はめんどいです)

あまりを自分で取るのが面倒であれば、AtCoder内で使えるAtCoder Libraryが提供してるmodintを利用すると楽です。

コード

#include <bits/stdc++.h>
using namespace std;
int main() {
  long long N, M;
  cin >> N >> M;
  // 人は0スタートとします、つまり人0~人(N-1)がいるとします。
  // dp[i][0]が「人iが人0と異なる整数を持っている時の場合の数」、
  // dp[i][1]が「人iが人0と等しい整数を持っている時の場合の数」とします。
  vector<vector<long long>> dp(N, vector<long long>(2, 0));
  dp[0][1] = M;
  for(int i=1; i<=N-2; i++) {
    dp[i][0] = dp[i-1][0] * (M-2) + dp[i-1][1] * (M-1);
    dp[i][0] %= 998244353;
    dp[i][1] = dp[i-1][0];
  }
  dp[N-1][0] = dp[N-2][0] * (M-2) + dp[N-2][1] * (M-1);
  dp[N-1][0] %= 998244353;
  // dp[N-1][1] = 0;
  cout << dp[N-1][0] << endl;
}

いくらmod 998244353を取るといっても、たとえばdp[i-1][0] * (M-2)の部分はintの最大値を超えてしまう場合があります。そのため、M,N,dpはlong longとしています。
(long longはちょうどintの2倍の桁数が扱えるので、int*intは必ずlong longに格納可能です)

ACL(AtCoder Library)のmodintを利用した方法

使い方は全て公式ドキュメントに書いてあります。

簡単に言えば、「% 998244353を毎回勝手にしてくれるint」です。
ただ、そのままcoutへ送ることはできず、出力時には.val()を取らないといけないことに注意してください。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

using mint = modint998244353;

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<mint>> dp(N, vector<mint>(2, 0));
  dp[0][1] = M;
  for(int i=1; i<=N-2; i++) {
    dp[i][0] = dp[i-1][0] * (M-2) + dp[i-1][1] * (M-1);
    dp[i][1] = dp[i-1][0];
  }
  dp[N-1][0] = dp[N-2][0] * (M-2) + dp[N-2][1] * (M-1);
  cout << dp[N-1][0].val() << endl;
}

まとめ

C以外はとても面白かったです。(DのstackやEのDPなど、典型と言われるタイプなのかな?)
Cは実装が重い上に、雑にやるとTLEになってしまいそうな問題でした。まあ頑張ればいけるはずです。
コンテスト中は、C解きながら「みんなD解いてるじゃん...どうしよ...」って考えてましたw