hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

CODE FESTIVAL 2018 参加記

CODE FESTIVAL 2018 に参加しました。予選は 2 年前から参加していましたが、3 度目の正直で今回やっと初めて本戦に参加できました。感想をいろいろつづります。

予選

予選 A で解けるタイプの DP が運良く出たので、通過しました。予選 B が結果的に早解き勝負になったことを考えると、 A で通ってよかった・・・。

0 日目 (前日)

前泊をしないと当然間に合わないため、前日から移動した。交通機関の遅延などもまったくなく、特に問題なく宿までつけてよい。

同じく前泊していた ixmel さんとラーメンに行った。ラーメンは活力。

明日は朝早いのでさっさと寝る。

1 日目

起床と朝食を AC して幸先が良い。いざ UDX へ!

恒例 (なのかな?) のオープニングムービーで自分の ID が流れて胸熱だった。本戦に来た感が出て良いですね。開会式が行われた後、早速コンテストへ。どうやらパーカーのボーダーは 1400 点 (前から 4 完以上) らしい。去年の THANKS ではあと 1 問通せず逃したけど、今年は獲得していきたい!!

コンテスト

注意: ネタバレを多く含みます

基本的に前から解いていくことに。というわけで A をやるも WA (は?) よく考えたら 2540 は偶数なんですよね、初見さん? 直して AC (09:09)

続いて B をやる。計算自体は単純だけど誤差が明らかに怖い。試しに普通に double で計算したら WA (それはそう)。あぁこれもしかして  x \times 10^{-y}  (x \in \mathbb{R},  1 \leq x \lt 10, y \in \mathbb{Z}^{+} ) の形で管理すればいいのでは?めんどいなあ、と思いつつ実装。AC (35:19) 解説でも言われてたけどこんなことしなくてももっと楽に処理できますね、反省。

C を見る。なんか面倒だけど難しくはなさそう。一次関数を殴りたいお年頃なので CHT で殴って AC (58:32)

あと 1 問でパーカーだなぁと思いつつ D を見たけど普通に難しい。真ん中を固定してやって  K (←文字の種類数) 一つオーダー落ちないかなぁとかいろいろ考えたけど (しかもそれで解けるらしんだけど) わからず。これはだめ。とりあえず次を見る。

E を見る。どう考えても DP だと筋が悪いので他の解法を考える。サンプルを実験すると、なんか区間 min をしまくれば良い感じだったので遅延セグ木で殴る。AC (88:02) どう考えても遅延セグ木いらないんですよね・・・さっきから殴ってばっかじゃないか?

F を見たけどむずかしそう。順位表見てもあまり解かれてない。困ったなあ 〜しばらく虚無タイム〜

G がそこそこ解かれているので見る。サイズが小さいグループには数が大きいものを割り当てたら得だよな・・・みたいに考えてたら降順ソートからの DP が生えた。これ 3 乗っぽいけど枝狩りできるよなぁと思って書いたら通ってウケた (153:56)

余った時間でもう一度 D を考えるもやっぱりわからない、そのままコンテスト終了。

結果は 37 位 / 100 でした。レートの割には健闘したのかもしれないけど、解きたかったものが解けなかったのは悔しい。でもパーカーとれたのはかなり嬉しかった。

各種コンテンツ

AI battle が行われていた。1 週間でここまで実装できるんですね・・・。

あとはルービックキューブとかマリオカートとかあったけどあまり見ていない。コネクションビンゴを早々に 1 行埋めてあとはひたすらおしゃべりしてた。

りんごの挑戦状、初めてみたけど面白かった。栃木には栃木さんが多いらしい。

チームリレー

本戦初参加だったので当然チームリレーも初参加でした。自分は Team D でした。

前半を自分と tsukasa_diary さん・enjapma さん・omochana2 さん・xxkiritoxx さんで分担して、さらに怒髪さんが前半全体を統括、そして後半を DEGwer さん・maroon さん・satashun さん・dnk さんが見てくれた。強い人たちの考察を間近で見れて、圧倒されました。実装も早いし知識も豊富だしバグ直すのも早いし、さすがですね・・・。

結果は優勝!なんと A5 宮崎牛をゲットしました。競プロをやっていると高級肉が食べられる、最高。

その後懇親会で楽しんで、全日程終了。あっというまでした。

終了後

その日にあったばかりのてんぷらさんとサシ飲みをした。懇親会後だけど普通にがっつり飲み食いした。たのしかったー

まとめ

本戦はやっぱりアツかった!来年もこどふぇすで会いましょう!!!!!!

競技プログラミングで黄色になるまでにやったこと

先月末に、めでたく AtCoder 黄色になりました。

きのう、ふと「黄色になりました記事書いてないなぁ」と思って雑に呟いたら、書いてくれという圧力声援を感じたので、記していこうかなと思います。記事の特性上自分語りしかありませんが、それでも良い方はお読みいただければと思います。

続きを読む

ACPC 2018 参加記

会津大学プログラミング合宿 2018 に参加しました。ACPC は実は初参加です。

0 日目

