hogecoder

tsutaj 競技プログラミングの記録

HCPC 北海道大学競技プログラミングサークル の紹介

競プロその他

tsutaj です。もうすぐ新年度になるので、弊学の競技プログラミングサークルを紹介します。特に春から北大に入学・進学する方々の参考になれば幸いです。

競技プログラミングとは？

まず、この記事を読んでくださった方で「競技プログラミングって何？」と疑問に思った方もいるのではないかと思います。

一言で言うと、競技プログラミング (以下「競プロ」と略記) とは、「与えられた問題に対して、適切な手続きを考えて実装することを競う競技」 です。より具体的には、人力では到底解けないようなスケールの問題が出題されて、それに答えられるようなプログラムを実装して提出する、というものです。コーディングの技術はもちろんのこと、問題解決に必要なアルゴリズムの知識や発想も求められます。

もっと詳しく知りたい方は、高校生向けに説明された sifue さんの記事 も参考にしてみてください。

競プロサークルに入るメリットとは？

競プロはサークルに入らなくとも、パソコンさえあれば気軽に始めることができます。ですが、せっかく始めるならば一度サークルに足を運んでくれたらいいなと思っています。

私が考えるに、サークルに入るメリットとしては以下が挙げられます。

  • 競プロに熱心に取り組んでいる仲間に会える
    • 毎週サークルで競プロをしていることもあって、メンバーの競プロに対する意欲は非常に高いと思っていますし、そういう仲間がいたほうが刺激になって良いと思います。大会が近くなると週末に有志で集まって追加で活動するようなメンバーもいたりします。
  • 強い (？) 人にいろいろ教えてもらえる
    • 2019 年 4 月 1 日現在、弊サークルには AtCoder 黄色が 2 人、青色が 2 人、水色が 5 人ほどいます。が、競プロを大学から始めた人がほとんどで、先輩方から教えてもらって地道に実力を上げていった感じです。基礎的なところからアルゴリズムに関する発展的なトピックまで、知識や経験を還元していけたらいいなと思っています。
  • チームを組む相手がすぐに見つかる
    • 競プロの大会の大半は個人戦ですが、ACM-ICPC など一部大会では、チームでの出場が必須となっています。サークルにいればチームを組む相手にはまず困らないと思います。

活動内容

サークルとしての大きな目標は、チーム戦である「ACM-ICPC 国際大学対抗プログラミングコンテスト」への参加、および予選突破です*1。これを達成するために週に 2 回、競技プログラミングの実力を上げるべく活動しています。活動内容は主に以下の 2 種類です。

練習会

練習会では、(バーチャル) コンテストを通じて決められた時間内で実際に問題を解きます。コンテスト終了後に解説もするので、わからないところがあればそこで解消できると思います。対面で問題について議論するのは楽しいです。

勉強会

勉強会では、予め決められたトピック (これは動的計画法や全探索など、競技プログラミングにおいてよく使用されるアルゴリズムになることが多いです) について発表担当者がスライドを作り、全員でその内容を勉強します。発表途中、わからないことなどがあれば発表者に質問しつつ、新しい知識を得ていきます。

参考までに、弊サークルの勉強会で使われたスライド類は、HCPC のホームページ にまとまっています。

また、これとは別に弊サークルでは作問も行っています。例年では、作った問題が会津大学プログラミング合宿・立命館大学プログラミング合宿で使われます。問題を作る側になれる機会は貴重だと思いますので、ぜひ一緒に作問しましょう！

連絡先など

HCPC のホームページ にもっと詳しく情報が載っていますので、こちらもぜひチェックしてみてください。

また、サークルを見学したい！などなど、興味がおありの際はぜひご連絡下さい。この記事の著者: tsutaj (Twitter: @_TTJR_) に連絡するか、hokudai.procon[at]gmail.com までメールしてください！ご連絡お待ちしています。

*1:今年の国内予選は 7 月 12 日 (金) に行われるようです

RUPC 2019 参加記

勉強会参加記

