ABC456を振り返る

プログラミング
2026.05.02

はじめに

皆様どうも、ばるとーくです。
今回も振り返りやっていきましょうかねぇ。

今回は残念ながら2完でした…
いけそうだったんだけどなぁ～（後述しますがガチで惜しいミスしてます）

あとどうでもいいけどさ、
なんかチンチロの問題出るみたいなのXで聞いて、実際でたじゃん？
何でかすぐにはわからんかったんやけど、なるほど、456(シゴロ)やからかぁ～って途中で気づいた（）

振り返り

A問題

問題文

6 つの面を持つサイコロが 3 個あります。
どのサイコロも、面には 1,2,3,4,5,6 が書かれています。

これらのサイコロを同時に振ったとき、出た目の合計が X になることはありますか？

制約

  • X は 1 以上 20 以下の整数
A - Dice
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoder

これは１発ACを取れました。（いや流石にね…？）
こんなコードです。

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

// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
  Init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
  }
} init;
// ------------------------------------------------

int main() {
  int x;
  cin >> x;
  for (int i = 1; i <= 6; i++) {
    for (int j = 1; j <= 6; j++) {
      for (int k = 1; k <= 6; k++) {
        if(i + j + k == x){
          cout << "Yes" << "\n";
          return 0;
        }
      }
    }
  }
  cout << "No" << "\n";
  return 0;
}

３重for文でゴリ押しさせていただきました～
スピード重視なら別の方法あるだろうけど、まあヨシ！

B問題

問題文

6 つの面を持つサイコロが 3 個あります。
i 個目のサイコロの j 個目の面には Ai,j​ が書かれています。
どのサイコロも、各面が出る確率は 61​ です。

これらのサイコロを同時に振ったとき、4,5,6 の書かれた目が 1 つずつ出る確率を求めてください。

制約

  • Ai,j​ は 1 以上 6 以下の整数
B - 456
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoder

これ、時間を30分くらい使った上になかなかWAから抜け出せずにいました。
時間をつかった原因は…数弱だからかな？
※自分で言ってて悲しいです

４の個数、５の個数、６の個数がそれぞれ違うときの処理をどうするか考えた結果、ごりごりに樹形図を書いて、それぞれの場合で確率計算を行い、最後に足すことにしました。
せいぜい６通りしかないので問題はないでしょう

ではWAが取れなかった原因は何かというと…⁉
タイポ、つまりタイプミスです…（悲しい）

ちょっと見比べてもらおうかと思います。

左側がWAのとき、右側がACのときのコードです。
何が違うかおわかりでしょうか？（違う部分にマーカー入れてます）

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

// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
  Init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(20);
  }
} init;
// ------------------------------------------------

int main() {
  double a4 = 0, a5 = 0, a6 = 0, b4 = 0, b5 = 0, 
b6 = 0, c4 = 0, c5 = 0, c6 = 0;
  for (int i = 0; i < 6; i++) {
    int inp;
    cin >> inp;
    if (inp == 4) {
      ++a4;
    } else if (inp == 5) {
      ++a5;
    } else if (inp == 6) {
      ++a6;
    }
  }

  for (int i = 0; i < 6; i++) {
    int inp;
    cin >> inp;
    if (inp == 4) {
      ++b4;
    } else if (inp == 5) {
      ++b5;
    } else if (inp == 6) {
      ++b6;
    }
  }

  for (int i = 0; i < 6; i++) {
    int inp;
    cin >> inp;
    if (inp == 4) {
      ++c4;
    } else if (inp == 5) {
      ++c5;
    } else if (inp == 6) {
      ++c6;
    }
  }

  double a, b, c, d, e, f;
  a = (a4 / 6) * (b5 / 6) * (c6 / 6);
  b = (a4 / 6) * (b6 / 6) * (c5 / 6);
  c = (a5 / 6) * (b4 / 6) * (c6 / 6);
  d = (a5 / 6) * (b6 / 6) * (c6 / 6);
  e = (a6 / 6) * (b4 / 6) * (c5 / 6);
  f = (a6 / 6) * (b5 / 6) * (c4 / 6);

  cout << a + b + c + d + e + f << "\n";
  return 0;
}

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

// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
  Init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(20);
  }
} init;
// ------------------------------------------------

