いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

立命館NAIST競プロ合宿参加記

どうも~~~らてあでーーーーーす~~~~~いえーーーー
知らない人も多い(ほぼ知らない)と思うんですが、立命館大のRiPProの方々と合同で1泊2日の競プロ合宿をしてきました
参加記と言うかバラエティーわくわくほっこり日記です

参加まで

NAISTのYazaten氏とRiPProのりか氏でなんかそんな話が出てて合宿しましょうみたいな感じらしいとYazaten氏から聞く
まあやろうやろうみたいなテンションでいた
サンクスフェスの帰りにYazaten氏とT.M.氏で内容とか喋ってたけど決め切らないまま当日を迎えてしまった、じっくり考えるのもありだったのかな

前日

実家に帰って向かうことにしたのでTLEするわけがない、わっはっは

1日目

立命館まで

10時ごろ起きて優雅に朝食を済ませた
indeedTシャツを着ておいた
NAIST勢が順調に遅刻してるのをTwitterで眺めながら余裕の到着を見せたが、駅合流したかったので駅で睡眠をした
まだ来ないやろと思って寝てたら普通に目の前にいてアイヤー
Yazaten氏、yurahuna氏、きりん氏と合流、NAISTメンバーがそろった
合流して駅近くのスーパーで昼飯とか買ってバスに乗り込んで立命へGO


構内を歩いているとりか氏に遭遇、挨拶してなんか立命のカフェっぽいスペースで買ってきたご飯を食べた
立命の建物にはおしゃれな名前があちこちについていてよくわからない、NAISTは建物数がわかりやすいので
きりん氏とノリでコンビニに行って買い物をした
立命館大は最先端を往くので仮想通過を当然持っている(?)
色々グッズが売ってて、まあ知人が立命生多いから知ってはいたけど面白かった

自己紹介とか

おしゃれな建物の上の階のおしゃれスペースへYazaten氏の導きでたどり着くと、RiPPro勢が集まっていた
全員揃うまで適当にネットワーク接続とか確認して自己紹介フェーズが始まった
なんか割と自由な自己紹介だったので


なぜか最近印刷したアイコンの紙がカバンにあったので「このアイコンの人です」って言うと「あー」って感じだった
そもそも知り合いが多いので概ね1回生と初めましてって感じ
その後「touristじゃんけんを作ってました」と言うと伝わったのでコンテンツに依存して生きているという感じだ

強い方々でよしなにばちゃを立ててくれた
水色以上はこどふぉばちゃ、未満はAOJ-ICPCばちゃ
1回生がAOJ-ICPCやりたいって言ってて強いなあって思った、僕はやりたくない
コイツ実装が嫌いすぎるだろ、楽しいけどね、辛い時が多いからね、良くないね

[おかしをじゅんびするYazatenの写真]

ばちゃ1

Dashboard - Codeforces Round #443 (Div. 2) - Codeforces
A問題
難読だった、うーんこの
まあ医者がたくさんいて、全員に診てもらわないといけないんだけど難病だから順番に診てもらわないといけない
でも医者がいる日が決まってるから時間かかるし何日かかるか教えてねって感じ
ストーリーは適当言いました
同じ日には一人の医者にしか見てもらえないという部分を読み逃して1WA、みんな同じミスしててウケ

B問題
1列に人が並んでて、先頭から2人が卓球して勝てば連戦、負けたら列の一番後ろへ行く
ただし各プレイヤーに強さが決まってて強い人が勝つ
これは理不尽、コナンの映画でも勝ったものが強いのだって言ってた
k連勝した人を出力
先頭からなめてってk連勝するか、一番後ろまで言った場合は一番強い人を出力ってやればいいはず
人が入れ替わるタイミングの1勝を数え忘れて無限にWAを出した

C問題
なんかAND,OR,XORを使った処理が入力されてるんだけど頑張ったらもっと短くできるから短くしろやみたいな(伝わらない)
XORで無理やりやればあらゆる状態が作れるから無理やりやろうとしたらダメだった
考察してる間に時間切れになったけど、徐々にわかって来て解法は生えそうだった
終わった後で教えてもらってしっくりきた、こういうのすきよりのすき

終わった後どんな感じかなと思ったらあちこちで感想戦が生えてて面白かった
みんなAもBも同じミスしてたりとかして笑ってた

しばらくしてカタンやってる勢と考察とか実装やってる勢と雑談やってる勢で別れてた
僕はりか氏と熱いなりきりトークをかましてた

ごはん

チェックインして部屋に荷物おいてご飯に行くことに
NAISTより安く泊まれるしなんか部屋も広くて机も置いてあって良い
Yazaten氏が立命時代に足しげく通ったと申すラーメン屋にNAIST勢+りか氏しゅもん氏で赴く事に
雨が降ってて寒くて険しい道のりだった
餃子セットにしたら餃子がかなりニンニク強めでつらかった
ラーメンはいいスープしてたし美味しかった、セットにお米もついてくるのでスープかけて食べたけどこれはイマイチだった、失策であった

[立命時代に足しげくラーメン屋に通うYazatenの写真]

みんぷろ

立命宿に戻ってPC準備して出た

A問題
yahoo

B問題
割ってかける

C問題
虚無
ゲーム系なのでDPテクニックを思い出して逆算しようとしたら最適な手が定まらない
順位表見ても解いてる人が少ないしなんかまた得点あてにならない奴でしょって感じだった
眠かったので寝た
起きたらわからないので実装して寝た
起きたら考察してたら終わった
悲しいね、みんなのプロコン
効いたよね、早めのパブロン

カタン

みんぷろ感想戦やってからきりん氏とシャワー浴びに行った
脱いでたらmel氏TM氏が来たのでカタンやってたら遅刻したとかC問題はダメだとかそんな話をしてた
雨だったこともあって気持ちいいシャワータイムだった
DDCCTシャツに着替えた
間違えて女子用に入りかけたのはきりん氏にはばれてないと思う、いや正直ばれてると思う

で、カタン混ぜてもらうことにした
カタンはよくやったので負けるわけにはいかない

