hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

立命館大学プログラミング合宿2017 参加記

立命館大学プログラミング合宿2017 に参加してきました。競技プログラミングの合宿に参加したのは初めてです。 帰りの電車ヒマなので参加記をつらつらと書いていこうと思います。

-1 日目 (作問班参加・準備編)

北大では立命合宿で作問を担当しているので、作問班をサークル内で作らなければなりません。大変そうだけど競プロできる先輩たちといろいろ議論しながら作っていったらためになるだろうなあと思って作問班に参加することに。

立命合宿の日程が北大の卒業式と被ってしまい、先輩方が合宿に出られなくなって当日現地に行くのが私だけになってしまったので、必然的に解説を全部やらないといけない感じになりました。これは全部解いてからいかないとまともに解説できなくてヤバいのでは!?と思ったので全問題のテスターをやることにしました (しかし、F の TLE に悩まされて結局 F 以外のテスターになりました)

作問に必要なツールの使い方は今回で一通り勉強できましたし、何に注意すべきかも分かったので勉強になりました。次に作問する機会があったら活かしたいですね。

0 日目 (移動編)

北の果てから移動するので前日から移動。宿は京都でとってました。烏丸おしゃれすぎてマジヤバい (語彙)

1 日目 (立命 & 阪大セット)

いよいよ合宿スタート!

kenkoooo さん、 kawabys さんとチーム ktky で出ました。

  • 最初 A 問題の担当だったのですが難しく考えすぎてハマる (戦犯)
  • B はあんまり読んでない (kawabys さんが AC)
  • C を見たら各頂点の深さみてよしなに足し合わせたらいけるなあとなってので書いて AC。
  • D は最初アルファベットを頂点にして右隣のアルファベットに辺を張るグラフみたいなのを考えていたけど嘘 (戦犯)
  • E は気づいたら kenkoooo さんが AC していた (すごい)
  • F は kawabys さんと kenkoooo さんが考察していたけどつらかったらしい (自分は他の問題やってて参加できなかった)
  • K を見たら DP なのかなあと思って書いていたけど、教科の最高点が複数人いた場合に詰むことが判明しておしまい (戦犯)

結果、4 完 20 位。全体的に戦犯でした。

懇親会ではいろんな人と話せて面白かったです。競プロサークルの事情はどこも同じようで、最初は大量に入ってくるけどその分幽霊部員もたくさん出るよねーみたいな話をしていました。九大の方々が今後の新歓について真面目に議論していてアツかったです。

2 日目 (会津大セット)

yurahuna さん、 odan さんとチーム toy18 で参加しました。

  • A 問題はやばかったらしい (yurahuna さんが AC)
  • B 問題は lower_boundupper_bound 使えばいいだけだったので書いて AC。
  • C 問題は odan さんから方針の相談をされたので、定数項を素因数分解して入る数字の候補を減らしていこうということを言った (でも実際範囲狭かったのでこれをやらなくても全探索で OK) odan さんは構文解析のプロなのですぐ実装してくれて AC。
  • D 問題は DP を考えていて、最初  10^{8} 回くらいの計算になりそうな感じの DP が出来上がって計算量的に不安だったけど書く → ひたすらバグるので 2 人に相談 → DP の方針を変えようということになり、想定解法と同じ DP にたどり着く → 添え字がややこしすぎる → yurahuna さんとひたすらデバッグをする → AC!!!!

この問題だけでコンテスト時間の半分を消費したといっても過言ではないかもしれません。正直チームメンバーがプロなので通った感じで、自分ひとりだったら完全にあきらめてましたね。本当に感謝です。

  • E 問題は平均最大化するだけといって yurahuna さんが早々に AC (ほんまプロ)

結果、 5 完 8 位。最終的に D が通ったのが大きかったですね。

懇親会はなんと RCO さんの援助があり費用が無料に。競プロ er に理解のある RCO さんに感謝です。自分の卓は北大・会津大・名古屋大・九大と津々浦々から来ている感がすごくて楽しかったです。チンチロやったら 3 つとも 2 の目が出たのはビビった (運を使い果たした)

3 日目 (北大セット)

いよいよ北大セットお披露目のときです。実は結構バタバタしていて、AOJ に初めて問題をアップしたのが前日の夜 10 時くらいで、最終稿が載ったのが当日の午前 9 時前後でした。原因としては私が AOJ 側にコンタクトを取る方法を知らなかったことと、準備の段取りを先輩方に聞くのが足りなかったことですね。次回は反省を生かして 3 日前くらいには上げられるようにしたいです。

