競プロ日記

問題
ACコード
WAコード

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cout << #x " => " << (x) << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 28;
constexpr lint   INFL = 1LL << 60;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  string n;
  cin >> n;
  const int len = n.length();
  // dp[桁][3出た][5出た][7出た][nと一致][上位桁が全て0]
  int dp[11][2][2][2][2][2] = {0};
  dp[len][0][0][0][1][1] = 1;
  vector<int> num{3, 5, 7, 0};
  rrep (i, len) {
    int digit = n[len - i - 1] - '0';
    rep (j, 4) {
      vector<bool> next(4);
      next[j] = true;
      const int x = num[j];
      bool big = x > digit, same = x == digit;
      rep (a, 2) {
        rep (b, 2) {
          rep (c, 2) {
            rep (d, 2) {
              if (d && big) continue;
              rep (e, 2) {
                if (next[3] && !e) continue;
                int na = a | next[0];
                int nb = b | next[1];
                int nc = c | next[2];
                int nd = d & same;
                int ne = next[3];
                dp[i][na][nb][nc][nd][ne] += dp[i + 1][a][b][c][d][e];
              }
            }
          }
        }
      }
    }
  }
  int sum = 0;
  rep (i, 2) sum += dp[0][1][1][1][i][0];
  cout << sum << endl;
  return 0;
}

上から順番にやっているだけなのに桁DP強化月間みたいになってる。
そもそも想定解が桁DPではないが、いかにも桁DPできそうだったので・・・。
全探索の方はすぐに思いつかなかったが、桁DPを縛ったとしたら思いつけたかなぁ、微妙だ。

桁DPでやることを考えたら青くらいはあるんじゃないか？
そもそも桁DP自体が結構難易度高めで、桁DPというだけで水色以上レベルなのだと最近理解した。


今回の桁DPは最近得た知見を総動員しようと頑張ってみた。
前回の記事ABC117 D XXORの「桁DPは上の桁が全て0の場合、DPが初期値かどうかで遷移を変える」という知見も使おうと試行錯誤したのだが、全然うまくいかなかった。
やってみれば理由は明白で、0という数字が出てこないことを前提とした遷移をしているのに、上位桁が全て0の場合のみ0が出てくることが許されるためだ。
いわゆるLeading zero。
「このLeading zero内での遷移をLeading zero以外で0が出てきた場合の遷移と同様に扱えるか」、これが重要なのだと気付いた。
前回の初期値かどうかで遷移を変えるという部分も、初期値である=Leading zero内であるということなので、初期値を考えることの真髄はLeading zeroを考えることだったのだ。
これに気付けたので、DPの状態に「0以外の値が出てきたか」というのを持つことでACできた。

DPの遷移はABC138 F Coincidenceの経験を多いに生かした。
全ての遷移前を、ありえる可能性の回数(今回は0,3,5,7の4回)見て、条件によってcontinueしたり遷移先を変えたりする。
初見ではこんなDPできるか！と思ったものの、2回目の今回、問題のランクはかなり下がったとは言え、この書き方はかなり理にかなってるなと感じられた。
コード中の遷移ではあまり良くない部分でna~neを宣言しているが、今回やABC138Fのように遷移や条件が多い場合、速度や効率重視するより見やすさ大事にした方が良さそう。
dpの全ての状態と遷移は以下の通り。

dp[i][a][b][c][d][e] = dp[桁数][3を1度以上使った][5を1度以上使った][7を1度以上使った][今の所Nと一致][今の所0しか使っていない(Leading zero内かどうか)] = 何通りか
digit = Nのi桁目の数字
x = 遷移しようとしている数(0,3,5,7)

dp[i][na][nb][nc][nd][ne] += dp[i+1][a][b][c][d][e]の遷移を桁数×(0,3,5,7)の4回ループする。
1. x=0かつe=0なら、Leading zero外で0を選択することになるのでcontinue。
2. d=1かつdigit<xなら、Nを超えた遷移になってしまうのでcontinue。
3. x=3,5,7のとき、a,b,cのxに対応する部分を立ててそれ以外はそのまま(na, nb, nc)。
4. d=1かつdigit==xのときのみ、今の所Nと一致を継続できるのでnd=1、それ以外はnd=0。
5. Leading zero内を継続できるのは、今の所Leading zero内で遷移先が0のときのみである。
x=0の遷移が許されるのは1.の条件よりLeading zero内のみなので、x=0のときのみne=1。


