AtCoderでぴったり入緑したので、落ちないうちに色変記事を書かせてくださいお願いします

はじめに

ABC350で入緑したので、色変記事としてこれまで取り組んできたことや考えていることを書きます。何かの参考になったら嬉しいです。

安定して緑を維持できるほどの実力はないのでそのうち茶色に戻ると思いますが、戻らないうちに書きます。戻る前ならセーフ！

名前が緑色だ！やったー！

なお、入茶の時はこんな記事を書いていました。今読むと若干恥ずかしい。

入茶から入緑までざっくり1年半ちょいってところですね。

書いている人

• 凡人ITエンジニア（開発系）
• 難しいアルゴリズムはわからない
• 複雑な実装で混乱する
• 数学は何もわからない
• でも競プロ頑張って少し良くなったかも

直近の戦績

ABCで3完はできることが多い、4完はできたりできなかったり。解くスピードはたぶんレート相応。緑パフォが出たり出なかったりで不安定、というか出ないことのほうが多い、という感じです。

スタンスについて

入茶記事で「緩く長く続ける」「短期で効率よくレーティングを上げることを考えていない」という主旨のことを書いたのですが、まさに今もそう思っています。これは何もしないということではなくて、これまで実力アップのためにあれこれやってはきました。ただし、レートを上げるための最短ルートを目指すことはせず、ただただ問題を解いたり、直近の関心事についてだけ勉強や練習をしたりしていました。何でもいいので何かすれば今よりは強くなるし、それを継続していったら長い目で見ればけっこう強くなると思うよー、みたいなゆるい感じです。
このような方針だとそのうち行き詰まるかもしれませんが、とりあえず緑タッチくらいまではできるようですね。

使用言語

Kotlinを使っています。当初はC++を使っていましたが私にはけっこう難しくて、仕事で使い慣れているKotlinを使ったらいいんじゃないかと思って使い始めました。それが灰の頃の話で、それが思った以上にうまくハマってそのまま使い続けてきました。
Kotlinが競プロに向いているかというと特にそうではないと思いますが、単純に汎用言語として強力なので競プロでもそこそこ戦える印象です。実行速度はJavaと同等で、少なくとも致命的不利にはならない水準です。
言語がボトルネックになったら乗り換えればいいと思っていますが、今のところ乗り換え検討には至っておらず。将来的にはわかりませんが。

なお、Kotlinは公式サイトに競プロガイドが存在することが一部では知られています。

取り組みについて

参加コンテスト

基本的にABCにしか参加していません。AtCoder以外のコンテストも現状は特に参加していません。バチャも試しに参加していた頃もありましたが、直近だと参加していないです。いずれも参加したほうが間違いなく強くなれると思うのですが、なかなか時間を割けないです。（あとARCは怖い…）

コンテストの復習など

コンテストに参加したら、コンテストの参加記として振り返りや感想を記事に書いています。灰の頃から書いているのでそれなりの量が溜まってきました。
過去に解いた類題について調べるのに自分の記事を読むこともちょいちょいあります。そういう意味では役に立っていますが、それ以外で実力アップに寄与してくれているのかはよくわかりません。半分趣味です。
なお、コンテスト外で解いた問題についての記事を書くこともあります。

コンテストで解けなかった問題については解説を見て、解説ACできそうだったらそうして、無理そうだったら一旦諦めます。以前は必ずACまで持っていくように頑張っていたこともありますが、労力の割には身につかないなと思って最近はそこまではやってません。

労力をかけた結果、本当に理解できたなら素晴らしいんですけど、理解できずに半ば解説のコードを書き写すかのような感じでACすることもあって、これはほんとに意味ないなと思いました。実際に書き写すわけではなく、理解したような気になってから解説コードは見ずに自分で書いてはいましたが、ただの短期記憶力テストでした。

もちろん、解説ACによって得られたことも多くあります。累積和や二分探索、それらのかけ合わせ、グラフ、などはコンテストで解けなかった問題の解説ACで覚えたと思います。

