ABC215 A~E 解法(やや自分用)

はじめに

この記事はAtCoder Beginner Contest 215(2021/8/21)の解法を自分用にまとめたものです。

解説

A問題 - Your First Judge

解法

Javaだけ等価比較してもダメなのでequalsを使おう。それ以外は多分普通に等価比較演算子でOK

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

int main(){
  string s; cin >> s;
  if(s == "Hello,World!") cout << "AC" << endl;
  else cout << "WA" << endl;
}

B問題 - log2(N)

解法

一発で求めるのはめんどくさいので $k$ を全探索します。
$log_2{10^{18}} \leq 60$ なので問題なし(嘘だと思ったらGoogleの検索バーに"log2(10^18)"と打ってみよう)。
ただし 1LL << 63 とするとこれはオーバーフローになるのでそこまでは回さないようにしよう。

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

using ll = long long;

int main(){
  ll n; cin >> n;
  int ans = 0;
  for(int i = 0; i < 63; i++){
    if((1LL << i) <= n) ans = i;
  }
  cout << ans << endl;
}

C問題 - One More aab aba baa

C++ 以外は DFS で実装せざるを得ないですね……

解法

ABC202のD問題が再来しててヤバイと思ったのですが、弱体化してました。
next_permutation してくださいと言わんばかりの制約 ( $|S| \leq 8$ ) なので、最初に $S$ を文字単位で sort した後に next_permutation をかけて $S$ をそのまま vector に突っ込み $K$ 番目を取得します。

解法( C++ 以外)

昇順の順列全列挙は DFS でも出来たりします。コード例は載せませんが例えば $N = 3$ の場合は

• 頂点1に入る まだ使用してない頂点は2, 3
  • 頂点2に入る まだ使用してない頂点は3
    • 頂点3に入る 全部の頂点を使用したので、入った順に頂点の番号を並べると1, 2, 3
    • 頂点3から出る 3は未使用になる
  • 頂点2から出る 2は未使用になる
  • 頂点3に入る まだ使用してない頂点は2
    • 頂点2に入る 全部の頂点を使用したので、入った順に頂点の番号を並べると1, 3, 2
    • 頂点2から出る 2は未使用になる
  • 頂点3から出る 3は未使用になる
• 頂点1から出る 1は未使用になる
• 頂点2に入る

以下略……
という処理を行うと、入った順に頂点番号を並べた時にそれが昇順の順列になっています。今回は制約が小さいので余裕で間に合うでしょう。

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

int main(){
  string s; cin >> s;
  int k; cin >> k;
  sort(all(s));
  vector<string> anslist;
  do{
    anslist.push_back(s);
  }while(next_permutation(all(s)));
  cout << anslist[k - 1] << endl;
}

D問題 - Coprime 2

ひいいいいまた見たことのある問題名がああああああ

考察

「互いに素である」と「共通な素因数を持たない」はお互いに必要十分条件です。
$1 \leq i \leq M$ である $i$ を一つ一つ確かめるため計算量に $M$ が付くのは確実だと考えます。$M \cdot 1$ か $M \cdot \log{X}$ 程度の計算量で解きたいところです。そうすると全ての数字について毎回 $A$ の各要素と gcd をとることはできませんが、前処理として $A$ の各要素について素因数の全列挙は出来そうです。

解法

高速な素因数分解(Smallest Prime Factor)を用います。$10^5$ はメモリに載せられるので $N \log{\max{Ai}}$ で全部解くことが出来ます。それらを全部 set $A$ に乗せてやりましょう。
高速素因数分解のやり方はこちら
$M$ の制約も $10^5$ なのでこちらも $1$ つずつ素因数分解しては set $B_i$ に乗せてやります。$i$ の素因数 set が $B_i$ とすれば、$B_i \cap A = (\emptyset)$ であるような $i$ を昇順に queue に乗せて出力します。

ちなみに set に対する値の所在確認は対数時間で出来ます。

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

int main(){
  int n, m; cin >> n >> m;
  vector<int> a(n);
  for(int i = 0; i < n; i++) cin >> a[i];

  vector<int> ert(100001, 0);
  ert[1] = 1;
  for(int i = 2; i <= 100000; i++){
    if(ert[i]) continue;
    for(int j = i; j <= 100000; j += i){
      ert[j] = i;
    }
  }

  // badlist
  set<int> badlist;
  for(int i = 0; i < n; i++){
    int p = a[i];
    while(p > 1){
      badlist.insert(ert[p]);
      p /= ert[p];
    }
  }

  queue<int> anslist;
  for(int i = 1; i <= m; i++){
    int p = i;
    bool flg = true;
    set<int> prmlist;
    while(p > 1){
      prmlist.insert(ert[p]);
      p /= ert[p];
    }
    for(int v : prmlist){
      if(badlist.find(v) != badlist.end()) flg = false;
    }
    if(flg) anslist.push(i);
  }
  
  cout << anslist.size() << endl;
  while(!anslist.empty()){
    cout << anslist.front() << endl;
    anslist.pop();
  }
}

E問題 - Chain Contestant

遂に出た！！DP！！

考察

コンテストの種類が $10$ 種類しかありません。これは大きな弱点の予感。
ABC142-E Get Everythingでもありましたが、集合を2進数化して添字に乗せるDPをbit DPと呼びます(ソース不明)。

解法

まずはコンテスト A ~ J を 1 ~ 10 に直します。
既に一度出たコンテストであり、かつ直前に出たものではないコンテストには出られないようにして、dpを組んでみます。

$dp[i][j][k] = i$ 個目までのコンテストで、出場済みのコンテストの集合を $j$ で、かつ直前に出たコンテストは $k$ である場合の選び方の総数 ( mod $998244353 $ )

ここで、初期条件は $dp[0][0][0] = 1$ なのですが、実際にはコンテストに $1$ 回も出ないという選択は出来ません。そこで最終的な答えは

$$\Sigma_{i = 1}^{1024} \Sigma_{j = 1}^{10} dp[n][i][j]$$

です。

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

using ll = long long;

# define ml modint998244353

int main(){
  int n; cin >> n;
  string s; cin >> s;
  vector<int> parse(n);
  for(int i = 0; i < n; i++) parse[i] = s[i] - 'A' + 1;

  // dp[i][j] = i個目のコンテスト、出場済みコンテスト:j、直前:k
  vector<vector<vector<ml>>> dp(n + 1, vector<vector<ml>>(1024, vector<ml>(11, 0)));
  dp[0][0][0] = 1;

  for(int i = 0; i < n; i++){
    int next = parse[i];
    for(int j = 0; j < 1024; j++){
      for(int k = 0; k <= 10; k++){
        // 出場しない
        dp[i + 1][j][k] += dp[i][j][k];
        
        // 出場する
        if(k != next && (j & (1 << (next - 1)))) continue;
        int alr = j | (1 << (next - 1));
        dp[i + 1][alr][next] += dp[i][j][k];
      }
    }
  }

  ml ans = 0;
  for(int i = 1; i < 1024; i++){
    for(int j = 0; j <= 10; j++){
      ans += dp[n][i][j];
    }
  }
  cout << ans.val() << endl;
}

(8/22 0:11 E問題のACL指定が消えていたので追記しました。)