二人が微妙に木と土に分散してどっちかは高くなりそうだったので発展戦法を選ぶことにした
鉱山の9と麦8と羊5が取れたのでかなり盤石に見えた
序盤から発展でサクサク点をかき集め騎士乱発しておいた
mel氏は安定して街道を伸ばしている
TM氏は4付近に開拓地を立ててバリュー上げをしていた
騎士で二人の邪魔をしつつサクサク発展しきって結構理想的な勝利をした

誰がカタンの感想求めてるんだ?

深夜徘徊

カタン終わって部屋に戻るとNAIST勢は偉いのでみんな寝てた
合宿と言う名前のバリュー、テンション、みんな寝ている部屋、ノスタルジックとか言いながらスマホのライトで頑張って音もあまり立てないように椅子に座ってボーっとTwitter眺めて歯磨きしに行った
mel氏もやって来てシャコシャコやってた
終わって部屋まで歩いているとりか氏もいた
仲間を増やして次の街へって感じだ
なんかみんな同じ感じで寝るテンションじゃなかったので1時間くらい雑談してそれぞれ部屋に戻った

寝る気が起らなかったので深夜徘徊した
部屋に戻るとTwitterにmel氏もりか氏もいて、3部屋借りてて各部屋一人だけ起きててなんだこりゃって感じだった

暇だったので575探しに深夜徘徊をした
流石にアレ
りか氏も出て来て一緒に575を検出したりしてた
絶対寝坊する奴やん
まあわが部屋の皆様は優秀なので既に僕より4時間睡眠アドを稼いでいる

つまり4時ごろ就寝

2日目

きりん氏の輝夜月のモノマネが聞こえて目が覚めた
コドフェスTシャツに着替えた
9時半ロビー集合だったので部屋の片づけとかささっとやってちょうど位にロビーに行った
移動して昨日の部屋で朝食食いながらばちゃばちゃ

ばちゃ2

Dashboard - Codeforces Round #326 (Div. 2) - Codeforces
ドォフォフォwww

A問題
難読英文^;^
今使うべき奴を持ってオラァってやったら通った

B問題
入力された数字の約数でx^2の約数を持たないような最大の数字を出力
説明下手なので英語読んできてw
最初はエラトステネスの篩かそれっぽい物を持とうとしたが全く間に合わない
よく考えると素因数分解してそれぞれの素数の次数を1にするだけじゃん
はいプロ自明に天才やはり天才は100%の閃き宝石の煌めき秋の色めき堂々のムキムキWA
おいおいなんでWAなんやって色々やってたら終了してしまった
方針を変えてx^2で割れるならxで割るってループを描いたらACした
後でYazaten氏とmel氏に見てもらったら素因数分解が上手く書けてなくて、最後に残った数字が0でなければその数字を追加する処理を書き加えたらAC
これはダメだ~ソースコードだけじゃなくてついでに頭も診てくれ~

C問題
ばちゃは終わったがせっかくなので開いたらTM氏がやってきた
ちょっと誤読しやすそうなところをヒントをくれて考察したら一瞬で解法が生えた
同じ次数の物は2つまとめてもう一つ上の次数に出来るってことに気づけばいいだけでKUPCのアレに似てた、わかれ
3完したいセットやんけ

お昼

時間が惜しいのでコンビニとかで各自って感じになった
カップラーメン買ったら移動してサークル棟(なんか確かアルカディアスみたいな名前の建物だった)
f:id:ratetion:20180213002407j:plain
6マナ12500
進化エンジェルコマンド
W・ブレイカー
光以外の呪文は使えなくなる

部室とか見せてもらった、楽しそうだし羨ましい
入口に近いミーティングルームが開いてたらしいのでそこでやることに
お湯沸かすアレ持ってきてくれたのでその部屋で入れてもそもそラーメン食ってた
食いながらコイツまたラーメン食ってるなと思った
スープも飲んだし塩分過多過多土方歳三

ばちゃ3

APCばちゃをやることになった
ぺとろざうぉーつくなんとかかんとか
petrはレジっただけで全完
AtCoder Petrozavodsk Contest 001 - AtCoder

A問題
forループ書いたンゴ

B問題
むっちゃ詰まった
操作が許される回数を数えてそれぞれ少なくとも必要な操作回数を数えて、許されてたらえいみたいなことをしてlong long intつけわすれてつけてAC

C問題
適当に二分探索書いたら通っちゃった、いえーい

D問題
なんか貪欲にやったらできそうだけどそれなら600マジ?とか言ってたらおしまい

感想戦ではきりん氏にBを解説してC問題のにぶたんを乱択するとはやくなるとか謎の議論をしたりしてた
Dはほえーって感じ、こういうのでUFとかササっと出てくるようにしたい

終わり

今度は夏やりたいねーとかNAISTには宿泊施設はあるけどNAIST勢は泊まらないやろなあとか、NAIST勢の家3つくらいにみんなを泊めればいいとか(←これ個人的にやりたいけど)話しながら解散
駅までのバスでりか氏ときりん氏とRUPCに行くべきとか、アルゴリズムの話について行けなさそうとか、でも同じ実力くらいの人と喋るときはこう、最近解いた問題トークとかがいいぞとか言ってた

駅で僕だけ逆方向なのでひとりで電車に乗って帰りました
堅苦しい文章書くと誰でも書けて感情がこもってないとか言っちゃう(は?)
準備とかなんか色々任せっきりだったしただただ楽しいだけをさせてもらってた
ありがとうございました
また是非卒業までには何卒
今度は僕もやりたい事とか考えておくんで、何卒

そりではこれでいいな、行きたいなと思った人は立命館大学の願書とNAISTの願書を取り寄せて下さい
ritsnet.ritsumei.jp
www.naist.jp

ACM-ICPC 2017 Asia Tsukuba Regional 参加記

ACM-ICPC 2017 Asia Tsukuba Regional | 国際大学対抗プログラミングコンテスト2017アジア地区つくば大会
参加しました
とても思い出に残る、忘れられない出来事となりました
どうぞよろしく

参加まで

きっかけ

大学院に入学してから競プロを始めた、そのころからやった事は以下を参照
ratea.hatenablog.com
4月にノリでコンテストに出ていたらゆらふな氏にメンバーに誘っていただいた
一旦保留したが、やはり競プロが楽しかったため混ぜてもらうことにした

国内予選