ABCの過去問埋め

精進のベースとなるのはやはり過去問埋め、特にABCの過去問です。とにかく解けそうな問題を解いてきました。解けなかったら解説に頼ります。これもコンテストの復習と同じで、理解できそうなら頑張る、無理そうな諦めます。

Streakをつなぐことはあまり考えていません。当初は問題を解く習慣を作るためにStreakをつなぐことを意識していたのですが、ちょっと重荷になったのでやめました。Streakを気にしなくなったことで、簡単な問題を取っておくみたいな無意味なことを考えなくなったし、過去に解いた問題を解き直すなどの精進も抵抗なくできるようになりました。
まあ、ざっくり1日1問くらいを解くことが緩い目標になっているので、結果的に何日かStreakがつながることはありますが。

ABCの過去問演習によって身につけたことは多くありますね。解けなかった問題を解説ACできたことで知識が得られたり、頑張って考察してなんとか自力ACする過程で考察力が鍛えられたり。また、簡単ですぐに解けるような問題でも、ちゃんと問題が解けるという実感が得られるので無意味ではないと思います。

ウォーキングしながら考察

直近は健康維持のために1日1時間くらいはウォーキングをしているのですが、歩いている間は頭が暇なので、出発前に問題文を頭に入れておいて考えながら歩くこともあります。これがけっこう捗ります。最初は全然解法がわからなくても、考え続けていたら案外解法が思い浮かんだりします。それから詳細な実装レベルまで考えておいて、早く実装したいと思いながら家に帰ります。

これが意外と効果があると思いました。これは解けないなあと思っても、諦めたら暇になるし、歩きながら解説を読むのも嫌だし、ってことでそのまま考え続けることになります。結果としてそれなりに深く考察が進んで、素の実力が鍛えられるように感じましたね。時間の有効活用にもなって一石二鳥です。

数学の勉強

競プロでは数学力がクリティカルに成績に結びつくと思います。知識も重要なのですが、それよりも数学的な思考力というか、数学の基礎体力というか、そういったものが影響すると思います。理系の学生や出身者がごく自然にやっている頭の使い方が私にはできないという感じがします。知識は都度調べればいいのですが、基礎体力となるとそうもいかず、地道に鍛える必要があります。なので数学をちゃんと勉強する必要があると思い、小学校の算数や中学数学からやり直しました。ただ、高校数学の内容に入る頃になんかすごく体調が悪くなってしまって一旦止まってしまいました。

その後、離散数学の本を読んでみました。競プロとは離散数学の実践編だという意見をどこかで見たことがあって、たしかに論理、集合、順列と組み合わせ、グラフなど、競プロに関係ありそうなテーマのオンパレードでした。読んでみてどうだったかというと、正直内容はほとんど理解していません。しかし、数学って楽しいなと思うことができました。特に論理。論理がすごいなと思ったのは、正しいかどうかが機械的に決まるということです。判断や解釈の必要がなく、答えが一意に定まる。少し、論理の力というものに恐れおののくような気持ちに…

考えてみたら、プログラミングというのは論理演算の集合体みたいなものです。論理が身についている人とそうでない人が同じくらいプログラミングができるかというと、そんなわけがないと思いました。論理の性質から、これを活用すればいかにも速く正確に実装できそうだよな妄想しました。
まあ論理的思考能力がなかったらアルゴリズムの証明とかできなさそうなので、むしろ基礎スキルなのかもしれないですが、何にしても私には十分に備わっていないのはたしかです。身につけるために記号論理学について勉強したり、証明の練習をたくさんしたりする必要がありそう。ただ、今は時間を割けていません。これはいつか絶対やります。

うーん、数学の重要性自体は理解したつもりなのですが、その割には取り組めていません。頑張りたい…
（まあ現状は数学ができないわけなので、数学の重要性に関しては想像というか妄想の域を出ないのですけどね。身につけて答え合わせしたい）

