AtCoder Beginner Contest 100 LOG === 6/16日に行われた記念すべき100回目のABC。 問題の内容もAtCoder社の方々が出てきてお祭り騒ぎ[^fes]って感じでしたね、楽しかったです。 問題としては、前回ほどの難易度ではなかったものの一部クセがある問題だった、という印象ですかね。 [^fes]: ジャッジもお祭り騒ぎでしたね...(AtCoder社の方々お疲れ様でした) それでは、振り返っていきましょう。 A - Happy Birthday! (お誕生日おめでとう!) === [問題リンク](https://beta.atcoder.jp/contests/abc100/tasks/abc100_a) ## 概要 中心から放射状に$16$等分された円形のケーキがある。 $16$個のピースから**隣接した要素を選ばないように**2人でそれぞれ$M$個、$N$個取ることが可能か判定せよ。 ちなみに可能な場合は「**Yay!**」、不可能な場合は「**:(**」と出力するように。 ## 解説 まず2人のうち一方でも$9$個以上のピースを取ろうとすると、2つの隣接した要素を選んでしまうのはお分かりだろう。俗に言う「鳩の巣理論」というやつ。 したがって$M,N \leq 8$が必要条件となるのだが、実はこれが**必要十分条件**となる。 というのも、ケーキのピースを時計回りに$A,B,A,B \dots$と割り振っていき、1人目が$A$から$M$個、2人目が$B$から$N$個取れば条件は自動的に達成されるからだ。 ## 回答例 ```cpp= int main() { int A, B; cin >> A >> B; if (A <= 8 && B <= 8) { cout << "Yay!" << endl; } else { cout << ":(" << endl; } return 0; } ``` A問題にしては少しひねりがあるが、落ち着けばなんとかなる。 出力にも要注意。この形式はさすがに初めて見た。FA対策? あと問題内容読んで思ったんだが、今日は双子くんの誕生日なのかな? だとしたらおめでとうございます。 B - Ringo's Favorite Numbers (りんごさんの好きな数) === [問題リンク](https://beta.atcoder.jp/contests/abc100/tasks/abc100_b) ## 概要 $100$で**丁度**$D$回割り切れる数で、$N$番目に小さいものを出力せよ。 ($0 \leq D \leq 2, 1 \leq N \leq 100$) ## 解説? 例えば$D=1$の場合、当てはまる数は $100, 200, 300, 400, \dots$ といった具合になる。 ここからもお察しの通り、$N$を$100^D$倍したやつがまんま答えになる。 ## 回答例? ```cpp= int main() { int D, N; cin >> D >> N; // hund = 100^D int hund = 1; REP(i, D) { hund *= 100; } cout << N * hund << endl; return 0; } ``` Bにしては簡単かな? とりあえず提出しましょ。 ![](https://i.imgur.com/Lvwc5Jn.jpg) はい、という訳でこの手の回答を提出した方々はまんまと双子くんの罠にハメられたのでした[^trap]。 [^trap]: 本人の解説を見る限り、別に引っ掛けるつもりはなかったのかもしれない。もしそうならごめんなさい。 ## コーナーケース では何がいけなかったのか? 答えを言ってしまうと、「$N=100$」の場合がコーナーケース。 例えば$D=1, N=100$では上のコードだと``10000``を出力するが、条件は「$100$で**丁度**$D$回割り切れる」ことなのでこれは条件を満たさない($2$回割り切れるため)。 という訳で、$N=100$の場合だけ$N$をインクリメントする必要があるのでした (そこさえ直せば通るので、回答例は省略)。 ここでWA吐いたか否かで順位が結構変わるので、ある意味で今大会の鍵を握る問題。 C - *3 or /2 (×3 or ÷2) === [問題リンク](https://beta.atcoder.jp/contests/abc100/tasks/abc100_c) ## 概要 数列$a_1, a_2, \dots, a_N$が与えられる、これらの全要素に対して、 * 2で割る * 3を掛ける のいずれかを行う操作を考える(ただし前者は**最低でも1要素に対して**行い、操作後の値は整数でなければならない)。 この操作が最大で何回できるかを求めよ。 ## 解説 まず、「3を掛ける」という操作は任意の要素に対して何度でも行える。 したがって操作が行えなくなるのは「2で割る」という操作が全要素に対して行えなくなる、つまり全要素が奇数となる場合である。 これを極力先延ばしにしたいんだから、一回の操作で2要素以上を2で割るのは明らかに無駄(2ターンに渡って1要素ずつ2で割った方が長持ちするため)。 従って答えは、**各要素の2で割れる回数の総和**ということになる。 これは$a_i$が偶数である間$a_i$を2で割り続ければ簡単に求まる。 ## 回答例 ```cpp= int main() { int N; cin >> N; int ans = 0; REP(i, N) { ll a; cin >> a; // aが偶数の間2で割り続ける while (a % 2 == 0) { ans++; a /= 2; } } cout << ans << endl; return 0; } ``` ``a``は配列に代入してもいいけど、どのみち使わないので上のコードではローカル変数にしている。 D - Patisserie ABC (ABC洋菓子店) === [問題リンク](https://beta.atcoder.jp/contests/abc100/tasks/abc100_d) ## 概要[^statement] [^statement]: 説明の便宜上、本文とは大きく異なる部分があります(でも問題の内容は同じです)。 ABC洋菓子店では$N$個のケーキが1個ずつ売られており、各ケーキのデータは$x_i, y_i, z_i$の3整数(負も含む)で与えられる。 この中からケーキを$M$個選び、$S = |x_i$の総和$|+|y_i$の総和$|+|z_i$の総和$|$を定義する。 $S$の最大値を求めよ。 ## 解説 ### 全部正なら 例えば$x_i, y_i, z_i$が全て0以上ならどうなるかというと、答えは以下のような**貪欲法**[^greedy]で簡単に求まる。 * 各$i$について、``data[i] = x[i] + y[i] + z[i]``を求める。 * ``data``を降順にソートする * ``data``を上から$M$個足していったのが答え。 [^greedy]: 後先のことを何も考えず、常に最善の状態を取るように行動するような手法のこと。 しかし問題は負の値が含まれている場合。もう少し深く考えてみる必要がある。 ### 負が混ざる ここで$S_x = |x_i$の総和$|$と定義する($S_y,S_z$も同様)。 例えば最適の選び方において$S_x < 0 < S_y, S_z$の場合、$S = -S_x + S_y + S_z$で答えが求まる。 このとき、上のアルゴリズムを``data[i] = -x[i] + y[i] + z[i]``のように書き換えてみる。 すると、最適に$M$個選んだ場合の$S$は選んだ要素の``data``の総和で求められる。 ではどのように$M$個選べばいいかといえば、先と同様の貪欲法でいいのはお分かりだろう。 したがって、``data``の計算式を上のように書き換えただけでそのままアルゴリズムを適用すれば、答えが求まるわけである。 この発想こそが本問の肝で、**$x, y, z$の符号を全探索**して上のアルゴリズムを適用すれば、実は答えが求まるのだ[^sign]。 [^sign]: ここで「$S_x < 0$と仮定しても上の方法じゃ$S_x \geq 0$になる場合もあるのでは?」と思った方はよく考えてらっしゃる。 証明は私には難しいので省くが、その場合でも$- S_x \leq 0$となることによってその振り分けが最適でないことが包意される(多分)。 符号の全探索は3bitの**bit全探索**[^bitsearch]を使えば比較的楽に実装できる。 [^bitsearch]: 値を2進数表記したときの、各桁の値を状態とみなすことで全パターンを調べる技法。上の問題では$(0, 1) \leftrightarrow (+, -)$と対応付けることで、$(+, -)$の全パターンを調べている。 ## 回答例 ```cpp= int main() { ll N, M; cin >> N >> M; V<tuple<ll, ll, ll>> cake(N); // tupleは2つ以上の値を持つPairみたいなもの REP(i, N) { ll x, y, z; cin >> x >> y >> z; cake[i] = make_tuple(x, y, z); } ll ans = 0; // 最悪のケースでもS>=0なのでこの初期化でよい REP(pat, 8) { // patが+,-の状態を管理するbit // 例えばpat=101なら // data[i] = - x[i] + y[i] - z[i] V<ll> data(N); REP(i, N) { ll x[3]; tie(x[0], x[1], x[2]) = cake[i]; // cake[i]の値を取り出し REP(j, 3) { if (pat & (1 << j)) { // ここでbitが1の位置に当たる値の符号を反転 x[j] = -x[j]; } } data[i] = x[0] + x[1] + x[2]; } GSORT(data); // 降順ソートで上から貪欲に選んでいく ll val = 0; REP(i, M) { val += data[i]; } ans = max(ans, val); } cout << ans << endl; return 0; } ``` bit全探索の部分は慣れてないと実装しにくいし読みづらいので、実装経験がない方は今のうちに練習しておくことをオススメする。 400点は妥当かな、という印象はあるが証明が難しい。 私は証明していないが直感で正しいと信じて提出したため、数分に及ぶWJの間ずっとソワソワしていた。通った瞬間の安堵感たるや。 感想 === 冒頭でクセがあると言っていたのはA,B問題のことで、どちらも点数の割には難しかったような。代わりにC問題が簡単めだったので打ち消しかな。 Dは発想自体は浮かぶのだが証明が難しく、最後の一歩をためらいそう。一目ではbit全探索とは気づかないし、面白い問題だと思う。 ![](https://i.imgur.com/E1y6Rz3.png) 一方で私の戦果は上の通り全体で36位。私にしてはとても良くできた方。 しかしUnratedなのが残念。来週は3週間振りのARCなので思う存分暴れてやりたいところ。