blogskol

思わず声に出して読みたくなるブログ

cpsco2019参加記

はじめに

これに参加して来ました。楽しかったです。

~0日目

初心者の方が初心者向けに合宿を開くというのを見てとても良い企画だなぁと思いました。僕が参加するのは違うかなと思い枠が溢れ始めたのもあって一度はキャンセルしたんですが、強い参加者と作問勢を見て枠が広がった時に再申し込みしました。

1日目

会場は駅から近い割に都会感がなく雰囲気のよいところにありました。会場に着くとたくさんの競プロerがいました。チーム決めからコンテスト開始までが思いの外早く、少し慌ただしかった気がします。

session1(チーム:cpsco_kkd)

てんぷらさんセット。てんぷらさんは前回のyukicoder（僕は解いていないんですが）が好評だったので楽しみでした。

A,B:チームメイトが通していた

C:nからk個選ぶのを列挙するところで詰まっていたので蟻本のp.144を教えた。解説聞いたらもっと簡単な実装があって恥ずかしい。

D:最初dpだと思ったら制約が1e18だったので行列累乗かなと思ったらチームメイトに算数だと言われました。式を見せられたので出したら通りました。

E:最初問題を誤読していてxorセグ木だと思ってました。結局わからず。ならしの概念を知らなかったのでほーんとなりました。まだ実装できてないのであとで書きます。

F:僕の大好きなにぶたん。そのあとは区間スケジューリングかなと最初思ったんですがよく考えたら全然違いましたね。作戦を思いついたのでpqueに乗せて通しました。

G:部分点だけ。本解法も時間があと二時間くらいあれば思いつきそうだったので残念。

H:部分点はlとrの二重ループでいいとチームメイトに言われ残り10分くらいで最大値の個数も持ったセグ木を作ろうとしたんですがバグらせました。

 オンサイト三位なのでまぁ頑張ったかな？苦手なグラフだけないバランスのいいセットだったのでとても好き。というか今回作問勢全員すごい。

アイキャッチA

この日の夜はAGCがあったよ！

CM

drogskol.hatenablog.com

アイキャッチB

drogskolくんおめでとう！

2日目

朝は人が集まり切らないままコンテストが始まりました。AGC明けの朝10:30だから仕方ないね。

session2(cpsco_d_precure)

やむなくくんとゴジラさんのセット。直前にGの配点が変わっていた、辛そう。

A,B,C:チームメイトが通していた。

D:大好物のゲーム問題。面白そうだなぁと思ったらチームメイトが暇になったので渡した。無証明だけど投げますと言って通していた。解説聞いて感動した。

E:グラフ。ぱっと見頑張れば解けそうかなぁと思ったけど先に点数の低いGからいったら戻ってこなかった。

F:設定が金塊ゲームに似てるなぁと思ったんですが（やむなくくんはこの問題を知らなかったらしい）僕はまだ金塊ゲームをACしていないため解説を見たくなく最高得点なのもあり飛ばした。燃やす埋めるらしい（別解もあるらしいけど）のでグラフ。

G:グラフ。蟻本を開いてクラスカル法の勉強を始めました。xが非xの値の間ごとで答えの式c+axが定まるなぁと思いx=0の場合を作った後うんぬんかんぬんをやったはずなんですがダメでした。あまりに要素数の少ないサンプル1と値がでかすぎて調べる気になれないサンプル2しか置いてなかったので自分でサンプルを作ったりしていました。

 チーム5位、個人0完。グラフ＝解けないは甘えなんですが、グラフ三つは悲しい。チーム内レート一位が0完の辛さやばいね。

session3(cpsco_f_groupf)

今回唯一のKUじゃないけんちょんさんのセット。問題を見るのは初めてなんですが、良問が出るんだろうなぁと思って楽しみにしていました。

A,B:チームメイトが通していた。

C:TLEすると言われて問題内容と方針を聞いたところ、いもす法だったので簡単な概要を説明した。いもす法を今回初めて知ったという人は是非こちらの記事を読んで欲しいなと思います。正直1次元だとすごさが伝わり切らない気がするので。

D:僕はパッと見て操作を逆から追うのかなぁと思ったんですがチームメイトが綺麗な方法で通しました。綺麗な問題で好きです。

E:いつものbit毎に考えていいってやつ。特に悩むところもなく実装権が回って来たところでスラスラ書いて、軽くバグを直したら通った。僕的にはDより簡単。

F:全然わからず。部分点は制約的にbitDPっぽいなぁと思ったんですが具体的な解法はわからず、Gの方が解けそうな気がしたためパス。

G:それぞれ最も絶対値が近くなる金額からせいぜい+1くらいしかないだろうと信じて疑わず。テストケースの2/3以上通っていたので多分やりたいことはできていたんですが、コーナーケースに最後まで気付かず。あれ非自明じゃないですか？あと問題設定がなかなか怖いなぁと。

 オンサイトは5位でした。1位も点数は一緒でしたね。綺麗な問題が多くてさすがだなぁと思いました。公式writer待ってます。

アイキャッチA

なんとこの日もAGCがあったよ！

CM

 

アイキャッチB

drogskolくんはno sub撤退だったね

3日目

少し参加者が減りました。寝不足が続き体力的に少しきつくなりつつも唯一の個人回なので頑張りたいところです。

session4(drogskol)

chocoruskさんのセットでした。1-2-3-4-6-8なのでなるべく6まで、できれば8までを目標にしました。

A:算数。こういうのの早解き苦手。

B:これむずい。O(ND)を考えて数秒固まったのち制約を見てAC。

C:実はFAを狙って最初に開いたんですが、N/3チーム作るのかと思って無理だーとなり撤退。問題文が悪いわけではないんですが競プロ脳にやられましたね。AB解いた後順位表を見たら無限人が通していたので慎重に問題文を読み直してAC。にぶたんで書いたけどしゃくとりの方が実装楽そう。

D:大好きにぶたん。実装もそんなに難しくなかった。

E:Dまでがスラスラ解けたので調子に乗っていて、3秒で思いついた解法を提出したらWAになって真顔に戻りました。問題内容の整理をした後紙に書きまくっていたらなんかそれっぽいのが出たので実装しながら詰めました。実装中に考えていたので提出したコードには一度も使われない変数などがあり相当汚いです。4WAののちAC。解説により僕の場合分けに無駄がかなり多いことがわかりました。

F:残り10分だったので気楽に見ました。面白い問題だなぁと思ったんですが全く解法はわからず。解説もまだ理解し切っていないのであまり語れない。

 Dを通した時点ではおそらくオンサイト2位だったんですが最終的には4位でした。Fはプロしか通していなかったので５完には割と満足しています。

終わりに

3日間通してとても楽しい合宿でした。運営の方々には本当に感謝です。今回チームを組んでくれた皆さんもありがとうございました。僕にしては交流もそこそこできたかな。これからもこういう企画は積極的に参加していきたいですね。