C++
AtCoder
競技プログラミング

result.png

  • バチャバチャ
  • 「列」と「経路」の解説書けてないけど1か月以内に書きます。はい。

ABC031 「数列ゲーム

考察

  • 高橋君が適当な場所に点を打ったとき、青木君が点を打つ場所は$N-1$通りある。
  • $N-1$通りの中で青木君が選ぶのは、青木君の得点が最大になるような場所である。
  • よって、高橋君が点を打ったときの青木君の得点は一意に決まる。それと同時に高橋君の得点も確定できる。

解法

  1. 高橋君が$i$に点を打つ。
  2. そのとき青木君が点を打つ$N-1$通りを全て試す。そして、青木君の得点が最大となる場合の両者の得点を記録する。
  3. 高橋君の得点は、2で記録された高橋君の得点の内の最大値である。

コード

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

int N;
int a[100];

int main() {
   // 入力
   cin >> N;
   for (int i = 0; i < N; i++) cin >> a[i];

   int ans = -1e8;
   for (int i = 0; i < N; i++) { // 高橋君が点を打つ
      int maxA = -1e8, maxT = -1e8;
      for (int j = 0; j < N; j++) { // 青木君が点を打つ
         if (i == j) continue;

         // 2つの丸とその間にある配列を取り出す
         vector<int> v;
         for (int k = min(i, j); k <= max(i, j); k++) {
            v.push_back(a[k]);
         }

         // 青木君と高橋君の得点をそれぞれ求める
         int size = v.size(), sumA = 0, sumT = 0;
         for (int k = 0; k < size; k++) {
            if (k % 2 == 0) {
               sumT += v[k];
            } else {
               sumA += v[k];
            }
         }

         // 青木君の点数に応じて、青木君と高橋君の得点を更新
         if (sumA > maxA) {
            maxA = sumA;
            maxT = sumT;
         }
      }
      // 答えを更新
      ans = max(ans, maxT);
   }

   cout << ans << endl;

   return 0;
}

感想

  • 配列の領域外参照、使う配列をミスる、添え字をミスる、をやらかして無限に時間が溶けたため解けなかった。
  • なんかちょっと複雑な問題だなーと思った。解くに、青木君の得点に応じて高橋君の得点が決まるところ。
  • でも、ちゃんと考えればそんなに難しくない問題なのでACしたかった。。。

ABC032 「

部分点

解法

  • 愚直に試す
  • $0 \leq K \leq 10^9$なので、ループ中にかけ算でオーバーフローが起こることはない。
  • ただ、数列中に$0$が含まれる場合は注意する必要がある。途中でオーバーフローが起きたら$0$に到達する前にループを抜けてしまうため、うまく判定できない場合がある。なので、$0$が含まれるかどうかは最初に判定してやる。

コード

満点

  • しゃくとり法ちょっとわかんないので、他のしゃくとり法の問題が出てきたときに再度考える。

ABC033 「数式の書き換え

解法

  • a*b*c*, ..., *zみたいな掛け算を1つの塊としてみる。
  • 塊が途切れた時、つまり+が来た時に掛け算の塊の中に$0$があるかどうかを判定する。
  • 塊の中に$0$があるならば掛け算の塊は$0$になる。$0$が無いとき、掛け算の塊の1つ$0$に置き換えればその塊は$0$になる。
  • こんな感じの操作を繰り返してく

実装

コード

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

int main() {
   string s;
   cin >> s;

   int cnt = 0, n = s.size();
   bool zero = false;
   for (int i = 0; i < n; i++) {
      if (s[i] == '0') zero = true;
      if (s[i] == '+') {
         if (!zero) cnt++; // 0がなければカウントをインクリメント
         zero = false; // '+'が来たら無条件でzeroを初期化する
      }
   }

   // !zeroは、最後の区間に0がないなら1プラスするという意味
   cout << cnt + !zero << endl;

   return 0;
}
  • コンテスト中はこんな感じにキューを使って解いた。
  • でも、キューを使うのは明らかに無駄なので、リファクタリングした。
  • 上位陣の中には、式の最後に+を付け加えて処理しやすくしていた人もいたので、この方法使えるなーって思った。このコードがこれ

感想

  • コンテスト中はキューを使うという奇行に出てしまった。キューは数式扱うのに便利だった気がしたのでキューを使ったのだが。。。
  • 式の最後に+を付け加えるのは頭いいなーって思った。

ABC034 「経路

  • 著者が数弱なため、まともな内容が書けません。

ABC035 「オセロ

解法

  • 愚直にやっていては間に合わないのでいもす法を使う。
  • いもす法は区間をすべて書き換えずに、左端と右端+1だけ書き換え、最後に累積和を取る。

コード

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

using ll = long long;

int N, Q;
ll a[222222];

int main() {
   cin >> N >> Q;
   for (int i = 0; i < Q; i++) {
      int l, r;
      cin >> l >> r;
      l--, r--;
      a[l]++, a[r+1]--;
   }

   for (int i = 1; i < N; i++) {
      a[i] += a[i-1];
   }

   // 偶数なら0、奇数なら1を出力
   for (int i = 0; i < N; i++) {
      if (a[i]%2==0) {
         cout << 0;
      } else {
         cout << 1;
      }
   }
   cout << endl;

   return 0;
}