ここから苦労話。

まず1番軽いところから。
さすがにDPの配列がここまで深くなるとvectorで書きたくないなぁとなって通常の配列を使ったのだが、普通の配列は0で初期化されないのである・・・。
ずっとvectorばかり使っていたらつい忘れてしまう。
値が明らかにおかしいと遷移を見てみると、オーバーフローのような値が出ていたので、配列外参照がないことを確かめた後、配列は0じゃないじゃんとすぐにたどり着けた。
学生時代に、「{}でも{0}でも初期化できるんだへー」と思ったのを思い出しながら{0]にしておいた。

i桁目の値をどう取り出すかがかなり大事だった。
最初文字列でやろうと思ったのだが、もともと数値なものを文字列に直してまた数値に直して計算するのはいかがなものかと。
10進数だから10で割って色々したらできるだろうとこの方針でやってみたらできたのだが、いかんせんややこしい。
初心に戻って文字列にしたらとても分かりやすい・・・。
さらに最上位の桁が既に分かっているので、NがLeading zeroということがなくなって遷移条件もすっきりできた。
Leading zero内かどうかを判断するために変な条件つけてミスったり、そこだけ抽出して遷移したがために肝心のDPの遷移が間違っていることに全然気付けなかったりと散々だった。
WAコードはこの方針でやっており、桁を取り出す部分やLeading zeroの判定部分は正しく行えているのだが、ACコードのほうが100倍分かりやすい。

もう1つ苦労したのが、テストケースを間違えて見ていたこと(?)。
この問題はテストケースが公開されているので、4つだけWAというところでテストケースを確かめに行ったのだが、間違えてDのテストケース(b16)を見ていた。
最近C問題で詰まるなんてことがなかったのでつい・・・。
他の人の解説のACコードもコードテストに貼り付けて確かめながらやっていたのだが、なんでこの遷移でだめなんだ・・・と、半ばやけくそでACコードにテストコードを貼り付けてみたところ、自分のコードと同じ結果を出したところでおや？となり気付いた。
試しにジャッジしてみたらあっさりAC。
何時間悩んだか。
運悪いことに、Dの入力も出力も同じような値だったのでぱっと見では気付けなかった。
解説も見たのに全然ACできなくて、理解が浅いのか実装をミスっているのか分からなくて何時間も悩み続けるこの感じ、最近は知識も実装力もついてきてほとんどなかったのだが久々に味わった。
もうちょっとで誰かこの桁DPを完成させてくれーーーと未解決問題として記事を書くところだった。


新ABC解き始めた頃、ほとんどテストケース公開されていないのがかなり辛い気持ちだったが、最近は公開されていてもテストケースはあまり見ないようにしている。
というのも、解説記事を見れば8割くらい正解のコードは書けるはずなので、そこからテストケースを見て答えが合うようにコードを弄るのは、意味も分からずパズルをかちゃかちゃして合わせているようであまり身になる気がしないからである。
見ないことに拘って時間を溶かすのも頭悪いが、見てさらに時間を溶かしたのは頭悪すぎる・・・。

