RUPC 2018 参加記

#RUPC2018 pic.twitter.com/cTQUtSQFcV

— tsutaj (@_TTJR_) 2018年3月26日

立命館大学競技プログラミング合宿 2018 (通称 RUPC 2018) に参加しました。去年に引き続き 2 回目の参加です。いやあ濃密な三日間だったなあ・・・

以下時系列順に振り返るいつもの

Day 0 (前日)

飛行機が遅延しまくる。11:10 離陸予定の飛行機が 15 時に飛んだ (は？) おかげで観光できず。大幅遅延は事前 (搭乗前日) に知らされていたとはいえ、残念な気持ちになる。

宿についてすぐに ARC があったので参加したけど構築が一生解けなくて人生終了した。こう振り返るとなんか虚無イベントしか起こってないような・・・。

Day 1

深夜バス組が南草津でボドゲを朝からやるらしいので、京都に普通に泊まってた自分も早起きして参加した。CODE THANKS FESTIVAL 前のボドゲ会にも参加してた人々が多くて、再会できてよかった。ギャンブラーギャンブルをやるとらてあ氏が無限に勝つのですごいと思いました (小並感)

コンテスト

立命館大学に移動して、コンテストのチームを乱択する。自分はうくさん ( @ukuku09 ) と、 wheson さん ( @wheson ) と組むことになりました。

最初の方針としては wheson さんが A を、自分が B を、うくさんが C を読むことになっていて、B を読んだのですが、国語と数学が壊滅的なため題意が一生わからなかった (後でうくさんに投げてしまった)。自分が題意理解フェーズしている間に wheson さんが A を通してくれた。

C はうくさんから問題文を聞いて map に入れるだけ解法はすぐ思い浮かんで、最悪ケースで普通に二乗オーダーになるのでやばそうだなあと思ったけど、投げたら通ってウケた。長さ最大で回文みたいになっている数列が来たらやばそうではある。そしていまだに B がわからない。

wheson さんとうくさんが B の解読に努めて、自分はとりあえず後ろを読むことに。D は区間 DP みたいな気持ちになるけどわからない。なんか E は全部張るだけでよさそうなので書いたら通る (この問題、最初有向グラフだと思っていた・・・)

F は若干面倒な桁 DP っぽいのでとりあえず飛ばす。G は最初見たとき並列二分探索かと思ったけどそれすらいらなくて、単にクエリを時系列順にソートして状態を更新していけばよい。セグ木でいい感じに書けそうだったので書く。若干バグったけど AC。

ここで全員で B と格闘するもまだ通らない。つらすぎでは？ (ここで 1 時間弱 AC がない虚無を過ごす)

F に戻ってきた。パターンが含まれていない文字列を数えて全体から引くと良さそうだと気づく。早速書くけどコーナーに引っかかって 1WA しつつ AC (自分はパターンの何文字目まで一致したかを状態として持ったけど、下 3 桁持ったほうがコーナー気にする必要なくて圧倒的に楽ですね)

あと F を書いてる途中で D の解法が浮かんだ。区画 merge の順番が関係なくて、最後にどうなっているかだけ気にすれば良いため、普通に左から DP すればよい、ということをうくさんに伝えて書いてもらって AC。

そしてさらに B がやっと解決する。出力の順番罠やんけ！

結果的に全完した (奇跡) 後ろの問題全部解けたので気持ちよかった。

懇親会

ひとがおおくてすごいなあと思った。去年よりも 30 人増えてますもんね。

去年は会話した人を記事に列挙できるくらいの人数だったけどもう列挙できないくらいお話しました。たのしかったです。自分とお話してくれたすべてのひとにありがとう。

Day2

なんか会場着いたらチノちゃんとティッピー載せた成人男性がいるけど

コンテスト

この日は事前にチームが決まっていて、 うしさん ( @ei1333 ) と treeone さん ( @treeone79 ) と組みました。

コンテスト開始 1 時間前が集合時間なんですが華麗に遅刻 (30 分遅れ) (ごめん)