競プロ典型90問

ABCの問題は全部典型と聞いたので、典型を身につけることが重要だなーとも思っています。自分がウンウン唸って何十分もかかって解く問題を5分くらいで解く人がいます。実装する時間まで考えると、事前に「知って」いないとそんなに速く提出できるはずがない。「知っている」とはもちろん不正行為という意味ではなく、典型要素を既に知っているということです。もちろん知っているだけでなくてそれを素早く見抜く必要もありますが、とにかくまずは知っている必要があります。

ということで、競プロ典型90問にも手を出しました。ABCの過去問と比べると教育的な意図が強いのかな、典型を身につけるには良いのかな、と思ったので。
ABCの問題は過去問と似すぎないようにするためなのか、典型にいくらか捻りを加えている問題が多いように感じます。一方、競プロ典型90問のほうは捻りが少ないように思います。なので、やはり典型を学ぶには良いという印象ですね。二分探索の使い方とか、dequeの使い方とか、ここで学んだことが直接ABCで役に立ったことが何度かあります。
最近は手を付けられていないですが、たまには埋めていこうと思っています。

鉄則本

典型を身につけるには、鉄則本も良さそうだよなあと思って読んでみました。しっかり読み込んでもたぶん理解はできないので、全体を俯瞰するためにざっと目を通したという感じです。

負の重みがあったらダイクストラは使えないのでベルマンフォード法を使うとか、セグメント木とか、詳細は理解してないけどいくつか記憶に残ったことがありました。これがいつか役に立つといいのですがね。

グラフの練習

当初はグラフという概念自体がよくわかってなかったのですが、ABCでそれが必要な問題と出会って、これは身に付けないとなと思ってアルゴ式で勉強して、ABCの過去問でもそれっぽいのを選んで練習しました。
DFS、BFS、あとUnion-Findについてそれなりには習得できました。おかげでグラフ系の問題がまあまあ解けるようになり、それでレートを稼いでいた時期もありました。なお、今回の入緑はUnion-Findのおかげです。ありがとう、Union-Find。

ただ、グラフが得意とまではまだまだ言えず、ちょっと捻られると解けないか、解けるとしてもコンテスト終了前ギリギリACみたいになります。ワーシャルフロイドなどのもう少し高度なアルゴリズムもわからず。
（ダイクストラで通したことが一回だけありましたが原理を理解しているわけではなく、ほんとに捻りなしでただダイクストラやるだけの問題だったのでたまたま通っただけでした）

印象深い問題

DPの練習

DPも言葉だけはけっこう前から知っていまして、脳内TODOリストに入っていました。ABCの過去問埋めをしている中で邂逅したのでこれを機に勉強してみようとやってみました。まずはアルゴ式で取っ掛かりを得て、それからABCの過去問やEDPCの過去問でもう少し練習しました。最初は全くもって理解できなかったですが、DPマジでわからんってTwitter（当時）で呟いたら多くの人に助けていただき、なんとか基本くらいは理解しました。（ありがとうございました）

その後DPで解ける問題をABCでも何度か見かけて、解くことができたこともあったので嬉しかったです。ただ、グラフと同じくちょっとでも捻られたら途端に解けなくなります。いや、グラフ系よりもさらに習熟度が低いかも。もっと練習したい。

印象深い問題

Typical StairsはなにげにABC初参加回の問題で、初めての「解けなかった問題」です。DPをある程度身につけてから見てみたら簡単に解けましたけどね。

再帰の練習

DPはメモ化再帰から理解していくといいのではというアドバイスを頂いたことがあり、再帰を使う問題を延々と解いていたことがありました。DPへの理解につながったかどうかは正直わからないのですが、再帰DFSを使って全探索すれば解ける問題、メモ化再帰を使って解ける問題、などは実際に解くことができるようになってきて、これはこれで大きな成果が出ました。