問題
ACコード

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cout << #x " => " << (x) << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 29;
constexpr lint   INFL = 1LL << 61;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  lint n, k;
  cin >> n >> k;
  vector<lint> a(n);
  rep (i, n) cin >> a[i];
  int limit = 1;
  while ((1LL << limit) < 1e12) ++limit;
  vector<int> digit_num(limit + 1);
  rep (i, n) {
    rep (j, limit + 1) {
      if (a[i] & (1LL << j)) ++digit_num[j];
    }
  }
  // inc[桁数][0or1] = 増加量
  vector<vector<lint>> inc(limit + 1, vector<lint>(2));
  rep (i, limit + 1) {
    inc[i][0] = (1LL << i) * digit_num[i];
    inc[i][1] = (1LL << i) * (n - digit_num[i]);
  }
  // dp[桁数][k以下が未確定or確定] = 合計
  vector<vector<lint>> dp(limit + 2, vector<lint>(2));
  rrep (i, limit + 1) {
    bool big = inc[i][0] < inc[i][1];
    if (dp[i + 1][1]) dp[i][1] = dp[i + 1][1] + inc[i][big];
    if (k & (1LL << i)) {
      dp[i][0] = dp[i + 1][0] + inc[i][1];
      dp[i][1] = max(dp[i][1], dp[i + 1][0] + inc[i][0]);
    } else {
      dp[i][0] = dp[i + 1][0] + inc[i][0];
    }
  }
  cout << max(dp[0][0], dp[0][1]) << endl;
  return 0;
}

自力で解けたものの実装が遅すぎる・・・！
大体こうやったら良いんだろうな、というのはわりとすぐに思い浮かんだものの、細部まで詰めて実装するのに時間がかかってしまった。

今回桁DPの状態で持つ桁数を、普通の数え方と同じく「下位からi桁目」にしてみた。
自分は桁DPするときは上の桁から見るので、前回桁DPを使った時は「上位からi桁目」としていたのだが、どちらが良いのだろう。
上位からの場合、仮定した最大桁数からi桁になってしまうので、実際のi桁目を取り出しづらいのがちょっと良くないが、遷移が直感的なのがちょっと良い。
下位からの場合、遷移の際に桁を足せば良いのか引けば良いのか少し分かりづらいのがちょっと良くないが、状態の桁数をそのまま実際の桁数に使えるのがちょっと良い。
前回上位からやったときは、i桁目を取り出す関数を作ったのだが、どうもスマートに感じなかったので今回は下位からやってみたのだが、やっぱり遷移の際に桁を足せば良いのか引けば良いのかに少し脳のリソースを取られるのが少し嫌だなぁ。
でもどちらかに明らかな優位性を感じるまではとりあえず下位からでやっていこうと思う。

本題に入って、基本的な方針は色々言った通り桁DP。
全てのAの各桁に1が現れる総数を数え、桁iを0と1にしたときのf(X)の増加量inc[桁][0or1]をそれぞれ計算する。
後は通常通り、今見ている桁と、K以下が確定しているかどうかを状態に持ち、その状態までの合計で桁DPを行いたかった。
しかし、K以下という条件を入れ込むのにかなり苦労した。
今回のように、i桁目が1の時のみ増加ではなく、i桁目が0でも増加する場合、値が0でも想定した最大桁数分の0が蓄積されてしまう。
これを解決するためには、桁をどこから始めれば良いんだろうと結構な時間考えた。
Kの値を最大桁数にしてしまうと、Aがそれ以上だった場合に正しく計算できないのは当然だ。
Aの値を最大桁数にしてしまうと、Kがそれ以上だった場合に、Aの最大桁数とKの最大桁数の間の蓄積されるべき0を計算することができない。

なんやかんやあって、サンプルケースのDPの遷移を観察することで大きく進展した。
最大桁数に依存するのではなく、DPの遷移をもっと詰めるべきだった。
直感的に理解したのでなかなか文章に起こすのが難しいが、K以下が確定した状態の遷移を考えることが正解の鍵だった。
Kを最大桁数limitから見ていき、桁iまで見た段階で未だ1が一度も出ていない(=Kの最大桁数より大きい)場合、dp[i~limit][1]が更新されることはない。
なぜなら全て0なのだから、K以下が確定することはないためである。
未更新であることはつまり、dp[i~limit][1]が初期値のままであることと同じなので、初期値であればK以下が確定した状態は更新しなければ良い。

自分がpの遷移を考える場合、適当に分かりやすい部分を選んで考えることが多い。
K以下が確定しているならi桁目の数は0でも1でも好きな方を選んで良く、これはKのi桁目の値に関係なく行えるから条件式は要らない、と当初考えた。
しかしこれだと、正しい「K以下が確定した場合の合計」ではなかった。
1度でもKの桁に1が現れた(=dp[i+1][1]が初期値ではない)を条件に加えることで正解にたどり着けた。

