hogecoder

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

ACM-ICPC 国際大学対抗プログラミングコンテスト アジア横浜大会 参加記

大会参加記 ICPC

2019/11/16 〜 18 に行われた ICPC アジア横浜大会 に参加しました。

Day 0

鳥取の学会に行っていたので、鳥取から横浜まで夜行バスで移動しました。所要時間は 11 時間 (つらい)。あまり寝られなかったので AOJ-ICPC の問題を考察してました。

Day 1

午前 7 時くらいに横浜到着。ネカフェでシャワーを借りたり駅で昼飯を食べたりして会場に向かった。

序盤の英語フェーズにもさすがに慣れてきた (言うことがある程度決まっているため)。

知っている人とお話したり Practice をやったりしていたら一日が終わった。

中華、うめ〜

さすがにバスの座席での睡眠だけで身体が持つわけはないのでちゃんと寝た。布団で寝ると・・・気持ちいいな！

Day 2

ちゃんと起きて、前日に会場でもらったカツサンドくん etc を食べてからコンテスト会場に行った。

緊張するな〜と思いながら過ごしていたらコンテスト開始時間が急に 5 分早まって緊張がどっか行った。

開始直後は B, C, D, E の問題文を読んでいた。B は面倒そうだけどできそう (あとで実装してそこまで面倒でないことがわかった)。C は解きたい。D は解きたくない (自分に正直)、E はぜひ解きたい、という感じ。

A が AC された後に B を実装した。例年 B 問題で異常にハマりがちだったんですが、今回は一発で AC できた。

その後はずっと E を考えていた。しばらくすると H ができそうとのことだったので見てみると、たしかにできそう。実装方針が最初破滅していたがマシな方針を提案して、TAB 君に書いてもらう。少々詰まったが AC、えらい

G もなんかできそうとのことだったので見てみた。TL がギリギリっぽいので余計な log とかはつけれないよなあと思いながらマシな実装方針を提案して、えび君に書いてもらう (自分は方針言ってるだけで実装なんもしてない・・・)。これも AC したのでえらい

E はほとんど何もわからなくて、非常に面倒な二乗解法を思いつくも落ちてしまった。あとで自宅番兵さんに解法を聞いたら天才的解法だったので完全に敗北した。公式の解説スライドはよくわからなかったので読み返したいですね。

解説を聞いた感じだと I をまともに考察してなかったのは痛かったなぁと思いました。

懇親会では、昨年あまり肉が取れなかった反省を活かして早めに肉を取りました。JAG バッジをもらったり Google のブースで配っていた問題トラップにハマったりしていた。

その後は北大勢で打ち上げをして、宿に戻った後も †酒†

酔った状態で海中を探検すると帰ってこれないので気をつけてください。

Day 3

企業見学に行った。最初は HUAWEI でした、コンピュータビジョンの話がたくさん聞けた気がする。

次は NEC でした。思ったより自由なんだな〜というのと、ビルの一階にある展示がすごかった。

最後は †しながわ水族館†

これが企業見学なんだよなぁ・・・ (楽しかったです)

まとめ

これで ICPC の現役生活が終わりました。ここまであっという間でした。今後は OB として大会をサポートしていけたらなあと思っています。来年また ICPC 会場に行くことができたら、現役の皆さんとお会いしたいです。

良い大会をありがとうございました！楽しかったです

PCK 2017 本選 5: 朝昼晩ごはん

AOJ グラフ

この難易度帯にしては難しいなあと思ったら、自分の解法が想定と違った。

問題概要

日本語なので原文参照 → Aizu Online Judge

解説

人 i と人 j の食事の時間を同時に満たせるかどうかを考える。この判定は if 文で容易に行える。

さて、元の問題は「 S に含まれる任意の人の組 (u, v) について、食事の時間を同時に満たせるような人の部分集合 S のうち、集合の濃度 (サイズ) が最大のもの」を求める問題であるが、 i と j が食事の時間を同時に満たせるときに (i, j) 間に無向辺を張るものとすると、 S に含まれる頂点は完全グラフを成す、すなわちクリークである。今回はサイズが最大のものを答えるので、つまりは最大クリーク問題である。

