Mister雑記

競プロやります。

ABC099 解説

6/10に行われたABC099。Unratedですがもちろん参加しました。 が、思わぬところで躓いてしまい、なんとも言えない感じに。 何はともあれ、振り返っていきましょう。

A - ABD

概要

Nが999以下なら"ABC"、1000以上なら"ABD"と出力せよ。

解説

上を実装するだけ。Aの中でも特に簡単。

int main() {
    int N;
    cin >> N;
    if (N <= 999) {
        cout << "ABC" << endl;
    } else {
        cout << "ABD" << endl;
    }
    return 0;
}

個人的に設定が好き。

(最初、誤読して"ABDXXX"って出力してたのは内緒)

B - Stone Monument

概要

高さが 1, 1+2, 1+3, \dotsの柱が一直線に並んでいるところに雪が均等に降った。 ある2本の隣り合う柱について、雪より上の部分の高さはそれぞれ a, b(a \lt b)だったという。

積もった雪の高さを求めよ。

解説

低い方から N本目と N+1本目の柱の高さの差は、定義から N+1となる。 従って隣り合う柱の内、高い方の柱は b-a番目と分かる(以降 d=b-aとおく)。

よって高い方の柱の高さは 1+2+...+d=\dfrac{d(d+1)}{2}で与えられるので、 これから bを引くことで雪の厚さが求まる。

int main() {
    int a, b;
    cin >> a >> b;
    int d = b - a;
    cout << d * (d + 1) / 2 - b << endl;
    return 0;
}

B問題としてはなかなかの良問では。とてもシンプルで好き。

詳しくは分からないが、中学受験で出てそうな印象。

C - Strange Bank

概要

  •  1
  •  6, 6^2, 6^3, \dots
  •  9, 9^2, 9^3, \dots

から和が Nになるよういくつか数字を選ぶ(重複可)とき、 選ぶ数字の個数の最小値を求めよ。

解説

頭が硬いので、メモ化再帰でゴリ押した。

具体的には、上のリストで選択できる要素のリストを作り、再帰関数で全パターン(各要素をいくつ選べるか)を試すというもの。ただしそのままだと余裕でTLEなので、 dp[i][m] = i番目の要素時点で残りがmのとき、最適に選んだ場合の最小個数という配列を用意してメモしていった。

V<ll> money;
// 選択できる要素のリスト
V<V<ll>> dp(100, V<ll>(100001, -1));
// メモ用配列
// dp[i][m] = i番目の要素時点で残りがmのとき、最適に選んだ場合の最小個数

int dfs(int itr, int N) {
    if (itr == SIZE(money)) {
        // 6, 9から始まる数列は全部使い果たしたので、残りは1だけ
        return N;
    }

    if (dp[itr][N] >= 0) {
        // 探索済みならその値を返して時間短縮
        return dp[itr][N];
    }

    int ret = INF;
    REP(i, 100) {
        // money[itr]をi回選んだ場合の最適解を求める
        if (money[itr] * i <= N) {
            ret = min(ret, dfs(itr + 1, N - money[itr] * i) + i);
        } else {
            break;
        }
    }
    dp[itr][N] = ret;
    // 計算結果を忘れずにメモ
    return ret;
}


int main() {
    int N;
    cin >> N;

    // 6の方から選べる値を追加していく
    int six = 6;
    while (six <= 100000) {
        money.pb(six);
        six *= 6;
    }

    // 9の方も同様
    int nine = 9;
    while (nine <= 100000) {
        money.pb(nine);
        nine *= 9;
    }

    // 降順ソート
    GSORT(money);

    cout << dfs(0, N) << endl;
    return 0;
}

上の解法が想定解なら、優に400点はあるし下のD問題より難しい。 解説が楽しみだ。

editorial解法

editorialの解法もまぁ全探索なのだが、私の解法よりは遥かにスマートだったので整理しておく。

まず、使える値に9のリストがない場合を考えると、使える値は

  •  1, 6, 6^2, 6^3, \dots

