2020-04-04

AtCoder Grand Contest 034 B - ABC やらかしコード

AGC Resolved 親の仇やらかし

問題はこちら。問題の紹介、解説は全くしない。

AGCなのにABCという謎な問題。

以前この問題を解いて最後の一つのWAが取れず、ずっと考えていて今回一からコードを書き直すことにした。その結果依然としてWAが取れず悩んでいた。そのWAが取れたのでその経過をここに記す。

オーバーフローの可能性を考えていなかったのがまず失策。最大の場合を考える。つまりABCABCABC・・・・・ABCABの合計200000文字の文字列が入力として与えられた場合である。その場合の答えは66666 * (66666 + 1) / 2である。

この計算結果は2222211111

一方でINTの最大値は2147483647

である。

ギリギリオーバーフロー。アルゴリズム的には問題なく、答えの型をintからlong long に変更。結果AC。

一応書いたコードも載せておく。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int (i)=0;(i)<(n);(i)++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
int main() {
  string s;
  cin >> s;
  int n = s.size();
  ll res = 0;
  int start = -1;
  vector<string> ans;
  for(int i=0;i<n;i++) {
    if(s[i] == 'A') {
      if(start == -1) start = i;
      else continue;
    }
    else if(s[i] == 'B') {
      if(start == -1) continue;
      else if(i == n-1) {
        ans.emplace_back(s.substr(start, i-start));
        start = -1;
      }
      else if(s[i+1] == 'C') i++;
      else {
        ans.emplace_back(s.substr(start, i-start));
        start = -1;
      }
    }
    else if(s[i] == 'C') {
      if(start == -1) continue;
      else {
        ans.emplace_back(s.substr(start, i-start));
        start = -1;
      }
    }
  }
  if(start != -1) {
    ans.emplace_back(s.substr(start, n-start));
    start = -1;
  }
  for(int i=0;i<ans.size();i++) {
    string ss = ans[i];
    int bcNum = 0;
    for(auto it=ss.rbegin();it!=ss.rend();it++) {
      if(*it == 'C') {
        bcNum++;
        it++;
      }
      else if(*it == 'A') res += bcNum;
    }
  }

  cout << res << endl;
  return 0;
}

感想

また親の仇が増えた。オーバーフローお前もだ。

2020-04-04

自分の書いたコードが正直ゴミにしか見えない件について。

競技プログラミングで書いたコードは往々にして後から読むことを考えていない。それはそのコンテストでしか書かないコードであるし、そしてデバッグするとしても100行もないコードなのでデバッグするのも容易だろうと勝手に思っている。そういう理由で僕は可読性やらそんなことを競技プログラミングの問題を解く際には全く考えていない。

だがふと今日自分が書いた競技プログラミング用のコードを見返してみた。そのコードはほとんど想定通りの動作をするのだが、一つのテストケースだけに通らないようなコードだ。「どこが間違っているのか」「どんなテストケースに引っかかっているのか」を検証するのにいい勉強になると思ったのだ。

結論として、自分が何を思ってこのコードを書いたのか全くわからなかった。というか後から読む人を殺すかの如く可読性の低いコードがそこにはあった。

if文は5つくらい重なっているし、さらにはその中の条件文には&&で繋いだものがあるし、とにかく酷いものである。コードリーディングをしていて体力が削られることこの上ない。

まだデバッグをするタイミングがそのコードを書いた五分後とかならこのコードもある程度理解できただろう。しかし、今は大体そのコードを書いてから1ヶ月近くがたっている。問題の設定を覚えていたとしても自分が何を思ってそのコードを書いたかなんて覚えているはずがないだろう。

そうしてデバッグ作業に疲れた僕は今こうしてその反省ブログを書いているわけだ。何と悲しいことで。

そんなことはどうでも良くて将来の自分のために言っておくことがある。

競技プログラミング用のコードだからと言って、可読性の低い即席コードを書くなということだ。

コンテストの時とかならまだ別である。その時は時間制限があるし、何よりも優先すべきは問題に正解することだ。

しかし、それ以外の場面で同じようなコードをずっと書いていると「あとでどこで間違っていたのか」が本当にわからなくなる。全部一から書き直して予想通りに動いたとしても、前回書いたコードのどこが間違っていたのがはわからない。正解はわかるが間違いが間違っている理由が理解できないまま先に進むということだ。

間違いは往々にして繰り返す。その時にいつも「何で自分の解放は間違っていたんだろうか」と考えて時間を無駄にすることになる。そのような時間の無駄をなくすためにも、そしてデバッグのスピードを上げるためにも、可読性の高いコードを書くことは必要なことだと思う。

競技プログラミングもそれ以外のプログラミングと同じようにデバッグが非常に大切なので可読性の高いコードを書いた方が自分のためになるよということが言いたかった。

以上。

(デバッグ予定のコードは全て葬り去り、一から書き直すことを決心しました。)

2020-04-03

AtCoder Beginner Contest 142 E - Get Everythingを解いた感想

ABC bitDP

実装にだいぶ時間がかかった。けどできたのでよし。実行時間800msecとかなりアルゴリズム的には良くないコードを書いてしまった。けどそれしか解法が思いつかんかったから仕方ない。

問題はこちらです。

atcoder.jp

宝箱が最大12個与えられる。そしてその宝箱を開ける鍵が最大1000個与えられる。鍵について使うコストと開けられる宝箱の番号が与えられる。最小で幾らのコストで宝箱を全て開けることができるかという問題。

解法

DPするんだろうなと思いつつ、結果DP。開ける宝箱は高々12個しかないので全探索できる(2^12通り）。そして左から何番目までの鍵を使えるかで1000通り。合計5000000回計算すれば終わる。

詳しい内容はコードを見て。

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

int main() {
  int n;
  cin >> n;
  int m;
  cin >> m;
  vector<int> cost(m);
  bitset<12> initial("000000000000");
  vector<bitset<12>> key(m, initial);
  for(int i=0;i<m;i++) {
    int a, b;
    cin >> a >> b;
    for(int j=0;j<b;j++) {
      int c;
      cin >> c;
      c--;
      key[i].set(c);
    }
    cost[i] = a;
  }
  const int lim = pow(2, n);
  vector<vector<int>> dp(lim, vector<int>(m+1));
  for(int i=0;i<lim;i++) {
    for(int j=0;j<m+1;j++) {
      if(i == 0) dp[i][j] = 0;
      else if(j == 0) dp[i][j] = -1;
      else {
        bitset<12> bit(i);
        bitset<12> amp = (bit & key[j-1]);
        if(amp.none()) {
          dp[i][j] = dp[i][j-1];
          continue;
        }
        int idx = 0;
        for(int k=0;k<12;k++) {
          if(bit.test(k) && !key[j-1].test(k)) {
            idx += pow(2, k);
          }
        }
        if(dp[idx][j-1] == -1) {
          dp[i][j] = -1;
          continue;
        }
        int tmp = dp[i][j-1];
        if(tmp == -1) tmp = INT_MAX;
        dp[i][j] = min(cost[j-1] + dp[idx][j-1], tmp);
      }
    }
  }
  cout << dp[lim-1][m] << endl;
  return 0;
}