コンテスト運営を 1 人でやるのは不可能だからと、ジャッジチーム側に tubo28 さんがまわってくださいました。実際 1 人 (しかも作問側未経験) では運営不可能だったので、本当に助けられました。

バタバタしながらもコンテストがスタート。私は総評とスライドの手直し、それから風船運びをしながら過ごしていました。

問題のこといろいろに関しては、長くなったので別記事を見てください。

プロがたくさんいる中で解説をしなければいけなかったので相当緊張しましたが、何とか終わったので良かったです。次に解説するときまでには自信もって解説できるくらいの力をつけたいですね。

まとめ

オンサイトはいいぞ。初参加でしたがとても楽しかったです。やっぱりチーム戦はいいですね。

あと帰りに買った漫画がよかった。以上です。

ICPC 国内予選 2016 D: ダルマ落とし

昨年歯が立たなかっただけに解けてうれしい。

問題概要

原文を参照してください → Daruma Otoshi | Aizu Online Judge

解説

take[i][j] := 区間 [i, j] のブロックを全て取ることができるか となる bool 型の配列を用意します。まずはこの take 配列に対して、真偽値を正しく入れていきます。

条件より、区間の長さが  2 であるときの判定は容易です。問題はその後でしょう。

次の  2 つの事項を確認することによって、より長い区間についても判定できるようになります。

  • 区間  \left[ i, j \right] のブロックを全て取ることができ、かつ  i-1 番目と  j+1 番目のブロックの重さの差が  1 以下であれば、区間  \left[ i-1, j+1 \right] のブロックを全て取ることができる
  • 区間  \left[ i, k \right] 区間  \left[ k+1, j \right] について、両区間に対して全て取ることができるならば、区間  \left[ i, j \right] のブロックを全て取ることができる

したがって、以下のようにすれば take 配列を正しく構築できます。

  • 区間の長さが短い順に以下を行う
  • 長さが  2 であれば、重さの差が  1 以下であるかを判定して配列を更新する
  • それ以外の長さであれば、より短い区間の結果を使って配列を更新する

この配列を元に答えを出すのですが、これに答えるには以下の補題を解かなければなりません。

 \left[ 1, N \right] の中に、長さが  N 以下の区間がたくさんある。その中から、区間どうしが同じ頂点を被覆しないようにいくつかの区間を選ぶときの、被覆できる頂点数の最大値を求めよ。

これは DP で解くことができます。

dp[i][j] := 区間 [i, j] において被覆できる頂点数の最大値 となるような配列 dp を用意します。

この配列の初期化は各区間を見ることによって行います。例えば 長さ  M区間  \left[ a, b \right] があったとします。 \left[ a, b \right] において被覆できる頂点数の最大値は当然  M なので、dp[a][b] = M が成り立ちます。これを全区間に対して行うことで初期化します。

あとは dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]) と更新してあげることで正答が得られます (発想としては前述の「より長い区間に対しても判定できる」の箇条書きの  2 つめと一緒です)、 O(N^{3}) パワーを信じましょう。答えになるのは dp[0][N-1] です。

ソースコード

bool take[310][310];
int dp[310][310];

signed main() {
    int n;
    while(cin >> n, n) {
        int w[310];
        rep(i,0,n) cin >> w[i];
        memset(take, false, sizeof(take));
        memset(dp, 0, sizeof(dp));

        rep(i,0,n) {
            rep(j,0,n-i) {
                int len = i+1;
                int s = j, t = j+i;
                rep(k,s,t) {
                    if(take[s][k] && take[k+1][t]) take[s][t] = true;
                }
                if(len == 2) {
                    if(abs(w[s] - w[t]) < 2) {
                        take[s][t] = true;
                    }
                }
                if(take[s][t]) {
                    int x = s-1, y = t+1;
                    while(1) {
                        if(x < 0 || x >= n || y < 0 || y >= n) break;
                        if(abs(w[x] - w[y]) >= 2) break;
                        take[x][y] = true;
                        x--; y++;
                    }
                }
            }
        }

        rep(i,0,n) rep(j,i+1,n) {
            if(take[i][j]) dp[i][j] = j-i+1;
        }

        rep(i,0,n) rep(j,i,n) rep(k,i,j) {
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
        }
        cout << dp[0][n-1] << endl;
    }
    return 0;
}

当時は「DP を  2 回やる」みたいなことを呟いている人がたくさんいるのを見て、こんなんできるわけ無いだろうと思っていたけど、今見ると DP を  2 回やる気持ちが確かに分かる。

KUPC2012 D: 権力