1つ前の記事ABC118 D Match Matchingでも初期値かどうかで遷移するかどうか決めており、実はこの時もこれに気づくのに時間がかかった。
今までの桁DPでは、桁の値が0の場合は遷移先に変更を行わないようなものがほとんど(全て？)で、ABC138 F CoincidenceのようにMSBも状態に持つのかと最初考えてしまった。
さすがに問題のレベルが違う気がするので考え直したが、KのMSBがまだなら遷移しないというのは部分的に同じだ。
桁の値が0の場合は遷移先に変化がないような桁DPでは、最大桁数より上の桁が0で埋められているため、「桁の値が0なら変更しない」という条件で、「初期値なら遷移しない」という条件も覆えているだけで、本来なら後者の条件も入れるべき(のはず)。
初期値なら遷移しない、というのはDP全般において重要だと感じるのでしっかり覚えておきたい。

YouTubeの解説も見てみたのだが、途中までは同じなのにやっぱり頭良さを感じた。
途中のincを計算するところまでは同じだが、その後。
ある桁を0にするか1にするかによる全体の変化量の違いは、それぞれの増加量ではなくその差となるので、上位の桁から貪欲にとは行かないのはかなり初期の段階で分かったが、その差を保持することで貪欲に求められるとは。
そもそも、初期を0として、「1にするかどうか」という視点の持ち方がなかった。
「0を選ぶか1を選ぶか」とは内容的は変わらないが、差を考えるとそうはいかない。
「良い方を選んだらその差だけ増える」と考えるのではなくて、「1にしたら正負もつけてその差だけ増減する」と考える。
初期が0なので、上位の桁から考えるとある時点でその後はどう選んでも良くなる。
どう選んでも良いなら差がプラスのものを全て選べば良いので貪欲に求められる。
桁DPのような「K以下かどうか」という考え方を活かしつつ貪欲といった感じだろうか。
頭良い。

桁DPの解説も少しだけあったので、K以下が確定した状態を0とするか1とするかも確認できた。
たぶんいつも「確定したら0」としていたのだが、今回桁数を下位からに変えたのも影響して(?)、確定したら0か1どっちにしようとなぜか悩んでにした。
悩んで決めたものは実装中に分からなくなって混乱しそうなのでコメントも残しておいた。
確定していない状況が特殊な分岐が必要になるのだから、やっぱり「確定したら0」が自然だよなぁ。
なぜ混乱したのか。

問題
ACコード

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cout << #x " => " << (x) << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 29;
constexpr lint   INFL = 1LL << 61;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  int n, m;
  cin >> n >> m;
  vector<int> a(m), b(m);
  rep (i, m) cin >> a[i];
  const vector<int> match{0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
  rep (i, m) b[i] = match[a[i]];
  unordered_map<int, int> num;
  rep (i, m) num[b[i]] = max(num[b[i]], a[i]);
  sort(all(b));
  b.erase(unique(all(b)), b.end());
  const int bs = b.size();
  vector<map<int, int>> dp(n + 1);
  auto comp =
    [&](map<int, int> &x, map<int, int> &y) {
      if (x[0] != y[0]) {
        return x[0] < y[0];
      } else {
        for (auto xitr = x.rbegin(), yitr = y.rbegin(); xitr != x.rend() && yitr != y.rend(); ++xitr, ++yitr) {
          int xf = xitr->first, xs = xitr->second, yf = yitr->first, ys = yitr->second;
          if (xf != yf) {
            return xf < yf;
          } else {
            if (xs != ys) return xs < ys;
          }
        }
        return true;
      }
    };
  dp[0][0] = 0;
  rep (i, n + 1) {
    if (dp[i].empty()) continue;
    rep (j, bs) {
      if (i + b[j] > n) continue;
      auto tmp = dp[i];
      ++tmp[0];
      ++tmp[num[b[j]]];
      if (comp(dp[i + b[j]], tmp)) dp[i + b[j]] = tmp;
    }
  }
  string ans;
  for (auto itr = dp[n].rbegin(); itr != --dp[n].rend(); ++itr) {
    ans += string(itr->second, itr->first + '0');
  }
  cout << ans << endl;
  return 0;
}

