DDCC2020参加記
はじめに
先日2020/1/25に株式会社ディスコで行われたDDCC2020本戦に参加してきました．初オンサイト楽しかった...
予選
ごちゃごちゃ書きまくったD問題が何故か通る
ダメ元でただただ周期をとっただけで何故か通る
あの時はダブリングとかの実装に自信がなかったので...
本戦
ということで本戦です．
僕はたまたま親が仕事で東京にいるので仙台から前日に東京に移り，前泊して本戦へ．
前日に観光をしました．
↓某映画の聖地に行きましたが，桜がないので威力が弱いですね．
会場に入ると初Tシャツをゲットし，こたつがめさんの隣に座ります．
そして寿司打をしてウォームアップをすると本戦が始まりました．
#ddcc2020
— むげん (@mugen_1337) 2020年1月25日
高級10,000円コース【普通】で、
★8,200円分 お得でした！（速度：6.6key/秒、ミス：41key）
https://t.co/wEk0pWBPle #寿司打
コード部門
-30:00
ちょくだいさんがいる．え？すげぇ本物じゃん
なまちょくだいさんはじめてみたな
— むげん (@mugen_1337) 2020年1月25日
-0:10
お姉さんがカウントダウンをする．
なんかもう楽しい
0:00
開始と同時にA問題をみます．周囲からものすごいカタカタ音が聞こえてきてビビリますが，落ち着いて読むとNimをしろと書いてあるのでNimをしました．
04:52
A問題AC
05:00~
B問題マジで何もわからん．C問題のほうが通されているのでC問題を観る．辞書順についての考察が盛大に間違っており，1時間が無駄に過ぎる
1:05:00~
SuffixArrayでやればいいじゃんと思いうしさまのﾗｲﾌﾞﾗﾘから引っ張ってくるが，使い慣れていない&残り時間が少ないという焦りで何もできず...
1:40:00
終了後もコードを書き続けて終了10分後に通る．もう帰りたい...
https://atcoder.jp/contests/ddcc2020-final/submissions/9706317
A問題を爆速で通した&B,C問題が難しかったおかげで87位という思ったよりいい結果になりました．
ですが85分無をしていた悲しみが大きく...
装置実装部門
日本語多すぎ．読めないわからないデバッグがヘタクソそもそも問題を読み違えている．
~完~
お昼
懇親がヘタクソなのでもくもくとビュッフェを食べる．終了間際に東北大の少ない競プロerと懇親をしました．
社内案内
お姉さんが可愛い
装置実装部門決勝
ちょくだいさんおもしろいし企画おもしろいし，観戦してるだけでめっちゃ楽しい．
疑惑の判定からのやり直しで逆転優勝はムネアツでしたね．
夜の懇親会
頑張って渾身の懇親をします．とりあえず碧黴さんとこたつがめさんと懇親をしました．ビールで乾杯をしました．こたつがめさんがめっちゃビール苦手そうだったので来年はビール以外のお酒もあるといいですね．確かにプラコップで飲むビールはなんか苦く感じました．ジョッキか缶で飲みてっす
その後もNはらさん(めっちゃ好青年)や，東北大のhaさんやbakuさんと渾身の懇親をしました．競プロの問題について話して盛り上がれるのってすごい楽しいですね！
まとめ
DDCC最高！一番好きなDDCCです！
本気でDDCC来年も出たくなってきたな、熱烈精進ワンダーランドするか
— むげん (@mugen_1337) 2020年1月25日
AtCoder で青色になれたお話
最初に
水に到達(2019/9/28)から約4か月，先日のキーエンスプログラミングコンテスト2020でついに青に到達しました！やったぜ！！（号泣）
精進したこと
水になった時に書いた記事で水になるまで精進したことを書いたので水になってから精進したことについて書きます．
まず，大まかに精進の時にどういうことを意識していたかについてですが，ずっと"難しい問題へのアプローチの仕方"を練習していました
「こういう区間がいっぱい与えられる問題は，セグ木などのデータ構造を使う，左端右端でソートすると何か嬉しくなるのどちらかだろう」だとか，
「制約がN<=18だから何かの情報をbitで表すんだろう，bit全探索，bitDPなどを疑おう」みたいな様々な問題のパターンに対するアプローチの手段をたくさん学ぼうとしました．
以下に具体的にやっていたことを書きます．
コドフォにいっぱい出た&コドフォのバチャをやった
はい．そのままです．AtCoderで解けるちょうどいい難易度の問題が減ってきたのでコドフォに手を出しました．楽しい！
コドフォは個人的には色んな要素が複合されて実装が重くなるような問題が結構出る気がします．コドフォをやってから実装力がついたと思います．
あっとこのコンテストがない平日は，コドフォのバチャをやって復習，を繰り返すことでモチベーションを保ちながら精進を続けられました．
下に勉強になったなぁという問題をまとめます．（これは自分がいつか復習をするためでもあります．)
カッコ列 - https://codeforces.com/contest/1263/problem/E
あんま見たことないDP - https://codeforces.com/contest/1202/problem/B
最小値の最大化は二分探索！ - https://codeforces.com/contest/1288/problem/D
なんかもっとあった気がするな...思いついたら追記します
旧ARCの青~黄色難易度を埋めた．
旧ARCは典型問題が結構転がっているような気がします．最近のコンテストの問題でも旧ARCの何かの問題に似ている問題がよく出ているような気がしなくもありません．
日経コンの D - Shortest Path on a Lineと
蛍光灯
ABC149のE - Handshakeと億マス計算
とか個人的に「え，だいたいおんなじやん」と思いました．
その他にも，ARCを埋めていると「はえ～BITで二分探索やるの知らなかった～」とか「ダブリングテーブルを自分で作ってクエリにこたえる問題初めてみた～～」とか学びが多かった気がしました．
まだARCの2問目までをあまり埋めてない人には個人的におすすめです．
だいたいこんな感じです．
まとめ的な
水色になった時は「なんかもうパフォ1500くらい出るし，青も頑張ればなれるんじゃないかな」みたいなことを思ったのですが，青になった今は次の黄色が全く見えません．困ったな...でも今年はICPC出たいしだらけずに頑張りたいと思います．
Codeforces 608 E Common Number
コンテスト中には解けなかったけど，おもしろかったので記事に残しておきます
オーバーフロー指摘して，助けてくれた某さん本当にありがとうございました．
問題のリンク
codeforces.com
問題概要
n，k(1<=k<=n<=1018)が与えられる．1~nのすべての数(xとする)に関して，偶数なら割る2，奇数なら引く1を1になるまで繰り返す．すべて操作し，登場回数がk回以上になる数のうち最大の数を出力する．
例えば(n=7，k=3)なら操作は以下のようになる
7 | 1 <- 2 <- 3 <- 6 <- 7
6 | 1 <- 2 <- 3 <- 6
5 | 1 <- 2 <- 4 <- 5
4 | 1 <- 2 <- 4
3 | 1 <- 2 <- 3
2 | 1 <- 2
1 | 1
よって3回以上登場する数の中で最大なのは3なので答えは3．
コンテスト中
とりあえずnとkが1018までってデカすぎるだろ正気か？となる->
まぁでもデータ構造は何も使えないだろうからどこかで単調性を見つけて二分法をするんだろうと思う->
とりあえず実験をいろいろやってみると，偶数と奇数で動きがちょっと違うけど↓こんな感じに式で表せそうと気付く
iの登場回数をg(i)とすると
g(i) = 0 (i>n)
g(i) = 1 + g(2i) (i:odd)
g(i) = 1 + g(2i) + g(i+1) (i:even)
1というのはi自体が登場することを言っており，iが奇数であれば2iからiになることを考えれば2iの数はすべてiに遷移するので2*iの登場回数を加えればいいです．偶数も同様に遷移を考えると上のようになります．1つ目の式を考えると上の式を愚直に再起で回せば各数の登場回数が求まりそう！
->証明は後述しますが，偶奇でそれぞれiが大きくなればg(i)は小さくなるという単調性があることに気づきます．
これを使ってg(i)がkを超えるかの境目を二分法を偶奇それぞれで探して，いいほうを出力するコードを提出します！
Submission #66962483 - Codeforces
-> TLE...（´・ω...:.;::..ｻﾗｻﾗ...
まぁそれはそうなんですよね，これめちゃくちゃ大量に再起するし，詳しい計算量解析はちょっと難しくてわからないけど，実験してみたらすげぇことになった(語彙)
コンテスト後にわかったこと
奇数の方は再起関数を使わなくても登場回数がわかるんですね．
まず，割る2するという操作はビットを1右シフトするという操作であることを考えると，一連の操作はビットで考えるとわかりやすいです．
操作は，11101->11100->1110->111->110->11->10->1 のように行われます．
最右桁を1から0にしてその0を消す．を繰り返すんですね．
このことを考えると，例えば3 (11)の登場回数は1~nの中の上位ビットが11となっている数の個数になります．
11XXXXXという数なら先ほどの操作を繰り返せばいずれ11になります．逆にそうじゃない数からは11に遷移することはありません．
よって奇数の方のg(i)はビットを考えてあげるとlog(i)で求まります．
よって奇数の方は先ほど言った単調性も成り立ちます．
偶数のほう，例えば110の登場回数は上位ビットが110もしくは111になるような数の個数になります．
これを考えると偶数のほうも単調性が成り立ち，二分法が可能そうです．
偶数のほうもいい感じに改良できるのかな？と思いましたが，偶数のほうはそのまま再起のままでとりあえず出してみたら通りました．(おい）
↓がその提出です．
まとめ
コドフォ最高！
AtCoderで水色になれたお話
はじめに
どうもこんにちはむげん(AtCoder ID: mugen1337 / Twitter)と申します．先日のAtCoder Beginner Contest 142でやっとレートが1209となり水色になれたので一つの区切りとして自分の今までの精進してきたことをまとめようと思います．（あとはてなブログのアカウントを作って記事を上げてみたかったてのもある．)
自己紹介&競プロをやるきっかけ
軽く自己紹介をするとぼくは仙台のどこぞの国立大学の情報学科に通う一般大学3年生です．競プロ以外のプログラミング経験はほとんどありません．
競プロをすることになったきっかけですが，2年のころ，一緒に授業を受けていた友人がAtCoderとかいうサイトで競プロをやっていると聞いて，どうやらおもしろそうってことでアカウントを作りましたが，ま～～～～ったくモチベがなく，毎日夜通しネトゲ三昧でした．これが長い灰色時代．
ところが3年の春休みなぜか競プロに熱中します（唐突）まぁ前々から何かプログラミングをしたいと思ってましたが，きっかけがなかったところ友人が競プロを始めたので僕も乗っかってやることにしました．
精進について
僕は3年の夏休み前に緑の1000あたりをうろうろしていて前半学期のテストが終わると夏休み中に水色になると友人に高らかに宣言します(インターン全落ちしたし)．
そこから怒涛の精進をして結果的に水パフォ以上が連続して(直近3回ですが)出せるようになったのでその夏休みの精進したことについて以下に書いていきたいと思います．ですので，この記事は「緑上位パフォ出るけど水パフォでないよぉふぇぇぇ～><」みたいなショートヘアの似合う女の子の助けになればと思います．
勉強したこと
アルゴリズムとしては蟻本の中級編まで(フローだけは飛ばした)と，4章のグラフマスターのところを勉強しました．これをしっかりと読み込んで理解して，人のライブラリをのぞいたり自分でライブラリを書いたりしました．
以下に夏休み重点的に練習したことを列挙して，実際その時に解いたおすすめしたい問題も一部添えてみます．
* とにかくbfsはdfsスムーズに！ ( ABC088D，いい問題->ABC070D )
* 組み合わせや順列の問題(dwacon2018, ABC110D)
* 答え決め打ちするニブタン(ABC023D,ABC020,ABC141E(別解))
* セグ木,SparseTableなど区間を嬉しくするﾔﾂ(ABC095,ABC125C)
* ゲーム(ﾏｼﾞで苦手だった) (TTPC,CADDI,ABC059D)
* グラフ諸々(ABC137E,ABC074D,AGC032B)
思いつくのはこんな感じですが，とにかくひたすら問題を解いていました．
夏休みの精進を通して感じたことなのですが，400~700点問題を埋めているとデータ構造の扱いが本当に上手くなったなぁと感じます．300~400くらいの問題で適切にmapを使うと高速に解けたり，難しい問題でsetで上手くシミュレートすると計算量が落ちてACできたりと，特に本当にmapとsetの扱いが上手くなったのは感じます．
よかったなぁと思う勉強法的なの
夏休みはこんな感じでパターンごとに問題を集中して解くことの他にもランダムにイイ感じの難易度の問題をじっくり考察する．をやりました
具体的にはAtCoder Problemsの水難易度の問題を超考えました．そして解説ACを実質禁止しました．もし2時間くらい考えても解けなければ他の問題に移ってその問題はあとで移動中とか，ご飯のときとかに頭の片隅で考える，みたいなことを毎日していました．
結果的にこれが考察力を上げることにつながったと思っています．シャワーを浴びながら700点の考察を完璧に詰めたときはうれしかったですね．風呂場で全裸で踊りました．
解けた後はしっかりと模範解答や強い人のコード見て反省も
おわりに
ずっと水色になりたいと思って精進していたのですが，いざ水色になってみると困ったことに青色になりたくなっちゃったんですよね．マジで終わりがみえねぇぜ競プロ．これからも精進を絶やさず色を変えていければと思います．