何でこれが詰まっちゃうかな・・・。

問題概要

原文 → D: 権力 - 京都大学プログラミングコンテスト2012 | AtCoder

 M 個の区間がある。 \left[1, N \right] を被覆するには、区間はいくつ必要であるか、その最小値を答えよ。

解説

まず、地点  1 を被覆する区間があるかを調べます。もし存在するならば、その中で一番右まで被覆できるものを選びます。存在しなければ Impossible です。

次に、先ほど選んだ区間の右端  + 1 の地点を被覆する区間があるかを調べ、存在するならば一番右まで被覆できるものを選びます。

これを繰り返す貪欲法によって正答が得られ、計算量は  O(NM) です。

ソースコード

signed main() {
    int n, m; cin >> n >> m;
    int a[110], b[110];
    rep(i,0,m) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }
    bool covered[110] = {};
    int ans = 0;
    rep(i,0,n) {
        if(covered[i]) continue;
        int r = -1;
        rep(j,0,m) {
            if(a[j] <= i && i <= b[j]) {
                r = max(r, b[j]);
            }
        }
        if(r == -1) {
            cout << "Impossible" << endl;
            return 0;
        }
        repq(j,i,r) covered[j] = true;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

どうも区間の問題が苦手らしい。

AtCoder Beginner Contest 018 D: バレンタインデー

バレンタインデー、みなさんいかがお過ごしでしょうか。私はいつもと変わらず競プロをやっています。というわけで今回は ABC018 D 問題です。

問題概要

原文 → D: バレンタインデー - AtCoder Beginner Contest 018 | AtCoder

女子が  N 人、男子が  M 人いる中から、女子  P 人、男子  Q 人からなるグループを作る。

チョコレートは  R 個あり、番号が  x_i である女子は番号が  y_i である男子に幸福度  z_i である  i 番目のチョコレートを渡すが、これは番号が  x_i である女子と番号が  y_i である男子が両方ともグループに含まれている時に限り渡すことができる。

渡されたチョコレートの幸福度の合計値の最大値を出力せよ。

解説

女子の組み合わせ、ならびに男子の組み合わせを総当りで考えてしまうと、組み合わせが  {}_N C_P \times {}_M C_Q 通りあるため間に合わず、この問題の制約では部分点止まりになります。

満点解法では、「グループに入れる女子を固定すれば、チョコレートを貰う男子とその男子が得る幸福度がわかる」ことに着目します。グループにどの男子を入れるかについては、幸福度が大きい男子から貪欲に選択するのが最適です。いわゆる半分全列挙というやつです。したがって、次の流れで実装すればよいです。

  • グループに女子を  P 人入れる各組み合わせについて以下を行う
  • チョコをもらう可能性のある男子について、幸福度を計算する
  • 幸福度が大きい順に男子を  Q 人選び、その男子の幸福度の合計を計算し、その max を答えとする

この方針で解くと男子の組み合わせを列挙する必要がなくなるため、間に合います。

ソースコード

signed main() {
    int n, m, p, q, r; cin >> n >> m >> p >> q >> r;
    vector<pii> v[20];
    rep(i,0,r) {
        int x, y, z; cin >> x >> y >> z;
        x--; y--;
        v[x].pb(pii(y,z));
    }
    int ans = 0;
    rep(i,0,(1 << n)) {
        int bcnt = __builtin_popcount(i);
        if(bcnt != p) continue;
        int value[20] = {};
        rep(j,0,n) {
            if(i >> j & 1) {
                rep(k,0,v[j].size()) {
                    int to = v[j][k].fr;
                    int cost = v[j][k].sc;
                    value[to] += cost;
                }
            }
        }
        sort(value, value + m, greater<int>());
        int temp = 0;
        rep(j,0,q) temp += value[j];
        ans = max(ans, temp);
    }
    cout << ans << endl;
    return 0;
}

余談

2/9 の SRM 708 で、念願の Div1 昇格を果たしました。初めて青になれたのでうれしかったです。

青底辺から上がれるようにこれからも頑張ります。

AtCoder Regular Contest 043 B: 難易度

ARC043 B問題、データ構造で殴ってしまったけど、明らかに想定解法より楽な方法だと思うのでいちおう紹介。

問題概要

問題原文 → B: 難易度 - AtCoder Regular Contest 043 | AtCoder

長さ  N の数列が与えられる。この数列から、(  i - 1 番目に取った数 )  \times 2 \leqq (  i 番目に取った数 ) となるように数字を  4 つとる。この取り方の総数を  1000000007 で割った余りを出力せよ。なお、同じ値でも違うインデックスにある数同士は区別される。

解説

まず数列をソートして、dp でできないかを考えてみます。

dp[i][j] := i 番目の数を j 番目に使う場合の数 という配列を考えると、 a_i の前に選んだ可能性のある数は  1 \leqq a_k \leqq \lfloor \frac{a_i}{2} \rfloor を満たす全ての数であるため、遷移は以下のようになります。

 dp_{i,j} = dp_{i,j} + \sum_{1 \leqq a_k \leqq \lfloor \frac{a_i}{2} \rfloor} dp_{k, j-1}

これをそのまま実装してしまうと  O(N^2) のコードになってしまい TLE しますが、  \Sigma をとっている部分は  a のインデックスが  0 からある数字までの区間の和ですので、この部分を BIT などのデータ構造で高速で計算すれば時間内に解くことができます。計算量は  O(N \log N) です。実装では BIT を使いやすくするために配列を再利用するとよいでしょう。

ソースコード

BIT を使いやすくするために配列の再利用をしています。

// BIT 略
signed main() {
    int n; cin >> n;
    int a[100010]; rep(i,0,n) cin >> a[i];
    sort(a, a+n);
    zeroIndexedBIT<int> dp(n);
    rep(i,0,n) dp.add(i, 1);

    rep(j,0,3) {
        repr(i,n-1,0) {
            dp.add(i, -dp.sum(i,i));
            int k = upper_bound(a, a+n, a[i] / 2) - a;
            k--;
            if(k < 0) continue;
            int temp = dp.sum(0, k);
            dp.add(i, temp);
        }
    }

    int ans = dp.sum(0, n-1);
    cout << ans << endl;
    return 0;
}

AtCoder Grand Contest 010 B: Boxes

AGC010 の B 問題。本番解けなかったけどこれは良問だとおもう。

問題概要

原文 → B: Boxes - AtCoder Grand Contest 010 | AtCoder

 N 個の箱が環状に並んでおり、 i 番目の箱に入っている石の数は  a_i 個である。

この環状に並ぶ箱に対して、ある箱を選んでそれを  i 番目としたとき、 1 から  N の各  j に対して、 (i+j) 番目の箱から石をちょうど  j 個取り除く、という操作が行える。ただし、 N+k 番目の箱は  k 番目と同一視するものとする。

この操作を繰り返して全ての石を取り除くことができるかを求めよ。ただし各操作において、取り除きたい個数の石がない箱があるときは、その操作を行えないものとする。

解説

箱の数を  n とおくことにします。

まず、この操作を  1 回行った時の重要な性質をいくつか見ていきます。

  1.  1 回の操作で  \frac{n(n+1)}{2} 個の石が取り除かれる
  2.  i 番目の箱に入っている石の数の変化量を  h_i とおくと、隣接  2 項間の  h の差分の和  \sum_{i=1}^N (h_{i-1} - h_i) 0 になる

前者は問題文より明らかです。後者は、差分が  -1 の箇所が  (n-1) 個あり、差分が  (n-1) の部分が  1 個あるため、結果的に差分の和は  0 になります。

したがって、操作が  k 回行われた場合、 k \times \frac{n(n+1)}{2} 個の石が取り除かれ、上述の差分の和は  0 であることがわかります。特に前者は非常に重要で、これを言い換えると、与えられた数列の項の総和から操作回数を計算できると言えます。

これで数列全体に対する操作の回数はわかりましたので、あとは「どの箱から何回操作を行ったか」の情報がわかれば解けます。以降、数列全体に対する操作の回数を  z とします。

 i 番目の箱から操作を行う数を  x_i とし、元の数列で自分より前の項との差分、すなわち  a_{i-1} - a_i s_i とします。このとき、 x_i はどのように表せるでしょうか?これは、次のことを用いて考えれば良いです。

  1.  i 番目から操作を行う回数が  x_i 回 → 前の項に比べて  x_i \times (n-1) 減っている
  2.  i 番目以外から操作を行う回数が  (z-x_i) 回 → 前の項に比べて  (z-x_i) \times 1 増えている

この事実と、 s_i が「前の項からいくつ減っているか?」を表していることから、次の一次方程式を立てることができます。

 s_i = (n-1)x_i - (z-x_i)

これを  x について解くと、

 x_i = \frac{s_i + z}{n}

となります。もちろん、 x_i は整数になりますので、分子  s_i + z n の倍数でなければなりません。

どの箱から何回操作を行ったかの情報さえあれば、数列を構築することができます。 1 番目の数列の値を  O(N) で構築すれば、 2 番目以降は前の項の結果を用いて  O(1) で計算できるため、結果  O(N) で構築できます。私のソースコードではこの方法で構築した数列と与えられた数列を比較して最終確認をしています。(この最終確認はしてもしなくても良いです)

ソースコード

signed main() {
    int n; cin >> n;
    int a[100010] = {};
    int sum = 0;

    rep(i,0,n) {
        cin >> a[i];
        sum += a[i];
    }

    int cs[100010] = {};
    int ret[100010] = {};
    int cntnum = 0;

    if(sum % (n * (n+1) / 2)) cout << "NO" << endl;
    else {
        cntnum = sum / (n*(n+1) / 2);
        rep(i,0,n) {
            int prev = (i - 1 + n) % n;
            int s = a[prev] - a[i];
            // n で割り切れなければ操作回数が小数になるので不適
            // 結果が負になるのも不適 (操作回数は非負整数)
            if( (s+cntnum) % n != 0 || (s + cntnum) / n < 0) {
                cout << "NO" << endl;
                return 0;
            }
            cs[i] += (s + cntnum) / n;
        }
        rep(i,0,n) ret[0] += cs[i] * ((n - i) % n + 1);
        rep(i,1,n) ret[i] = ret[i-1] - cs[i] * n + cntnum;
        rep(i,0,n) {
            if(ret[i] != a[i]) {
                cout << "NO" << endl;
                return 0;
            }
        }
        cout << "YES" << endl;
    }
    return 0;
}

この、特殊なデータ構造を理解している必要もなく、実際はループと単純な演算だけで答えが導けるっていう考察重視の感じね。さすが最強高校生が考える問題は一味違う・・・。

AtCoder Regular Contest 027 C: 最高のトッピングにしような

またまた DP 自力で解けた記念。

問題概要

原文 → C: 最高のトッピングにしような - AtCoder Regular Contest 027 | AtCoder

 N 種類のトッピングがある。トッピング  i t_i 枚のチケットを交換することで入手でき、その価値は  h_i である。

チケットにはスペシャルチケットと通常のチケットの  2 種類が存在し、どのトッピングにおいてもスペシャルチケット最低  1 枚を含むチケットの組み合わせでなければ交換できない。

いま、スペシャルチケットを  X 枚、通常のチケットを  Y 枚持っている。トッピングの価値の合計値を最大化せよ。

解説

ナップザックの亜種、ということで動的計画法を使って解いていきます。説明のため、スペシャルチケットは ST と、通常のチケットは RT と略記します。

dp[i][j][k] := i 番目までのトッピングを使って、ST の残りが j 枚で RT の残りが k 枚である時の価値の最大値 となるように配列を用意します。

どちらの種類のチケットも十分な数あると仮定するとき、 h_i 枚のチケットが必要なトッピングに対して使うチケットの組み合わせは  h_i 通りありますが、これを全て試していってしまうと DP の更新が  4 乗ループになり時間的に間に合いません。どこかを工夫して、計算量を落とせないでしょうか?

今回の場合は、ST と RT を組み合わせて  h_i 枚使えば良いとのことですので、使うチケットの枚数はどの組み合わせでも等しいです。さらに、いずれのトッピングも ST が最低  1 枚以上必要であることも重要で、これらを考えると RT の方をなるべく多く使っていけば (ST がなるべく余るように使っていけば) 良いことがわかります。この貪欲で  3 乗ループになりますので間に合います。計算量は  O(XYN) です。

ソースコード

最初メモ化で書こうと思ったけど、意味不明なコードになったので DP で。

int x, y, n;
int t[310], h[310];
int dp[310][310][310];

signed main() {
    cin >> x >> y >> n;
    rep(i,0,n) cin >> t[i] >> h[i];
    memset(dp, 0, sizeof(dp));
    
    rep(i,0,n) repq(j,0,x) repq(k,0,y) {
        dp[i+1][j][k] = dp[i][j][k];
        if(j+k >= t[i] && j != 0) {
            int p, q;
            if(k >= t[i] - 1) {
                p = 1;
                q = t[i] - 1;
            }
            else {
                p = t[i] - k;
                q = k;
            }
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-p][k-q] + h[i]);
        }
    }
    int ans = 0;
    repq(i,0,x) repq(j,0,y) ans = max(ans, dp[n][i][j]);
    cout << ans << endl;
    return 0;
}

さすがにナップザックの亜種は割とできるようになってきたけど、他の DP にもトライしてみなければ・・・。