- バチャバチャ
- 「列」と「経路」の解説書けてないけど1か月以内に書きます。はい。
ABC031 「数列ゲーム」
考察
- 高橋君が適当な場所に点を打ったとき、青木君が点を打つ場所は$N-1$通りある。
- $N-1$通りの中で青木君が選ぶのは、青木君の得点が最大になるような場所である。
- よって、高橋君が点を打ったときの青木君の得点は一意に決まる。それと同時に高橋君の得点も確定できる。
解法
- 高橋君が$i$に点を打つ。
- そのとき青木君が点を打つ$N-1$通りを全て試す。そして、青木君の得点が最大となる場合の両者の得点を記録する。
- 高橋君の得点は、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;
}