印象深い問題

グリッド系問題の練習

自分は数学できないし、難しいアルゴリズムもわからないけど、実装自体はできると思っていました。しかし、グリッドを探索するだけの問題で立て続けに爆死したことがあって認識を改めました。グリッドが苦手というより単純に実装力自体が低かったのだろうと思います。ちょっと実装が重くなるだけで途端に解けなくなって、おいおいマジかよとだいぶショックを受けることになりました。
（グリッド系は重実装になりがちですよね）

まあ嘆いていても問題は解決しないので、グリッド系の問題を延々と解き続ける練習をしました。やっているとそれなりにコツが掴めてきます。なんてことはない、処理を関数に分けたりデータをクラスに分けたりして認知負荷を下げる、できるだけ処理を共通化する、などのプログラミングで一般的に有効なことをやればよかったです。それと、いきなり実装に着手せずにまずは解き方をちゃんと考えてイメージができてから実装に着手するというのも重要でした。
できるだけ早く提出したいので焦ってそういうところをおろそかにして、なかなか読めたものではないコードを書いていました。仕事ではそういうことはしないのですが競プロだとやってしまっていました。その結果として混乱して実装をミスるし、コードが読みづらすぎてデバッグも難航するし、ってことで解けずに終わるという結果を連発しました。今思えば、何も考えずに8重ループとかをベタ書きしたらそりゃそうなりますよね、という感じなのですが。アホでした。

そういう感じで、練習を続けていたら以前よりはだいぶマシになりましたね。実装が重いとして多くの人（自分も含め）が悲鳴をあげていたような問題をなんとか解ききれるようになりました。それもWAを連発して半ば提出デバッグみたいなことをしてからのACではなく、一発ACもしくはWAが出るとしても1回程度に収められることが増えました。体感的には、コンテストの成績にも明らかにプラスの影響が出ていると感じます。WAを出す回数が明らかに減りました。出してしまったとしても、デバッグがわりと早くできて2回目の提出でACというパターンが多いです。回数は少なくなったとしてもWAを出してしまうことがあるわけなのでまだまだなのですが、それでも以前よりかは自分の実装が信頼できるようになったと思います。

これは競プロの成績だけでなくもちろん仕事でのプログラミングにも良い影響が出ていると感じますし、何よりプログラミングって楽しいなと以前よりも強く思えるようになりました。

スローペースではありますが実力アップのための取り組みを色々やってみて、その中でこれが一番やって良かったかもしれません。考察が正しくても実装が正しくなければ0点、そういうゲームです。実装力はなんだかんだで要となる能力ですね。

直近でも、グリッド系の実装が重い問題を解く練習をしています。一時的なバフではなく素の実力として定着するまでもっと練習したいです。

印象深い問題

解いた問題はXでシェアするのですが、普段はそんなに多くの反応はありません。しかし、Ideal SheetとPolyominoの提出には有意に多くの反応がありました。みんな好きなんですねぇ😊

ライブラリ化

問題を解いていくと、作ったクラスや関数が他の問題にも使えそうな汎用的なものになっている場合があります。そういうのはライブラリとして使いまわしています。

よく使うのは二分探索、順列全探索、素因数分解あたりです。直近だとbit全探索のテンプレ化をしてみました。

C++にある機能でもKotlinにはなくて作らないといけないということがけっこうありますね。

二分探索

fun binarySearch(minNg: Long, maxOk: Long, isOk: (Long) -> Boolean): Long {
    var ng = minNg
    var ok = maxOk

    while(abs(ok - ng) > 1) {
        val mid = (ok + ng) / 2
        if(isOk(mid)) {
            ok = mid
        } else {
            ng = mid
        }
    }
    return ok
}

順列全探索

class Permutation<T>(private val list: MutableList<T>) {
    private val queue = ArrayDeque(list)

    fun forEach(action: (MutableList<T>) -> Unit) {
        forEach(0 ,0, action)
    }

