ICPC2019 アジア地区横浜大会 参加記
11/16~18に行われたICPC2019アジア地区横浜大会に参加しました。
ICPC 2019 Asia Yokohama Regional
〜前日
国内予選が終わってから特に何もしてなくて、何もしないまま当日を迎えるのは怖かったので、チーム練は今年のJAG夏合宿の問題で3セットやりました。
ICPCに何年も出ると、チーム練で使える問題が枯渇しがち。
day1
朝から新幹線にのって横浜に。
ICPC楽しみすぎて全然眠れなかった〜〜〜😭😭😭😭😭😭😭 pic.twitter.com/DGOYWZPPmD
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月15日
名古屋コーチン食べたしICPC名古屋大会優勝!w pic.twitter.com/f3uTBYd8g7
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月16日
横浜駅の地下においしい親子丼があったので実質ICPC名古屋!w
(ところで後から知ったんですが、今年のしまじろうコンサートは愛知だったらしくて、縁みたいなのを感じました)(いいえ)
我々がこうしてICPCの準備をしている間にも、愛知県ではしまじろうコンサートが
— くりんぺっと (@climpet) 2019年11月16日
チームメイトがいません… pic.twitter.com/mmQ2ApGb8m
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月16日
会場についてチームメイトと合流し、レジを済ませる。
他大学チームと久しぶり〜〜〜〜〜をしているとアナウンスが始まって急いで席に戻る。
practiceは4問だった。
forループがどのくらい回るかとか、メモリサイズを確かめたりとか、スタックが無限という話をほんまか?とかいいながらdfs書いたりしてた。
何か印刷しようという話になって、一番美人な人が届けてくださいみたいなことを英語で書いたものをチームメイトが印刷しようとしてた。
practiceが終わって、チーム紹介が始まる。スライドで間違い探しするやつ好き。
去年はカツサンドが配られたけど、今年はカツサンド弁当にグレードアップしていた。
解散したあと、ツイッターの知り合い10人くらいと中華街に行く。
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月16日
中華街 pic.twitter.com/5Si9aDt8RG
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月16日
おいしかった。
駅に向かう途中、みんなでタピオカを買う。
初タピオカだったんですが、あまりのおいしさに、感動……
中華街散策したり赤レンガ街に行ったりして青春をする。
✨最高✨ pic.twitter.com/L4IVReOvDw
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月16日
ホテルに帰るとABCが終わっていたので、ABCばちゃをしてから就寝
day2
夜景の赤レンガも良かったんですが、夜景じゃないのも見たかったので朝から行く
asa! pic.twitter.com/k5JV6YuWHi
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月16日
街がICPC歓迎ムード pic.twitter.com/2pH1Uj6NrQ
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月16日
会場についてチームメイトと合流してから荷物チェックを受けて席に向かう。
筑波の人とめちゃくちゃ喋った。
コンテスト開始5分前にコンテストが始まる。(「こどふぉる」の対義語ってなんですか?誰か教えてください)
とりあえずAを読むことになっていたので、読む。難しい。
考えると「×3」を連続で何回か適用して、「×1/3」を連続で適用するのが最善なので、書く。バグる。
辛い気持ちになりながらデバッグし、pcをBの人に譲る。
Bもつらそう。Bも実装がうまくいかないみたいで、何度かpcを代わったりしているうちに、Bが通る。
Aも実装の仕方をちょっと変えてAC。この時点で1時間ちょっとが経過。
順位表を見て、Hに向かう。Hは括弧列を追加したり削除したりしながらvalidな区間を数えるもの。
削除があるので、構文解析みたいにdfsで探索して削除のときに前の状態にもどれるといいよねってなって、それを書く。
ちょっとバグらせながらサンプルがあったので提出するとREで、確かに添字がごちゃごちゃしてるからな〜とか言って印刷デバッグ。その間にEやGを考えてもらう。
Eができそうらしいので、Eを書いてもらうけど、こっちもやばそうで、サンプルがあわないらしい。
いろいろあって、HのREが配列外参照ではなくスタックオーバーフローが問題(???????)らしいことに気づく(開始4時間過ぎくらい)。再帰を使わないコードに書き換える。投げてAC。
そのままコンテストが終わる。
荷物を持って会場を移動。外が寒い。
英語がわからないのでツイッターをして過ごす。眠いなーとか思っていたらyes/noが始まる。
去年は凍結後に提出をしなかったのですが、自分のチームがyesって言われると、嬉しい。
3完50位でしたー
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月17日
ギリギリで通ってアツかった pic.twitter.com/XentKirFdz
応援していたUKUNICHIAが4位ですごかった。(まだyoutubeの中継みてないので、後で見ます)
コンテストをしていた会場に戻って懇親会。マスコットで交流したり、企業ブースをまわっていろいろもらったりした。
中盤からみんなGoogleの問題に夢中になってあまり話しかけられず………
— idsigma (@IKyopro) 2019年11月17日
個人情報を配慮しました pic.twitter.com/OJoGcVLjXb
— th“Xuelei”_yucpc (@xuelei7) 2019年11月17日
— しーある (@cs_c_r_5) 2019年11月17日
これは懇親会で3Dになったティッピー pic.twitter.com/iA9q4sZvqP
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月17日
懇親会が終わった後、2次会でカラオケに行った。
2次会でリステ縛りカラオケしてたんですが、最後に367Days歌って優勝した pic.twitter.com/ZPHSoUUyR2
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月17日
367Daysは「みんなで力を合わせて夢を実現して、そしてこれからもみんなで先を目指して頑張っていく」みたいなテーマの曲で、ICPCみたいなチーム戦の大会にはぴったりの曲すぎる。最高。みんなで力を合わせて国内予選を突破して、そしてみんなで世界大会を目指してほしいね、KiRaReに。
day3
企業見学なので、しながわ水族館に行きます。
行くぜ!(ガタッ pic.twitter.com/qFdyhR727N
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月18日
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月18日
イルカショーを見てすげーって言ってた
たのしー pic.twitter.com/KL1aZ7WbTY
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月18日
そのまま水族館の横で昼食
水族館で食べる海鮮丼は最高だなあ〜〜 pic.twitter.com/n4EDAfLCEF
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月18日
水族館ではしゃいだ結果、疲れ果てたうさぎの図
対あり pic.twitter.com/hYBlrJIZj1
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月18日
体力があって元気な朝に水族館行けたの、良かったな
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月18日
水族館とても良かったので、次は動物園とかどうですか?
動物園で時間制限あり幸福度最大化問題を解きたいです!!
運営さんへ
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月18日
来年は上野動物園とかどうですか
当方上野動物園未経験です
https://t.co/aO9YwClNMl
ご飯を食べて、新幹線で帰る。在来線が事故でストップして帰宅困難になりました。
今日でICPC引退、ICPC楽しかったです!青春をありがとう!!
— そすうさ@ICPC横浜 (@wk1080id) 2019年11月17日
topcoder SRMに初参加してみた
topcoder登録
難しいと聞いていたんですが、そこまで難しくなかったです
- topcoderのトップページ右上のcommunityをクリックし、competitive programingの「take me to the coders!」をクリックする
- ページ中部のLaunch Arena(beta)を選ぶ
- ログイン画面になるので、一番下の「NOT A MEMBER YET? JOIN NOW」を押していろいろ入力して登録する
- 送られてきたメールのリンクをクリックして終了です
初めてのSRM!でるよ! pic.twitter.com/9e7vhVaosW
— そすうさ(素数うさぎ) (@wk1080id) 2019年10月10日
コンテスト
75分で3問を解いて、それが終わってからchallengeフェーズがあるので、75分間は問題を解くことに集中できます。嬉しい。
指定された名前のclassをつくって、その内部に指定されたmethodを作る必要があります。事前に問題を解いて練習しようね!
class $CLASSNAME$ { public: $RC$ $METHODNAME$($METHODPARMS$) { } };
言語は初期設定はJavaになっているので、変更する場合はコードを書く欄の左上の歯車マークから選択します。
直書きしないでローカルで書いてちゃんとサンプルを試す!(素振り)
— そすうさ(素数うさぎ) (@wk1080id) October 10, 2019
SRMさんいままでありがとうございました(完)
ACPC2019(会津大学競技プログラミング合宿2019)参加記
会津大学競技プログラミング合宿2019 : ATND に参加しました。
day0
6時間かけて関西から会津に移動
#acpc2019 前泊行くぜ!(ガタッ pic.twitter.com/y2HAEgu5DP
— そすうさ (@wk1080id) September 17, 2019
きた!#acpc2019 pic.twitter.com/7bmIBkZj5T
— そすうさ (@wk1080id) September 17, 2019
前泊組で喜多方ラーメンを食べる
#acpc2019
— そすうさ (@wk1080id) September 17, 2019
来夢で喜多方ラーメンたべてる(with @rsk0315_h4x , @wakuwinmail_C , @hazhihazhi ) pic.twitter.com/vagzpXGKvv
ホテルにチェックインしてのんびりする
day1
無料朝食を食べる
†大学の金†で食べる健康的な食事#acpc2019 pic.twitter.com/Kvio0y46dU
— そすうさ (@wk1080id) September 18, 2019
早めに大学について学食に行く
来たぜ! #acpc2019 pic.twitter.com/vl1Qeuehps
— そすうさ (@wk1080id) September 18, 2019
学食のソースカツ丼!みんなで!#acpc2019 pic.twitter.com/IkcGtLuGmC
— そすうさ (@wk1080id) September 18, 2019
会津のソースカツ丼は名物らしい、とってもおいしかったです
自己紹介で老害発言をして、コンテストのジャッジをする
day1お疲れ様でした#acpc2019 pic.twitter.com/BM3WItmaoF
— そすうさ (@wk1080id) September 18, 2019
3人でジャッジをしつつ風船配りをするの、体が足りなくて、自分が合宿に参加し始めた頃の北大はすごかったんだなあという気持ちになっていた
さあ,コンテストも終わって夕食開始だ!とあなたは意気込んでいるところかもしれないが,ちょっと待ってほしい.一つだけ先に忠告しておくことがある.それは駅への道に潜む謎の店舗,肉のプロ・ステーキ宮の存在だ. #ACPC2019 pic.twitter.com/pbdu80oYJl
— tsutaj (@_TTJR_) 2019年9月18日
ステーキ小宮 #acpc2019 pic.twitter.com/357162dCUQ
— そすうさ (@wk1080id) September 18, 2019
10人くらいでステーキを食べに行く
open cupの話がおもしろかった
day2
大学についてすぐチームメイトを確保する
メイドさんになった
おつでした@platypus999 さんと @pazzle1230 さんとACPC_PPPで出て、ABCGHIMの7完でした。
— そすうさ (@wk1080id) September 19, 2019
マスコットを担当しました。
コンテストは自明を解いた後は何も貢献できませんでした
懇親会会場までみんなであるいた
fixstars社感謝🙏 #acpc2019 pic.twitter.com/jDCmiWSni7
— そすうさ (@wk1080id) September 19, 2019
レート順に回る円卓 #acpc2019 pic.twitter.com/dB4pwZ4o0S
— そすうさ (@wk1080id) September 19, 2019
#acpc2019 pic.twitter.com/an0qyaptRb
— そすうさ (@wk1080id) September 19, 2019
メニューはいつものなのではいなんですが、参加者が違うといろいろ面白いことがあって、うくさんがびーとさんに乗り移ったみたいに見えた
お酒を無限に飲んでいる人がたくさんいてすごいなあと思った
day3
day3は朝が早くてつらい
1億年ぶりにランダムチームを組みました、新鮮な気持ちになれて良い
ACPC2019 day3コンテストは @C7C7LL さんと @shiro537 さんとチーム「ACPC_futsukayoi」で出ます!
— そすうさ (@wk1080id) September 20, 2019
Bを嘘でぱーっと実装してACできたのはいいんですが、DEのバグをとりきれず、Fで蟻本を見ておきながら文字列をくっつけてLCPすることに気づけなくて最悪をしました
ABCの3完でした…
— そすうさ (@wk1080id) September 20, 2019
学食でお昼を食べて駅まで歩いて、みんなを見送った
day4
観光をしました
まとめ
たのしかったので来年も行きて〜って感じなんですが、来年は社会人で厳しい…………
いろいろな人と話せた気がします、気がするだけです
会津バス北柳原停留所を返して……
ゆるふわ競プロオンサイト #2 参加記
9/14にゆるふわ競技プログラミングオンサイト at FORCIA #2 ゴリラの挑戦状のオンサイトに参加してきました。
コンテスト前
新幹線に乗りながらオンサイト準備
slackにも入ったしHackerRankのアカウントも作った これで完璧
— そすうさ(素数うさぎ) (@wk1080id) 2019年9月13日
新宿駅で迷っていたら着くのがギリギリになってしまいました…。会場にはすでに人がたくさんいました。
きた! pic.twitter.com/21pz5j9siC
— そすうさ(素数うさぎ) (@wk1080id) 2019年9月14日
2時間12問で100点~600点とスピードランみたいなコンテストらしい、開始前にペナがないという話を聞きました。
コンテスト
時系列順で、
A:ifで分岐するだけだなーと思って下までみたらコードを書く欄があって途中まで書いてあったのでそこに直接書いて出しちゃった。
B:やるだけだったのでこれも直書きした。
C:どの列どの行にも1つだけ白いマスを作ればいいんだなーこれはN!!wとか思って直書きしたらCE出たので手元実行は大事だなあと思いました。次の問題からはエディタで書いてます。
D:n-ドイッチすこ。#の個数をもって、|が連続したら答えにして個数リセット、をした。
E:kameの場所はqiなので気にしなくてよくて、usagiはクエリごとにしゃくとり?っぽくして比較すればいいやーって思った。クエリが昇順なのありがたいなあ。
F:あれ、これクエリ先読みしてしゃくとりか?また?クエリ先読みの練習題?とか思ってたら、各暗唱の文字数を前計算しておいてクエリごとにlower_boundでいいことに気づいた。
G:各クエリで範囲Aを全部ひっくりかえして範囲Bを全部ひっくりかえしても等価なので、ひっくり返した回数を持つ2次元配列を用意して、クエリごとに長方形を2回加算して(加算場所は4箇所*2回)最後に累積和。2次元累積和わすれたのでいもす研をググっちゃったけどよく考えると覚えてた(は?)。回数が奇数のマスの総和を出して終了。
H:ゲーム苦手で実験したくないな…と思っていたら、制約が小さすぎたので、dfsで探索すればいいや!wって思ってたらバグらせた。デバッグ出力とかしてたけど、わからないまま残り時間があまりなかったので後でデバッグしようとして次の問題に進む。
I:なんだこれ…と思ったけど制約の「少なくとも2つは1」を見て、じゃあ各味について少ない人から貪欲にすれば、箱の数にぶたんでできるじゃーんって言って実装した。ピノ食べたことないので、バニラ10アーモンド7チョコ7で固定されてるの意味わかんなくて、これ与えれば良くない?ってずっと言ってた。
J:サイズが大きいので愚直DPはできなくて、500を使うんだな〜となる。DPの遷移は一定なので、これ行列累乗で高速化できるね!とか言ってたんですが、これは実は縦が10^9以下の奇数、横が500だと誤読していて、ずっと合わないなーとか言ってた。誤読していることに気づかなくては?とか言いつつ次の問題を見る。
L:Success Rateを見てKよりLを優先した方が良さそう?と思ってLを開く。なんかWUPCで似たようなの見た(ACはしていない)なあ*1とか思ったけど、わかんないからフローか?とか言ってた。
K:trieだと構築でTLEしそう、じゃあSAか?とか思って考えてたんですが、存在しなくて自分より後ろを調べるときに愚直に1つずつ見る以外の方法が思いつかなくて、1つずつ見てたらTLEしないか?ってなって、じゃあどうすんの、って思ってた。
最後まで問題見たあと残った時間が10分くらいしかなかったので、デバッグしたりしてた。
#ゆるふわコンテスト
— そすうさ(素数うさぎ) (@wk1080id) 2019年9月14日
ABCDEFGIの8完でした
頭が悪いので画面にコードが途中まで書かれているとそこに全部書いてしまうんだよな、最初の方は直書き+サンプル試さずに投げてた
— そすうさ(素数うさぎ) (@wk1080id) 2019年9月14日
この画像からはわかりませんが(AtCoder ID が書いてある人はオンサイト参加者の一部)、オンサイト順位はけっこう良さそうに思える。わーい!
コンテスト後
prdさんがほぼ全ての原案をしたと聞いて、すごいなあと思いました。問題を思いつく秘訣を聞けばよかった。
Lの解法が天才すぎて、こういうのコンテスト中に思いつきたいなあって思った。
オンサイト優勝者と各色ごとの優勝者には賞状と賞品のバナナが渡されていました。さすが「ゴリラの挑戦状」…
懇親会ではピザが出ました。美味しかったです。FORCIA社ありがとうございます!!!!
懇親会のようす pic.twitter.com/OImkhfjLH2
— そすうさ(素数うさぎ) (@wk1080id) 2019年9月14日
懇親会でホワイトボードアンケしてたんですが、参加者は競プロ歴~2年くらいの人が多かったみたいです。
感想
日程がJAG夏合宿と被っていたのですが、そのぶん普段オンサイトで会えない人とも交流できてよかったです。ゆるふわオンサイトに参加した後JAG夏合宿に行く人すげえ…
これは新宿で見つけた のしさん と しなもさん pic.twitter.com/pImisg54hf
— そすうさ(素数うさぎ) (@wk1080id) 2019年9月14日
*1:https://atcoder.jp/contests/wupc2019/tasks/wupc2019_d、今から思えばこれ解いてたら解けてたかも
ICPC2019 国内予選 参加記
noy先輩とHao君と一緒に「UnRated」というチームで出場しました。
3完54位でした。
〜前日
チーム練は3回くらいしたと思います。
HCPC 2019 Virtual Vol.20 - 足跡-sokuseki-
ICPC2019模擬国内予選 - 足跡-sokuseki-
four-t practice 2019 Vol.12 - 足跡-sokuseki-
国内突破には4完が必須なので、ABCを早くACしてD以降の考察に時間を割きたいと思っていました。
何度かチーム練して、ABCを自分とnoy先輩で考察&実装、D以降をHao君に考察してもらう戦略を立てました。
自分は今年でICPC引退なので、悔いの残らないようにしたいなあと思って個人でAOJ-ICPCをいっぱいときました。
コンテスト前
15時ごろに大学に着きそうだったので2人にpracticeを任せる。
ライブラリを印刷したやつと蟻本とティッピーを持って部屋に行く。
へへーん pic.twitter.com/cTVjaupDVo
— そすうさ(素数うさぎ) (@wk1080id) July 12, 2019
実装練習にICPC2017国内Cを解く。
チーム練では自分のPC(JIS)を使っていたのですが、突然外付けUSキーボードを使うことになり焦る。
さらに、プリンタを接続して印刷テストしようとしたらPC側でプリンタを認識してくれなくて、これどうするの?使うPC変える?とかいう話になる。(3人はみんなMacBookだけどエディタ等の環境がバラバラすぎるのでア)
いろいろググったりして試行錯誤したところ、開始20分前くらいにうまく認識してくれるようになったので、一安心。
ぞいぞい。
コンテスト
ACを自分が、Bをnoy先輩が、DをHao君が担当することにして、Aから読む。やるだけなので書く。AC。Bの方針を聞いて良さそうなので書いてもらっている間にCを読む。
Cがちょっと難しそうなのでHao君と一緒に考えると、右に載せる分銅と左に載せる分銅をビット全探索すれば0かどうかの判定はできることがわかる。1つ追加して〜のところがよくわかんないなーとか言ってるうちにBがかけたみたいなので見る。answerとprogramをまちがえそうになりながらもAC(複数人で提出チェックしててよかった)。
Cは右と左を全探索すると、そのとき必要になる分銅が一意に決まるので、その重さの分銅がすべてのAiで必要であればそれが答えとなりうるみたいな考察をして、実装する。Hao君に3^Mって言われたけど、計算量的に4^Mでも大丈夫そうだったので、4^Mを書く。
ICPCにはTimeLimitがないので、素早く実装できる方針を立てましょうということです(3^Mはバグらせる自信があって4^Mはバグらせない自信があったので、4^Mをしました
— そすうさ(素数うさぎ) (@wk1080id) July 12, 2019
↑いかにもすんなり通りましたみたいな書き方をしているんですが、実はデバッグ出力と答えを見間違えていて「は?答えが出力されてないやが」とか言いつつ、解法が出てたDに実装を変わったりして、20分ほど溶かした(バカか?)。
DはCを実装している間にDP解が浮かんだらしくて、C終わった後に聞いたけどよくわからなかった(は?)。E以降を読んで解けそうなのを探したりしてると、Dのサンプルが合わないらしいので、Dを一緒に考えることにする。Dは区間add区間minの遅延セグ木でできるんじゃない?とかいう嘘解法をはやしつつ順位表を見てみるとEが0ACでFにACがでているのでFを考えてみる。FはAtCoderぽいな〜(Dもだけど)とか言いつつわからないのでDに戻ってくる。順位表をみるとEもACがでてきたので、noy先輩にEを任せてDの遅延セグ木解のコーナーを探す作業をしてた。コーナーみつからないのでサンプルあうか試そうとおもってコードを書いていると、Eは実装激重やるだけゲーらしいのでPCをnoy先輩に譲る。ここで残り45分くらい。Dは諦めてHao君とFを考えてた。
ラスト1分くらいでEの実装が終わったけど、サンプルが合わず終了。
コンテスト後
4完がアジアボーダーだと思っていたのですが、4完以上のチームが少なく、3完でもアジア行けそうな感じがする。
焼肉を食べた。
放送見ながら打ち上げ〜 pic.twitter.com/mD0WecN36U
— そすうさ(素数うさぎ) (@wk1080id) July 12, 2019
感想とか
Cのバカがなかったら10個くらい順位上がってたので泣いてる。
ICPC引退が(たぶん)半年延びたので嬉しいです。もっと精進したいです。
four-t practice 2019 Vol.12
https://onlinejudge.u-aizu.ac.jp/beta/room.html#fourt_2019_12/info
チームでときました
ABCを自分とnoy先輩、D以降をHao君が読むことにする。
Aを読む。やるだけなので実装する。AC。
Bを書いてもらう。入力形式がアでつらそう。その間Cを読む。なんだかんだBが通る。開始20分くらい。
Cは実は解いたことがあったけど実装することになる。実装つらいんだよね〜とか言いながら書く。その間noy先輩はHao君と一緒にDを考えてもらう。
Cの実装が終わってサンプルを試しても合わないので、Dを書いてもらうことにする(といいつつ、全探索しかわかんないっぽい状況だった)。
デバッグをするとlower_boundとかupper_boundのあたりがまずそうなのでかわってもらう、サンプルがあったので投げる、RE。intじゃだめなことに気づいてもう一回投げる、WA。完全にわからなくなる。ここで1時間20分くらい。
Cがわからなくなったので、Cを捨ててDを一緒に考えることにする。Dは答えが8より大きくならない(1文字ずつ区切った場合、最大が9で最小が1になる)ので、A桁で分割したあとにありうる分割の桁数はA-1, A, A+1 くらいしかないんじゃないかって話になってたんだけど、「0」は使われないのでA>2のときはAでしか分割できないのでは?となって、A>2の場合はNの約数だけ考えることにする。A=2のときどうすればいいかよくわかってなかったんだけど、Hao君がいい感じの案を思いついたらしくて、全部実装してもらうことに。ばちゃ開始から2時間15分後、見事DをAC!!わーい!
反省
一度ACした問題は、バグらせずに解けるようになりましょう(終わった後昔のACコード見たけど同じことやってるんだよね、いまだに今日のコードのだめなところがわかりません、たすけて)
ICPC2019模擬国内予選
問題文:
http://icpc2019.jag-icpc.org/icpc2019/contest/problems_guest_ja.php
順位表:
2019/Practice/模擬国内予選/順位 - ACM-ICPC Japanese Alumni Group
チームUnRatedで出てABC3完75位(有資格者46位)でした。
BCあたり時系列ちょっと怪しいですが、コンテスト中を書きます。
コンテスト
Aを自分が、Bをnoy先輩が、CをHao君が担当することになる。
Aは見たらわかるので提出、AC。Bは場所と沼地の個数をもってbfsらしいので書いてもらう、Cが読解がやばいらしいので一緒に読む。
Bは実装がつらそうで、Cはx軸とy軸独立に考えたら良くて、偶奇で良い感じにできるので、先にCを書く。WA。
Cのコーナーを考えつつBを書いてもらう。BつらそうなのでDを考える。
Dは回転だけ最初にしてそのあと編集距離を求めればできそうで、書きます。投げます。WAになります。ここで1時間経過。
BはそのあといろいろがんばってもらってAC。
Cは実験しようということになって、Cのコードをかいてもらう。20くらいまで実験すると規則性が見えます。Cが通ります。
Dのコーナーがわかって、削除してから回転したほうが得な場合があって、でもそれをどうしたらいいかわからなくなったので、先を読みます。ここでコンテスト半分くらい。
E:Mが小さいので半分全列挙とかするのかな、いや何もわからねえ
F:構文解析マジ?と思ったら文字列数え上げじゃーん、むり
G:一番長いやつから1つ内側にはいると2番目になりませんか?どうなんですか?みたいなことを考えていた
H:グラフだし(部屋、コイン)で拡張ダイクストラしたらできませんか?とか考えてた
なんだかんだ自分にはHが一番できそうだったのでHを考えると、まずコインボタンは途中で押す必要がなく、脱出直前にどの部屋のボタンを押すかを考えればよくて、これは昨日のABC-D。よって、(今いる部屋、通った部屋の数、ワープで得たコインの数)を持ってDPをして、 にきたら、「 - ワープで得たコインの数」を「通った部屋の数」に分割するcombinationを求めて答えに足せばいい、みたいになる。しかし、状態が2000*2000*6000になって配列で持てないので、 を使ってクエリ先読みして、各部屋でその都度求めることにする。あとdp[2][2000][6000]もつらいのでpriority_queueでがんばる。ここまで考えた時点で残り1時間で、とりあえずコードを書き始めたんだけど、途中でcombinationの引数が1e9までなことに気づいてつらくなる。combination以外を書いて、どうするかかんがえることにする。残り30分くらい。
FができそうらしいのでHao君にバトンタッチする。
combinationの第二引数は高々Nなので、階乗の逆元だけ前計算することにして、分子はO(N)かけて求めて計算機の力を信じることにする。ラスト10分になってFつらそうなので変わってHを書く。サンプルがいくつか合わなくて終了。お疲れ様でした。
反省など
Cですぐ実験できなかったところ
多少時間がかかってもいいから全探索するという選択肢が頭になかった
ABCあたりを高速に通したい