初回 -> はじめに
ABC134を解きました。
4完です！
E問題は解説を見て解きました。
| 問題 | 時間 | アルゴリズム | 実行時間 |
|---|---|---|---|
| A | 1min | - | 8ms |
| B | 3min | - | 8ms |
| C | 15min | - | 41ms |
| D | 35min | xor | 30ms |
| E | - | 最長増加部分列 | 34ms |
A - Dodecagon
int r;
cin >> r;
cout << 3 * r * r;
問題文に数式が載っているので、当てはめると答えが出ます。
問題名が面白いですね。ドデカゴン。ちなみに12角形の正式名称です笑。
B - Golden Apple
int n, d;
cin >> n >> d;
cout << (n - 1) / (2 * d + 1) + 1;
ひとりの見れる範囲が[i−D, i+D]なので、ひとりあたり2D + 1の範囲を見れますね。
そのため、範囲Nを監視するのに必要な人は、Nを2D+1で割って切り上げたものだとわかります。
double型にキャストしてceil(N / (2D+1))で計算できます。
int型のままでN / Dの切り上げをすることもできて、今回はそれを使いました。
( (N - 1) / D ) + 1 の式です。
C - Exception Handling
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i)
{
cin >> a[i];
}
int max1 = 0;
int max2 = 1;
for(int i = 1; i < n; ++i)
{
if (a[max1] < a[i])
{
max2 = max1;
max1 = i;
}
else if (a[max2] < a[i])
{
max2 = i;
}
}
for(int i = 0; i < n; ++i)
{
cout << (i == max1 ? a[max2] : a[max1]) << endl;
}
そのままするとO(N^2)となってTLEします。
解き方としては、数列の中で一番大きいものと二番目に大きいものを覚えておきます。
・一番大きい要素の時は二番目に大きいものを出力
・それ以外は一番大きいものを出力
とすると答えになります。
同じ要素が二つ以上あるときにうまくいかない恐れがあったので、インデックスで管理しています。
と書きましたが、今思い返すとインデックス管理は不要だったかもしれません。（複雑にしただけかもです）
D - Preparing Boxes
int n;
cin >> n;
vector<int> a(n + 1, 0);
for(int i = 1; i <= n; ++i)
{
cin >> a[i];
}
// 1は考えなくていい
// 半分以降は決まり：倍数が1つだけ
// 前半の半分について考える
bitset<200000 + 1> ball;
for(int i = n / 2 + 1; i <= n; ++i)
{
ball[i] = a[i];
}
for(int i = n / 2; i >= 1; --i)
{
int next_b = a[i];
for(int j = i * 2; j <= n; j += i)
{
next_b ^= ball[j];
}
ball[i] = next_b;
}
cout << ball.count() << endl;
for(int i = 1; i <= n; ++i)
{
if (ball[i]) cout << i << " ";
}
各要素に対して2で割った余りを求めるとあるので、2進数が思い浮かびます。
bitmaskやxorを使います。
「いいボールの入れ方」のうち、i番目の箱に関係するのはi, 2*i, 3*i, ...です。
この時、入力サイズNに対して、N/2 ~ N番目の箱に関係するのはi番目の入力値だけですね。
というのも、2*iがNより大きくなってしまうためです。
つまり、N/2 ~ N番目については入力値がそのまま「いいボールの入れ方」になります。
また、どの箱にもi番目の箱は自由に設定できます。
2*i + 3*i + 4*i + ... の値がどうなっていようと、i番目の箱にボールを入れるか入れないかで結果を操作できます。
このようにどの箱も結果を自由に操作できるので、必ず「いいボールの入れ方」は存在します。
つまり出力結果に-1はありません。
また、試してみると、入力値をa、箱をbとして
b[i] = a[i] ^ b[2*i] ^ b[3*i] ^ ...
であることが分かります。
この形になっているため、bは上から更新する必要があります。
ここまでわかれば実装です。
実装時は境界値に注意です。
E - Sequence Decomposing
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i)
{
cin >> a[i];
}
reverse(a.begin(), a.end());
vector<int> dp(n, INF);
for(int i = 0; i < n; ++i)
{
*upper_bound(dp.begin(), dp.end(), a[i]) = a[i];
}
cout << lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
最長増加部分列（LIS）です。
今回の問題は最長現象部分列の長さが答えになる問題でした。
数列をreverseさせればLISに帰着できます。
LISの発想はあったのに解けなくて悔しいです。次は解きたい。
プログラムは蟻本にあったものをvectorになおして使いました。
以上です。ありがとうございました。