初回 -> はじめに
ABC100を解きました。
4完です！
| 問題 | 時間 | アルゴリズム | 実行時間 |
|---|---|---|---|
| A | 3min | 鳩の巣原理 | 10ms |
| B | 5min | - | 10ms |
| C | 3min | 約数 | 12ms |
| D | 28min | 全探索 | 7ms |
まとめ
先にまとめを載せます。これ自体は最後に書いてます。
入力が3つ以上のまとまりの時はタプルを使うと便利です。
vector<tuple<ll, ll, ll>> cake(n) で宣言して、
cake[i] = make_tuple(xin, yin, zin)でタプル化して、
tie(x, y, z) = cake[i] でタプルから変数に戻します。
これ以降は個人的なことですが、、、
キリのいいABC100ということもあり、勉強方法をかえようと思います。
これに伴って、記事の投稿頻度が落ちる見込みです。
解いた問題をしっかり復習したいときに投稿する形にしようと思っています。
これまでは過去のコンテストを解いて、復習としてQiitaに投稿する形をとっていました。
これを毎日やっていました。
ですが、解く問題の難易度が安定しなくてあまり勉強にならない回もありました。
もっと効率よく勉強したいので、自分に合った難易度の問題を解く方式にします。
もし記事を楽しみにされている方がいましたらすみませんが、よろしくお願いいたします。
A - Happy Birthday!
int a, b;
cin >> a >> b;
cout << (a > 8 || b > 8 ? ":(" : "Yay!");
ケーキは16等分されているので、隣り合うケーキをとらない場合は最大で8ピースとれますね。
9ピース以上を取ろうとするとあふれてしまうので条件を満たせません。
この考え方は鳩の巣原理とも呼ばれていますね。
B - Ringo's Favorite Numbers
int d, n;
cin >> d >> n;
n += n / 100;
int ans = pow(100, d) * n;
cout << ans;
求める値は「100 で ちょうど D 回割りきれる正の整数」のうち N 番目の数字です。
これは $N \times\ 100^D$ で求まります。
ですが、N=100 のときは100で割り切れる数がD + 1になってしまうので注意です。
「100 で ちょうど D 回割りきれる正の整数」のうち 100 番目の数字は $101 \times\ 100^D$ になります。
C - *3 or /2
int n, a;
cin >> n;
int ans = 0;
for(int i = 0; i < n; ++i)
{
cin >> a;
while(a % 2 == 0)
{
a /= 2;
ans++;
}
}
cout << ans;
数列に「*3」「/2」の演算を適用する回数を最大化するという問題ですね。
*3は全ての整数に対して演算可能です。
また、/2は2の倍数に対して演算可能です。
*3は回数に上限がなくて、/2には回数に上限があります。
これをもとに適用回数を最大化することを考えると、毎回1回ずつ/2をしていけばいいですね。
つまり、数列内の数値を素因数分解したときの2の個数が答えになります。
D - Patisserie ABC
ll n, m, xin, yin, zin;
cin >> n >> m;
vector<tuple<ll, ll, ll>> cake(n);
for(int i = 0; i < n; ++i)
{
cin >> xin >> yin >> zin;
cake[i] = make_tuple(xin, yin, zin);
}
ll ans = 0;
for(int mask = 0; mask <= 8; mask++)
{
vector<ll> points;
for(int i = 0; i < n; ++i)
{
ll x, y, z;
tie(x, y, z) = cake[i];
ll point = 0;
point += ((mask & 0b001) > 0) ? x : -x;
point += ((mask & 0b010) > 0) ? y : -y;
point += ((mask & 0b100) > 0) ? z : -z;
points.emplace_back(point);
}
sort(points.rbegin(), points.rend());
auto st = points.begin();
auto de = next( points.begin(), m);
ans = max( ans, accumulate(st, de, 0LL) );
}
cout << ans;
x,y,zの3入力に対して、和の絶対値が点数になります。
つまり、和が正値だったらそのまま、負値だったら符号を反転させます。
この符号をまえもって固定することを考えます。
つまり、x,y,zの3入力について正の場合と負の場合で計算します。
これは $2^3=8$ 通りですね。
コードではbit演算で書いていますが、x,y,zについて3重のfor文を書いても同じです。
ネストを深くしたくなかったのでbit演算で書きました。
こうすると、絶対値を考えなくても各ケーキの点数がわかります。
出た点数をソートして、大きい順にM個とったときの合計点を求めれば最大点数がわかります。
入力をタプルで受けています。
入力が3つ以上のまとまりの時はタプルを使うと便利です。
vector<tuple<ll, ll, ll>> cake(n) で宣言して、
cake[i] = make_tuple(xin, yin, zin)でタプル化して、
tie(x, y, z) = cake[i] でタプルから変数に戻します。
以上です。ありがとうございました。