国内予選に出た
ratea.hatenablog.com
自分にできることは精々A問題、考察、サンプル図示などのように見えていた
なんとかつくばに行けることになったが、連れて行ってもらうって表現が正しく感じ、何度もYazaten氏に励ましてもらったりしてしまった
そもそもメンバーを集めることが難しかったり、そんな中でこれだけコンテストに出てたら十分だとか、ありがとうございました

チーム練習

週1回会津大学のvirtualや海外リージョナルの過去問などを3時間でやっていた
僕は主にA難易度相当の実装や、その他の問題の考察などを担当していた
問題とかは二人が選んでくれたし、僕はテンプレとか持ってないし海外の大会とかよくわからないし介護って感じだった
辞書と蟻本持ってサンプル図示とか考察をしてなんとか役割を探しているような感じだった

0日目

荷物の準備をして夜行バスに乗り込んだ


前日に奇跡的に生活リズムが改善されていたためバスの中で熟睡できてしまった、すごい

1日目

朝6時ごろ新宿に着いた
何も考えていなかったので適当に秋葉に向かってネカフェに入った
ネカフェは実は初めてで、個室がなんだかいい感じだった
のんのんびよりをダラダラ読んでると、れんちょんが尊すぎて寝足りないから寝ようとしてたのを完全に忘れてしまった
1冊読むたび返しに行って飲み物取って帰ってくるようなことをしていた
10時ごろに出てつくばへ向かった
つくばにつくば
電車内でなんかこどふぇすTシャツ着てるし「ICPCが~」とか喋ってる人がいるので話しかけてみた
阪大チームでこちらのことも普通に知っていてそんな話で盛り上がっていた
駅へ着いて集合場所に行ってみるとそれっぽい人がちらほらいた
btk氏が居たので色々話す
つくば大会が終わったら帰らずタイ大会へ向かうらしく地獄のスケジュールだとか、大会でTシャツを得られるから洗濯しなくても数日何とかなるとか謎のライフハック情報を共有していた
北大勢や京大勢とも遭遇した
京大勢に中学時代の友達がいてとても驚いた

JAXA見学

バス内で昼ご飯を頂いた後JAXAの見学が始まった
ツカサ氏にふられたボケを全部拾うヤバい奴になっていた
頭おかしい大学院大学ではない

その他色んなものに惹かれたしじっくり見学し直したいレベルだった、時間が足りない
きぼうの管制室はかっこよすぎて開いた口がふさがらなかった

リハーサル

大会登録をして荷物を預けて体育館的な場所に入った
去年ニコ生で見ていたような景色が広がっていて泣きそうになる

Tシャツを着てあちこち徘徊、ふーらくたる氏、treeone氏がいたため話す、おいおい
お菓子エリアに行くとixmel氏とTM氏が居たのでまた話す、ネカフェは良いぞと言う話をしていてこれから泊まるネカフェを探すとか、バイタリティが凄いんじゃ

リハーサルコンテストが始まるとYazaten氏がテンプレ写し、ゆらふな氏がA、僕がBを読む
Bは何をやるかはすぐにわかったが制約が読みにくく、テンプレを書き終えたYazaten氏に相談して考えてた
Yazaten氏が強そうな解法を生やしてくれたが実装できる気がしないためうーんうーん唸りながら式を整理すると解の公式が出来ると思った
解の公式では?と伝えて計算するが答えが合わない、なんと僕の解の公式は解の公式ではなかった
中学生
正しい式でやると合う、実装もすぐ終わるので書かせてもらって投げるもWA
ゆらふな氏に当たり前のミスを指摘してもらってAC、これは高校で習うよね?みたいな事を言われて明日がとても不安になった、ふにゃん

なんとか全完
Yazaten氏がいきなり紙を取り出す


国内予選の時に僕が描いたロゴだった、おいおい捨てたんじゃなかったのか
今日まで黙ってたらしい、なんでなんやなんでこいつにまた会えるんや

懇親会

筑波学院大学に移動して素敵なご飯とチーム紹介を
ご飯はティキンがとても美味しかった、次々炭水化物が出て来てお腹がMLEしていた
チーム紹介は頼んだと急に言われ拙い英語でチーム名が575っぽく聞こえる事と、コーチのしょラー氏が月になったと伝えた
マスコットニキアさんとか114514が面白かった

toホテル

Yazaten氏と公園を歩き橋を渡り解散、僕が取ったホテルは安くて遠かったので黙々と歩いていると目の前に北大の4人がいた、おいおいおい
あたかも僕がストーカーみたいじゃないか、こらこら
一緒に喋りながら歩く、案の定同じホテルだった、ウケ
明日ちゃんと起きようなって言って解散し部屋に入った
ARC出たかったがさすがにICPCを優先した
CDだけ眺めて考察して寝た
疲れていたためすぐ寝れたしぐっすり寝れた

2日目

会場入り

6時半ごろ起床、準備して出発
徒歩20分くらいかかるんだけどまあ早めについた
smiken氏が会場で一人でいて、自分だけホテル違うとこにしたからさみしいね見たいな話で共鳴していた(???)
チームがそろって入場、Yazaten氏が朝ご飯を買いに行くためついて行った
帰ってくるともうすぐ始まるみたいな感じで準備して待った
割と落ち着いていた、やることは変わらないし冷静にね、やろうね

コンテスト

リハーサル通り、テンプレYazaten氏、A問題ゆらふな氏、と言う事で問題をゆらふな氏から受け取りBを読む
定規で封筒をきれいに開けていてしゅき
B問題は最初読んだ感じ全探索でもするんだろうかと言う気持ちになっていたが、制約を読もうとした段階でYazaten氏が合流してくれた
最低限しっかり読めていてパラレルは平行ですねとだけ確認してもらった、読めてよかった
解法はわからんしとりあえず制約を一緒に確認したら全探索は出来なさそう
傾きの良い持ち方がわからないのでゆらふな氏に相談した方がいいと結論付けてAを通したゆらふな氏にお願いし
一緒にBの解法を考えているとゆらふな氏が出来そうで実装に移ってもらう
C問題へ移る
C問題はTOEICの長文読解最難関問題だった
二人で何度も読んで文法の復習とかやってなんとか問題文の意味はわかった
各人の待ち時間がいい感じに方程式で表せそうって話をしているとYazaten氏がサクサク立式してくれたのでそれを確認していた
あまり式の意味が理解しきれてなくて自分で再現したりしていたが辛かった、前日のフラグがここで
どうも出来そうとの事で実装に移ってもらった