グラフ G における最大クリーク問題は、 G の補グラフ (隣接関係を逆転させたグラフ) において最大独立集合と等価である。枝狩りすると今回の制約でも高速に解けるため、AC できる。

ソースコード

// 最大独立集合問題ライブラリ 省略
int main() {
    int N; cin >> N;

    vector<int> ast(N), aet(N), hst(N), het(N), bst(N), bet(N);
    for(int i=0; i<N; i++) {
        for(int j=0; j<6; j++) {
            int h, m; cin >> h >> m;
            int t = h * 60 + m;
            if(j == 0) ast[i] = t;
            if(j == 1) aet[i] = t;
            if(j == 2) hst[i] = t;
            if(j == 3) het[i] = t;
            if(j == 4) bst[i] = t;
            if(j == 5) bet[i] = t;
        }
    }

    Graph<int> G(N);
    for(int i=0; i<N; i++) {
        for(int j=i+1; j<N; j++) {
            bool isc = true;
            if(aet[i] < ast[j]) isc = false;
            if(aet[j] < ast[i]) isc = false;
            if(bet[i] < bst[j]) isc = false;
            if(bet[j] < bst[i]) isc = false;
            if(het[i] < hst[j]) isc = false;
            if(het[j] < hst[i]) isc = false;

            if(!isc) {
                G[i].emplace_back(j);
                G[j].emplace_back(i);
            }
        }
    }

    MaximalIndependentSet<> mis(G);
    cout << mis.solve() << endl;
}

ACPC 2019 参加記

勉強会参加記

会津大学競技プログラミング合宿 2019 に参加しました。昨年に引き続き、2 年連続 2 回目の参加でした。

Day0

JAG 夏合宿 (参加記へのリンク) の後だし、休むか・・・と思っていたはずなんですが、昼からひたすらボドゲカフェでボードゲームをし、やよい軒で優勝し、泊まるために適当に寄ったネカフェがオープン席しか空いておらずオープン席で浅い睡眠を取る始末。休むどころか体力を消費していませんか？？？

Day1

早朝に東京から会津へ向かうバスで移動。なんだかんだだいぶ疲れていたのでひたすら寝た。

時間ギリギリすぎてタクシーを使って大学に来たら風船を持った会津勢に遭遇。tubuann さんに会場まで案内された (ありがとう)

自己紹介とスポンサーセッションを終えて、コンテストへ。チームメイトが決まっていなさそうだったりあんさんに声をかけて組んでもらうことになった直後に、tubuann さんが組みたいと言ってくれたのでその 3 人でチームを組むことになった。

チーム名は acpc_tubutsutatkb です。由来は内緒です。

競技プログラミングをしてレートが低い順に前から問題を開いて解く戦略にした。自分は A を読んで、解ける問題だったので通す。FA は逃した。ゆるせね〜

B はいつの間にか通っていて、C は SCC を貼るといけるとりあんさんに言われたので自分が実装して通した。

C を書いている間にりあんさんが D を、tubuann さんが E を詰めていた。自分が代わる代わる解法の相談に参加していた。りあんさんが D を通していたり tubuann さんがソートでうまく行くことを証明して通していたのでこの辺はほとんど何もしていません (すみません・・・)

F はとりあえずそれはそうみたいな解法が生えて、tubuann さんが書いたが TLE した。しかもこれは制限時間 +0.2s くらいの TLE だったのでなんとかなりそうな見た目だった。闇みたいな高速化を色々試したが惜しくも通らず残念。

G はフローだろうなぁという話をりあんさんとしていて、考察してはコーナーを見つけを繰り返していたらコンテストが終わっていた。悲しいなぁ・・・

夕食はステーキ宮でした。

ホテルに帰ったらロビーにボドゲ勢がいた。ビール飲みながら観戦してた。

Day2

この日は事前にチームを組んでいて、idsigma さんと olphe さんと出た。

なぜか自分が C 問題の担当になったので読む。数学ですが・・・角度の計算どうするんだ、となったけど冷静になると atan2 という関数がありましたね。olphe さんに少し確認を取りつつ AC した。割と速い方だとは思うんだけど FA は逃していた。ゆるせね〜

M がめちゃくちゃ通されていたので見る。そんなに簡単でもなくない？と思いつつも二項係数っぽいので式を書くとできそうな気持ちになる。olphe さんに渡して AC

