AtCoderのレートが水色になるまでにやったこと

水色になったので自分語りをしたくなりました.
水色の大したことNASAofNASAなど思う人もいるかもしれませんが, 自分にとってはそこそこの到達点なのでここでだけはいろいろ言わせてください().

はじめてのコンテストのおもひで

2018/06/16に初めてのコンテストは30分ぐらい遅れての参加だったことを覚えてます.
Twitterやってたら今日やってんだ〜と思って参加しました. プログラミングが趣味でB2のときにたまーにAtCoderの問題を見ていたのでIDは持っていました. そのときはアルゴリズムのアの字も知りませんでしたが.
B問題のコーナーケースが通らずA,Cの2完という微妙な結果でした.
このときに大学の講義でアルゴリズムについてやっていたので, ある程度勉強すれば競プロもできるかもしれないと思い, 本格的に勉強をはじめました.
そのときに, ぼくの競プロは始まりました.

今までのレート

競プロを始めてから今に至るまで, 時系列順に成績を振り返ってみます.
f:id:xxxasdfghjk999:20181017224808p:plain
(右下の時計君の自己主張はゆるしてください)
6月半ばに競プロをはじめ, 3回目のコンテストで茶色(2018/07/01)になり, 6回目のコンテストで緑色(2018/07/21)になっています. そこからさらに7回のratedコンテストを重ね, 水色(2018/10/13)となっています.
ここで, 過去のAtCoder過去問埋め精進記録を見てみましょう. f:id:xxxasdfghjk999:20181017230137p:plain
軸がおおざっぱですが, 夏休み中の8月に猿のように精進を重ねていたことがわかります.
しかし, 実を言うと8月辺りで猿精進を重ねた後のコンテストの成績はあまり良くなかったです. ABC105とABC106, ARC102辺りではC問題が解けていなかったり, パフォが伸びなかったりで, (ABC105は運良く(?)unratedになりましたが...)正直メンタル的にだいぶ厳しかったです. グラフを見てみても, この辺で停滞してる感じです.
しかし, 来る9月中頃, 予定も立て込んでいて精進もできていなかったのですが, ABC110で初めて上限パフォを出すことができました(これは運悪くunratedになりました). おそらく, この辺りでやっと8月中の精進が効いてきたのかなと思います.
精進の効果が現れるのには時間がかかることを意識するのは個人的に重要だと思っていて, 成果がでなくてもしゃーないかーとか思いながら気楽にできる点が精神にいいと思います.
ABC112では, WAを重ね続けてしまってパフォは微妙なものの全完を成したので, なかなか成長を感じました.
そしてAGC028のA早解きで青パフォを出して水色になりました(ABCで1600出してなりたかった気もします.)

水色になるまでにやったこと

本題です.
その前に, 自分の経歴(?)を紹介しておきます.

わたし

  • 競プロ開始時点で地方旧帝情報系学部のB3
  • 講義や趣味で軽いプログラミング経験あり(Haskell(趣味), C(講義でよく使ってる) , SML(講義でちょっとやった), Python(Twiterのbot作ったぐらい))
  • 微妙な高校を出ていて, 特に数学やら算数が得意でもなんでもない
  • 中古のPC屋で15kのThinkPadubuntuを突っ込んで環境を整えたもので競プロをやっています(emacs使い)

特に, いつでも気軽に起動できるノートPCがあって, ubuntuでCtrl + Alt + Tでいつでもターミナルが開けて, コマンドちょちょいと打つとコンパイルできたりemacsが開けるというのがだいぶ大きかったように感じます. ものぐさで, ささっとできるものでないと続かないんです.
CをやっていたのでC++もすんなりわかったような気がします(わからない).
隙あらば自分語りをしてしまいました. この辺を前提にして読んでください.

蟻本

競プロを始めるとともに, amazonでポチりました. しかし, 新品が高かったので第1版の中古を買ってしまったんですね. この前本屋に行って蟻本を見かけたら, 第2版というものがそこそこ厚くて驚きました... 幾何やらなんやらの追加コンテンツができていたみたいですね. うーん安物買の銭失い...

蟻本でやったこと

やった項目は
2-1 すべての基本"全探索"
2-2 猪突猛進!"貪欲法"
2-3 値を覚えて再利用"動的計画法"
2-4 データを工夫して記憶する"データ構造"
2-5 あれもこれも実は"グラフ"
3-1 数学的な問題を解くコツ
3-2 値の検索だけじゃない!"二分探索"
3-3 厳選!頻出テクニック(1)
は一通りはやりました.

蟻本はぶっちゃけわかりにくいです. わかりにくいんですが, 競プロの問題がテクニック別にカテゴライズされているので, テクニックの辞書として使えます. コンテスト中に詰まったらとりあえずペラペラして使えそうなものないかなーって探すこともできるので, 持っておいて損はないです.

