CPSCO2019参加記(3日目)
この前の
CPSCO2019参加記(２日目) - Tallfallの日記
の続きです。
3日目
最終日で前夜に飲み会があったということで参加者が半減位するかなと思いましたが結構人来てました。
この日は個人戦だけだったので気楽ではありました。
Session4
writerはチョコラスクさん、個人戦とあって難易度は控えめとのことでした(ほんとかなぁ～みたいに思ってました笑)
全体的にかなり必要知識が少なめでいいなぁと思いました。
A - Swimming
長さLメートルのプールを往復しながら泳ぐとき、Xメートル泳いだ時の位置を答える問題。
格好つけて絶対値とか使おうと思ったら時間かかりました。
提出:
Submission #5285008 - CPSCO2019 Session4
B - Meeting
要約すると集合がD(10以下)個与えられるのでそのうち二つの和集合の要素数を最大化する問題。
こう書くとかなり簡単に見えますけど200にしては少し難しめかな？といった印象でした(趣旨的にはその方が良さそう)
NとDを逆にして実装しました。
提出:
Submission #5285153 - CPSCO2019 Session4
C - Make a Team
N人のレートRiが与えられ、チーム内の最大レート差がD以下になるようなチームの振り分け方を数える問題。
modの逆元使わなくていい所がいいですね。見てすぐはマッチングだと思いました。
問題文はちゃんと読もう!
提出:
Submission #5285387 - CPSCO2019 Session4
D - Boring Sequence
数列Aの要素をK個まで変えて同じ要素が連続する長さを最小化する問題、二分探索は比較的見えやすいかなと。
二回目の二分探索だったのでオンサイトの人たちはCが解けていたら大体解けていたのが印象的でした(逆に解けていなかったら次は大丈夫ですね！)
途中で二分探索する対象を間違えて最初に出したコードはKを使っていなかったという...(あほすぎた)
priority queue を使う別解は思いつかなかったです。すごい。
提出:
Submission #5285602 - CPSCO2019 Session4
E - ox Concatenation
与えられたoxooxxxoxのような文字列を与えられた文字列で作れるかを判定する問題。
かなり問題の意味が分かりやすく、解いている時は少しづつ階段を上っているような感じがして楽しかったです。
部分点のboolを持つdpは無駄なことが多いので添え字を一つ削減できる、みたいなのも典型要素で勉強になりました。
提出:
Submission #5286091 - CPSCO2019 Session4
F - Lost Tree
コンテスト中は残念ながら解けなかったです。木の頂点のある部分集合のすべての点対の距離が与えられるのでそれを復元する問題。
解いている時は木の直径みたいなのは出せるけどそこからどうしようかなぁみたいな感じで終わりました。
再帰という発想が出てこなかったのは反省ですね(絶対実装終わってないけど)
どんな時に他の頂点が必要かを考えると比較的ナチュラルな道筋で根から決めていくみたいなのが出るんすかねぇ。
面白かったです。
提出:
Submission #5415083 - CPSCO2019 Session4
A~Dは問題の意味を理解してからほぼすぐに解法は生えてるのに全て実装で詰まって時間をかけたのは本当に改善したいところです。ペナ込みでDまで44分は流石に遅すぎる(実装するだけなのにの意)。
Fすき
Session4が終った後表彰式があって(優勝された方のアカウントはなんとrated未参加(黒)らしい...)、そののちに解散となりました。
終わった後梅田でてんぷらさんラスクさん煎茶さんと寿司としゃぶしゃぶを食べました、優勝できてよかったです。
帰りに蟻本を買いました、鯵本はなかったです。
三日間本当に楽しくて実りのあるイベントでした！主催とwriter陣には本当に心から感謝です。参加者の方々もほぼ初対面の方ばかりでしたけど競プロerは優しいですね...皆さん有難うございました。
来年あればwriterお手伝いできるくらいには強くなっていたいものです。