JAG に行っていたので東京にいた。TIke さんと seica さんと ferin さんと olphe さんでボドゲカフェに行ってあそんだ。ワイナリーはワイン農家をやめた者が勝つゲームだった (いやプレイングが悪かったのもあると思うけど)

その後夕食を食べに行ったが seica ちゃんが限界をしていておもしろかった。夕食後解散になったが実は宿を取っておらず (は?) 東京駅近くで適当に発見したネカフェに泊まった。これがまた結構あたりを引いて、ネカフェなのに完全に個室だしコインランドリーはあるしシャワーも追加料金なしで使えてとてもよかった。次に東京行くときはまたお世話になります。

1 日目

東京からバスで会津に移動。会津に着いてバスから降りた瞬間 olphe さんと waku 君に遭遇したので一緒に会津大学まで歩く。けっこうあるくね

この日のチームはランダムに決めていただきました。pachicobue さん、tubuann さん、moritaoy さんと 4 人でチームを組みました。自分は C の篩書くやつと E の虚無 DP と B の戦犯を担当しました。(制約をよく読まずに、積分するみたいなミスリードをしてしまい多大な迷惑をおかけしました・・・)

解説聞いたら E は貪欲でも解けるらしいんですが貪欲が世界一苦手なのでしょうがないね。あと不可能が 2 〜 3 問あっておもしろかった

この日の懇親会は中止でしたが、宿が近い人たち 10 人くらいで集まって中華料理屋行って魔女ラーメンを食べてきた (魔女なので (いいえ))

2 日目

5 時間の会津セット、この日は事前にチームを組んでいて、drken さんと TIke さんと一緒に出ました。

自分は D を担当したんですが FA が取れなくてかなしいね。あと G は結構悩んだのですが場合分けすれば簡単に解けてしまい、場合分け力のなさをかんじた。あとは TIke さんとペアプロしたりしなかったり、一緒に考察したりしなかったりしてました。後ろの問題はほぼ drken さんが通していました (流石すぎる・・・)

†懇親会† ではお酒が無限に出るのでもちろんビールをたくさん飲んだんですが、体の許容量が有限だったので破滅しました。記念撮影から記憶が全くなくて気づいたら宿の和室で寝てました。ご迷惑をおかけしました・・・

3 日目

なんか普通におきられたので大学に行った。この日はコンテストの運営でした。やはりコンテスト開始 2 時間前に会場入りする作戦はかなり有効で、今回もちょうどよく準備を終わらせることができました。

特に大きなミスもなくコンテストが無事終わったので、とてもよかった! (ただ、G が既出なのはすいませんでした・・・)

終わった後は TIke さんと シンヤカトー さんと Noimin さんとカラオケに行きました。みんな仕上がってた。次の機会までにまた練習しとくか〜

この日は引き続き会津に泊まることにしていて、まだ行ったことがなかった富士の湯に行った。あれは最高だったね、至急札幌にもつくってほしい

その後帰ろうとしたんですが道中にボウリング場を発見したので 2 時間投げてきてしまった、温泉の後にボウリングをすると汗をかくのでオススメしません (それはそう)

4 日目

適当に観光をした。

あとこの日の宿は郡山で取っていたので郡山まで移動した。爆睡しすぎて駅員に起こされた (もうしわけない)

宿に着いた後に CODE FESTIVAL 予選 A がありましたが、解ける数え上げがたくさん出たので通過した。いえい

5 日目

空港まで移動して、飛行機で新千歳へ。まだ新千歳空港のフードコードが復活していなくてかなしい・・・

そんなこんなで帰宅

作問について

気づいたら自分が作った問題がセットの半分以上を占めていました。RUPC で簡単めにしたらやたら解かれたのでちょっと難しくしましたがそれでもやたら解かれました。合宿のレベルがあがっているのを感じますね。

B 問題

北大の B 問題は難しい説、そろそろ定着しそう (ア

あるデータ構造で管理するとクエリ O(1) で処理できて嬉しいです。他にも想定解はあったのですが、クエリ平方分割は完全に想定外でした。

正直なんでこの問題が生えたのかよくわかってません。生えるときは生えるんですよね、作問って・・・

E 問題

5 秒くらいで適当に思いついた問題です。分かる人にとっては解法まで一本道でいけると思いますが、コーナーケースにひっかからないように気をつける必要があります。実際、コーナーで引っかかった人は多かったようです。

F 問題

最初思いついた問題文が解法を隠しきれていなくてアレだったので、頑張って問題設定を考えた結果こうなりました。それなりに隠せたのではないかと自負していますが、隠しすぎて想定解通りに通してくれた人がほとんどいませんでした (ア

G 問題

ありがちな問題設定なので事前にかぶっていないかどうかこちらでも調べていたのですが、どうやら既出だったようです。すみません・・・。 コンテスト中に beet さんからこの問題の解説記事の印刷クエリが飛んできてすべてを察した

元々は unique でない数え上げをさせるつもりでした。ちなみに unique でない場合についても、真面目にやれば  O(|S|^2) で、若干手を抜いてデータ構造に頼っても  O(|S|^{2} \log^{2} |S|) くらいになります。興味があれば考えてみてください。

総括

合宿は楽しみながら圧倒的成長できる最高コンテンツですね (再確認)

来年もいくぞー!!!