蟻本がわかりづらいと感じたら, けんちょんさんのQiitaのAtCoder蟻本(大変お世話になっています)とか見てみるといいと思います. いい問題がたくさん集まっていて, 解説もネットの海を探せばいろいろあります.

蟻本に関しては以上です.

yukicoder 埋め

8月の終わりぐらいにyukicoderをやり始めました. AtCoderとは毛色の違う問題が多いですが, 解くのが面白い問題が非常に多いです. 緑のときは★2 , または★2.5ぐらいを埋めていました.

AtCoder過去問埋め

こんな進捗です.
f:id:xxxasdfghjk999:20181017234419p:plain
D問題がわりかしたくさん埋まっていますが, 水色を目指すのならC問題を埋めたほうがよかったかなーと思います.
コンテスト中にDが解けずとも, Cの早解きでパフォが十分とれることがかなりありました.
ABC-C埋めが終わったらARC-A埋めもいいと思います. A,B問題が埋まっていませんが, やってもいいと思います. 虚無埋めなどと言われてますが, ACとれるのは楽しいですからね.

過去問を解くときは, 20分ぐらい考えてわからなかったら解説を見る, の繰り返しです. そして, 重要な問題だと感じたら記事を書く... という感じです.
こういう過去問埋めのときに知らないテクニックが解説に出てくると萎えるので, 埋める前に蟻本(中級までで簡単なところ)をやっておくことをおすすめします.

ブログ

あなたが見てくださっているこれです.
解説ブログを書くと, 意外と自分理解してないなーとか思うことがよくあって, いろいろ発見があります. 解法の言語化っていうのは大事だと思います.

Twitter

8月の終わりぐらいだったか競プロ垢を作りました. 強い人やレートが同じぐらいの人をフォローすると, 憧れやら, 自分もがんばんなきゃなーと思ってがんばれます. あと, コンテストの情報が入ってきたり, 新鮮な解法情報がコンテスト後に流れ込んでくるので, 作っといてよかったと思います.

まとめ

  • 蟻本でよく使うテクニックを学ぶ
  • 過去問を解く
  • 解法を言語化する
  • 同好の士をフォローする

こんなことをやってきました.

これからの目標

とりあえず青を目指してがんばりたいです.
まずは蟻本を進めて, セグメントツリーなるものをがんばって作りたいです.
まだまだこれからですね.

AGC 028 反省

Aのみの1完. 早ときかどうか微妙なタイムでしたが青パフォがとれ, 無事水色になることができました. Bもちょっと考えたんですけど, わからずじまい....とりあえず水色になった喜びも込めて, Aのみ書きます.

A問題

解法

条件から, |X|G = k*lcm(N,M)であること必要となります(kは整数).
まず, 答えの最小値であるk=1, |X| = GS, Tが構成できるかを調べます. 具体的には, mapXn番目の文字をSについて埋め, Tで答え合わせします.
構成できなかったときは-1を出力し, 構成できたときはk=1, Gが答えとなることがわかります.
では, k=1, |X| = Gで答えとなるものを構成できなかったとき, あるkが存在して, 条件を満たすGが存在するのかどうかを考えます.
結論を言うと, 答えを構成できなかったときはこのkは存在せず, -1を出力するのが答えです.
なぜなら, 答えとなるものが構成できないということはXにおいて, STが参照するものが衝突(食い違っている)している, ということになります. この衝突が起こる文字の位置は, lcm(N,M)を何倍しても変わりません(添字の計算式に代入してみるとわかります).
等号が成り立っている両辺に同じ数をかけても等号が成り立つのと同じです.

感想

やれることを探すと, 発想は自然に出てきます. しかし, この解法が成り立つのかどうかを考えるのに時間がかかりました. 開始15分ほどのsubmissionでしたが, 水へのパフォは十分で, なかなかAGC-Aにしては解きづらい(というより読みづらいでしょうか)問題だったような気がします.

総評

とりあえず水色やったああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああ!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
というのが第一です. Twitterでもいろいろな人に祝ってもらえてうれしかったです!
競プロのコンテストにではじめて4ヶ月, あのときはC問題もおぼつかない状態でしたが(これは罠で今もおぼつかない), なんとか水色になれました. 真っ直ぐな道ではなく, なかなかレートが伸びない時期もありましたが,
伸び悩んでいた時期に読み漁った先方erの『水色になるまでにやったこと』記事がなかなか助けになったため, ぼくも暇があれば執筆したいです. というかそれを書きたいのが精進のモチベになっていた気さえします().
次からARCじゃないとレートがつかないのかーとか思うとなかなかプレッシャーですね...
ひとまずは緑に落ちないようにがんばりたいと思います.
埃被った蟻本を再び開くときがきたようだな...って感じです.