BがWAが出たらしいのでそちらも考える、さっき聞いてた解法のコーナーケースを見つけたので図示してトイレから帰ってきたゆらふな氏に見せようとするとお互い同じ考えだったらしく、いろいろ確認して解法を見直す
ここら辺の時系列が曖昧だけどその後ゆらふな氏がBを通しCに合流したタイミングで次に解かれているIを読み始めた

I問題もやや問題文で詰まってしまった
概ね理解できたが重要なアルゴリズム部分がわかりにくくて読み直したりしていた
ゆらふな氏に伝え3人で考えると、うまく言いかえをしてくれてすごくわかりやすくなった
後は求めるだけだが計算量が~とか言っていたのでimosで求めやすそうとか言って概念的な説明をしていると理解してくれたらしく実装してもらう
バグらせていたのでYazaten氏が以前imosのややこしい奴の実装とか教えてくれたなぁとか思って頼む、直してもらってAC
みんなで通したって感じがしてよかった
残り15分とかで厳しいなあと言いながらFを聞いて解法の怪しいところに突っ込みつつ整理していたら時間が来てしまった
キーボードをまるで触らずに終わったが、考察役としては最低限の動きは出来たかなって感じ
しかし悔しい、自分の力は小さい物だったけどもっと何かできたかと言えば自信ないけど

TLを観ているとNAIST3完かーみたいなのが見えてふっふっふ凍結後をよくみることだなとか思ってた(?)
しょラー氏にむっちゃ疲れてるやんけとか笑われた、糖分
そのまま結果発表のホールへ移動

解説、順位発表

解説が英語で雰囲気しか理解できなかった
ゆらふな氏にたまに聞いて教えてもらってあーうーとか言うてた
Fの解法もかなり近づいてたっぽくて5問見えたなぁって言ってた
企業挨拶を経て順位発表が始まった
去年ニコ生で見ていたYesNoおじさんが現れマシンガンイングリッシュフルーエントトークで下から順番に凍結後に出された問題が正解か不正解か開示していく
凄い速度感
我々はIを残り15分で通したのでYesだと知っているんだけどウッキウキだった


去年ニコ生があったので今年もあると油断していたがなかったっぽく、しょラー氏がしっかり動画を取ってくれていた
何度見てもうれしすぎる、114514回見ろ

懇親会

ご飯食べて企業ブース徘徊してコネクションハントとかやってた
英語でいろんな人に話しかけて(あえて?)質問に答えてもらった


大悪魔様のしもべなので最後の枠を空けておいた
ドワンゴでWAなげをしたりGoogleインターン申し込んでって言われたりタタに入社試験受けようって言われたり
色んな企業が覚えててくれててI問題通したの凄かったねーって褒めてくれたりした、えへへ

秋葉

NAISTからインターンに来ていた友達に導かれてメイドさんと喋りながらお酒を飲む店に行った
名札をぶら下げたままだったので本名がバレバレだったし服装がそれっぽいのでスタッフって呼ばれた、悪くない(?)
筑波で2泊とってしまったのでまた筑波へ帰った
Yahooからもらった去年のみんぷろ問題を考えながら歩く
ホテルに向かっているとスマホの充電が切れた、完


なんとか運命力でホテルにたどり着きチェックアウトの準備をして就寝

3日目

企業見学

企業見学だった
つくばを朝早くにでてtreeone氏とこうき氏と一緒につくばエクスプレスに乗った
昨日見ていたYahooの問題を相談して教えてもらったりした、わかりやすくてすごい
こうき氏と一緒にindeedTLEかました

indeed

Indeed->LINEの順番だった
Indeedに昨日もらったTシャツを着て行ってありがとうございましたとか伝えた
Indeedのオフィス凄い凄いとかいいながらはしゃいでた
ixmel氏とTM氏とこそこそしながらオフィスを練り歩いてふざけていた(ごめんなさい)
ホワイトボードに"ixmel"って書いたけどさすがに消した
椅子がいいオフィスだった、椅子がいいのはいい
椅子だ

その建物の1階でお昼を頂いた


なんでも頼んで良いよと言われた、しゅごひ
筑波学院大学の学長(多分)様が近くに座っていてICPCの開催の裏側や、熱い想いを聞かせてもらった
スポンサー企業も年々変わっているし、ICPC出た人が企業に入ってスポンサーになりましょうみたいな事を言って広がるいいループが出来ているらしい
来年は僕にはないのですが、とてもいい想いをさせてもらえたので僕もその一端になれればいいなと思ってた
なんらかの形でICPCに関わっていたいという気持ちが高まっていた
後は一緒に座ったりあん氏と喋っていた
問題の話や身の回りの話をしていた、周りに座っていた人も色々聞いてくれてあったけぇ

???「飯食ったし帰るわ」

LINE

LINE社に着いた
りあんプロの導きで簡単についた


LINEがダウンしたときの話と、人工知能の歴史についての話をしてもらった
人工知能の方かなり面白くて質問もしたりした
シンギュラリティって感じだし"私もそろそろディープラーニングやってみようかなー!?"
オフィス見学はまたひたすらはしゃいでいた


えびちゃんが3席ほど離れたところから攻め立ててきた、こわい><
ごめんなさい(?)
まあ正直前半のLINEがダウンしたときの話はあんまり理解できなくて、競プロっぽい話とかいすこんの話とかは聞きたかったりした

TAB氏とえび氏と喋りながらLINE社を後にした
これから僕は目標が消えた事や、今回北大チームが辛かったこと、来年頑張ってほしい事、風船でも配りに行きますよとか言って別れました
すごく応援したいチームの一つでありけり

夜ごはん

Yazaten氏、マヨ子氏と合流、お店に向かう
とりかわとかハムカツとかとても美味しかった
競プロ始めたきっかけとかどんな環境だったかとかそんな話が印象的だった
やっぱみんなどこかでかなりの努力をしたから今があるんだし僕もまだまだできてないしこれからでも頑張りてえと思ってた