int main() {
  double a4 = 0, a5 = 0, a6 = 0, b4 = 0, b5 = 0, 
b6 = 0, c4 = 0, c5 = 0, c6 = 0;
  for (int i = 0; i < 6; i++) {
    int inp;
    cin >> inp;
    if (inp == 4) {
      ++a4;
    } else if (inp == 5) {
      ++a5;
    } else if (inp == 6) {
      ++a6;
    }
  }

  for (int i = 0; i < 6; i++) {
    int inp;
    cin >> inp;
    if (inp == 4) {
      ++b4;
    } else if (inp == 5) {
      ++b5;
    } else if (inp == 6) {
      ++b6;
    }
  }

  for (int i = 0; i < 6; i++) {
    int inp;
    cin >> inp;
    if (inp == 4) {
      ++c4;
    } else if (inp == 5) {
      ++c5;
    } else if (inp == 6) {
      ++c6;
    }
  }

  double a, b, c, d, e, f;
  a = (a4 / 6) * (b5 / 6) * (c6 / 6);
  b = (a4 / 6) * (b6 / 6) * (c5 / 6);
  c = (a5 / 6) * (b4 / 6) * (c6 / 6);
  d = (a5 / 6) * (b6 / 6) * (c4 / 6);
  e = (a6 / 6) * (b4 / 6) * (c5 / 6);
  f = (a6 / 6) * (b5 / 6) * (c4 / 6);

  cout << a + b + c + d + e + f << "\n";
  return 0;
}

そう、問題は下から７行目。このマーカー部分です。
ここに速く気づいていれば…

C問題

問題文

a, b, c からなる文字列 S が与えられます。

S の空でない部分文字列であって、同じ文字が隣り合わないものの個数を 998244353 で割った余りを求めてください。

ただし、 2 つの部分文字列が文字列として一致しても、取り出す位置が異なるならば区別するものとします。

部分文字列とは

S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。 例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。

制約

  • S は a, b, c からなる長さ 1 以上 3×105 以下の文字列
C - Not Adjacent
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoder

この問題はフルフルに時間を使っても解けず、時間切れとなりました。

同じ文字が隣り合わないようにしたいなら、ってことで、文字列をランレングス圧縮してから数え上げることにしました。
これが最終的に書いたコードです。

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

// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
  Init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
  }
} init;
// ------------------------------------------------

int main() {
  string s;
  cin >> s;
  ll ans = 1;
  vector<ll> rlen(0);
  char f = 'z';
  int len = 1;
  for (int i = 0; i < s.size(); i++) {
    if (i == 0) {
      f = s[i];
      len = 1;
    } else {
      if (s[i] != f) {
        rlen.push_back(len);
        f = s[i];
        len = 1;
      } else {
        ++len;
      }
    }
  }
  rlen.push_back(len);

  cerr << rlen.size() << "\n";

  for (ll i : rlen) {
    cerr << i << endl;
  }

  int l = 0;
  for (int i = 1; i < rlen.size(); i++) {
    if (rlen[i] != 1) {
      ans += rlen[i] + (i - l) * (i - l + 1) / 2;
      l = i;
    } else {
      ++ans;
    }
    cerr << ans << "\n";
    ans %= 998244353;
  }

  ans += (rlen.size() - l - 1) * (rlen.size() - l)/ 2;
  cout << ans % 998244353 << endl;
  return 0;
}

しかしWAでした。
全く理由がわからず、Claude君に聞きました。
そしたらこういわれました。

ll ans = 1; の初期化です。これは「最初のランから 1 文字だけ寄与する」と決め打ちしている形ですが、rlen[0] が 2 以上のときに (rlen[0] − 1) 個ぶん足りなくなります。

具体例：

入力コード出力正解差
"aaaa"143
"aabbcc"781
"aaabb"462

ずれは常に rlen[0] − 1。rlen[0] == 1 のテストケースだけ通ったので気づきにくかったやつです。

  • 修正

rlen.push_back(len); の直後で

cpp

ll ans = rlen[0];

に直せばロジック自体は通ります。それ以降の (i - l)(i - l + 1)/2 の式と末尾項は、実は正しく組めていて、l ≤ a < b ≤ i を満たすクロスラン部分文字列をちゃんと数え上げてます。最初の1点だけが穴でした。

要するに、自分は「最初の文字は1つしか連続しないだろう」と。そう思い切っており、このパターンを見逃していたのが敗因です…
いや、マジで盲点でした…
※気づけてたら終了の20分前には通せてた

とはいえ、ちゃんと自分で気づけた点もありました。数え上げ方とか（最初階乗と勘違い）、総和の公式を使った計算量節約とか…

さいごに

反省点として、「コードレビューをもっとちゃんとする」ことを重点に置きたいですね…
WAで返ってきたときは、Easy testだけに頼らず自分でもテストケースを考えていく癖、要りますね…
※今までなかったんかよ⁉って話ではあるんですけども…極度の面倒くさがりなのが裏目にぃぃ

あとは、4Q~2Qの問題をもっとちゃんと詰めたいです。
いや、まさにやるべきなんだろうけども

最後に、レート推移を貼って終わりたいと思いまする

これからも、とりあえず茶色を目指してがんまります！
ちなみに今日のせいで400になるために973パフォが必要になってしまった。
360には702パフォが必要である。こっちならまだ現実的かもね。

コメント

タイトルとURLをコピーしました