ABC 112 反省

全完しました.
しかしC問題に時間をかけすぎてパフォは低め...

A問題

解法

なんかいつものA問題と少し違って驚き.
一個入力を受け取って, 場合分けをします.
"Hello World"のつづりに注意します.

感想

ちょっとびびるもACできてよかった.

B問題

解法

ループを回して, 条件を満たしているものの最小値を取ります.

感想

うん.

C問題

問題

C - Pyramid

解法

問題文をじっっっっっくり読みます.
Cx,Cyが小さく, これら2つを全探索できそうであることがわかります. これらを決めると, あるx_i, y_iについてHが1つ決まります. これに対し, すべての(x_i,y_i,h_i)を調べ, このHが条件を満たしているか調べます.
しかし, これだけでは不十分で, あるh_iが0のとき, 状態が2つ考えられます. この状態に関してはHが確定した後で考える必要があるため, 後回しにして考える必要があります. 制約から, ある0でないh_iが存在しているので, 後で考えてもよいことがわかります.
これを実装するとやっとACできます(9WAしました).

感想

顔を真っ赤にしながら実装していました.

D問題

問題

D - Partition

解法

答えは, Mの約数であることが必要っぽい(?)ことをエスパーしたので, 約数を全列挙し, その約数を何個作れるか?を考えると, すべての約数について, max\{q | qはMを割り切り, M/q \geq N \}が答えになります.

感想

CをやっとACしたあとで, ろくに証明もせずになんとなく出したのですが, ACできてよかったです.

総評

次のAGCこそ水色になりたい

C++でNimをつくった

C++で某石取りゲームNimを作りました. Nimのコンパイラを作ったわけではありません... CPUと対決するようなものを作りました.

付録のソースコードコンパイルしてお楽しみください.
開発環境の都合で表示がバグったりするかもしれないですが勘弁.

使い方

  1. 起動します
  2. なにも始まりませんが, 石列の数(数値)を入力します(面倒なので数値以外を入力することを想定していません...)(1~30ぐらいが安全です. )
  3. ゲームが始まります(必ず先手でスタートします順番ぎめが面倒だったので)
  4. 最後の石をとると勝ちです. がんばりましょう. CPUは一瞬で石を取るのですぐに自分の番が来ます.

各石列が16個までなのは開発環境の都合です.
クラスとかメソッドとかいろいろ学べてよかったです. あまり活かせてませんが.
にしてもグラフィカルなUIはめんどいっすね〜めんどいめんどい.

コンパイルオプション

	g++ -std=c++11 -o nim nim.cpp -lglut -lGLU -lGL

スパゲッティなソースコードは続きから

続きを読む

ARC103 反省

CとDの部分点の1.5完. とれるところは全部とれたと思う. けど立ち回りがよくなかった.

C問題

問題

C - /\/\/\/

解法

偶数添字と奇数添字でグループ分けできる. それぞれで最も数が多い数字にするのが最善であるが, その数字が同じだったときの処理が面倒(最後のサンプルで気づいた).
具体的には, 数字の数が最も多い数字を記録しておき, プリオリティーキューに偶数番目と奇数番目の数字の数を別々のものにいれておき, 数字が一致してしまったときに, どっちかのキューの2番めに大きいものと交換して差が小さくなる方を選ぶと最善.

感想

コンテスト中はコーナーケースあるのでは?とか考えてちょっと提出をためらってしまいました. 実装も面倒で面倒な問題です.

D問題

部分点のみで, 後で満点は解き直します.

解法

部分点解法のみ.
まず, がんばって問題文を読解します.
X_j,Y_jについて, (X_j+Y_j) \space mod \space 2を考えます. この値が異なるものが存在したとき, どうやっても答えを構築することはできません.
なぜならば, d_jをどのように設定してどのように足しあわせても, 各d_jの和の偶奇は不変で, 偶数グループまたは奇数グループについて, 移動しえない場所が存在してしまいます.
上の条件を満たしていると考えると, すべてのd_jについて, d_j = 1としたとき, 部分点の制約ならば十分小さいmで構築が可能であることがわかります.
具体的には,
(X_j+Y_j) \space mod \space 2 = 0のとき, m = 20として目的の場所まで真っ先に移動し, 反復横飛びでもして残りの移動を費やします.
(X_j+Y_j )\space mod \space 2 = 1のとき, m = 19として目的の場所まで真っ先に移動し, 反復横飛びでもして残りの移動を費やします.
これを実装して300点です.
600点はまた今度...

感想

和の偶奇とかいうの, 結構当てずっぽだったんですけどヒットしたみたいでよかったです.

総評