うしさんはコンテスト開始 30 秒前くらいに到着、パソコンを開いたら FA が奪われていたらしい。さすがのうしさんもパソコンの起動時間には勝てなかったらしい。

B 問題担当ワイ、WA を出す (は？) もなんとか AC。A 問題と C 問題もチームメイトによって気が付かない間に片付けられていく。

D 見た一同、これ不可能では？？となる。あとで気づいてたんですが問題解釈間違ってたね (かなしいね)

F はうしプロと treeone プロが通してくれた。 I は制約的に bit DP で、点集合を全て覆うような円の最小半径が欲しい気持ちになるので適当にググったら tubo さんの記事を見つける。前でチーム戦をしている tubo さんに感謝しつつ貼ってメモ化再帰を書いたら TLE する (えぇ・・・) いやオーダー的には大丈夫だよなあと思ってループで書き直したら AC した。メモ化再帰が世界一苦手。

H はうしさんが「あぁこれは Suffix Array でいけそうだなぁ破滅だなぁ」とかなんとか言いながら通してた。プロすぎる。このへんからうしさんが床コーディングをはじめる。

G は一般マッチングが欲しい気持ちになって、これまたググったら出てきたのでうしさんが貼って提出。 の だけど難なく通って草。

相変わらず D は破滅なので J とか E とかをやるも破滅する。後半は全員で破滅虚無人生終了コーディングしてた。つらい。

あとで気づいたけど E の悪魔的ケース気づいてなかったね。

懇親会

ツイッター映えする焼肉 #RUPC2018 pic.twitter.com/89H9816qL3

— tsutaj (@_TTJR_) 2018年3月27日

焼き肉！！！なんかやたら火力が強くて、定数倍高速化を極めた焼き肉とか言ってた。

食べて飲んだあとは近くの温泉に入って疲れを癒していました。やざてんさんのかばん無事でよかった。

Day 3

コンテスト

今日は admin です #RUPC2018 pic.twitter.com/hN3HGY1ouo

— tsutaj (@_TTJR_) 2018年3月27日

泣く子も黙る †admin† でした。コンテスト開始 2 時間前から会場入りしていたんですが割とちょうどよい感じで準備が終わって、チーム決めたり解説編集したりしてました。

割と典型を集めたセットになっていて、全完はでるだろうとは思っていたけど、おわってみれば 19 チームが全完していて、これは想像していたよりもはるかに多い数でした。次回はもっと難易度上げるか！ｗ 皆さん解いてくれてありがとうございました。

その後

その後は立命のキャンパス内にある超いい感じの食堂？に行ったり、南草津駅で虚無をしたり、再びカラオケ屋でボドゲをしたり、某 treeone の通知欄を破壊したり、京都でご飯を食べたり、某 treeone に通知欄を破壊されたりしました。南草津着いた後はずっと olphe さん・TIke さん・フェリンさんと遊んでました。正直超たのしかったです、ありがとうございました。

まとめ

いや立命合宿は楽しいかな〜やっぱｗ チーム戦も楽しめるし作問もできるし (聞いてないｗ)

来年もまた参加したいです・・・！！！

AtCoder Regular Contest 089 D: Checker

問題概要

日本語なので原文参照 → D - Checker

解説

公式解説 が詳しく書かれていますので、そちらもご覧ください。ここでは実装上楽な書き方を中心に書きたいと思います。

考慮すべき領域は以下のような形をしており、 箇所の累積和を求めれば良いです。これらの領域の位置は、領域 の右下を定めるとすべて定まります。黒の累積和・白の累積和をとって足して・・・と書いても出来ますが、今回は累積和の配列を つだけ使って実装してみましょう。

黒が置いてあるところはインクリメントし、白が置いてあるところはデクリメントすることを考えます。黒で塗りたい領域を決定したとき、黒は して白は しているため、決定した領域内に本当に黒が置いてあれば、条件を満たしているのでそのぶん加点されますし、白が置いてあれば、条件を満たしていないのでそのぶんペナルティとして減点される、というイメージになります。