青だけど自力で解けてうれC。
本番だとAからDまで通せていないくらいの時間はかかっているので、そろそろ速度も考えないと。

10分程解析的に解こうと色々考えたが、最終的にDPで良い感じになりそうなことが分かった。
その後色々試行錯誤して以下のようなDPに至った。
DP[使用したマッチの総数]=最大桁数 & map{使用する数字：その数字を使用する回数}
0はマッチで作る数字には存在しないので、0に桁数を格納することでpairがいらなくなる。
使用したマッチの総数iを1～Nまで、使用するj番目の数字を0からMまでループして値を更新する。
j番目の数字a[j]、a[j]を作るのに必要なマッチの数をb[j]とし、newDP[i]を、DP[i][0]を+1、DP[i][a[j]]を+1したものとする。
すると更新はDP[i+b[j]]=max(DP[i+b[j]], newDP[i])となる。

mapの比較は以下のように行う。
まず、桁数が異なれば大きい方を大とする。
次に、等しい場合は先頭要素のkeyを比較し、異なる場合は大きい方を大とする。
先頭要素のkeyも等しい場合は、先頭要素のvalueを比較し、異なる場合は大きい方を大とする。
それも同じ場合は次の要素を比較する。

初期値はDP[0][0]=0とし、DP[i]が空だった場合は更新しない。
答えは、DP[N]から数字が大きい順に指定回数取り出したものになる。

この流れの実現に当たって少し工夫したのが、使用する数字の選別である。
同じ本数で作れる数字が複数あれば、必ず大きい方を使うべきなので小さい方は取り除いても良い。
mを減らせるので速度の改善が期待できる。
しかしこの作業を行ったがために、処理が色々と複雑になってしまった。
1発でACしたものの、実装中は色々とすんなり行かなかった。
実装中にDPに持つ情報を色々変えたので、当初は被りがあるとまずい予定だった。
最終的には被りがあろうと関係ないDPになったので、1～9のMを減らしてもせいぜい定数倍レベルしか改善さないようなこの操作はなくすべきだったかもしれない。

AC後に解法を調べてみると、どの解法も方針は大体同じものの、実装はもっと楽にできたらしい。
特に、DPの値に文字列を持つのはかなり頭良いと思った。
DPで持つ値が文字列と連想配列だとどちらが一般的かと言われれば間違いなく文字列だろうが、なぜか全く思いつかなかった。
DPは一言で言っても、本当に千差万別なのをまた実感した。
もっと慣れていきたい。

新ABCを制覇し、コツコツと旧ABCを埋めている。
ABC124～ABC120の水色レベルの問題全てを解説なしで解けて、今までで一番の成長を感じている。
緑以下からでも色々吸収できてニコニコだったのだが、環境の違いにかなり困惑してしまった。

問題はABC120D Lazy Faith。
ACコード
WAコード

解説PDFと少し解き方は違う。
①神社siに東西それぞれに最も近い寺tj、寺tiに東西それぞれに最も近い神社sjをあらかじめ求める。
②クエリ地点に東西それぞれに最も近い神社2箇所寺2箇所と、既に求めたそれらの神社・寺から東西に行く8通りを見る。
結局やっていることはPDFと同じく8通りを見ているだけである。
書いていて思ったが、最初の神社/寺に近い寺/神社を求める部分は、東西方向それぞれじゃなくてどちらか近い方だけでよかったな。

本題の環境の違いについて。
まず、WAコードの間違えた部分について説明しておく。
①である神社/寺より西側あるいは東側に寺/神社ない場合、INFを与えている。
その判別に使ったのが、lower_boundしたインデックスが0なら西側にはない、配列サイズと同じなら東側にはない、というものである。
この配列サイズのsとtを間違えて逆にしてしまった。
間違いなく間違えているのだが、なんとWAコードでもローカル環境では正しい答えが出ている。
間違えている部分は37,44行目。ifの中身のaとbが逆。
どうして・・・。