解散して東京駅を徘徊したのち夜行バスに乗って帰った
僕の初めてで最後のICPCが終わった

おわりに

競プロやってよかったです
誘ってくれてチームとして一緒に参加してくれたゆらふな氏Yazaten氏、コーチを務めて下さったしょラー氏に多大な感謝を申し上げます
ありがとうございました
また話しかけてくれた方、話しかけさせてもらった方、ありがとうございました
こう言うのなんか恥ずかしくて下手なので許して、態度で示したい

さて、今後ですが、僕にとっての選手としてのICPCは終わりましたが、悔しくて来年も出たくて仕方ありませんが、チームも名残惜しいですが、競プロは今後も続けたいと思います
一つ目標は消えましたが、それだけじゃないしICPCにも貢献したいなと漠然とそんな感じです
ではまたどこかでお会いしましょう

連続ACを8か月続けた感想

はじめに

adventar.org
4日目の記事です
自分が長けているといえばこれくらいしかテーマが無かったため連続ACについて書きます

f:id:ratetion:20171203185740j:plain
AtCoder Problems

2017/4/8にABC58に出たところから連続ACを本日まで続け、今日でちょうど8か月になりました
単純に良かったことと良くなかったことを書きます

良かったこと

  • 毎日最低でも1問は解けるため萎えない
  • 頑張ってなくてもみんな褒めてくれる
  • モチベーションを保ちやすい
  • 日が変わったら解いているので習慣が出来た

良くなかったこと

  • 簡単な問題ばかりに手を伸ばしてしまう、意外と簡単な問題が尽きない
  • AtCoderでしか解かなくなる
  • 解ける問題が減るため1日1問しか解かなくなる
  • 遠出しても何があろうと解かないといけないので、特にネット環境が無い時のスマホコーディングなどが辛い

感想

続けてよかったとは思いますがデメリットも目立つ結果になったと思います
今後続けていくかはわかりませんがもっと別の目標に焦点を当てたい気持ちがあるので気が付いたら切れてるかもしれません
始めたての頃は連続ACの存在を知らずとも勝手に連続ACが生えていたため、そういう場合ではなく、モチベーションが保ちにくくなる時にやると意味があるのかもしれないなと思いました

まとめ

連続ACは勝手に生える

CODE THANKS FESTIVAL 2017参加記

行ってきました、どうぞよろしくお願いします
コンテスト内容も言及しますがいつも通り時系列にやっていきます

参加まで

5月ごろだったか記憶が曖昧だがodan氏が大学へ来たことがあった
彼はその時CODE FESTIVALのTシャツを着ていて、デカデカとよくわからないグラフが描かれていてかっこよかった
Yazaten氏もおり、学生しか出れないことや、むしろ出やすいコンテストだとかそんな話をしていた
まだまだ競プロ始めたてで何もわからなかったが、とりあえず出たいなあと思っていた

予選AはJAG夏合宿中に参加し、絶望を感じた
本戦どころかTHANKSさえ行ける気がしなかったし、あまり予選に出る気も起きなくなってしまった
しかしその頃からICPCまでに青コーダーになるという別の目標を立てていたため、予選はレート上げに最適だった
予選Cでは早解き力を生かしてレートを大きく上げた
これが奇跡的にTHANKS参加権を獲得していた
嬉しいような複雑な気持ちだったけど日に日にうれしさが増していくのであった

前日

東京

前泊が許されたので、早起きして新幹線で東京へ
駅のホームで佇んでいると後ろから肩を叩かれ変な声が出た
Yazaten氏だった、車両がは違ったが同じ新幹線だった
社内では噂のtouristじゃんけんのアップデートを行っていた
そろそろ怒られてもおかしくない


東京へ着くと、同学のきりん氏と合流、3人で昼食へ
良かった、これは美味しい、美味しい、どうかなと思ったけど、美味しい、美味しかったよ
www.nicovideo.jp
解散してホテルにチェックイン、リクルート様ありがとう、リクルート様ありがとうコンテストって感じ

ボドゲ会1

荷物を置いて品川へ
駅でTIke氏と竹雄氏と合流しファミレスでも行くかーって感じになる
小粋な旅(ただの遠回り)をしてファミレスへ、僕は昼ごはん直後だったのでパフェを食べました
力強い💪💪💪


店内で待っているとこうき氏、つたじろう氏とも合流、食事を済ませてフェリン氏と合流しカラオケでボドゲ会を始めた
やったゲームはNot My Fault! ~俺のせいじゃない!~(蔦さんが買って来てくれた)とインサイダーゲーム(フェリン氏持参)です
僕は7個ほど持って行ってたけど色んな都合で出来なかった
感想としてはNot My Fault!は一手が重い、始めたてだからかわからないが数字が想像より大きいことが多く、もう数戦すると裏をかいたりし始めるのかなと思った
インサイダーゲームは僕が悪かった💪
退店後、ふーらくたる氏と合流、晩御飯へ
ポルチーニおいちかった>

ホテル

ホテルに宿泊勢で戻ると、すぐに外へ出て、ドクペマックスコーヒーと明日の朝食を買った
マックスコーヒーは甘すぎて凄かった
アパホテルの漫画があったので読んだけど、まあ感想は控えさせていただきます

ボドゲ会2

ホテルで宿泊勢で続きをやるぞやるぞやるぞおいおいおいつりーわん
と言う話になっていたつたj
ということでつたじろう氏と竹雄氏とギャンブラーギャンブルをプレイ、なかなかに受けた
他者心理を読むゲームでセオリーは少ないと思っていたが勝ってしまいア
その後treeone氏が僕の通知欄を壊しながらやって来て一緒にラブレターをやった
Tなんとかさんがやりたいといっていたものをプレイしました!
こうき氏、Yazaten氏も集まって来てみんなでクーをした
寝坊が怖い時間辺りで解散しました

当日

開場まで

余裕の起床をした
まさかTLEするような人がいるなんて思えない><
TIke氏がいつ来るのみたいなメッセージをくれたのでウッキウキで向かった
開場最寄り駅で合流し向かうと、20分前くらいに着いて開場横の休憩スペースでたむろしている競プロ勢っぽい人が声をかけてくれたので一緒に開場まで待つ

