hogecoder

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

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 チームくらいしか全完されない、をひとつの指標にセットを作っているつもりなのですが、概ねうまくいってよかったです。参加してくれた皆さんありがとうございました。

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

総括

酒は飲んでも飲まれるな

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

JAG 夏合宿 2019 参加記

勉強会参加記

JAG 夏合宿 2019 に参加しました。昨年に続いて二回目で、今年も four-t としてチーム全員で参加しました。今回は作問もすることになったので昨年とは少し違う面持ちで参加した気がします。

Day 1

割と時間ギリギリでオリセンに向かっていると、知ってる顔のひとたちも同タイミングでたくさん向かっていたので一緒に歩く。

去年と部屋違ってビックリ、部屋おおきい。

いろいろとコンテスト前のアナウンスがあったのち、準備してコンテスト開始。

最近は自分が A を解く担当をしているので A をやる。よめない (は？) もたもたしてるとえび君が B 解けたらしいので代わると通る。FA。プロか？

チームメイトと A を確認していたらいろいろ解釈がまちがっていたことがわかる。介護をうけて AC。

C はペナ出しながらもわりと早い段階で通ってよかった。

これ以降で最初に読んだのは E だった気がする。わりと考えた。

TAB 君によると D が解けたらしいので話を聞くと中国剰余定理が必要らしい。中国剰余定理は持ってるので写経する。一応 __int128 を使いながら実装して通った。

えび君がやっていた J 問題の話を聞くと、最小化は二部グラフの最大マッチングやればできそうという話になり、これも持ってるので写経する。通った。

その後 E の解法を TAB 君がひらめいて、重み付き UnionFind が必要というという話になって、これも持っているので写経しようとしたが、持つ値がヤバそう。これ Python でやったらよくない？となって、えび君に Python に移植してもらった。再帰が多くて RE しているようだったがそれも最終的には回避して AC。この辺チーム戦ならでは感があった。

あとはだいぶ冷えていて、2 問おしかった

  • I: 誤差死
  • K: FFT の工夫がたりなかった

この辺詰められるようになりたいね

終わった後はご飯と風呂を済ませて、Day3 の準備とかボドゲとかやってた気がする。たのしかった。

Day 2

この日も自分が A を解いた。WA (は？) 冷静になる時間が必要なので代わる。

えび君が E を AC。最初の一問担当、代わったほうが良くない・・・？

冷静になったので A を AC した。

F をかなり考えるがわからない。このグラフ上で最大独立集合すればできるんだけどな〜、無理だな〜、で終わってしまった

TAB 君と自分が F を考えている間に I がいつのまにかえび君によって通されていた。FA らしい。やったじゃん。でもそのすぐ後にジャッジ解の間違いによるリジャッジのアナウンスがあった。結果的に FA は幻となった。かなしいね。

D が無限に通されてるわりにわからんとなるが、流石におかしいので問題をよく読む。解釈を間違えていて、正しい解釈をすると書くべきコードが分かったので書く。通った。

中盤何してたのかおぼえてないんですが多分ずっと F やってた。

最後の方に J を考える。全員でなんとか考えると数式が生えて、さらにこれはラグランジュ補間があればどうにかなりそうなことがわかる。これは持っているので写経する。でも最後の詰めが甘くて、偶奇によって標本を変えないといけないことを失念していて人生終了した。この辺は実力が如実に現れたという感じがしますね・・・。

懇親会があってカツサンドくんを撮ったりおしゃべりをしたり翌日の Writer として紹介されたり哀愁ただようカツサンドくんを撮ったりした。

https://twitter.com/_TTJR_/status/1173173793721765888

https://twitter.com/_TTJR_/status/1173193726329413633

この日にあった ABC で黄色になった (5 回目)。ボーダー芸人を安定させるんじゃなくて黄色を安定させてほしい。

Day 3

Writer なのでコンテスト前にいろいろアナウンスした。この日のコンテスト時間は 4 時間でした。

https://twitter.com/_TTJR_/status/1173471957037154304

A は偶奇でなにかやりたいなと思ったのと、簡単枠が枯渇していたので作りました。A 問題なので本質部分はとても軽く、注意力のほうが重要だったかもしれません。

B はそもそも原案が生えた時点で (合宿に限らず) コンテストに出すかどうかすら迷いました。相談したら、いいんじゃない？とのことだったので置きました。逆から処理するとわりと破滅すると思いますが、実は楽が出来ます。

あとテスターをちょこちょこやりました。個人的にヤバい問題だと思うのは F, G, I, J あたりで、この辺は概ね想定通りの結果となりました・・・。

HUPC が終わって問題が余っていたときに声をかけてくれた not さん、JAG のセットを作るためにたくさん作業してくれた Writer の皆さん、英語の校正や連絡面などでたくさんサポートしてくださった JAG スタッフの皆さん、本当にありがとうございました。当日は特にトラブルなく終わって本当に良かったです。

なお、Day3 の解説は Google ドライブ に上げたので、復習にお役立てください。そのうち JAG の Wiki にも載る、はずです。

以下個人的メモ

持ってないもの

  • 一般グラフ最大マッチング
  • 重み付き UnionFind (や、持ってるんだけど久しぶりすぎて中身がどうなってるか曖昧だったのが非常に良くないし改変しづらそうだったからなんとかする)
  • CHT (や、持ってるけど 復習してない問題 があることに気づいてしまった )

復習するもの

ぜんぶ

その他

疲れをとる (明後日から会津合宿マジ？？？？？)

総括

学びしかなかったです、行って本当に良かったです。会津も行く人はまたよろしくお願いします！