AtCoder 黄色になる方法のうちの一つ
ついに黄色になりました。嬉しいです。多分人生で一番嬉しい。
思えば、競プロ始めてから 4 年と 3 ヶ月が経過しており、青になってからも 2 年と 4 ヶ月が経過してました。 黄色になるまでの rated なコンテスト参加回数は、なんと 166 回です。
家族とハワイ旅行に行った時も、深夜に起きてコンテストに出場したのはいい思い出です（レートは落ちましたが）。 インターン先の人事の方に飲みに誘っていただいた時も、コンテストに出場するのでごめんなさいをしました。あの時はごめんなさい。
青になってから、幾度となく黄色チャレンジをしては心を折られる毎日でした。 見えない壁が存在して、毎回グラフが反射しています。黄色になれたのは、5 度目の正直といったところです。
黄色になるための方法のうちの一つ
多くの人が言及している通り、ABC で高度な考察を要する問題はほとんど出ません。 出題される問題のほとんどが、典型アルゴリズムの組み合わせで解ける問題です。
橙くらいの強い人が、コンテスト後に以下のようなツイートをしているのをよく見かけます。（これは特定のツイートを指すものではなく、蓄積された橙コーダーのツイートのイメージです。）
ABC◯◯◯お疲れ様でした。 A：うし B：たぷ C：にきあくん笑 D：一番難しい。D 問題に 998244353 difficulty の問題を出すのやめろ E：問題文答えが書いてある F：はるだけ
最初は初級者を煽っているのかと思っていましたが、そうではないことに最近気がつきました。おそらく、ABC レベルの典型アルゴリズムを習得した上級者にとって、D, E, F 問題の 難しさに差がない のだと思われます。
ABC は考察の難しさというより必要知識 / ライブラリのレベルで配点が決まってるっぽいので、その知識を持ってる人にとっては D〜E より F の方が楽なことが多々あるよね
— opt (@opt_cp) 2021年6月27日
例えばそのまま書くと「ABCは思考力0の問題が出題され、ARCから思考力が問われ始めます」みたいなことがあって、自分はその意図はわかるんだけど、それをそのまま発信すると明らかに正しく伝わらないので、頑張って翻訳をしないといけないところがあり……。
— chokudai(高橋 直大)🍆 (@chokudai) 2021年6月26日
これを翻訳すると、「ABCは、競技プログラミングにおける典型を把握し、論理的に突き詰めれば自然と引き出せる典型を選択する、という行為をマスターした上級者であれば、問題を読めば一瞬でわかる問題が出題されますが、ARC/AGCからは、上級者でも一瞬でわからない問題が出題されます」みたいな感じに
— chokudai(高橋 直大)🍆 (@chokudai) 2021年6月26日
ABC の E, F で出題されるレベルのアルゴリズムは難しいですが、時間をかけて理解をし、類題をたくさん解くことで、凡人でもコンテスト中に解けるようになります。 一方で、E, F 問題で出題されるアルゴリズムは事前に知っていないと ほぼ勝ち目がない です。（論文になるようなアルゴリズムを、コンテスト時間中に再発明できる人は稀です。）
僕は ABC までに出題される典型アルゴリズムをほぼすべて習得することで、黄色になれました。 典型をすべて抑えることが、黄色になる一つの方法だと思います。
賛否両論あるかと思いますが、新しいアルゴリズムを勉強した時は、関連する問題を集中して全部解くという精進方法を取ってました。 例えば、F2 線形代数を勉強したら、「F2 線形代数 競技プログラミング」と Google で検索し、hit した問題をすべて解いてました。 そのあと、信頼できる上位陣のコードを読み、ライブラリにできるところはどんどん盗みました。
この方法は、以下のような pros/cons があると思っています。
- メリット：出題パターンを網羅できる。短期集中で習得できる
- デメリット：ネタバレを受けた状態で問題を解くので、より高度な問題（AGC など）への応用力がつきにくい
もちろん、ARC/AGC で勝ちまくって黄色になる人もいると思います。そういう方法に関しては、僕にはできそうにないので、記事に書くことができません。
これから
競技プログラミングからは少し距離を置こうかと思います。 最近は、ABC で勝つためだけの精進をしてきたので、これからは高度な問題をじっくり考えるような精進をしていきます。 当面の目標は、大学同期の TAB (@_____TAB_____) | Twitter にレートで追いつくことです。
軍艦ゲーム、Sugoroku2 と似てるから、一次式を持つ DP ができませんか？
できません
対象読者
- F - Sugoroku2 の公式解説を両方理解している人
- D - 軍艦ゲーム が Sugoroku2 みたい 一次式を持つ DP でとけるのでは？と思っている人 （公式解説は二分探索して DP）
理由
軍艦ゲームは、Sugoroku2 と違いプレイヤーに選択肢がある（等確率に隣接頂点に移動するか、スタートに戻る）。DP なので、2 つの選択肢のうちコストが安い方を採用したくなるが、x がまだ決まってないので比較のしようがない。
AtCoder 黄色になるまでやったこと（黄色になっていないバージョン）
この記事は「色変記事 Advent Calendar 2020」 5 日目の記事です。
4 日目は ⚫️Y.Y.⚪️ さんによる「Y.Y. の Y は Yellow の Y」です
6 日目は drogskol さんによる「黄色じゃなくなりました」です．
12/5（土）は、鹿島建設プログラミングコンテスト2020（AtCoder Regular Contest 110） が開催されました。
参加前のレートは、1983 で、色変の可能性は十分でした。
アドカレですが、土曜日が熱すぎて、楽しみです！
— 蟹道きりみ@競プロvtuber (@ayoiyouyoeyo) 2020年12月3日
monkukuiさんが黄色まで残り17なので、ギリギリいけるかです！
(もちろんお遊びですので、みなさまプレッシャーに思いすぎず、リラックスしていただければと思います💦)
結果
monkukui のさらなる挑戦に期待してください。
ICPC 国内予選 2020 参加記
結果
ICPC 国内予選 2020 にチーム「tsutaj」で参加しました。 ABCDE の 5 完で、全体 18 位、学内 1 位で予選突破しました。
本記事では時系列に沿ってタラタラと思い出を語ります。
3 年前（2017）
学科紹介で ICPC を知る。 とりあえず出てみるか 順位：204/358 まぁそりゃあね
2 年前（2018）
1 年間準備をした。大学生活の全てを競プロに費やしていた。 学内 2 番手と言われるチームで ICPC に出場した（1 番手は tsutaj, TAB, えびちゃん の four-t）。
結果は学内 3 位で敗退 どうして...
1 年前（2019）
過ちは繰り返す...
学内 3 位、敗退...
半年くらい前
tsutaj が卒業するので、TAB、えびちゃんにチームに入れてもらう。 偉大な先輩に最大の敬意を込めて、チーム名を「tsutaj」にする。
定期的にチーム練をしたりした
1 ヶ月前
かなりチーム練をした気がする。
2 週間前くらいから、土日全てを返上してチーム練していた。
前日
前日の夜に突然、顧問から電話がかかってきて、一緒に松屋に行った（どうして？）
当日
A が monkukui、B がえびちゃん、C が TAB でやる。
A より先に B が AC される（えびちゃんはやすぎない？）
1 分後くらいに僕が A を AC する。最初、2020 だけでなく、1010 とか 5656 とかでもいいかと勘違いしていた。（焦りすぎ）
C を TAB がつらそうにしているので、少し問題文を読んだけど、僕が苦手な問題っぽい。TAB 君を信じて任せる（ごめんね）
D が構文解析なのでえびさんに伝えると、「やったー、わーい、えへへ」みたいなことを言っていたので任せることにする。
E を読む。
見当はずれな DP を思いついて、Slack で解けたと発言したり、解けてなかったと発言したりして、かなり迷惑なことをしていた。（焦りすぎ）
この時点で学内 3 位だったかな？ICPC のトラウマが蘇る。今年も敗退か...
TAB 君が愚直に近い解法で 15 分くらいで PC を回して、C を AC してくれた。ありがとう。
えびさんが D をつらそうにしているけど、えびさんを信じて放置（ごめん）
TAB 君に E を相談すると、流れるような考察ステップで見事に計算量を落としていく 痺れた
「60 * 60 は 行の偶奇に分けると 30 * 60 になるね」
「市松模様は二部グラフで、頂点集合ごとに独立に解けるよね、15 * 60 になった」
「一列ごとに bitDP ができるね、遷移は 215 * 215 をするとやばいけど、部分集合を列挙するいつものテクを使うと 315 になるね」
この考察を盛りなしで 3 分でやってた。TAB 君すごすぎ。
TAB 君は考察担当ということが決まっていたので、E の実装を僕が引き受け、TAB 君には D に加勢に行ってもらう。
D はえびちゃんが途中で何かにひらめいたっぽくて、TAB 君はそれを信じて F に行ってた気がする（E の実装に集中していてうろ覚え）
間も無く D が AC されて、えびちゃんすごい
本番で構文解析が AC できて、努力の賜物です。
E がバグったことを報告し、すぐさまコードを共有した。
えびちゃんはデバッグが得意で、ここが怪しいとか、ここで配列外参照をするとかたくさん指摘してくれる。
指摘されたところを直すとサンプルが合うので実行する。なかなか終わらないな〜と思っていたら、えびちゃんがパラレルで実行してくれていたらしく、PC スペックの違いを感じる。
E 通ることをお祈りしていたら、
えびちゃん「あ、E 通ってますね」みたいなことを発言していて、なんかよくわからなかった（順位表を見てたくさんの人が通しているのか、僕の E が通ったのか）。
TAB 君が F を解けてるっぽくて、実装を頑張っていた。
「果敢にも、GH に挑戦するか、F の愚直を書くか、どっちがいいですか？」とか発言したら、「愚直を書いて」と言われたのでそうした。
E を通して興奮していたので、問題文が 10 分くらい頭に入って来なかった ごめん
F の愚直が書き上がる
F は提出するも WA
残り時間が 5 分だったので、generator を書いてる時間はない。手で Hack ケースを探していると、
1 0
で RE していることに気がつく。
TAB 君に伝えて、提出してもらうと、
the contest has been over みたいな表示がされてて時間切れ。もし通ってたら全体 5 位だったと思うと悔しいので、落ちててほしいね みたいな話をした。
まとめ
「2 度あることは 3 度ある」で、3 回連続国内予選敗退していた。今年は「4 度目の正直」で突破できたので、ものすごく嬉しかった。 アジア地区予選に出場するのは初めてなので、オフライン開催されるといいなぁ いろんな人と交流したい。
応援ありがとうございました。
競技プログラミング用、グラフ可視化ツールを開発しました
これはなに？
グラフを可視化する CLI ツール ggg を開発しました！
何ができる？
グラフの問題を解いている時、サンプルを可視化したくなる時がありますよね？ ターミナルにサンプルをコピペすると、グラフが可視化されます。
step 1
グラフの問題です。サンプルに図がないので、可視化したいです。
step2
❯ ggg --weighted （省略） Please input your graph. >>> 3 3 1 2 3 2 3 5 1 3 4
コマンドラインから、ggg を起動し、サンプルをコピペします。
step3
グラフが可視化されます。終わり。
使い方
GitHub の README.md に、Install 手順や使い方を詳細に書いたので、是非使ってください！
メルカリ summerintern-gophers-2020 に参加して，競プロ用のコード生成ツールを作った話
メルカリ主催の「summerintern-gophers-2020」に参加してきました！
概要はこちら
前半2日間は、Goの静的解析に関する講義やプログラミング言語Go完全入門の資料で参加者が興味を持つ領域を中心とした講義をWorkshopを交えながら実施。後半3日間では、静的解析ツールまたはその周辺ツールの開発に取り組んでいただきます。開発に取り組む期間は、メルカリ・メルペイのエンジニアがメンターとしてサポートします。
前半に行われた講義資料は，なんと公開されています（びっくりですね）． 14 章の「静的解析」を扱いました． engineering.mercari.com
何を開発したか
競技プログラミング用のコード生成ツールを開発して，公開してあります．
詳しい使い方は，GitHub の README.md をお読みください．
gpcg（go-procon-code-generator）
何ができるか
競技プログラミングでは，単一のファイルで記述されたソースコードを提出する必要があります．
一方で，複雑なアルゴリズムやデータ構造は事前に実装しておいて，コンテスト中はライブラリとして使用したいです．
gpcg を用いると，複数ファイルにまたがるコード群を一つにまとめて，提出用のコードを生成してくれます！
AtCoder Beginner Contest D 問題 を題材に具体例を紹介します．
この問題は，オブジェクトのグループ分けを管理するデータ構造を使えば解くことができます．
有名なデータ構造として，UnionFind が挙げられますが，コンテスト中に UnionFind を一から実装すると タイムロス です．
そういうものは事前にコーディングしておいて，コンテスト中はいつでも使える状態にしましょう．
a.go： コンテスト中に書くコード．UnionFind を使用する．
package main import ( "bufio" "fmt" "os" "a/lib" // 事前に実装してあるデータ構造のライブラリを import ) func main() { r := bufio.NewReader(os.Stdin) w := bufio.NewWriter(os.Stdout) defer w.Flush() var n, m int fmt.Fscan(r, &n, &m) uf := lib.NewUnionFind(n) // import してきたデータ構造「UnionFind」を使う！ for i := 0; i < m; i++ { var a, b int fmt.Fscan(r, &a, &b) a-- b-- uf.Union(a, b) } ans := 0 for i := 0; i < n; i++ { if ans < uf.Size(i) { ans = uf.Size(i) } } fmt.Fprintln(w, ans) }
UnionFind： 事前にコーディングしてある．
package lib type UnionFind struct { par []int } func NewUnionFind(N int) *UnionFind { u := new(UnionFind) u.par = make([]int, N) for i := range u.par { u.par[i] = -1 } return u } func (u UnionFind) Find(x int) int { if u.par[x] < 0 { return x } u.par[x] = u.Find(u.par[x]) return u.par[x] } func (u UnionFind) Union(x, y int) { xr := u.Find(x) yr := u.Find(y) if xr == yr { return } if u.Size(yr) < u.Size(xr) { yr, xr = swap(yr, xr) } u.par[yr] += u.par[xr] u.par[xr] = yr } func (u UnionFind) Same(x, y int) bool { return u.Find(x) == u.Find(y) } func (u UnionFind) Size(x int) int { return -u.par[u.Find(x)] } func swap(a int, b int) (int, int) { return b, a }
gpcg を使うと，これらのコードを一つにまとめてくれます．
その際，
- パッケージ間で名前が衝突しないように，rename してくれる
- main 関数で使用していない構造体や関数の定義は無視する
などを行ってくれます．
gen.go：生成されたコード
package main import ( "bufio" "fmt" "os" ) func generated_alib_swap(a int, b int) (int, int) { return b, a } func (u generated_alib_UnionFind) Size(x int) int { return -u.par[u.Find(x)] } func (u generated_alib_UnionFind) Union(x, y int) { xr := u.Find(x) yr := u.Find(y) if xr == yr { return } if u.Size(yr) < u.Size(xr) { yr, xr = generated_alib_swap(yr, xr) } u.par[yr] += u.par[xr] u.par[xr] = yr } func (u generated_alib_UnionFind) Find(x int) int { if u.par[x] < 0 { return x } u.par[x] = u.Find(u.par[x]) return u.par[x] } func generated_alib_NewUnionFind(N int) *generated_alib_UnionFind { u := new(generated_alib_UnionFind) u.par = make([]int, N) for i := range u.par { u.par[i] = -1 } return u } type generated_alib_UnionFind struct{ par []int } func main() { r := bufio.NewReader(os.Stdin) w := bufio.NewWriter(os.Stdout) defer w.Flush() var n, m int fmt.Fscan(r, &n, &m) uf := generated_alib_NewUnionFind(n) for i := 0; i < m; i++ { var a, b int fmt.Fscan(r, &a, &b) a-- b-- uf.Union(a, b) } ans := 0 for i := 0; i < n; i++ { if ans < uf.Size(i) { ans = uf.Size(i) } } fmt.Fprintln(w, ans) } /* this code was generated by the code below package main import ( "bufio" "fmt" "os" alib "a/lib" ) func main() { r := bufio.NewReader(os.Stdin) w := bufio.NewWriter(os.Stdout) defer w.Flush() var n, m int fmt.Fscan(r, &n, &m) uf := alib.NewUnionFind(n) for i := 0; i < m; i++ { var a, b int fmt.Fscan(r, &a, &b) a-- b-- uf.Union(a, b) } ans := 0 for i := 0; i < n; i++ { if ans < uf.Size(i) { ans = uf.Size(i) } } fmt.Fprintln(w, ans) } */
このコードをコピペして提出すると，AC（accepted）を得ることができます
今後の課題
このツールは，実は 未完成 です（）
考慮すべきケースを網羅できていなかったり，特定のディレクトリ構造じゃないと panic を起こしたりします．
「お前のツールを使ったから，AtCoder でレートが下がったやんけ」とか言われると怖いです． 普段の精進とかで，遊びで使ってもらえると嬉しいです．
今後は，ツールとして誰かに使ってもらえるようなクオリティーに高めていきます．