この文章会場と開場が入り乱れていていいですね
しばらくするとちょくだいさんがやって来てアイドルっぷりを発揮していて凄かった
開場したので並んで名札受け取って交通費やら誓約書やらやってTシャツゲット
早速着ましたが意外と着ない人もいるんだなあって
前日会った方や、minami氏、ツカサ氏、りか氏、隣の席の馬氏らに話しかけたりしていた
コンテストは1800点取るとパーカーがもらえるみたいなので軽く絶望を感じたが、最後まで戦うぞと決意
Yazaten氏がやって来て、500点を解けばもらえるし、解けるよと励ましてくれた

コンテスト

CODE THANKS FESTIVAL 2017 - CODE THANKS FESTIVAL 2017 | AtCoder

A問題
風船が見えたためFA賞だと思って問題文で雰囲気を感じ取りコンパイルもせず投げたら通った
全然FAじゃなかった・。・v
問題文とか覚えておらず

B問題
開いてしばらく焦った
変な実装とかをしていたが、後ろから区間を決めて回文かどうか判定してmaxを取ればいいことが分かった
文字列をくっつける処理とかが苦手なので添え字を頑張って動かした
なんとかAC

C問題
開いてしばらく上昇量をグラフにして交点を求めていくかとか思っていたが無謀そう
priority_queueを以前一度だけ使ったことあるので、計算量覚えてないけど多分それだろうと思った
しかし2値を扱えるか知らなかったのでググって出てきたのを必死で真似して実装
オーバーフローに悩みながらもなんとかAC、今までの成果が出た問題って感じで嬉しかった

D問題
これは解説をじっくり読めばいいと思うの
全探索を色々やろうとして絶妙に通らずWAを連発
これがダメならgcdを使うんだろうと思ったのでgcdの使いどころを探しながらサンプルと自分で作ったケースをにらめっこした
すると法則が降ってきたのでえいAC

E問題
意味が分からない
双子の問題を思い出した
sist8.com
これの答えみたいな感じで頑張れば実は何か出来るんじゃないかなって
ちょくだいさんが解説で「そんなものはいりましぇ~~~んwww」
みたいな感じでとても辛い時間を過ごした
もちろん解けなかったさ

F問題
問題を見るにDPするんだろうと思った
しかし10^5*10^5必要でメモリは配列使いまわしで出来るけど計算量が無理だった
制約も不明で、これを使うんだろうなあとは気付いていたけどわからなかった
ので、排他的論理和の性質を必死でググって何か得るものはないか考えていた
方向性は間違ってなかったみたいで、思いっきり排他的論理和の性質利用して計算量落としててふえーん
フェーン現象
WA
いいえ

G問題
UFするまでもない、深さ優先探索してやるぜ
しかしわからないのでWFしてやるぜ
タイムオーバーだ!

H問題
読んだだけ
速読のプロ

ABCDの4完でした
パーカーまでは2問届かず、普段より難易度難しいように感じてしまったが、解けなかったことに変わりはない
来年がラストチャンスなので精進するぞと誓った

懇親タイム

CONNECTION HUNTでは、「touristに勝てる日が来ると思いますか?」という質問をさせていただいた

集団で喋ってるところへtouristじゃんけんを持って行ってプレイし書いてもらう変な人間役をやっていると50マスFAした
景品はトートバックとタンブラーで迷ったが、引きこもりのため毎日使えるタンブラーを選んだ

結果はこんな感じでした


その後いろんな方と談笑しながらおいしいぽしゅしなどを頂きました
ぽしゅしです


おまけにじゃんけんは

奇遇にも帰りの新幹線がYazaten氏TM氏と同じなため一緒にホームでお話ししました
TM氏とはまた会う機会があるためとても楽しみ
帰りの新幹線ではシンカンセンスゴクカタイアイスを購入してもしゃもしゃしてました
コンテストが楽しくて自大でも開きたいと思って問題案を考えていたけど難しくて辛いなあと思っていたら奈良に帰ってました
日が変わって数十分で帰宅し僕のこどふぇすが終わりました
楽しかった、来年はパーカー着て帰るぞ、おわり

DDCC2017本戦参加記

19卒枠で参加できることになったの参加してきました
問題はここ
ddcc2017-final.contest.atcoder.jp
今さら書くのは気が向いたからです
逆にね、記憶が薄いから雑に書いても許してねみたいなね
全体の感想としてはすごく満足滅茶苦茶楽しいこれに尽きるのでみんな来年出ようね

前日

同研究科のYazaten氏とウージー氏と共に新幹線に乗り込みました
新幹線では蟻本を読むふりをしながら寝る人間になっていました
DPのページを読み直して謎を深めてたりもしました

小粋なギャグをかましながら昼飯を取りました

その後はスーパーカミオカンデについて理解を深めたり環境について考えたりしました

夜はYazaten氏の呼び掛けで集まった競プロ勢と鍋をつついて酒を飲みつつ、よろずの話題を話しけりしました
傍から見たらヤバい集団だったろうなぁってレベルで話題がシュールだった、毎日やってくれ

ここら辺からTIke氏のブログを参照すると情報の精度が高まります
ti11192916.hatenablog.com

飲み会解散後はホテルに戻ってそわそわして連続ACを更新して寝ました

当日

ウキウキで起床するも一緒に来てた二人はじっくり寝てたので一人で駅の方を散策しに行くことにしました
駅前に行くとTIke氏に遭遇、やっぱりね(?)そう言う事なんですね(?)
一緒に会場に行きました
ここら辺もTIke氏のブログを見るとね


コンテストは非常に険しかった
A問題は去年のA問題そっくりで、解法はすぐわかったんですが、実装で無限にバグらせ続けました
B問題は全然わからなくて色々試してたら通りました
C問題を眺めて終了しました


コンテスト終了後特製ビュッフェを頂きながら雑談していました
みんな問題の話をいっぱいしていて、オンサイトコンテストだなぁと思ってました
ビュッフェはトークに夢中で味がわからなかったけどお寿司が食べれたので東京へ来た全ての目的を達しました(いいえ)

