RUPC2017 Day3 北大セットのまとめ

この記事は立命合宿の 3 日目に行われた北大セットのまとめ的記事です。勝手にまとめてしまいました。

※ 随時更新します

問題

実際にコンテストで使われたバージョン

A 問題 | B 問題 | C 問題 | D 問題 | E 問題 | F 問題 | G 問題

正式掲載

A 問題 | B 問題 | C 問題 | D 問題 | E 問題 | F 問題 | G 問題

解説

A 問題 | B 問題 | C 問題 | D 問題 | E 問題 | F 問題 | G 問題

テスターやった人並みの一言

解法詳細はスライドを見てください。

• A は (奇数個ある種類数) / 2。誤読しやすいのは正直申し訳ないし誤読する人が出るだろうなあという予想はしていたけど、問題をちゃんと読むという注意力を問うた部分もある (たとえ誤読していてもサンプル 3 で気づくと思ったんですけどね・・・)
• B は 「x 点上げるときに 8 位以上になれるか？」で二分探索できる (全探索でも可)。同率の扱いや、得点を上げた時の順位変動に注意。
• C はパスグラフとしてみるとよくて、端を特定したあとは端と任意の頂点について質問攻め。順列のサイズが 1 のときに注意。
• D はパラメータが増えたダイクストラで、距離をキーにして priority_queue を使えばよい。N を通過したか否かのフラグを持つと楽に書ける。速度をキーにしてもそこそこうまくいくけど 1 ケースだけ落ちます (後述)
• E は区間を set に突っ込むときの set のサイズがそのまま答えになる (更新は頑張らなければいけない)
• F は根つき木の同型性判定を応用して、木の中心を根として同型性判定を行う
• G は パターン順列の run の数に応じて解法を変えていく。run の数 が 4 以上なら確実に No
  • run の数 = 1 なら LIS
  • run の数 = 2 なら 山 → 谷 のパターンに合うように点を貪欲にとる
  • run の数 = 3 なら 山 → 谷 → 山 のパターンに合うように貪欲に

コード例 (tsutajiro 解)

A 問題 | B 問題 | C 問題 | D 問題 | E 問題 | F 問題 | G 問題

ちょっとした裏話

• 作問班唯一の学部生・・・ (若人がいない)
• 情報系学生の底辺なので作問するまで Git の使い方が分からなかった (爆笑)
• B は最初二分探索が想定解であったため、チーム数が まで、得点上限が まで、といった感じだったが、 B にしては難しすぎるため全探索可能な範囲に落ちた
• D で始めの自分の解では距離比較でなく速度比較でダイクストラをやっていて、それで一旦全ケース通ってた
  • → のちに Darsein さんがチャレンジケースを生成して見事に落とされる
  • → 理由は最悪計算量がベルマンフォードと同じになり間に合わないため (しかし通常のベルマンフォードよりは速い模様)
  • → tsukasa_diary さんが SPFA を実装したところ爆速で通る (が、最悪ケースを作るのが難しいためこれは許容する流れに)
• 先輩方はみんなプロ (それはそう) (精進します)

以上です。

立命館大学プログラミング合宿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_bound と upper_bound 使えばいいだけだったので書いて AC。
• C 問題は odan さんから方針の相談をされたので、定数項を素因数分解して入る数字の候補を減らしていこうということを言った (でも実際範囲狭かったのでこれをやらなくても全探索で OK) odan さんは構文解析のプロなのですぐ実装してくれて AC。
• D 問題は DP を考えていて、最初 回くらいの計算になりそうな感じの 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: ダルマ落とし

昨年のだるま落とし、ちらっと解説読みながらだけど AC できた。ちょっと嬉しい。

— つたじろう (ABC-D 29/43) (@_TTJR_) March 6, 2017

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

問題概要

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

解説

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

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

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

• 区間 のブロックを全て取ることができ、かつ 番目と 番目のブロックの重さの差が 以下であれば、区間 のブロックを全て取ることができる
• 区間 と 区間 について、両区間に対して全て取ることができるならば、区間 のブロックを全て取ることができる

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

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

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

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

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

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

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

あとは dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]) と更新してあげることで正答が得られます (発想としては前述の「より長い区間に対しても判定できる」の箇条書きの つめと一緒です)、 パワーを信じましょう。答えになるのは 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 を 回やる」みたいなことを呟いている人がたくさんいるのを見て、こんなんできるわけ無いだろうと思っていたけど、今見ると DP を 回やる気持ちが確かに分かる。