立命館大学プログラミング合宿 2019 (RUPC 2019) に参加しました。RUPC への参加は 3 年連続 3 回目です。

Day 0

飛行機で関西国際空港に到着、その後電車で立命館大学まで移動。空港に 14 時半 くらいに着いたし、集合時間の 18 時にはまあ間に合うでしょうと思っていたんですが意外と電車の所要時間が結構あって遅れそうになる。それでも天才的乗り換えにより乗り換え検索アプリ上の到着予定時刻よりも 20 分ほど早く到着、なんとか間に合う。

晩御飯は立命のりかさんと、北大のろであ君・TAB 君と一緒にまぜそばを食べた。おいしかった。

Day 1

参加者の受付開始。立命に続々と競プロ er が集まってくる。

自分が作った チーム分けアプリ を使う際に必要な情報 (HN や AtCoder ID など) を参加者に教えてもらう。皆さんご協力ありがとうございました。

自分は事前にチームが決まっていて、てんぷらとけんちょんさんと一緒に組むことに。とりあえずレート順に問題を見ていこうということになったので自分が A を読むことになった。

コンテスト開始。A はさすがにちょっとした計算をするだけっぽい。題意を若干間違えるも 1:45 でオンサイト FA を取る。その後てんぷらが B を通してこれもオンサイト FA。

C はけんちょんさんの担当だったがチラ見させてもらった。なんかやばそうな雰囲気を感じ取る。

D を読んでみる。なんか構築とインタラクティブの雰囲気を感じて途端にやりたくなくなる (は？) これは自分がやらないほうがよさそうなのでてんぷらに投げて E を読む。ペアのセグ木を持てば更新ができそうなので書く、通る 全体 FA だったのでうれしいね

自分が F を読んでいる間にてんぷらが D と C を立て続けに通す (やばい)

残っているのが F と G だけになったので自分とてんぷらが F を、けんちょんさんが G を考察することに。数列の値とインデックスの値をまとめてソートして上半分と下半分に分けて考察していくと良さげな方法をてんぷらが思いつく。実際あっていそうだし実装も大丈夫そうなのでやってもらう 通る ここまで 1 時間で相当いいペース

最後は G で、フローである、もっというと燃やす埋めるであることは疑っていたがどのようなグラフを構築したらいいかがなかなかわからない。グラフの頂点が何に対応するかを少し変えて考察するとうまく行きそうなことに気づき、更に同色ペナルティ (伝わって) 制約も二部グラフなので頑張れば表現できる・・・みたいなところに行き着くまで 1 時間以上使った気がする。

実装してもらうも WA が出た。サンプルケースの値を少し変えて実行すると答えがおかしいことに気づく。インデックス周りが間違っているらしい。それを直すと通る！！

結果は全完でオンサイト 1 位。終盤で逆転したので嬉しかった。

この日の懇親会会場は学内だった。2 時間ずっと競プロの話ができて楽しかったです。初めてお話できた方々も多くいてよかった。

Day 2

この日も事前にチームを組んでいた。りかさんとえび君とチームを組んで出ることに。

コンテスト開始。B を最初に読んだが明らかに苦手なのでチームメイトに投げて C を読む。全部のパターンを試せることに気づいて、数字列も (前, 後) のペアの個数を持っておけば高速に処理できるとりかさんにアドバイスをもらったので書く 書き終わるまでに少し時間がかかったが通る

自分が D, H を、えび君が E を担当して、りかさんに他の問題文を読んでもらった。D は y = 0 を考えていたためにサンプルが合わず虚無を過ごしたが通る。その後 E も通る。

H は Day1 G を解いているならかなり楽に書けるため書く 通る 問題演習大事だね。

しばらくして G の解法も思いつく。1 本だけ棒があった際に勝ち負けがどうなるかはわかるため、あとはそれを Grundy 数にして考えればよい。えび君に書いてもらって AC。

その後は F や K, I, L, M などに手を付けたが AC が増えず。特に L をえび君がずっと考えてくれたり、I をりかさんがずっと考えてくれたりしていたが、あまりアシストできなくて申し訳なかった。