となる。実はこの場合、最適な選び方というのは即座に分かる。 というのも、 Nを6進数表記したときの下から i桁目の値が、 6^{i - 1}の使用回数になるわけだ。厳密な証明は難しいが、1つの値を6回選ぶよりその上の値を1回選ぶ方が効率的なことからも分かるだろう。

これと同様のことが9のリストでもできるのだが、2つのリストが混合した状態では直接適用することはできない。

ならどうするか? Nを2つに分割すればいい。 つまり、使える値のリストを

  •  1, 6, 6^2, 6^3, \dots
  •  1, 9, 9^2, 9^3, \dots

と分離して、 Nの一部を上のリスト、残りを下のリストで作ろうということである。 この発想で書いたコードが以下の通り。

int main() {
    int N;
    cin >> N;
    int ans = INF;
    REP(p, N + 1) {
        // pを6のリスト、N-pを9のリストで作る

        int six = p, nine = N - p;
        int ope = 0;
        while (six > 0) {
            ope += six % 6;
            six /= 6;
        }
        while (nine > 0) {
            ope += nine % 9;
            nine /= 9;
        }
        ans = min(ans, ope);
    }
    cout << ans << endl;
    return 0;
}

実装してみたら3分もかからなくて驚いた。めちゃくちゃ実装軽いやん...。

D - Good Grid

概要

 N×Nのグリッドが1から Cの色で塗られている。 このグリッドの色を変えることで、以下の条件を満たすようにする:

任意の 1 \leq i, j, x, y \leq N について、  (i + j)\%3 = (x + y)\%3ならマス (i, j) (x, y)は同じ色。 さもなくば2マスは違う色である。

1つのマスの色を aから bに塗り替えるときのコストが D_{a, b}で与えられるとき、最小のコストを求めよ。

解説

例えば N=5の場合、同じ色になるマスは以下のようにグループ分けできる:

1 2 3 1 2
2 3 1 2 3
3 1 2 3 1
1 2 3 1 2
2 3 1 2 3

同じグループに入るマスは全て同じ色に置き換わるのだから、 あるグループを1つの色に置き換えるときのコストは、 そのグループに属するマスの各色の数さえわかれば求まる。

あとは3つのグループにどの色を割り振るかを全探索すればいい。 計算量は O(N^2 + C^4)になるはず。制約が C \leq 30なので意外と余裕で間に合う。

int main() {
    ll N, C;
    cin >> N >> C;
    
    V<V<ll>> D(C + 1, V<ll>(C + 1));
    NREP(i, C) {
        NREP(j, C) {
            cin >> D[i][j];
        }
    }

    // cの初期化はせず、各グループに各色がいくつ含まれるかだけ記録する
    // cnt[g][c] = グループgに含まれる色cの数
    V<V<ll>> cnt(3, V<ll>(C + 1, 0));
    REP(i, N) {
        REP(j, N) {
            ll c;
            cin >> c;
            cnt[(i + j) % 3][c]++;
        }
    }

    ll ans = INF;
    V<ll> itr(3);
    // 各グループに割り振る色の配列
    for (itr[0] = 1; itr[0] <= C; itr[0]++) {
        for (itr[1] = 1; itr[1] <= C; itr[1]++) {
            for (itr[2] = 1; itr[2] <= C; itr[2]++) {
                // 3色のうち同じ色があればスルー
                if (itr[0] == itr[1] || itr[1] == itr[2] || itr[2] == itr[0]) continue;

                ll x = 0;
                REP(l, 3) {
                    NREP(m, C) {
                        x += cnt[l][m] * D[m][itr[l]];
                        // グループlに含まれる色mのマスを、全てitr[l]に変える
                    }
                }
                ans = min(ans, x);
            }
        }
    }

    cout << ans << endl;
    return 0;
}

シンプルな全探索問題。400点の中では易しめな方かな〜という印象。

潔く全探索に踏み切れるかどうかが難しいところ。

感想

C問題が本当に謎。でも40分で全完できたので及第点かなって感じではある。 黄色になるまでには30分で解けるようになりたいね。