H, I あたりが解けそうだけどすぐにはわからない。しばらく考えたら解けたのでどっちも書いて通した ( ModInt を二回連続で貼った)。このへんは結構仕事できてよかった

自分が H, I あたりをやっている間に idsigma さんと olphe さんが G を詰めてくれて、出したら一発で通った。ありがたい

ここからはしばらく停滞したものの、「もうこれで一回提出して情報を得ても良くない？」ということで E を投げたら通って草。さらに L のバグも直って一発 AC。書いた idsigma さんが偉すぎる。

その後は F を解こうとして自分の CHT を olphe さんに渡して一緒にコードを書くもサンプル +α くらいしか通らなくてコンテスト終了。これが解けていればオンサイト優勝だっただけに悔しいな、ありえね〜

解説が終わると懇親会がはじまりました。

いくらかおもしろいことがおこったようですが自分は記憶がないのでわかりません (は？)

真面目に書くと写真撮影の前に机などをどかすところまでは覚えていて、その後は・・・という感じです。気をつけましょう。

Day3

なんだかんだ朝 5 時半くらいに普通に起きて、いろいろ身支度をして会津大学に向かう。

朝会ったら「元気そうで安心しました」みたいなことを何度も言われましたが、当の本人は何も覚えていないため、普通に反省をしました。

この日はジャッジ側だったのでセットについて簡単に感想戦をします。

北大セットについて

まず HUPC 2019 (参加記へのリンク) の影響で問題ストックが割と減っていて、なおかつ新しく生やしている時間も無いし、正直かなり困っていました。そこで過去に出ていた原案をかき集めたら意外となんとかなりそうだったのでそのまま問題を決めました。こういう経緯もあって、原案が 1 年前だったとか、そういう問題が半分くらいあります。

自分は A, D, G の Writer をしたのと、F の高速化 (制約を上げた)、全問題の Tester をしました。それぞれ簡単に触れておきます。

A 問題

元々は別の問題が assign されてましたが 1 ヶ月前くらいに ABC で全く同じ問題が出てしまって使えなくなりました。そこで自分が A 問題枠を 3 問くらい適当に生やしてその中から決めることにしたのですが、これはそのひとつです。それ以外は特にいうことないです。

B 問題

問題文担当がつらそうでした。要求されるのはほぼほぼ実装力です。

C 問題

例のケースは Writer が突然思いついたもので、追加したら Tester 全員の解法が落ちてウケました。注意力がないとペナが生えるので注意力は大事なんですが、今回に関しては一発 AC が誰もいなかったのでペナルティの意味がなくなりました。

D 問題

総和を求める桁 DP ってあまり見ないかも、と思って作りました。もっと解かれるかとも思っていましたが、最終的にはいい感じの AC 率に収まったようです。

E 問題

開催 3 日前くらいに既出を指摘したんですが、どう考えてももう少し早く言うべきで (JAG 関係で余裕なかったから許してほしい・・・)、どうにもならないのでそのまま出しました。抽象化の練習にご活用ください。

F 問題

最初の計算量は O(|S| \log |T| + |T|^{2}) くらいだったんですが、速くできたので出しました。EF 続けてギャグみたいになってすみません。

G 問題

1 年前に生やした問題で、解法を書きたくない + テストケース作りたくない + 問題文書きたくない が原因で放置されてました。ストックの枯渇により泣きながら出しました。コンテスト中に二乗解法が通された。ありえね〜ゆるさね〜 (話を聞いたところほぼほぼ AC 解法だったので、まぁよかったのですが)。甲子園をテレビで見ながら Tester 解を書いた記憶があります。どうでもいいね。

全完が残り 10 分前後に出て、なおかつ 1〜2 チームくらいしか全完されない、をひとつの指標にセットを作っているつもりなのですが、概ねうまくいってよかったです。参加してくれた皆さんありがとうございました。

おわったあとは学食に行きました。

総括

酒は飲んでも飲まれるな

今年もコンテスタント側・ジャッジ側両方参加できてよかったです！今回の自分たちのセットがなんらかの勉強になってくれれば幸いです。来年から社会人なので次行けるかどうかはわかりませんが、またどこかのオンサイトでお会いしましょう〜