AtCoderのコードテストではしっかり間違えている。



色々考えてコードを追ってみると、配列外アクセスをしている可能性があることに気付いた。
そう思って少し調べてみた。

サンプル1だと、sのインデックスの判別がうまく行かず、sのサイズは2なのにs[2]にアクセスしてしまう。
そこでローカル環境とAtCoderのテストコードでs[2]の値を出力して値を確かめた。
ローカル環境: 4294967295(unsigned intの最大値)
コードテスト: 0
結果はこのようになっており、1が並んでいるか0が並んでいるかの違いがあった。
これを見るとなるほど納得が行く。
最終的にminを取っているので、ローカル環境ならINF-xの値が保存されるので、正しい答えが出る可能性は十分ある。
逆にテストコードでは0-xの値が保存されるので、minを取ると明らかに正しい答えが出ない。

正直これをデバッグするのは至難の業だと思う。
しっかり解法を立ててサンプルケースが合っている時点で、実装ミスよりは細かい条件分岐にミスを疑ってしまう。
今回はローカル環境でサンプルケースが合っているにも関わらず、提出結果を見るとサンプルケースが間違っていたので、コードテストを試すことで気づけた。
最初は全く分からず、サンプルケースは間違えているわけないし、提出をミスったのかと全く同じコードで2度提出して2度WAをもらった。
本番ならかなり痛い。

今回はサンプルケースが違っていたので分かったが、運悪くサンプルケースは正解で非公開のテストケースが間違えていたらどうしようもない。
どうしようもないが、こういう事態も起こり得るというのは肝に銘じておく必要がある。
ローカル環境だけではなく、コードテストを試すという選択肢を持っていくのも大事だ。

例えば、ABC122 B ATCoderを考える。
文字列を文字の配列とみなし、「要素が'A','C','G','T'のどれかである」という条件を満たす、連続した要素の数の最大値が答えである。
これを実現するコードを2つ乗せる。

方法1

int main(void) {
  string s;
  cin >> s;
  int cnt = 0, maxi = 0;
  // allrep(c, s) = for(auto &&c : s)
  allrep (c, s) {
    if (c == 'A' || c == 'C' || c == 'G' || c == 'T') ++cnt;
    else {
      maxi = max(maxi, cnt);
      cnt  = 0;
    }
  }
  maxi = max(maxi, cnt); // 忘れやすい
  cout << maxi << endl;
  return 0;
}

方法2

int main(void) {
  string s;
  cin >> s;
  int maxi = 0;
  rep (i, s.size()) {
    int start = i;
    while (i < s.size() && (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T')) ++i;
    maxi = max(maxi, i - start);
  }
  cout << maxi << endl;
  return 0;
}

最初、方法1で書いていたのだが、これはミスしやすい。
最後にmaxを更新するという操作をあまりに忘れる。
仮に配列内の全ての要素が条件に合っていた場合、maxiは0のままである。
この問題では忘れたまま提出し、久々にB問題でWAを出してしまった。
実はこの間違いは、覚えているだけでもこの問題と合わせて少なくとも3回している。
1つは初コンテスト参加のABC139 C Lower、このミスに気づくのに少し時間を取られてしまった。
もう1つは、まさかのこの問題と同日に解いたABC124 D Handstand、実装中のデバッグ段階で気付いたのでこのミスによるWAはなかったが、そういや初参加のコンテストでミスったなぁと思い出した後のBでのミスである。ひどい。

他人のコードを見て、これは良さそう！となったのが方法2。
for文の中で最後のmaxiの更新も済ませられるため、忘れるということがない！
カウント用の変数や、条件に前の要素が絡んでくる場合に前の要素を保存するための変数等、必要な変数のスコープが抑えられるのもGood。
これを機に間違えづらくてスマートな方法2を使っていくように習慣づけたいと思う。

しかしrange-based forの使い所がどんどんなくなっていく。
添字を使わないループなんて、文字列のループの一部か答えの配列の出力くらいしかなかったのだが、数少ない文字列ループの一部がさらに減ってしまった。
好きなんだけどなぁ、range-based for。