    fun toList(): List<List<T>> {
        val list = mutableListOf<List<T>>()
        forEach {
            list.add(it.toList())
        }
        return list.toList()
    }

    private fun forEach(count: Int, layer: Int, action: (MutableList<T>) -> Unit) {
        if(count == list.size) {
            action(list)
            return
        }

        for(i in count until list.size) {
            val elem = queue.removeFirst()
            list[layer] = elem
            forEach(count + 1, layer + 1, action)
            queue.add(elem)
        }
    }
}

bit全探索

fun bitmask(n: Int, action: (List<Boolean>) -> Unit) {
    val limit = 1 shl n
    for(i in 0 until limit) {
        val bits = i.toString(2).padStart(n, '0')
        action(bits.map { it == '1' })
    }
}

あとはランレングス圧縮もたまに使います。

ランレングス圧縮

fun rle(s: String): List<Pair<Char, Int>> {
    val ret = mutableListOf<Pair<Char, Int>>()

    var c = s[0]
    var count = 1

    if(s.length == 1) {
        ret.add(c to count)
    }

    for(i in 1 until s.length) {
        if(c == s[i]) {
            count++
        } else {
            ret.add(c to count)
            c = s[i]
            count = 1
        }

        if(i == s.length - 1) {
            ret.add(c to count)
        }
    }
    return ret
}

それと、今回の入緑の立役者となったUnion-Findくん

private class UnionFind(n: Int) {
    private val roots = IntArray(n) { it }
    private val ranks = IntArray(n) { 1 }

    fun find(i: Int): Int {
        if(roots[i] != i) {
            roots[i] = find(roots[i])
        }

        return roots[i]
    }

    fun isSame(x: Int, y: Int): Boolean {
        return find(x) == find(y)
    }

    fun union(x: Int, y: Int) {
        val rootX = find(x)
        val rootY = find(y)

        if(rootX == rootY) {
            return
        }
        if(ranks[rootX] > ranks[rootY]) {
            roots[rootY] = rootX
            ++ranks[rootX]
        } else {
            roots[rootX] = rootY
            ++ranks[rootY]
        }
    }
}

体調管理

あんまり競プロと関係なさそうに思えるけど非常に重要です。一時期、体調が悪すぎてコンテストに参加できない週が続いたことがありました。不戦敗というのは、心情的にはレートが下がるのよりも辛いです。
食事や運動に気を遣うようになったら嘘みたいに回復しましたが、何もしなければずっと体調悪いままでフェードアウトしてしまっただろうなあ…

そこまではいかないとしても、体調が悪いと間違いなくパフォーマンスに影響します。むしろ、体調不良のせいでパフォーマンスが出ていないのにそれに気づかないというほうがたちが悪いかも。お気持ちとしては、体調管理は精進よりも重要です。

体調管理のために何に気をつけているかまで詳細には書きませんが、雑に書くとタンパク質の量を計算してちゃんと摂る、野菜や果物も食う、上でも書いたけど1日1万歩以上歩く、ちゃんと寝る、それとストレス解消のためにゲームする、といったところです。
ゲームじゃなくてもいいけど、ストレス解消の手段は必要ですね。

競プロについて思うこと

競プロをやってきて痛感したのが、私は今まであまりにも動作確認に頼りすぎたプログラミングをしてきたなということです。動作確認自体は重要なのですが、低い実装力を動作確認でカバーしてきたといいますか。動作確認はそれなりに得意で、とにかく愚直に多くのパターンを試しまくって、低い実装力で埋め込まれたバグをけっこう根こそぎ取り去って、それによってなんとか動くプログラムを作ることができてしまっていました。自分のだけでなく他人の作り込んだバグも多く発見して、それが評価されたこともありました。しかし、競プロではそれが見事に通用しませんでした。