Cを遅解きしたあと順位表を見てみると, 誰もDをやっていなかったのでEを見たんですが, 結局は解法は生えずに結構な時間を費やしてしまったので, 結果論ではありますがDをもっと速く考えていればレートは伸びたかなーと思います.
コンテスト中は自分の身の丈にあった問題を考察していきたい.
rating 1089->1134

ABC 110 反省

ABDの3完.

A問題

解法

条件から, どれか一個だけ10倍して足すことができるのと同値になる. よって,  max\{10A+B+C, A+10B+C, A+B+10C \} が答え.

感想

Aにしてはちょっとむずかしい.

B問題

解法

max\{x\} \leq min\{y\} \land X \leq Yならば'No War' ,そうでなければ'War'です. 本番ではmin\{y\}とmax\{x\}だけ調べてmax\{x\} \leq min\{y\}かどうかを見て, X < Z \leq Yを満たすZが存在するかどうかはそこにさらにループを回して調べました.
今考えると, 無意味ですし実装が面倒になるだけだと思います. 実際, 実装のミスで1WAしています. (リジャッジ後もWAのままでした...)

感想

これもなんか問題文が読みにくく, Bにしてはちょっと面倒です.

C問題

解法

コンテスト中に解けず. 考えていたのは, あるアルファベットからアルファベットへの対応を調べ, 2つ以上に対応するものがあればNo, そうでなければYes, というロジックだったのですが, 実装も考察もまずくWAを連発.
WA解答では無向グラフのように対応を双方向に一気に定めていたため, ハッシュマップがめちゃくちゃになってしまっていたようです.
書き直した解答では, 対応する文字が2つ以上あったときにNoを出力するのは同じですが, あとで対応先の文字がただ1つのアルファベットのみに対応していることを確認するようにしています.
前者がアルファベットからアルファベットへの単射であるかの確認, 後者がその対応がアルファベットへの全射であることの確認となっています.

感想

えーこれ難しくないですか><.

D問題

解法

『素因数をいくつかの箱に入れて分割する』というのは, ARC-004D
D - 表現の自由 ( Freedom of expression )で見ていた(解いていませんでしたが)ので, 分割数やらで掛け合わせるのかなとコンテスト中は, ベル数やらスターリング数やらを調べていましたが, 結局素因数をN個の箱に分配するときの重複組み合わせでDPができることに気づき, それを実装しました.
今考えると, ARC-004Dの解答を見れば早かったですね...
DPは,
dp[i] = i番目の素因数までを使ってN個の箱に素因数を分配する場合の数
とすると,
dp[0] = 1
dp[i+1] = _{N}H_{p_{i+1}}dp[i] \space( p_i はi番目の素因数の個数. 2*3*5^2 ならば p_1 = 1, p_3 = 2)
となります.
前後のみを見ているdpなので0次元DPに落とせます.
制約の中では, 素因数の数はたいして大きくならず, コンビネーションの前処理は定数なので, この問題の計算量はM素因数分解がネックとなり, O(\sqrt M)となります.
実は本番のコードはO(M)素因数分解をしてしまっています...
しかし, 通ってしまいました.

提出

(コンテスト時提出したもの)
Submission #3257928 - AtCoder Beginner Contest 110
(O(\sqrt M)に改善したもの)
Submission #3270638 - AtCoder Beginner Contest 110
実に800倍の速度の差が出ています.

感想

ささっと思いつけてよかった.

総評

B問題に不備があり, 結果unratedとなりましたが, 初めて推定パフォ1600上限を出せたのでよかったです.

ABC 041-D 徒競走

問題

D - 徒競走

解法

 N \leq 8 のときの部分点はnext_permutationを使うと獲得できます.
満点解法では 16! = 2.0 * 10^{13}通りを考える必要があるので, 別の解法を考える必要があります.
2^{16} = 65536と, うさぎの集合を見るようにすると数が小さいです.
これに着目して, bitDPを行うことを考えます.
 dp[S][n] = 集合Sにおいてn番目のうさぎが最後尾であるときの並べ方
とすると,

基底

 dp[\{n\}][n]  = 1

遷移

 dp[S][n] = 0 \space  (\exists_k ( (n < k)  \land k \in S))
 dp[S][n] = \sum_{(k \in (S-\{n\})) } dp[S-\{n\}][k] \space (otherwise)
とかけます. 遷移においての (n < k)というのは, 与えられた \{x\} , \{y\}について, 最後尾が n であるが,  k \in Sより nの方が速いといったときには矛盾を孕むことになるので, そのような場合の数は存在せず0となる, ということです.

感想

 Mについての制約をよく見ておらずに領域を十分にとっておらず, ACときどきWA状態でオンオンしてました. 領域足りてなかったらREでてほしいです...(我儘).