LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@Shiroha_MK3((Mitta Kazuki) 白羽)

ABC202 まとめ、Dまで解説

Posted at

はじめに

この記事はAtCoder Beginner Contest 202(2021/5/22)の解説や個人的な反省点をまとめたものです。

解説

A問題 - Three Dice

事前知識

標準入出力の方法を覚える
小学生レベルの四則演算をプログラムに書くための文法

解法

解説にしっかり反対の面を出す方法が載っていますが、改めて説明するとサイコロのある面が$n$のときその反対にある面は$7-n$です。
下のコードはぐちゃぐちゃですが、式を整理したら$21-a-b-c$になります。

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

int main(){
  int a, b, c; cin >> a >> b >> c;
  cout << (7 - a) + (7 - b) + (7 - c) << endl;
}

B問題 - 180℃

事前知識

使っている言語で文字列を逆転させる方法
使っている言語で文字列を比較する方法(JavaではString.equals()が必須などちょっとした罠があったりします)

解法

反転したうえで文字列を置き換えることになります。C++には幸いにもreverse関数がありStringにも利用できるので利用していきましょう。
ちなみにこれも本番中のコードなので無駄が多いですが、反転した後置き換えるのは6と9だけでそれ以外はそのまま1文字ずつ出力してしまってよいです。

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

int main(){
  string s; cin >> s;
  reverse(s.begin(), s.end());
  for(int i = 0; i < s.length(); i++){
    if(s.substr(i, 1) == "0"){
      cout << "0";
    }else if(s.substr(i, 1) == "1"){
      cout << "1";
    }else if(s.substr(i, 1) == "6"){
      cout << "9";
    }else if(s.substr(i, 1) == "8"){
      cout << "8";
    }else{
      cout << "6";
    }
  }cout << endl;
}

C問題 - Made Up

事前知識：連想配列

キーと対応する値が配列と違って連続でなくてもよい、なんならStringとかでもよい配列です。詳しくはこれなどを参考にどうぞ。
C++にはmap JavaにはHashMapなどがあります。

解法

制約が大きくてちょっと面食らいましたが、滅茶苦茶な解法が通ってしまいました。
具体的には

  • $C$における各数字の出現回数をmapに保持 -> c_mapとする
  • $B$の各数字$B_1 B_2…B_n$について、c_map[$B_1～B_n$]を$B$の値ごとに合算したmapを作成 -> b_mapとする
  • 最後に$A$についてそれぞれb_map[$A_1～A_n$]を合算したものが解

となります。意地悪そうにみえて実は愚直を改良したら通りました的な雰囲気がありました。
ただし、解は最大で$10^{10}$になり得るので、64bit整数型で宣言しましょう(1敗)。
ソースコードは案の定ぐちゃぐちゃです。

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

using ll = long long;

int main(){
  int n; cin >> n;
  vector<int> a(n), b(n), c(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < n; i++) cin >> b[i];
  for(int i = 0; i < n; i++) cin >> c[i];
  map<int, ll> capp;
  for(int i = 0; i < n; i++) capp[c[i]]++;
  vector<pair<int, ll>> blist(n);
  for(int i = 0; i < n; i++){
    blist[i] = make_pair(b[i], capp[i + 1]);
  }
  map<int, ll> bapp;
  for(int i = 0; i < n; i++){
    bapp[blist[i].first] += blist[i].second;
  }
  ll ans = 0;
  for(int i = 0; i < n; i++){
    ans += bapp[a[i]];
  }
  cout << ans << endl;
}

D問題 - aab aba baa

問題文でちょっと嫌な予感はあったのですが、やはり全列挙させない問題でした。

予備知識

パスカルの三角形

220px-Pascal's_triangle_5.svg.png
i行目の左からj番目の数字が$iCj$になる有名(らしい)な三角形です。私はお恥ずかしい限りですが調べながら通しました。

同じものを含む組み合わせの数

ここでは2種類のものしか考えないためその前提で進むと、
"A"がa個、"B"がb個あってそれぞれ同じ文字どうしを区別しない時、その組み合わせは
$\frac{(a + b)!}{a!b!}$
通りあります。
そして、これは選ぶ対象が2種類のとき、
$_{(a+b)}C_a$
に変形できます。