対談は内容がもちろん専門的には浅いんですが、興味深くて、将棋AIに限らず競プロAIが強くなってくるんじゃないかとか、以前麻雀AIに関しては色々調べてたのでなるほどなあと言う感じで、強みはいくらでもあるしリアルな話だと思ってました

会社見学もなぜかTIke氏と同じ見学班でね、やはりね
と思って荷物を預けて集合場所に行ったら誰もいなくてね、TLEですねこれはね
悲しいなあと思いながら同じようにおどおどしてる人を捕まえてスタッフに聞いたらおいて行かれた班が完成してるからそこに合流してくれとの事、ふええ
合流すると6人いて、名前を聞いたことがあるなぁと思ったctyl氏に話しかけ、一緒に見学した


以前行った広島のDPCの時の見学より時間は短くてあっさりしていたが、こっちの方がおしゃれで面白い部分もちょろっとあったかなと思った
生活がほぼ会社だけで完結しているのは羨ましいけど実際やると複雑かもしれない

見学後は懇親会がありTIke氏と感動の再開
また色んな人に話しかけに行ったりローストビーフやケーキをむさぼっていた


最高である
最高
最の高

その後ノリと勢いで体を犠牲に†ボウリング†をしに行った


あらゆることを競プロ用語に例えようとしていて会話が凄かった

その後品川で解散しolphe氏と新幹線で帰宅した
始めて新幹線の切符を買ったため、切符の買い方を教えてもらっている大学院生がそこにはいた


おわり
雑ア

競技プログラミングを初めて半年が経った

競技プログラミングを大学院に進学した直後に始めました
そこから何をやっていたか軽くまとめておこうと思います
ゆらふな氏のブログが参考になったので僕もと言う事で良いループに混ざれたら何よりかなと
pakapa104.hatenablog.com

2017/4

AtCoderのコンテストにノリで出てみる
参加は実際は2回目で学部時代に一度出た事があったが、まじめにやろうと思ったのはここからなので
AtCoder Beginner Contest 058 - AtCoder Beginner Contest 058 | AtCoder
参加したのはこれ
2完で順位は324位、レートもロクにつかなかった

ゆらふな氏の上記ブログを読んでいたのでABC埋めから始めた
#1日1ABCと言うタグを使ってモチベーションを保っていたけどするまでもなく、ACの表示が見えるだけでうれしかった
#1日1abc hashtag on Twitter
わからない問題はツイートしたら競プロ勢がヒントをくれたし、そうしているうちに競プロ勢がいっぱいフォローしてくれた

ゆらふな氏本人からICPCに出ないか誘われたが、僕が出ても足手まといになるとしか思えず保留した
出れるならうれしいとは思った

また、大学でYazaten氏と知り合いアルゴリズム講座を何度かやってもらった
アルゴリズムはどれも画期的で感動的で涙が出そうだった
特にimos法がかっこよすぎて鳥肌が立った
ワーシャルフロイドは何が起きてるかわかるまでホワイトボードで試して説明してくれた
たまにゆらふな氏も見に来てワイワイやってた

また、みんなを誘って一緒にAtCoderのコンテストに出たりしていた

2017/5

C問題が難しくなり始めて解けなくなってきた
たまに解けるけど無理なものはバンバン飛ばしていった
大学でできた友達とバーチャルコンテストを開いて解いたりもした
一緒にやってくれる人も楽しいと言ってくれて嬉しかった


ABCのAとBが埋まった

多分このころからICPCに出る意欲が高まっていた


緑には難なくなれた
ABさえサクサク書ければどうという事はなさそうである

蟻本を購入したので寝る前に1節とかそんなペースで読もうとしていたが全然続かなかった
内容が難しい、僕の読解力が足りない
いずれにせよ、辛い書籍ではあるし、学習は辛い事でもあると思った

2017/6

ARCに出るようになる
ABはサクサク解けるようになったのでC問題にじっくり時間を使いたいと考えた
レートは気にせず、下がってもいいのでとにかくTLでみんなが解法をツイートする前に解きたかった
時間内に解けなくても開設を見るなりして必ず通すようにしていた

難しいと感じた問題は記憶しておいて、時間があるときにノートを取り出して考えたりしていた
シャワー中とか選択物干してるときとか皿あらってるときに解法がわかって叫んだりする頻度が増えた
どうしてもわからない問題は解説を観て通していた

ゆらふな氏とYazaten氏とICPCに出ることを決めてチーム練習をしはじめた
二人が過去のコンテストのバーチャルなどを開いてくれたので模索しつつ出来ることをやる感じでやっていた

鬱を自覚したりもした

2017/7

ICPC国内模擬予選に出た
ratea.hatenablog.com
DPCにも出た
広島旅行みたいな感じだったし気楽で楽しかった
またICPC国内予選にも出た
ratea.hatenablog.com

100日連続ACを達成


連続ACはかなりモチベーション維持に繋がったので価値があった

たまにAOJを解いたりSRMやこどふぉにも出たが苦手というか時間が様々で参加が困難だった
なのでAtCoderだけはきっちり毎週出るようにしていた

2017/8

だらだら連続ACだけを続けていた
300ACを達成したが、簡単な問題を毎日解くだけだったのであんまりいいとは言えなかった

ARCのAが埋まった


そろそろ解ける問題がなくなってきていた
解説を読んで時間をかけてじっくり1問を通すようなことが増えた

2017/9

touristのAGCで水色に到達した
f:id:ratetion:20171005014232j:plain

Yazaten氏とACPCday3に出た
ratea.hatenablog.com
久しぶりのチーム戦だった、二人でやるのは特に初めてで、割とうまく機能してて楽しかった記憶がある

JAG合宿にも参加した
ratea.hatenablog.com
初対面の人とチームを組んでコンテストに出る経験とか、TLの人と実際に知り合えたりとてもいいイベントだった
自分の課題も見つかったので競プロ方面においても価値があった

2017/10

YouTubeで競プロの問題を解く生放送をやってみた
結構みんながコメントくれて嬉しい
考察も逃げずに向かえるので価値があると思う
出来る人はやってほしい

KUPCに参加した
ratea.hatenablog.com
ソロで5時間コンテストは初めてでかなり疲れた
しかし考察をじっくりできるので短時間じゃ解けなかった問題が解けたりして嬉しかった
またJAG合宿と同じく、いろんな方と話しが出来て、みんな本当に競プロが好きなんだなと認識した