懇親会は居酒屋で行われ、他大学の ICPC 事情や今回の合宿のセットの感想などをワイワイ話す。今回は平和に終わったのでよかった。

Day 3

北大セットなのでジャッジ側に回る。 8 時に集合して準備をすすめたにもかかわらずプリンターの速度がおそすぎて A しか刷れなかった (えぇ・・・)

チーム決めも無事終わってコンテスト開始。開始すぐの段階で A, B, C の AC が出て、開始 1 時間時点では 5 完のチームもいた。その後主に G 問題に阻まれ全完が出るのかどうかという展開になったが、まず rickytheta さん (オンライン) が全完。その後 rupc_ohauku チームも全完、結果的にかなり良いバランスでコンテストが終了したので難易度設定はこれくらいがいいのかもしれないなと思った

自分は C, F の Writer と全問題の Tester をやっていました。なんか自分が Writer をやった問題に対して rupc_homu_aishiteru チームが FA をとったので解説時に homu_aishiteru を読み上げさせられる事態になった。 包除原理はぜひ覚えて帰っていってね！

そしてなぜか自分が締めの挨拶をした。運営っぽいことができた。

その後ご飯を食べたりゲーセンに行ったりご飯を食べたりした。大いに懇親できた気がする。

総括

参加者の皆さん、運営さん、ありがとう！！！たくさん楽しみました！！！！！

またお会いしましょう〜〜〜

Codeforces Round #540 Div.3 F1: Tree Cutting (Easy Version)

Codeforces グラフ

問題概要

原文 → Problem - F1 - Codeforces

N 頂点からなる木が与えられ、各頂点は赤・青のどちらかで塗られているか、何も塗られていないかのいずれかである。

木の辺を 1 つだけ取り除き、同じ連結成分内には色が高々 1 種類まで登場するようにしたい。これを達成できる辺の切り方は何通り存在するか？

解説

辺は 1 つだけしか取り除かないので、DFS をして解くことができます。

まず、適当に根を設定して根付き木として考えます。各頂点 v に関して、「 v を根とする部分木内に存在する 赤 / 青 の頂点数」を覚えておきます。これは DFS で可能です。

次に、ある辺を切ったときにできる 2 つの連結成分 T_{1}, T_{2} について、 赤 / 青 がそれぞれいくつ含まれるかを各辺に対して計算します。これは、一方 ( T_1) は DFS 時に得られた値を使えば良いですし、もう一方 ( T_2) は全体から T_1 の情報を引くことで得られます。

f:id:tsutaj:20190302224746j:plain

どちらの連結成分に関しても、どちらか一方のみの色が含まれている場合、それは条件を満たす辺のひとつです。

ソースコード

const int S = 300000;
int cntR[S+10], cntB[S+10], col[S+10];
int ans;
vector<int> G[S+10];

void dfs(int cur, int par=-1) {
    if(col[cur] == 1) cntR[cur]++;
    if(col[cur] == 2) cntB[cur]++;
    for(auto to : G[cur]) {
        if(to == par) continue;
        dfs(to, cur);
        cntR[cur] += cntR[to];
        cntB[cur] += cntB[to];
    }
}

void dfs2(int cur, int par=-1, int root=0) {
    for(auto to : G[cur]) {
        if(to == par) continue;
        dfs2(to, cur);
        int R1 = cntR[to], B1 = cntB[to];
        int R2 = cntR[root] - R1, B2 = cntB[root] - B1;

        bool ok = true;
        ok &= (R1 == 0 or B1 == 0);
        ok &= (R2 == 0 or B2 == 0);
        ans += ok;
    }
}

signed main() {
    int N; scanf("%lld", &N);
    for(int i=0; i<N; i++) {
        scanf("%lld", &col[i]);
    }

    for(int i=0; i<N-1; i++) {
        int a, b; scanf("%lld%lld", &a, &b);
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(0);
    dfs2(0);

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