実務で書くプログラムだと、多くの場合は画面ベースで操作するので動作確認がしやすかったですが、競プロだと画面とかないのでなかなかそうはいきません。それに競プロだと提出が通らなかった場合に、デバッグのために役立つ情報があまりにも少ないです。間違った出力をする場合の入力も出力もわかりませんし、デバッグ実行もできません。また実行時例外が発生しても、どこで何の例外が発生したのかわかりません。このように手がかりが少ないのでは、動作確認でカバーなんてことは現実的にはできません。私の手元にあるのは低い実装力だけ。それはもう悲惨なことになりましたね…

まさか自分の実装力がこんなに低いとはと強烈なショックを受けたものですが、このような自分の問題点を知ることができたのは幸運でした。また、競プロによって検出された問題点なのだから競プロによって克服できるはずだとも思いました。そんなわけで、心折れそうになりながらもなんとか取り組みを続けてきました。

動作確認でカバーができない以上、実装力を鍛えるしかありません。前述の通り、ちゃんと考えて方針が立ってから実装するようにして、認知負荷が低いコードを書くように心がけながら重実装問題を解いていきました。通らなかった場合は修正ガチャみたいなことをするのではなく、自分で書いたコードとちゃんと向き合ってデバッグしました。
（ちゃんと考えてから書いたコードであることと、認知負荷が低いコードになっていることで、明らかにデバッグはしやすくなりました）

それを繰り返して、克服できたとまで言えるかわかりませんが、それでも競プロを始める前や入茶時点などと比べればはるかにマシになったと思います。前述の通りWAを出すことが明らかに減って、動作確認しまくらなくてもそれなりの確度で正しいプログラムが書けるようになった実感があります。

そのような経緯があるので、自分にとって競プロは自己研鑽という面が強いです。競プロでは提出したコードが、強い人によって用意されたテストケースで容赦なくテストされます。自分で書いたコードをこんなに容赦なくテストしてくれる、そのような環境を手軽に得られるのって、すごいことですよ。競プロでは鍛えられないスキルもたくさんあるのですが、競プロによって強烈に鍛えられるスキルもたしかにあります。

とはいえ、100％自己研鑽ってわけでもありません。やっぱり楽しいですよ、競プロは。コードを書いて提出して、ドキドキしながらジャッジの様子を見ている時の緊張感、ACと表示された時の嬉しさ。これによってしか得られない栄養があるってやつです。わからせられ続けて辛いことも多かったですし、今でも辛さを感じることはありますが、それでも続けていくことで成長し、その実感が得られる楽しさもはっきりと感じてきました。競プロは、良いですよ。

もっとも、競プロでは鍛えられないスキルも多くあるというのは忘れないようにするということも意識しています。純粋に趣味でやっている人であれば気にせず楽しめばいいんですが、自己研鑽という側面からすると競プロばかりに注力するのも問題があります。競プロにそれなりの思い入れを持ちつつも、精進ペースがまったりなのはそのあたりの事情も影響しています。他にもやることはあるということで。

まあ、競プロにもそこそこの時間は投入したいし、していいとは思っていますが。

競プロを本格的に始めてからだいたい2年弱くらいになります。長かったような短かったような。しかし、これから長く続けていきたいです。

おわりに

緑になったので次は水と言いたいところですし、実は水色になりたいと、茶色の頃から密か思っていました。ただ、現状からするとあまりにも厳しいですね。そもそも、緑を維持できずに早々に茶色に落ちる可能性が高いです。潜在能力の全てを解放してしまったとまでは思っていないので、継続していけば緑を維持できるラインまで上がっていく可能性もありますし、じわじわと水に近づいていけるかもしれません。

実際にどうなるかわからないものの、目指してはいきますよ。とはいえ長く継続することが最も重要と思っているので、水色にはなれないと確信してしまうことがあったとしてもやめないつもりです。レートが伸びない中でモチベを維持できるのかまだわからないですが、それはそうなってから考えます。とにかくゆるゆると継続していきたいですね。