Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

ABC100 解説

6/16に行われた記念すべき100回目のABC。 問題の内容もAtCoder社の方々が出てきてお祭り騒ぎ1って感じでしたね、楽しかったです。 問題としては、前回ほどの難易度ではなかったものの一部クセがある問題だった、という印象ですかね。

それでは、振り返っていきましょう。

※今回の記事は数式が多い一方で、はてなブログMarkdown記法ではtex記法がバグって使えないため一部大変見づらいです。 個人的にもこちらのHackMD版の方を推奨します。

目次

A - Happy Birthday! (お誕生日おめでとう!)

問題リンク

概要

中心から放射状に16等分された円形のケーキがある。 16個のピースから隣接した要素を選ばないように2人でそれぞれM個、N個取ることが可能か判定せよ。

ちなみに可能な場合は「Yay!」、不可能な場合は「:(」と出力するように。

解説

まず2人のうち一方でも9個以上のピースを取ろうとすると、2つの隣接した要素を選んでしまうのはお分かりだろう。俗に言う「鳩の巣理論」というやつ。

したがってM,N ≦ 8が必要条件となるのだが、実はこれが必要十分条件となる。

というのも、ケーキのピースを時計回りにA,B,A,B ...と割り振っていき、1人目がAからM個、2人目がBからN個取れば条件は自動的に達成されるからだ。

回答例

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 (りんごさんの好きな数)

問題リンク

概要

100で丁度D回割り切れる数で、N番目に小さいものを出力せよ。

(0 ≦ D ≦ 2, 1 ≦ N ≦ 100)

解説?

例えばD=1の場合、当てはまる数は

100, 200, 300, 400, ...

といった具合になる。 ここからもお察しの通り、Nを100D倍したやつがまんま答えになる。

回答例?

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にしては簡単かな? とりあえず提出しましょ。

f:id:misteer:20180616235126j:plain

はい、という訳でこの手の回答を提出した方々はまんまと双子くんの罠にハメられたのでした。無論僕もハメられた1人。

コーナーケース

では何がいけなかったのか? 答えを言ってしまうと、N=100の場合がコーナーケース。

例えばD=1, N=100では上のコードだと10000を出力するが、条件は「100で丁度D回割り切れる」ことなのでこれは条件を満たさない(2回割り切れるため)。

という訳で、N=100の場合だけNをインクリメントする必要があるのでした (そこさえ直せば通るので、回答例は省略)。

いや〜、いい問題作るね。これに引っかかったか否かで順位が結構変わるので、ある意味で今大会の鍵を握る問題。

C - *3 or /2 (×3 or ÷2)

問題リンク

概要

数列a_1, a_2, ... , a_Nが与えられる、これらの全要素に対して、

  • 2で割る
  • 3を掛ける

のいずれかを行う操作を考える(ただし前者は最低でも1要素に対して行い、操作後の値は整数でなければならない)。

この操作が最大で何回できるかを求めよ。

解説

まず、「3を掛ける」という操作は任意の要素に対して何度でも行える。 したがって操作が行えなくなるのは「2で割る」という操作が全要素に対して行えなくなる、つまり全要素が奇数となる場合である。

これを極力先延ばしにしたいんだから、1回の操作で2要素以上を2で割るのは明らかに無駄(2ターンに渡って1要素ずつ2で割った方が長持ちするため)。

従って答えは、各要素の2で割れる回数の総和ということになる。 これはa_iが偶数である間a_iを2で割り続ければ簡単に求まる。

回答例

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洋菓子店)

問題リンク

概要2

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以上ならどうなるかというと、答えは以下のような貪欲法3で簡単に求まる。

  • 各iについて、data[i] = x[i] + y[i] + z[i]を求める。
  • dataを降順にソートする
  • dataを上からM個足していったのが答え。

しかし問題は負の値が含まれている場合。もう少し深く考えてみる必要がある。

負が混ざる

ここでSx = | 選んだケーキのx[i]の総和 |と定義する(Sy,Szも同様)。

例えば最適の選び方においてSx < 0 < Sy, Szの場合、S = - Sx + Sy + Szで答えが求まる。

このとき、上のアルゴリズムdata[i] = - x[i] + y[i] + z[i]のように書き換えてみる。 すると、最適にM個選んだ場合のSは選んだ要素のdataの総和で求められる。

ではどのようにM個選べばいいかといえば、先と同様の貪欲法でいい。 したがって、dataの計算式を上のように書き換えただけでそのままアルゴリズムを適用すれば、答えが求まるわけである。

この発想こそが本問の肝で、x, y, zの符号を全探索して上のアルゴリズムを適用すれば、実は答えが求まるのだ4

符号の全探索は3bitのbit全探索5を使えば比較的楽に実装できる。

回答例

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
        // 例えばbit=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全探索とは気づかないし、面白い問題だと思う。

f:id:misteer:20180617001155p:plain

一方で私の戦果は上の通り全体で36位。私にしてはとても良くできた方。 しかしUnratedなのが残念。来週は3週間振りのARCなので思う存分暴れてやりたいところ。


  1. ジャッジもお祭り騒ぎでしたね…(AtCoder社の方々お疲れ様でした)。

  2. 説明の便宜上、本文とは大きく異なる部分があります(でも問題の内容は同じです)。

  3. 後先のことを何も考えず、常に最善の状態を取るように行動するような手法のこと。

  4. ここで「Sx < 0と仮定しても上の方法じゃSx ≧ 0になる場合もあるのでは?」と思った方はよく考えてらっしゃる。証明は私には難しいので省くが、その場合でも-S_x ≦ 0となることによってその振り分けが最適でないことが包意される(多分)。

  5. 値を2進数表記したときの、各桁の値を状態とみなすことで全パターンを調べる技法。上の問題では(0, 1) ↔ (+, -)と対応付けることで、(+, -)の全パターンを調べている。