連続ACが180日になった、一応これで半年が経った
f:id:ratetion:20171005014114j:plain
レートはあまり変わらずこんな感じ
f:id:ratetion:20171005014153j:plain

まとめ

  • 周りの人のおかげで楽しく続けられている
  • 興味があればまずやってみて欲しい
  • とりあえずABC過去問を解こう
  • まだまだこれからなので頑張る

ポエム

いつもTwitterでポエム書いてるからそっちを見てくれ~~~

以上ありがとうございました

KUPC 2017 京都大学オンサイト参加記

京大が好きなので参加しました(?)
Kyoto University Programming Contest 2017 - Kyoto University Programming Contest 2017 | AtCoder

参加まで

TL等で見かけるし誘ってもらっていたりしたので即決で参加した
申し込みが遅かったので申し訳なかった
コメントに575をかましておいたので一読ください

前日に天下一プログラマーコンテストがあり0完で太陽をキンキンに冷やして精神が逝かれてしまったのでD問題を解くまで寝ないような配信をした
www.youtube.com
結局ACまでに3時間程かかり、寝たのは4時になってしまった
ゆらふな氏、しょラー氏、Yazaten氏と一緒に行く約束をしていたので9時には起きるようにして寝た

京大まで

結果異様な眠さで起床AC
駅で合流して京大最寄り駅へ、近くのラーメン屋で昼を済ませる
f:id:ratetion:20171002020957j:plain
INF回チャーシューが食べれて幸せだったけど腹LE寸前だった

会場へ着くとJAG合宿その他でお会いした方が結構おられ、あいさつしつつ準備をした
ネットがつながりにくかったのでスタッフの方が頑張ってくれて快適な環境でコンテストに参加できた
結果自己紹介がWi-Fi接続タイムになっていてバジリスクタイムを彷彿としてしまったが、感情を抑え込んだ(何故?)

コンテスト

実は時系列で書きます

A問題

貪欲マシーンを使ってウィーンした、AC

B問題

木を登るときに倍か倍+1になってるなとわかったが、それだと数が増えていく一方だったので逆算しようと思った
そのまま実装したらAC

C問題

開いた瞬間辛いと思った
とりあえずハッシュの値を求めてみようと思って何故か10^1000を10^10と勘違いしてlong long intで持てると思って実装
当たり前のようにオーバーフロー:kinniku:
まあハッシュ値を求めたところで僕はそれをどうやって直せばいいか思いつかなかった

ここら辺で順位を確認するとCを飛ばしてD,Eに進んでる人がちょいちょいいて、なるほどと思いながらDとEを開く

D問題

とにかくテストケースを試してみた
なんだか2文字で全部行けそうな気がしたので、2文字敷き詰めを考える
特に2*2に着目して、これを敷き詰めたらどうなるか考えてみた
〇〇 〇〇 〇〇 〇×
〇〇 〇× ×× ×〇

全部でこれだけあるが、左1は周りを×で囲む必要が出来るためまず不可能
左2も周りに×と〇の配置が確定していき3つ置かざるを得なくなる
右1も同じようにして詰む
右2は同じものを並べていけばどんな大きさにも対応できることが分かった
これから2文字で常に敷き詰めれることが言えると思ったので、細かい検証をして、数えて場合分けして投げたらACして拍子抜けした
まじかいや、ほんまかいや
2完で残り4時間半地蔵とかにならなくてよかったなぁって安堵のため息をついた

E問題

鍵を記録しようと思ったが、開けた段階でどのカギを使ったか決める必要がないなと思って、使った鍵の種類だけ記憶することを考えた
記憶するのが困難だと分かった
次に全部箱を開けたとして、開けられない箱の分だけ引いてみる事を考えた
これもなんか難しそう管理がダメ
飛ばしてCに戻ることに

C問題(2回目)

さっきはオーバーフローしてしまったので、各項に注目した
サンプルがどのような動きをするか考えると、右のほうに行くほど大きいが、一つ左に進むときに、右の項を1減らして左の項にa足せばいいことが分かった
これを利用してなるべく左端に数字を集めるようにすればいいのではと思った
しかし調整が難しいので、雑に寄せれるだけ寄せた後で慣らすイメージでforループを2回回したらAC
なかなか気持ちよかった

E問題(2回目)

こういう問題で思考が詰まったときはどうすればいいかなって思って考えた
眠くなってきた、4完出来てしまった
もうゴールしていいんじゃないか?
と思ったけど考察すれば解けると信じて考えると、そういえばこの問題だけサンプル図示してないじゃないかと気付いた
サンプルを図示するとどうなるかと言えば、グラフっぽくなった
そしてグラフを見ると、辺と頂点の数の差があればすべての箱が開けられないと言えるなどわかってきた
どうも合ってそうなので実装したかったが、実装力が足りなかった
辛いなぁと思いつつ、もっと簡単に実装できるかもしれないから別解を探す旅に出た
彼に会うことは二度となかった

タイムアップ
解説を聞いて、F以降は異次元だと思ってしまった
まあ4完出来たのでよかったが、何より問題がすごくおもしろかったなと思った
賢い人はもっとうまく解くけど、僕のように考察をしまくれば何も知らずとも解ける問題があったりして、地蔵になるような事が無かった
問題も面白いし、多分AC出来なくても楽しかったんだろうなと思った

懇親会

焼き肉


適当に目の前の席に座ったら運営のあしぃ氏が運営の話や、競プロの話をわんさかしてくれた
まだ僕は始めたてだし、あまりオンサイトとかに参加することもなかったのですごくいい話が聞けたと思った

どの机でも競プロの話が飛び交っていて、当たり前なんだけどこんなに楽しんでてええなぁと思ってた
める氏と肉を頼みまくって腹LEした

帰路ではりか氏、T.M氏、odan氏らと駅まで歩いて向かい持ち前のクソトークとコミュ障を披露した(???)

まとめ

  • 楽しかった
  • 問題の質が良く、作問者に感動していた
  • 知り合いが増えてきて競プロやってる実感が沸いた、もくもく
  • 考察はとにかくサンプルを書く等すると捗る

運営のみなさま、参加者各位ありがとうございました
おわLE