これをパスカルの三角形と組み合わせたら……

考察

最初にaとbをそれぞれ0と1に置き換えてみます。
そして、aが3つ、bが2つの条件で作り得るすべての文字列を考え、昇順に並べると、

00011
00101
00110
01001
01010
01100
10001
10010
10100
11000

以上の10通りが考えられます。
ここで、この通り数は$_5C_2$より10通りであることがすぐに計算できます。

例として、問題文中の$k$が4であった場合を考えます。

ここで先頭の桁だけをみると、綺麗に0と1が分かれています。
そして、0と1の比は$a:b = 3:2$ すなわち最初に決めたaとbの個数の比に一致します。

では次に$k=4$なので先頭が0である前半6行に絞って2桁目を見てみましょう。するとこれも綺麗に0と1が分かれています。
1桁目に0を使ったので、2桁目以降はaが2つ、bが2つの条件で全ての文字列を作ったものと一致します。
この6行とは何でしょうか？それはまさに、$_4C_2$です。
以後、$k=4$なので2桁目が1である4～6行目に絞って……

これを繰り返していくと、

先頭の桁からならば、今から知りたい桁がaかbかは計算で解くことができ、それを繰り返してゆけばすべての桁を決定できる

ことがわかります。

解法

最初にパスカルの三角形を60行目まで求めておきましょう。これは加算のみで計算できるため64bit整数であればオーバーフローせず、最大でも$60^2$のループで計算できます。

次に入力を受け取り、解答を保持するためのstring型キューを作りました。別に+=しても間に合うんですけどね()

aとbの残り出現回数を保持する変数をlaおよびlbとします。
そして、$a+b$回ループを回します。
(プログラム内でaやbを書き換えるとこれでハマります。)

  • la + lb = xとします。
  • パスカルの三角形から$_xC_a$を取得し、$la:lb$で分けた時の境目を計算します。これをdとします。
  • d <= k ?
    • kがdより大きいならば解答キューに"b"をpushします。また、lbをデクリメントし、kからdを引きます。
    • そうでなければ、解答キューに"a"をpushします。また、laをデクリメントします。

ループ終了時点で文字列の生成が終わるので、キューの中身をFIFOで吐き出させて出力します。

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

using ll = long long;

int main(){
  // 先に組み合わせを求めておく
  
  vector<vector<ll>> c(65, vector<ll>(65, 0));
  c[0][0] = 1;
  for(int i = 1; i < 61; i++){
    c[i][0] = 1;
    for(int j = 1; j < 61; j++){
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
  }

  ll a, b, k; cin >> a >> b >> k; k--;
  int fullLen = a + b;

  queue<string> anslist;
  for(int i = 0; i < fullLen; i++){
    // a+b C a
    ll s = c[a + b][a];
    // sをa:bで分ける
    ll division = s * a / (a + b);
    //cout << division << endl;
    if(division <= k){
      // b
      anslist.push("b");
      b--;
      k -= division;
    }else{
      // a
      anslist.push("a");
      a--;
    }
  }
  while(!anslist.empty()){
    cout << anslist.front();
    anslist.pop();
  }cout << endl;
}

反省点

  • 数A範囲であるパスカルの三角形に少々手間取った
    • 商業高校だったからと言い訳をしておきます
  • CでWAを出した
    • 痛すぎる
      • プライド的にintをlong longに置き換えたくはないけど本気で検討しないとダメか……？
      • 考察もちょっと甘かった
    • $10^{10}$に細心の注意を
  • Dの考察が甘すぎる状態で1回出してしまった
    • $a:b=1:1$とは限らないことくらいサルでもわかる

まぁ、数学やれって感じですね……
過去に数学問題で数敗しているのでそろそろやばいです。

終わりに

私にとって2回目となるABC4完となりました。これから水レートを目指すにあたってはこの程度は余裕にならないと厳しい、というのはとてもつらいですが、やる気のある日は頑張ろうと思います(そんなんでいいのか)。
では今回はここまで。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?