このようにすると、白の要素の個数を覚えておくことで、 (累積和) + (白の要素の個数) とすれば、領域を決定した時に得られる値が分かります。

先ほど決定した領域の白黒を反転した状態における値の計算も簡単にできます。 (黒の個数) - (白の個数) と定義すると、盤面全体の累積和は と一致しています。白黒を反転しているため、 (累積和) とすることで、領域を反転させた際に得られる値が分かります。

ソースコード

#include <cstdio>
using namespace std;

int max(int a, int b) { return a < b ? b : a; }
int board[2010][2010];
int main() {
    int N, K; scanf("%d%d", &N, &K);

    int sum = 0, white = 0;
    for(int i=0; i<N; i++) {
        int x, y; char c; scanf(" %d%d %c", &x, &y, &c);
        x %= 2*K, y %= 2*K;
        if(c == 'B') board[x+1][y+1]++, sum++;
        if(c == 'W') board[x+1][y+1]--, sum--, white++;
    }

    for(int i=1; i<=2*K; i++) {
        for(int j=1; j<=2*K; j++) {
            board[i][j] += board[i][j-1];
        }
    }

    for(int j=1; j<=2*K; j++) {
        for(int i=1; i<=2*K; i++) {
            board[i][j] += board[i-1][j];
        }
    }

    int ma = -(1 << 25);
    for(int i=0; i<=K; i++) {
        for(int j=0; j<=K; j++) {
            int a = board[i][j];
            int b = board[i+K][j+K] - board[i+K][j] - board[i][j+K] + board[i][j];
            int c = board[2*K][j] - board[i+K][j];
            int d = board[i][2*K] - board[i][j+K];
            int e = board[2*K][2*K] - board[2*K][j+K] - board[i+K][2*K] + board[i+K][j+K];
            int tmp = a + b + c + d + e;
            ma = max(ma, max(tmp, sum - tmp));
        }
    }
    ma += white;
    printf("%d\n", ma);
    return 0;
}

おまけ

二次元累積和を使う問題として、他に ARC のチョコレート があります。こちらに関しても累積和の配列 つで解くことができます。

CSAcademy Round #72: Spring Cleaning

問題概要

原文 → CS Academy

頂点からなる有向グラフがある。このグラフは各頂点から 本ずつ有向辺が出ており、自己ループがないことが保証されている。

はじめ、全ての頂点に対して駒が 個ずつ置かれている。ここから、以下のルールにしたがって駒を取り除くことができる。

• 頂点 から出る有向辺によって繋がっている頂点を とおくとき、 ともに駒がある場合、 にある駒を取り除くことができる。

できるだけ多くの駒を取り除くとき、この操作列を出力せよ。

解説

頂点 辺の有向グラフなので、いわゆるなもりグラフで、ループが必ず つあるグラフです。なので、それぞれの頂点に対して「ループに繋がっている頂点」であるか「ループ内の頂点」であるかのどちらかです。

ループ内の頂点から探索を始めると、ループに繋がっている頂点を取れない可能性があるので、ループに繋がっている頂点から優先的に探索をすればよいです。これをするには、入次数が である頂点から先に探索すれば良いです。

なお、ひとつの大きな閉路になっていて入次数が である頂点がひとつもない場合もあることなどに注意してください。

ソースコード

void solve(vector<int>& edge, vector<int>& visited, int cur) {
    visited[cur] = true;
    if(visited[ edge[cur] ]) return;
    solve(edge, visited, edge[cur]);
    printf("%lld %lld\n", cur+1, edge[cur]+1);
}

signed main() {
    int N; cin >> N;
    vector<int> to(N, -1), deg(N, 0), visited(N, 0);
    rep(i,0,N) {
        int p; cin >> p; p--;
        to[i] = p;
        deg[p]++;
    }

    deque<int> deq;
    rep(i,0,N) {
        if(deg[i] == 0) deq.push_front(i);
        else deq.push_back(i);
    }

    rep(i,0,N) {
        solve(to, visited, deq[i]);
    }
}