30歳で競プロに目覚めた霊長類のブログ

チンパンジーと一般人のあいだ

ARC111-A Simple Math 2

ARC Python

Simple (笑) とは...
コンテスト中に解けなかったので、どうやったら自然に解けるようになるか整理してみます

問題リンク
A - Simple Math 2

問題概要

\lfloor \frac{10^N}{M} \rfloor \mod M を求めよ
( \lfloor x \rfloor は x の整数部分)
1 \le N \le 10^{18}(クソデカ), 1 \le M \le 10^4

M=10で題意を理解してみる

まずは題意を感覚で理解しようとしてみます
maspy さんのおっしゃるように、 M=10 で一度考えてみることにします。

10^N の部分はとりあえず適当に 12345 とかにしといて、 M=10 を代入します
\lfloor \frac{12345}{10} \rfloor \mod 10
これの、
\lfloor \frac{12345}{10} \rfloor の部分は、
1234.5 の整数部なので 1234 となります。
したがって
1234 \mod 10 となり、 4 が得られます。

実はこの問題の題意は、 10^N (クソデカ数) を M 進数で表したときの下から 2 桁目を出力せよ と同じなのです。

本当に？

\lfloor \frac{x}{M} \rfloor の意味を改めて考えてみます。
これは、x を M で割った商です1
x ÷ M = a あまり b と表されるとき、
x = aM + b となります。 商がa、あまりがb です
整数部分を取る操作は、あまりを無視した商の部分ですので、
\lfloor x ÷ M \rfloor = \lfloor \frac{x}{M} \rfloor = a です。

次に、 y \mod M の意味を考えます。
これは読んでそのまま、 y を M で割ったあまりです。
y ÷ M = p あまり q と表されるとき、
y = pM + q となります。これの、q の部分が y \mod M です。

さて、求めたいものは \lfloor \frac{x}{M} \rfloor \mod M でした。
y = \lfloor \frac{x}{M} \rfloor として、まず \mod M の式に当てはめます
y = \lfloor \frac{x}{M} \rfloor = pM + q
(↑これの q の部分が求めたい答えです)
次に、 x = aM + b 、 \lfloor \frac{x}{M} \rfloor = a を使います。
a = pM + q となるので、
x = (pM + q)M + b = pM^2 + qM + b
となります。

ここで、M進数とは、x をこのように分解して表した表現だと言えます。
x = k_0M^0 + k_1M^1 + k_2M^2 + k_3M^3 + ...
k_0 が M進数における下から1桁目、k_1 が M進数における下から2桁目... です。
x = pM^2 + qM + b と係数を比較すると、
k_0 = b, k_1 = q となります。
したがって、求めたい数値はqなので、 x を M 進数で表したときの下から 2 桁目を出力せよ と言い換えることができました！
なお、残りの部分は M^2 で括れるので k_2M^2 + k_3M^3 + ... = pM^2 として良いです (が本問では無視して良いです)

実装

Pythonが本領発揮できるところでした
以下でACしました！

N,M = map(int,input().split())
ans = pow(10,N,M*M) // M
print(ans)

ここで、 pow(10,N,M*M) は、Pythonでは 「10^N を M^2 で割った余り」を高速に求めてくれます。2
上述の式で、 10^N = pM^2 + qM + b と表せるところの、
qM + b が求まります。
これを // M で M で切り捨て除算することで、求める答えである q が得られます。

おわり

simple (笑) とは... という感じだったけど、分かってしまえばなるほど simpleかもです
しかし 300点 緑difficultyとは納得しがたい...
いずれにしても、数式を見て一目で分かるぐらいには慣れていきたい...！

  1. 私はこの言い換えすらコンテスト中にできませんでした…↩

  2. 愚直に求めるとTLEやMLEを起こすのですが、第3引数にMODの値を入れることで高速にMODをとりながらの累乗を求めてくれます。このような機能のない言語では繰り返し2乗法という手段を使うと思うのですがそのようなライブラリがないと辛いですよね。。↩

ABC177-E coprime 4つの解法

ABC

ABC177-E coprime のPython or PyPyで間に合う解法を4つ記します

AtCoder Problems では緑difficultyらしいのですが(！？)コンテスト中には解けずに苦汁を飲みました

問題概要

  • N 個の整数が与えられる
  • N 個の整数の異なるすべてのペアが互いに素 ( \gcd(A_i, A_j) = 1 ) のとき、pairwise coprime と出力する
  • そうでなくてすべての整数の \gcd が 1 のとき、setwise coprime と出力する
  • いずれでもないとき、not coprime と出力する
  • 2 \le N \le 10^{6}, 1 \le A_i \le 10^{6}

コンテスト中の思考

  • not coprime は最初に全体の \gcd を取ればok。 (2 以上なら not coprime)
    • (追記) 以下紹介する4つの解法は最初に↑の判定を済ませている前提で書きます
  • 本質は pairwise か setwise の判定
  • A の異なる要素に共通の素因数が見つかったら setwise 確定。
    • とりあえず全部素因数分解するのが思いつく
    • O(N \cdot \sqrt{A_i}) ぐらいかかってしまうと思い敬遠。1
      • →実は間に合う(解法3)
  • 全部素因数分解、を避ける方法で判定しなきゃいけない！ (←思い込み)
  • 前計算で 10^{6} までの素数を求めておいてうまくゴリゴリやろう...！ (←沼の始まり)

解法1 高速素因数分解

writer の kyopro_friends さんの想定解です。
エラトステネスの篩の進化版みたいなやり方で、osa_k法 とも呼ばれているみたいです。2

MAXN = 10**6+10
sieve = [i for i in range(MAXN+1)]
p = 2
while p*p <= MAXN:
    if sieve[p] == p:
        for q in range(2*p,MAXN+1,p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1
  • まず配列を用意し
    • [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, ...] のようにします 3
  • 次に2の倍数で書き換えられていないところを2で書き換えます
    • [0,1,2,3,2,5,2,7,2,9,2,11,2,13,2,15,...]
  • 次に3の倍数で書き換えられていないところを3で書き換えます
    • [0,1,2,3,2,5,2,7,2,3,2,11,2,13,2,3,...]`
  • 次は4ですが すでに2に書き換えられているのでスキップします
  • 次に5の倍数で書き換えられていないところを5で書き換えます
  • ...

のようにして配列を作っておくと、素因数分解がめっちゃ高速にできます！！

tmp = set()
while a > 1:
    tmp.add(sieve[a])
    a //= sieve[a]

素因数の列挙は a > 1 である限り sieve[a] で割り続けるだけ！
(今回は列挙だけなので set でやっていますが、もちろん dict や Counter を使うことで素因数の個数も数えられます)

例えば a=60 として、

  • sieve[60] == 2 なので 2 を抽出し、a を 2 で割る。
  • sieve[30] == 2 なので 2 を抽出し、a を 2 で割る。
  • sieve[15] == 3 なので 3 を抽出し、a を 3 で割る。
  • sieve[5] == 5 なので 5 を抽出し、a を 5 で割る。
  • a==1 になったのでおわり。 tmp = {2, 3, 5} が抽出された。

計算量は O(A \log \log A + N \log A) のようです
配列の前計算が O(A \log \log A)、素因数分解が O(N \log A) です
素因数分解めっちゃ速いですね！！

ACコードの全体はこちら Python: 834ms

解法2 等間隔に舐めて調和級数で間に合うやつ

これは解説放送ですぬけさんが説明されていた方法です
詳しくは放送をご覧いただきたいのですが、なんと 素因数分解も素数判定も必要ありません

MAXA = 10**6
B = [0] * (MAXA+1)
for a in A:
    if a==1: continue
    if B[a]:
        print('setwise coprime')
        exit()
    B[a] = 1

まずヒストグラムみたいのを作ります (上記の B です)
同じ数値が2度出現したら setwise 確定で exit() しています。
ただし 1 が複数個あっても \gcd(1,1) = 1 なので setwise とは確定しないことに注意！ (コーナーケース！)
結果として B の要素としては 0 か 1 のいずれかが入る形になります。

for n in range(2,MAXA+1):
    c = 0
    for m in range(n,MAXA+1,n):
        c += B[m]
        if c > 1:
            print('setwise coprime')
            exit()

さてここが肝です。上のコードでは

  • 2,3,4,5, ... 1000000 までのそれぞれを n として、
    • n から始めて 2n, 3n, ... (これを mとする) の B[m] をチェックしています
    • 各n のどれかで、B[m] が 2回以上カウントされたら setwise 確定です。

一見 10^{6} までのループを2重に回しているので間に合わなそうに見えるのですが、実は間に合います
よく見ると1回の外側のループでは MAXA // n 回ぐらいしか処理されません。
O(\displaystyle \sum_{i=1}^{A} \frac{A}{i}) は調和級数という考え方で O(A \log A) になりますよというのが知られています (詳しくは解説放送をご覧ください)

ACコードの全体はこちら(PyPy) 327ms と、こちら(Python) 1320ms※ 4

解法3 愚直に素因数分解しちゃう

えー！間に合っちゃうんですか！

ライナスさんにTwitterでリプライ頂きました
なんと愚直に試し割りして素因数分解しても間に合っちゃうみたいです！

計算量を雑に見積もると O(N \sqrt{ \max A}) で 10^{9} オーダーなんですが、ちゃんと考えると1桁以上落ちるようです
というのも、

  • 10^{6} 以下の素数は 78498 個で、 10^{6} に比べて1桁以上少ない
  • 鳩ノ巣原理という考え方を適用すると、(追記)2以上のN が 78499 個以上存在すると自動的にどれかしらの素因数が重複する！ →setwise 確定 ！！
  • 最悪ケースを一応考えると
    • 999983 のような素数がならぶ → 1000 までの試し割りでok
    • 2 の n乗、 3 の m乗、 5 の l乗、、、みたいに (l,m,n は \max A を超えないような最大の指数) が並ぶことも一応あるけどこれは早く検出できるうえに指数はせいぜい20以下

となり、78499 \cdot 1000 (追記) + 10^{6}程度で 8 \cdot 10^{7} に収まるオーダーです
これでPyPyで間に合いました

私も書いてみました(Pythonは間に合いませんでした)
ACコードの全体はこちら PyPy: 678ms

解法4 ゴリゴリスペシャル

きれいな解法ではないのでおまけです
コンテスト中に 2WA までこぎつけたのですがコーナーケースでやられていました
コンテスト後にねちょさんにコーナーケースを見つけていただきました！

先にコンテスト後のACコードを貼ります (下記2つは同一コードです)
PyPy 425ms、Python 1986ms (！！)

やったこと

  • 全体の \gcd を取って 2 以上なら not coprime
  • 重複チェック。1 以外で 2 つ以上重複している要素があれば setwise coprime
    • 1 以外で の部分は本番中で見つけられなかったコーナーケースです...
  • エラトステネスの篩で 10^{6} ぐらいまでの素数を検出する。実際に使ったのはそのうちの 10^{3} 以下の素数
  • 各 A_i について、
    • 10^{3} 以下の素数 で割れる限り割っていく
      • その過程で割れた素数は記録する
      • 重複していたら setwise coprime
    • 1 以外になったら 10^{3}より大きい素数なので記録する
      • 重複していたら setwise coprime
  • いずれのチェックにもかからなければ pairwise coprime

という方法を取りました
ちょっとでも試し割りの回数を減らそうと素数を列挙したのですが、結局解法3で述べた鳩ノ巣原理 による影響の方が大きくて結局計算量的には間に合っています (本番中は鳩ノ巣原理も見破っていなかったです)

おわりです！！
1問でたくさん学びがある良い問題でした！！！！

  1. \sqrt{A_i} \le 10^{3} ぐらいまで試し割りする方法しかないと思い込んでしまった。。PyPyは基本的にPythonより速いが 10^{8} オーダーは間に合うけど 10^{9} オーダーは間に合わない肌感。↩

  2. おさけ？↩

  3. 0,1は素数じゃないので扱い注意です (-1などで埋めるのが良い？)↩

  4. リンク先を見ると分かると思うんですが、PyPyと同一のコードではTLEしてしまいました。簡易的なPythonの高速化として「全体を関数で囲む」というのがあるんですが、それをしたらACしました！↩

Pythonで各要素にO(1)でランダムアクセスできるdeque(両端キュー)を書いてみた

Python アルゴリズム スニペット

表題の通りなのですが、まず何が嬉しいかを説明します

Pythonで、from collections import deque とすると、 deque モジュールが使えます
これは、両端キューと呼ばれていて、両端の要素への追加や取り出しがいずれもO(1)でできるリストのようなものです
これは単純な list と比較すると良さがわかって、
list は末尾への追加(append(x))、取り出し(pop()) が O(1) でできる反面、先頭の追加(insert(0,x))、取り出し(pop(0)) はO(N)かかってしまい、Nが大きい時にたくさん呼び出すととても遅いです。1

Pythonでは、Stack(LIFO)として配列を使いたい時は listで十分なのですが、 Queue(FIFO)として配列を使いたい時は dequeモジュールが必要になります。
もちろんdequeは両端キューなのでStack(LIFO)としても使えます。

しかし、dequeモジュールにも意外な弱点があります。
それはランダムアクセスの遅さです。
ここでランダムアクセスと言っているのは q[10] とか q[20] のようなindexを指定してのアクセスと思ってください。
deque モジュールでも、q[10] を参照したり、 q[20] = 'hoge' のように代入したりすることは可能ですが、遅いです
例えば、要素数 N=200000 の時に q[100000] を参照しようとするのは、内部的には端から順番に辿っていくので10万ステップぐらいかかります。
deque でのランダムアクセスは O(N)かかると言えます。
一方、list ならindexからアドレスを直接算出できるので O(1)です。

そこで、dequeモジュールの基本的な機能は抑えつつ、indexを指定しての参照・変更がO(1)でできるモジュールを作ってみました

そんなことできるの？と思うかもしれませんが、螺旋本の91ページあたりにある「リングバッファ」を参考に書けそうだなと思ったので書いてみました
また、ざっと調べた感じC++のdequeは要素へのランダムアクセスはO(1)のようですね
Javaの LinkedList も両端キューですが、こちらはランダムアクセスはO(N)っぽいです
→有名な教訓 https://qiita.com/neko_machi/items/d620c4a8958e74df3550

実装

次のように実装しましたのよ

class Deque:
    def __init__(self, src_arr=[], max_size=300000):
        self.N = max(max_size, len(src_arr)) + 1
        self.buf = list(src_arr) + [None] * (self.N - len(src_arr))
        self.head = 0
        self.tail = len(src_arr)
    def __index(self, i):
        l = len(self)
        if not -l <= i < l: raise IndexError('index out of range: ' + str(i))
        if i < 0:
            i += l
        return (self.head + i) % self.N
    def __extend(self):
        ex = self.N - 1
        self.buf[self.tail+1 : self.tail+1] = [None] * ex
        self.N = len(self.buf)
        if self.head > 0:
            self.head += ex
    def is_full(self):
        return len(self) >= self.N - 1
    def is_empty(self):
        return len(self) == 0
    def append(self, x):
        if self.is_full(): self.__extend()
        self.buf[self.tail] = x
        self.tail += 1
        self.tail %= self.N
    def appendleft(self, x):
        if self.is_full(): self.__extend()
        self.buf[(self.head - 1) % self.N] = x
        self.head -= 1
        self.head %= self.N
    def pop(self):
        if self.is_empty(): raise IndexError('pop() when buffer is empty')
        ret = self.buf[(self.tail - 1) % self.N]
        self.tail -= 1
        self.tail %= self.N
        return ret
    def popleft(self):
        if self.is_empty(): raise IndexError('popleft() when buffer is empty')
        ret = self.buf[self.head]
        self.head += 1
        self.head %= self.N
        return ret
    def __len__(self):
        return (self.tail - self.head) % self.N
    def __getitem__(self, key):
        return self.buf[self.__index(key)]
    def __setitem__(self, key, value):
        self.buf[self.__index(key)] = value
    def __str__(self):
        return 'Deque({0})'.format(str(list(self)))

使い方

上のコードをコピペする。ドーン。

初期化

次のいずれかの形式で初期化します

q = Deque()
q = Deque([10, 20])
q = Deque([10, 20], 500000)
  • 第1引数 src_arr はDequeとして初期化したい配列を指定してください。省略した場合は空です。
  • 第2引数 max_size はDequeが内部で保持するバッファの長さを指定します。実行中に要素数が50万になる見込みなら、500000を指定してください。省略した場合は300000です。
    • →必要に応じて拡張されるようにしたので基本気にしなくて良いです (2020/02/07 18時半頃update)

append, pop

この辺は dequeモジュールと同じ感じで使えます

q = Deque([10, 20])
print(q) # Deque([10, 20])
q.append(30)
print(q) # Deque([10, 20, 30])
q.appendleft(40)
print(q) # Deque([40, 10, 20, 30])
a = q.pop()
print(q, a) # Deque([40, 10, 20]) 30
b = q.popleft()
print(q, b) # Deque([10, 20]) 40

indexを指定してのget, set

この辺も dequeモジュールと使い勝手は一緒ですが、listのようにO(1) です！
Pythonらしく負のindexにも対応しています！

q = Deque([10, 20, 30, 40, 50])
a = q[1]
print(q, a) # Deque([10, 20, 30, 40, 50]) 20
q[1] = 60
print(q) # Deque([10, 60, 30, 40, 50])
b = q[-2]
print(q, b) # Deque([10, 60, 30, 40, 50]) 40
q[-2] = 70
print(q) # Deque([10, 60, 30, 70, 50])

型変換

list(q) のようにすれば list に変換できます！
set(q) で set に、list(reversed(q)) で逆順リストに変換できます
もちろん len(q) で要素数も取れます

できないこと・課題

  • メモリの動的確保
    • dequeモジュールは追加されたサイズに応じて拡張されるけれど、このDequeは初期化時の max_sizeを超えて格納はできません
      • 競プロ用途ならサイズが見積もれることが多いのであまり困らない気がする
    • → max_size を超えて格納しようとするときに動的に領域を増やすように改修しました (2020/02/07 18時半頃update)
  • indexを指定しての挿入や削除とか、count() とか remove() とか
    • 未実装 (実装するとしたらO(N) かな)
      • listに変換するのもO(N)っぽいので困らなそう
  • rotate() とか
    • 未実装 (実装するとしたらO(1) かな)
      • いる？
  • エラーハンドリングが甘いですけど
    • よしなに使ってください

ところで

両端キューを使っているとき、ある要素にO(1)でランダムアクセスしたくなる需要ってありますか？
たまにあった気がするけど思い出せない…
この問題に使えるかも！みたいなのがあったら教えてください！
あとツッコミや改善案などもあればTwitterで教えてください！

thanks

えびちゃんさんに改善案をもらったので改修しました (2020/02/07 18時半頃update)

  1. 先頭に要素を追加する場合は各要素をi番目→i+1番目にアドレスを動かさなきゃいけないからね。逆もしかり。↩

ゆるふわオンサイト#2 ゴリラの挑戦状 でwriterをした話

どうも〜 prd_xxx ですゴリ〜〜
9/14(土)に、「ゆるふわ競技プログラミングオンサイト at FORCIA #2 ゴリラの挑戦状」というイベントで、writerをさせていただきました！

コンテストページ
解説スライド

初作問チャレンジではあったのですが、第1回の作問を全て務めたmatsu7874氏のノウハウもあって、無事に成功に終えることができました！

本番までの準備など (時系列)

A〜K問題(11問) の原案と問題文とテストケースを作成しました。

5月頃

会社slackの競プロ部チャンネルで、作問者募集がかかる。
絶対やってみたかったので迷わず手をあげる。
300〜400点ぐらいの原案を空き時間で考えはじめる。

6月頃

引き続き、空き時間で原案を考える。
実際のG問題までの原案がだいたい揃う。
緑コーダーが5,6完できる水準をイメージしていたので、それはだいたいクリアできた認識。

〜7月中旬

500点以上の問題が作りたい気分になる。
I問題とJ問題の原案ができる。
ここまで原案9問、あとmatsu7874氏も作問するので一旦十分かな〜という気分になる。

7月下旬

日付が9/14に決まり、イベント告知。(JAG合宿とかぶった件はごめんなさい)
予想を上回る応募の多さにゴリのテンションMAX！ (定員で来れなかった方はごめんなさい)
幅広いレート帯の方に参加いただけるようで嬉しかった！
ところがある懸念も同時にあって、それは
トップ層が30分で全完して90分暇になったらどうしようと思った ゴリ怖かった
というのも自分よりレートが上位の方もおそらく半数ぐらいいらっしゃって、全然ゆるふわじゃない この人たちにも楽しんでもらいたい という気分になった。
あの けんちょん氏を60分は全完させないぞ！というつもりで張り切って問題を作ることになる。

8月上旬

matsu7874氏にプライベートリポジトリを作ってもらい、過去の作問リポジトリも見せてもらった。
それとbeet氏の記事であるところの Rimeの使い方 - beet's soil を参考にする形で、粛々とテストケースを作っていった。
結構大変な作業だなと思いながらも、最初の7問 (A～G)は詰まるところなくできた。

8月中旬

J問題のテストケースを作りたいと思っていたが、中だるみというか急に乗り気がしなくなってテストケースを作る手が1週間ぐらい何も進まなかった。
代わりにいくつか問題案を生やすことをしていた。
問題案を考えるのは楽しくて、テストケースを作るのはつらい、ってのを肌で感じていた。
ただそんなことも言ってられず、testerに見てもらう期間をとるため、作問作業は8月いっぱいで終えることにした。

8月下旬

駆け込みの時期。IとJのテストケースを完成させた。
H問題を追加したのと、K問題(の前身のすがた) のテストケースを生むために、8月いっぱいでやるはずだった予定を少しすぎてしまった。

9月1週 (2週間前)

testerのkyuridenamida氏とrian_tkb氏を作問slackに招待し、その時点でできている問題を解いていただいた。
ほとんどの問題で問題なく解いて頂けたので一安心。
問題文はいくつか指摘いただけて、こうやって曖昧さを消していくんだな～と勉強になった。

9月2週 (1週間前)

K問題を改題するモチベーションだったので、改題して最終形にした。(これはあとで書きますがめっちゃ苦労した)
あとは解説スライドをがんばってつくった。
結構気合入れて作っていて、修正や加筆は当日まで重ねた。

本番前日

HackerRankに問題を登録する作業をした。
結論から言うとこれは前日にやるべきでない作業だった。慣れてない状態だと特に、とても焦るので。
この辺の知見は別記事で残したい気持ちある (いつ書くかは未定... )
前日でやることになったのは、ちょうどお仕事で残業もあったのでやれなかったという事情があり。(仕方ないね)
一番焦ったのが、登録した問題でAC確認しようとしてて、午前3時ごろにやばい事態になってた。

何が起きたかと言うと、1問目を除いて、提出時に選ぶ言語が Ada しか選べなくなっていた...
というかAda って知ってますか？？ 下手したら全員 Adaで解かされるところだったので本当に焦った
原因はどうもHackerRankのバグっぽくて、使える言語の選択を選べる限り全部にチェックしていたらなぜかそうなってしまった。 デフォルトと同じにしたら got a kotonaki.

本番当日

あんまり寝ずに賞状を作って即コンビニプリントした。印刷がかすれてしまったの許さん。
副賞のバナナはmatsu7874氏が買ってきてくれた。
matsu7874氏が作ってくれた名札をチョキチョキしたりした。
会場の設営とかがんばった。
あとはHackerRankのトップページをいじったり、Twitterに告知したりした。

HackerRankのトップページ、何書いて良いか分からなくて適当を書いた。
上の英文2つは消せなかったのでシュールな感じになった。

本番中

コンテスト開始後はwriterルームからslackやTwitterや提出一覧を監視していた。
slackがclar地獄になったらどう対応しよう... みたいな状況も想像していたが、思いのほか至極平和で、若干手持ち無沙汰気味だった。
matsu7874氏はこのタイミングで解説スライドを書き始めて流石経験者だなと感じた。
全完もオンサイト・オンライン1名ずつでいい感じに時間いっぱい使ってもらったのでいい感じだった。(語彙)
何よりなんとか平穏無事に終わってよかった。

解説

12問ぶっ続けて喋ったのでめっちゃのど乾いた。
それよりもマイクがなくて聞こえづらかったみたいで本当にごめんなさい(事故だったのでは...)(教えて欲しかった...)

懇親会

たのしかったー！！
ほんっとうにポジティブな感想しか聞けなくて嬉しかった！！
色んな人に喜んでもらえて、がんばってよかったです

打ち上げ

おいしいお肉を食べ放題した！！！
直前でピザ食ったの忘れてたの、あたまわるかった！！

問題ごとの思い入れとか裏話とか

A - honda's janken

ABC-A を意識した。5分で生やした問題。
Twitterの某じゃんけん企画で本田の勝率が異常に高かったのでそのネタを利用。
問題文に「hondaは決して負けることはない」って書いたのにクスっときましたか？きてほしかった。

B - sentouryoku

これもABC-Bを意識した。5分で生やした問題。
肩慣らし的に、for文を回して問題文の通りにやらせるのがしたかった。
特に元ネタはないですがドラゴンボールの戦闘力はマジでインフレしすぎですよね。

C - mosaic tile art

もともと原案はN-Rook問題だった。
300点問題を作りたいなーと思って、N-Queenは実装重めなDFSっぽいけど、斜めの動きを封じるとただのN!になるよねーと気づいて出そうとした。
まあでもN-Rookってググると普通にN! だよと出てくるので、そうとバレない工夫が必要だった。
それでタイルの色ってことにして、N-1個の部分にフォーカスさせるような誘導を問題文で試みた。
白黒ではなくて白青なのはちょっとした狙いがあって、白vs黒だと色を対等に見られがちだけど青ってすると青のほうに注目するんじゃないかなーと。(根拠ないけどなんとなく心理的に)
ちなみにN*Nの正方形でなくN*Mの長方形だったら400点になって教育的にも良さそうだったけど、逆元の説明はめんどくさそうだったのでこれで。

D - n-dwich box

これはいつかローソンで買ったサンドイッチが、ここでいう2-ドイッチと3-ドイッチが入っていたことがあって、つまり|#||#|#| となっていて、3-ドイッチを2-ドイッチだと思って具の部分に指を突っ込んでしまい、ちょっとした怒りを覚えた体験が元ネタ。
この製品は2-ドイッチと3-ドイッチです、みたいに書いてほしいよね。
n-ドイッチという呼び方は私のお気に入り。

ありがとうございます。

E - usagi vs kame

性質の違う何かを競争させたい気持ちになって、うさぎとかめの童話を思い出して生やした問題。
なぜゴリラではないのか、とわりと疑問に思われたみたいだけどそんな理由でした。
kameを毎秒シミュレートするとTLEするけど、それをさぼれることに気づくと貪欲で解けるのがお気に入り。

F - mneme game

どうやって思いついたかあまり覚えていない。
mnemeという英単語は記憶能とかいう意味らしい。(なじみのない単語だったけど使ってみた)
想定解は二分探索だけど、別の賢い方法があればそれで解けてもいいかなと思っていた。
rian_tkb氏に、E問題と同じ解法で解けることを指摘いただいたが、私はそれまで気づかなかった。(目からうろこだった)
EとF、どちらも350点ぐらいの評価だったのであえてEを300、Fを400で出してみた。

G - double range queries

最初の原案は、重なる長方形領域というよりは、幅1の四角い輪っかだった。
ただ輪っかってことにしちゃうと愚直に外周をなぞるとカウントできてしまって、O(Q(R+C)) ぐらいで普通に通ってしまう。
どうせ2次元imosを使わせる想定なら、輪っかの形に限定しなくてもいいんじゃないかと気づいて、出題された問題になった。
2つの領域を裏返すと、結果はXORのような領域が裏返るため、あえて問題文は「Aに含まれてBに含まれない」「Bに含まれてAに含まれない」みたいにした。
あと解説スライドの2次元imosの図、地味にがんばった。

H - gori uho game

朝のゴリラジオ体操でARC038をやった回があり、 B - マス目と駒 を解いたときに、末尾から結果が決まる系のゲームDP、最近AtCoderで出てないな～と思って出題しようと思った。
状態をbitで持たせようと思ったのと、手でテストケースを作って検証するのを楽にしようとサイズは5x5に固定した (それでも正しさの検証はそこそこ大変だった)
Nは10じゃなくて12とか15とかでも良かったかも。まあいいか。

I - pino assort

全問題の中でwriterお気に入り。
実際に売られているリアルのピノアイスを制約に使うことにこだわった。
画像
この制約を使ってガチガチのナップサックDPを作りたかったがうまく作れず、制約をいじるという暴挙にでたｗ
少なくとも2つの味は1 、って制約をつけると貪欲に解けるようになることに気づいたので、それをそのまま出題した。(全然DPじゃない)
ちなみにwriter想定は400点だったがrian_tkb氏の見立てでは500点評価だったので、前日まで400点として出すか500点として出すか迷った。
当日は意外とさくっとACが出なかったので、500点で良かった。

J - swapping paths

これはDPの問題を作ろうと思ってうまくできたほうの問題。
横幅はだだっ広くする意味は特になくて、考察と実装を1ステップ加えるためだけについた制約。
自分で問題を設定して、それがギリギリ自力で考察できたときは何とも言えない嬉しさと楽しさを感じた。
横幅のめんどくさい制約を除くと正統派DPだと思っているので、よければ練習にどうぞ。

K - fuzzy search queries

これは一番の意欲作で、最も労力を割いた問題、に結果的になってしまった。
最初はsimple search query という題目で、部分文字列が含まれるかどうかのYES/NOだけだった。しかも制約も|S| <= 1000 だった。
題意としてはSAでもロリハでもいいからいい感じの文字列アルゴリズムを貼れば楽勝、みたいにするつもりだった。
制約が|S| <= 1000というのは私がSuffix Arrayというものをとんでもなく勘違いしていて、なんと全てのsuffixを配列に詰めてソートしただけだと思っていた！ｗ
実際は線形メモリで作れるんだよとkyuridenamida氏 に教えていただき、ありがたかったです (蟻本を読みましょう！ｗ)
それならばということで制約を30000にして、さらにせっかくSAを想定解にするのだからSAの旨味を使った問題にしようと改題を試みた。
蟻本のSAのページも読んでいなかったので、ちゃんと読んで理解することにした(それがなんと1週間前！)
クエリと同じ長さかつ、辞書順でクエリの直後に来る部分文字列を出力する、ってのがその部分で、改題案自体はすぐに思いついたけど、ちゃんと解くにはめちゃめちゃ頭つかった。
解説スライドにも書いた、愚直に文字数チェックしていくのは間に合うか？という問題が愚直では間に合わないと思っていて、BITと二分探索を駆使して無駄に高速化を試みたけど2時間以上バグらせまくりでつらかった。
それを作問slackで相談したら実は愚直で大丈夫ってことをkyuridenamida氏が指摘してくれて、got a kotonaki.
(結局自力でそこまでは考察しきれなかったな～って感じ。計算量の見積もりはちゃんと考えましょう)
すごく勉強になって得るものが多かった問題。

L - rivals

matsu7874氏の作問。
問題案を見た時にまったく解法が見えなくて、2週間ぐらい解けなかった。
2週間ぐらいたった時に見直して、累積和を使ってがんばったら解けた。
これはLやRが1000以下であるから解けるやり方で、10^5 だとこのやり方はだめだった。
writer解はセグ木なのでたぶん10^5 いけたと思うのですが、そうしなかったのはやさしさだなぁと思った。

おわりに

#ゆるふわオンサイト タグ、もう本当に嬉しい反応しかなくて、感激です
#ゆるふわオンサイト - Twitter Search

お忙しい中testerを引き受けてくださった、kyuridenamida氏、rian_tkb氏には本当に感謝です。 おかげさまで、問題の質がブラッシュアップされていきました！
matsu7874氏は会場の手配、ピザや飲み物の手配から、諸々の調整、slackやGitHubの環境、作問ノウハウの提供などありがとうございました！

最後に、実際に参加してくれたり、Twitterで感想書いたり、ブログ書いたりしてくれた皆さん本当にありがとうございました！！！

Pythonでheapqから大きい順に取り出したいときにもバグらせにくいやつを書いた

Python スニペット

表題の通りです。

お気持ちを説明すると、ご存知 heapq は優先度付きキューと呼ばれていて、適当に要素を追加したり取り出したりしても常に取り出す値は最小を保っている便利なやつです。 しかも追加・取り出しはともにO(logN)でとても実用的！

しかし欠点があって、これの逆バージョン、つまり常に最大値を取り出したいときには対応していないんです。

一応それを実現するテクはあって、全部符号を反転してheapqに突っ込めばデカい方から順に取り出せます！
でも追加したり取り出したりするたびに符号を反転するの結構メンドイし、バグらせやすい。
コードは運よくバグらなくても、実装中に頭がバグる。

そんな悩みを解決するために、classでラップしちゃおう！と思い立ちました。

大したことないコードですが、あると地味に嬉しいだろうと思ったので、書いてみました。

import heapq
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        return heapq.heappop(self.hq) * self.sign
 
    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)
 
    def top(self):
        return self.hq[0] * self.sign

使い方

まず上のコードをコピペする。ドーン。

初期化

q = Heapq(arr, desc) のように書けばいいです

  • 第1引数 arr は初期化に使う配列です 空っぽから始める場合は []でいいです
  • 第2引数 desc は大きい順に取り出すなら True、小さい順ならFalse です。Falseは省略可です。

pop()

q.pop() のようにすると値が返ります
一番小さいの or 一番大きいのを集合から取り出します。
初期化時 desc=Trueを指定していたなら大きい方が出てきます。
取り出された要素は集合から消えます。

push()

q.push(a) のようにすると集合に aを追加します

top()

q.top() のようにすると値が返ります
一番小さいの or 一番大きいのを参照できます
初期化時 desc=Trueを指定していたなら大きい方が出てきます。
pop()に似てますが、参照するだけで、集合から値が消えることはありません。
O(1)でめっちゃ速いです

個人的に気に入っている点

元の heapq.heappush(hq, 3) みたいな書き方くどくない？
hq.push(3) みたいに書けるので楽ちん！

試し切り

heapq と逆向きのheapqとを2個持つ問題だったのでちょうど良かった。
atcoder.jp

注意点

本家のheapqのように配列やタプルの配列には対応していなくて、単純な数値の配列のみに対応しています
もし改良してくれる人がいたら教えてください

→→ここから下は2019/6/25追記

情報提供1

@tatyam_prime さんが改良版を考えてくださいました

上のリンク先から引用します

import heapq
class Reverse:
    def __init__(self, val):
        self.val = val
        
    def __lt__(self, other):
        return self.val > other.val
        
    def __repr__(self):
        return repr(self.val)
    
class Heapq:
    def __init__(self, arr, desc = False):
        if desc:
            for i in range(len(arr)):
                arr[i] = Reverse(arr[i])
        self.desc = desc
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        if self.desc: return heapq.heappop(self.hq).val
        else: return heapq.heappop(self.hq)
 
    def push(self, a):
        if self.desc: heapq.heappush(self.hq, Reverse(a))
        else: heapq.heappush(self.hq, a)
 
    def top(self):
        if self.desc: self.hq[0].val
        else: return self.hq[0]

見た感じ、desc=Trueのときは Reverse() オブジェクト同士を(おそらくheapq内部で)比較するようにしていて、Reverse()オブジェクトは __lt__() がオーバーライドされてて本来と逆向きに比較されるんでしょうかね？
かなりテクいです
これで数値の配列に限らず、文字列やタプルや配列の配列にも使えて、汎用的ですね！

情報提供2

@juppyjappy さんからさらに情報提供がありました！

なんとheapq には最大値から取り出すバージョンが存在しない、というのは思い込みで、一応できる方法があるらしい！！ 完全に知らなかった！

もう少し書くと、heapify() に当たるものは heapify_max()という名前で存在している！
だけどheappop() や heappush() に当たるものは存在しない笑！
惜しい部品はあるからそれでやってね、みたいな感じらしい
上のブログ記事から引用します

import heapq
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

こうやってやると、heapify_max() で構築した降順heapに対して、heappop() と heappush() ができるらしい！
ほえ～、これそのまま使えるように組み込んでくれ～～
元記事はheapについて詳しく書いてある記事なので、気になった方は読んでみてください！！

結局どれを使えばいいの？

好きなのを使いましょう！！

AtCoderJobs経由で転職ACするまでの記録

自分のこと

intro

この度、無事に中途採用での内定をいただき、転職活動を終えることができました！！

その際、昨年サービスが開始したばかりのAtCoderJobsを利用したので、それにも触れながら、私の転職活動がどんな感じだったか振り返りつつ記録に残していこうと思います！

転職に至るモチベーション

私は7年ぐらい、モバイルアプリエンジニアとして1勤めていました。
小規模な会社ながら、知名度の高い(高かった)サービスがあり、ユーザー数が数百万人規模のアプリの改修・リリースに関わることができました。
また、開発の色々な役目 (要件定義・実装・テスト・保守)も経験できましたし、リーダーとしての役目や顧客との折衝を求められることもありました。
大きな規模の会社に常駐させてもらったこともありました。

少なくとも2年前 (=私がAtCoderと出会う以前) までは、転職の転の字も考えていませんでした。
そこから徐々に転職へのモチベーションを高めることになり、最終的には転職を決意します。

競プロer社会人たちとの出会い

この2年間で、競プロ関連のイベントを通じて同業・同趣味 (競プロer)の社会人と知り合うことが多くありました。
それまで外の会社の人間とプライベートで知り合うことはなかったので、すごく刺激を受けました。
まず気づいたのが、出会う人出会う人、自分のキャリアや人生設計についてしっかり考えている人がとても多いです。
これに関しては、私がそれまで考えてなさすぎだっただけかもしれませんが、そのギャップを認識できたのは大きいです。
次に驚いたのは、転職でステップアップを図ろうとする人の多さです。
新卒で入社した会社に居続ける人はむしろレアなのかなと思うくらいです。
とにかく、同業の意識の高い人たちとの出会いが、人生について考えるきっかけになりました。
意見を交わしてくれた皆さんに感謝します。

いつ転職するのか？

私は、それまで漠然と考えていたのは、転職するとしたら「今の会社で学ぶことがなくなった時」だと思っていました。
しかし最近になって、その時を待っているのは間違いだ2と気づきました。
同じ会社にいても、仕事ガチャの結果によっては身につかないスキルは必ずあります。(これはどこに居てもそうだと思います)
だから、別にその会社が持っているスキルをコンプリートしなくても辞めて良いのです。というか、コンプリートしようなどという発想がおこがましかったです。
それに、仮にコンプリートできた時が来たとして、そのコンプリートするまでの間、もっと効率よくスキルを磨ける環境があったら？と考えると、どう考えてもそっちの方がお得です。
私は「仕事とは退屈なものだ」という先入観もあったので気づくのが遅かったのですが、仕事の9割が退屈だと感じていた3～4年前にはとっくに辞めるべき状態だったということです。

成長できる環境への憧れと欲求

退屈な状態というのがどういう状態だったかというと、
まず、競プロで得た、計算量改善等の知見は業務で一切必要とされませんでした。
それ自体はわりと普通のソフトウェア開発現場でよくあることだと思うのでまだ良いのですが、
保守担当の時は頭を使わない割に体力だけ消費するルーチンワークや、テスト担当の時は仕様の明文化されていない謎製品を動かして延々と挙動を記録する日々もありました。

その頃は「食べていくため」にそんな環境であっても我慢するのが当たり前と思っていました。
ですが本来は、そんな時期こそが自分の環境に疑いを持つべき時期なのかなと思います。
明らかに、会社が私に求めていることと、私が会社に求めていること には大きな食い違いが生じていました。
私が会社に求めていたのは、持てる力を活かしたい欲求を満たせることと、日々「学び」や「成長」があることでした。
それはルーチンワークやテスト消化の日々では決して満たされることはありません。3

私は、エンジニアがその能力を評価されて尊重され、適材適所の仕事ができる環境にあこがれていました。
また、優秀な方に囲まれて能力を高めあえる環境も欲していました。
これも、様々な社会人競プロerと接する中で徐々に感じるようになったことです。

私自身はまだまだひよっこだと思っていながらも、客観的にはプログラマとしての能力があるほうだという自覚も(AtCoderのおかげで)あり、それを生かしたい、そして成長したい、という欲求があることに気づきました。

どのようにして内定を得たか

会社との出会い

2月頃、ある会社さん4で競プロのオンサイトイベントが開かれました。
きわどく枠が空いていたのと、こういうイベントには積極的に参加するようにしていたので、迷わず参加しました。
ゆるふわなイベントとのことでしたが問題はしっかり作られていて、かなり楽しませてもらえました。
参加無料でピザまで振舞われてちゃんと本格的なイベントだったので、かなり満足でした。

交流の場では、主催した社員さんに声をかけてもらえて、AtCoderJobsで中途採用もしていることを知りました。
当時私は、転職に興味はあったが、なんだかんだ理由をつけて「転職はしたいけど今はまだその時期じゃない」と言い、特に動けていない状況でした。
AtCoderJobsも興味があって、転職するとしたら一番にAtCoderJobsを頼るだろうと決めていたものの、登録したきり見ていませんでした。

その会社は検索サービスを作っている会社で、競プロの知見を持つ人をある程度歓迎しているようでした。
競プロ部が活動し始めたことも聞きました。
知らない会社だったけど良さそうだな～というのが第一印象でした。

後日、その社員さんに声をかけてもらえて、食事に行くことになりました。
(私の方から声をかけようと思っていたときに、DMがきました)
そこで会社の魅力を色々聞いて、行きたい度合いが強くなりました。

AtCoderJobs

ということで、何かの縁だと思い、AtCoderJobsを使ってその会社に応募してみることにしました。
応募がAランクからということだったので、つい1か月ちょっと前に青色(Aランク)に到達していた自分には、「早速のタイミングで役に立った」と感慨深いものがありました。

食事の時に社員さんに色々聞いたのですが、そこで一つ、
Jobsで応募する人必見の最重要アドバイスを いただきました。
それは...

「その他PR」欄を充実させる！！

「その他PR」欄は、フリーフォーマットなので人によって手を抜きがちなところであり、差が出やすいです。
さらに、人事の人が応募者を知るうえでかなり参考にするところであり、PRが弱いと落とされてしまうケースもあるようです！
(現に、面接の際も割と「その他PR」に書かれた文章をもとに面接が進んで行きました！ )

ということで、その他PRはみっちり書きました。
私の場合、業務での経験と、業務外での経験に分けて書きました。
業務外のところに、AtCoderの実績(?) (連続400日AC, PythonAC数1位, ゴリラジオ体操続けてます～) みたいなのも書きました。
(これは実際面接でもウケが良かったです。)

このアドバイスがなかったら、落とされるところでした。

面接対策

面接対策ですが、私の場合
「面接官になったつもりで履歴書やその他PRにツッコミを入れていく」はやりました。
なぜそれをやろうと思ったのかや、関連するエピソードを話せるように準備していました。
これは主に脳内で、通勤の行き帰りの時間やお昼休み中など、任意のタイミングで自問自答を繰り返していました。

また、ちょうどこの時期に見つけた記事で、ヴァネロピさんの記事 に感銘を受けていました。
この記事を見るまではもっと転職活動を甘く考えていたので、しっかり対策しなきゃという気持ちになりました。
(気持ちになっただけでここまでしっかりと対策はできていませんでした)
(あとから思うともっとちゃんと準備すべきだった点があるので、反省)

あとは、ホームページを見るなどして、この会社に入社するぞ！という意識を高めていました。

退路を断つ決断

これは内定とは直接関係ないのですが、実は選考前に退職を決めるという、少し危ない橋を渡っていました。

これは勢い任せながらも、かなり考えたうえでの行動でした。
転職を本格的にやるなら、遅かれ早かれ辞めるだろうということと、勤務しながらの転職活動のやりづらさを非常に感じていました。
選考のたびに会社を休んだり早退したり、というのは好きなだけできるわけではありません。5
現に選考をリスケしてもらうこともありました。
収入が止まるリスクはありましたが、転職活動自体を短期決戦で片付ける覚悟で決めました。
最後に決定打になったのは、ちょうどこの時期に告げられた人事的な不遇でした。

選考～内定

内定までに選考に赴いたのは2回でした。
初日が面接→SPI→面接→面接 でとってもハードでした。

面接の詳細は書けませんが、一番PRしたい職務経験は何か、ぐらいは整理しておくべきでした。
あとはSPIを甘く見ていてボロボロでした。
こんなに難しかったっけ？という感想だったので、ちゃんと対策した方が良いですね。

最終面接の日も面接が2回ありました。
私が想定していた以上に志望動機を掘り下げられて、一時こんな状態になりました。

ぐにゃぁっとなりながら、そこまでは考えていませんでした、と素直に言いました。
(というか緊張もあいまって全体的にボロボロだったので、ダメかと思いました...)

最終面接の後、胃に穴が開きそうな状態で1日過ごしましたが、なんとか内定を得られていました。
2度の作戦会議とその他PRのアドバイスと、最後までお世話になったイベント主催の社員さんには感謝です！
5月から同僚になるのでさらにお世話になることと思います。

転職活動を通じて

結果として、Jobsから応募した1社目で内定を得られました。
(ちょっと通常とは違う流れでしたが...)
しかも、かなり希望に近い環境・職種だし、福利厚生もめっちゃ良いのでこれ以上ない結果です。
AtCoder青達成、オンサイトイベントの参加、社員さんからの手引き、、などなど、1つでも欠けていたら内定が得られなかったと思います。
面接も失敗した部分があったので、運が良かったと思います。
AtCoderJobsのスカウト機能はここに落ちたらONにするつもりでしたが、最後までOFFのままでした。

AtCoder経由で応募できたことが自信になった

普通の転職活動だと、職業での経験をもとに、応募先の会社が期待するスキルとマッチするか？という面談になると思います。
私の場合それだけだと心もとないと感じます。
ですが、AtCoderでの実績がアピールに使える会社、となれば、ずいぶんと心強い自信になっていました。
私の場合、業種が違うこともあり、これがなければ採用されなかった可能性がかなり大だと思っています。

実際、AtCoder青(Jobs Aランク)の評価は、意外と高い、と感じました。
内定をもらえた以外にも2社ほど、(AtCoderJobsとは別経由ですが) AtCoder関連でお誘いを受けていて、カジュアル面談に行きました。
大体、「業種が変わると戦力になれるかが不安」とか言うと、「AtCoder青なら全然大丈夫だと思います」という答えをもらえました。

サンプル数が少ないので確かではないかもしれないですが、AtCoder経由で募集してくれている企業さんは、AtCoderの色ごとのレベルがどれ位かをちゃんと把握してくれている印象を持ちました。

コンプレックスの解消

私は大学を複数年留年したことがコンプレックスの1つになっており、なぜと聞かれると未だに答えに窮するポイントではありました。
結果として5回の面接の中でそれに触れられたのは1回で、しかも「答えにくかったら大丈夫ですよー」って感じで優しくしてくれたので助かりました。
転職面接では学歴よりも職歴を重視する傾向があるんだな～というのが分かりました。6
この経験をもって、このコンプレックスはほぼ消滅しました！！

AtCoder万歳

マル秘情報ですが、寝相が悪いとちょっと足向いてます

outro

勉強しなきゃ... するぞ...！！

  1. そんな格好いい職種名はありませんでしたが勝手に名乗っていました。実態は雑用屋さんでした。↩

  2. 575。↩

  3. AtCoderがそこの欲求を満たしてくれる存在ではありました↩

  4. 特定してもそっとしておいてね(//)↩

  5. 575。↩

  6. これもサンプル数が少ないので一般的に言えるかは分かりません↩

AtCoder青になるまでの軌跡

2018年12月29日のAGC030 (=今年最後のAtCoderコンテスト)にて、
ついに、ここ1年7ヶ月力を注いできたAtCoderで青コーダーになりました！！！！ 上のレートグラフからも苦労の様子がある程度わかりますが、本当に紆余曲折ありましたので久々にブログに記していこうと思います。

前半はAtCoderに出会うまでの自分語り的なことも多少書くので、 興味がなければ適宜読み飛ばしてください(><)

目次

(推定) 茶色になるまで

まだAtCoderには出会っていない頃の話ですので(推定) と付けました

情報系学部を卒業した

大学をギリギリ卒業しました。成績は下の下の[検閲により削除] でした。
(恥ずかしい記事ですが下記に当時の状況を少し書いています) 1
競プロと出会うまで(前編) - 30歳で競プロに目覚めた霊長類のブログ

学ぶのには最適な環境だったはずなのですが、学業について行けず、諸々やる気も出ずに、かといって休学などもせず 無駄に学費をつぎ込んで2 虚無をして過ごしてしまいました。

記憶に残っているのはダイクストラ法を授業で教わったときはなんか凄い、面白いって思いました
当時はこれを実装するなんて思いもしませんでしたが、今ではスラスラと書けるぜー当時の自分よ！

1年ぐらい趣味で自分なりにコードを書いた

これは大学に在籍していた最後の1年ぐらいのことなのですが、ようやくこの時期になってプログラミングって楽しいって思えたんですね
(プログラムを書くお仕事をしたい、とハッキリ思ったのもこの時期でした)
自己流なので誰かにレビューしてもらうわけではないですが、下のようなものを書いたりしていました

CUIでオセロできるやつ

自分 vs. 自分で対戦したり、自分 vs. AI で対戦できるオセロゲームを書きました
AIといってもαβ法みたいなことは挑戦していなくて、各マスに固定の優先度がつけられてるだけのシンプルなやつでした(笑)

数独ソルバ

数独の解を見つけるプログラムをこの時期に書きました。
条件分岐と配列をすごく駆使して、えぐいスパゲッティコードになっていたと思います。
このとき、実は今思うと自己流の深さ優先探索を書いていたんじゃないかと思います。
自明でないマスはとりあえず仮定を置いて、そのマスに深さ1の仮定だよとマークをつけて、さらにその仮定でマスが埋まりきらなかったら深さ2の仮定を置く...
みたいな感じだったと思います。
自己流なので、当然再帰なんて使おうとも思いませんでした。
今思うと当時の力でよく実装できたなーという気持ちです (ただし1ヶ月かかりましたが...)

こんな感じで自分なりにコードを書いていた時期がありました。
成績自体は下の下の... でしたが、プログラミングのいろはというか、if, for, 配列... をゴリゴリ使った手続き的な処理は、 CS学科の中でも中程度には書けるようになってたんじゃないかなーと思います[要出典]。
この頃の自分にAtCoderをやらせたら推定茶色ぐらいかなーと思っています。(実装は遅かったので...)

(推定) 緑色になるまで

なんだかんだで就職しました。このセクションもAtCoderに出会う前のことです

ソフトウェアエンジニアとして実務経験を積んだ

これは競プロ力とはあまり直結しないのですが、単純に趣味でゆるーくコードを書いていたところから、お仕事で毎日8時間3 向き合うようになったので、単純にプログラムに触れる時間が増えました。
また、実務の中で、先輩にレビューしてもらう中で効率の良いコードのまとめ方なんかは身に着けられたかもしれません。

Project Euler を90問ぐらい解いた

ある半年～1年の間ぐらい、 Project Euler 埋めにはまっていたのを思い出しました。
最初のころは完全自力で解くのを目指していましたが30問解いた辺りから辛くなったので、どうしても分からなかったらググって色んな人の解法を見るようになりました。今の精進方法と同じ！
今思うと、累積和や簡単なDPのような解法は自力で発明していたように思います (当時はそれが名前のついた定跡であると知りませんでした)
ただ、競プロのように正解までの早さを競うわけではないので、めっちゃ(ものによっては1週間とか)考えて編み出したりしていました
にぶたん(二分探索・バイナリサーチ) は知っていました。

素因数分解させたり、素数を列挙させる問題がやたらと多かった4 ので、競プロでよくある整数問題に対する考え方もこのときに多少磨かれた気がします。
あとはLU分解を調べて実装して、任意の有理数が係数になっているn元連立一次方程式を解けるようになって感動した記憶があります(これは競プロで出なさそう？)

90問ぐらい解いたところで行き詰って、それから熱が冷めてしまったのですが、思い出したのでまた久々に再開しようかな ^^

CODE VS 5.0 に出た

2016年3月ごろの、CODE VS 5.0予選に出ました5 。
同僚がたまたま話題に出していたので、いっちょやってやるか！という気持ちで出てみました。
このとき、キャラクターを動かす場所の候補を探すのに、初めて幅優先探索を書いた記憶があります。
最終日にヒューリスティックなパラメータを怪しくいじったのが意外と善戦して、全参加者の真ん中ぐらいの順位にはなれました。
CODE VSはリアルタイムで他のユーザーと対戦できて、対戦のようすがグラフィカルに表示されるので、やたらと楽しかった記憶が強いです。
6.0があるとしたら有給を何日か使ってでもやりたいなーと思っています6

AtCoderと出会うまではこんな様子でした。
この頃の自分にAtCoderをやらせたら推定緑色ぐらいかなーと思っています。

AtCoderとの出会い～水色になるまで

AtCoderと出会って、人生が変わりました

初回参加

忘れもしない、初めて参加した時のことを書きます。初参加は2017年5月、ABC062でした
この頃の私は、井の中の蛙だったので、プログラミング力には多少の自信をつけていました。
そして、AtCoder 「Beginners」 Contest だと思って舐めていました。
言語は、当時一番慣れていたJavaではなく、独学で少し触ってみただけのPythonで挑みました。(心境的には舐めプに近いです)
結果は、4問中の2完で、これほどまでに通用しないのか、と凹みました (全部解けて当然とぐらいに思っていたので)
が、同時に 俺はこんなもんじゃねぇ～～！！ という、熱い気持ちが沸き上がってきました
これが、私に火をつけたきっかけになり、以降は毎週のAtCoderコンテストでレートを上げることを目標にしました。

ABC全完を目指し、ABC埋めをした

とりあえず、AtCoder Problems を参考に、手当たり次第に過去問をやりました。
言語は、引き続きPython を使いました7。
ABCのA～C問題は絶対解くつもりで解いて、解けたらD問題にも挑戦していました。
CやDには自力で解けない問題も多かったので、逐一解説を見たりしては、身に着けていました。
それをがむしゃらに、日によっては2セットや3セットや4セットやりました。(多分、この時期が一番新規ACを稼いでいた)
公式のEditorial が数学的な記述や グラフ理論の言葉を使った記述が多くて、読み解くのに苦労していました。(これは今は多少慣れてきましたが今でも苦労します^^;)
こんなとき先人の書いてくれたブログ記事たちはとても理解の助けになりました。
初めて全完できたときの達成感、気持ちよさは今でも覚えています。

蟻本を買った

プログラミングコンテストチャレンジブック (通称：蟻本) は競プロerのバイブルだと知って、購入しました。
1ページ1ページに情報が凝縮されているので、理解するのに1時間以上かかるページも存在しました。
2017年8月頃にちまちま読み進めて、水色になる前に初級編は読了したと思います。8

水色になるまでに学習したアルゴリズム、考え方

  • 計算量・オーダーに関する感覚
  • list, set, dict, deque(双方向キュー), heap(優先度付きキュー) を使いこなす
  • グラフ理論の基礎
  • ソートして貪欲
  • ソートして二分探索
  • しゃくとり法
  • 累積和、いもす法
  • DFS、BFS
  • ダイクストラ、ワーシャルフロイド、ベルマンフォード
  • DP
  • Union-Find, クラスカル法
  • 二項係数のmod 1e9+7 を求めるかわりにmodの逆元を繰り返し二乗法で求めるやつ
  • (Pythonの) itertoolsの便利そうなやつを抑えておく (permutation, combination, product, ...)

青色になるまで

水色～青までの時代は長かったので、時系列通りに書いてません。(書けません)

このブログを始めた

何か学習した知見をアウトプットしようと思いこのブログを始めました。
しかし記事にまとめるのって物凄く大変だと分かって、あまり記事を書かずに長らく放置しちゃいました。
今後も思い立った時に書こうと思います。。

Twitterを始めた

DDCC2017の決勝に進めたのがきっかけで、Twitter を始めました。
畏れ多くも1000名を超える方にフォローいただいています。ありがとうございます。9
特にコンテスト後に解法に関する議論が活発に行われているのを知って、軽い情報収集の目的がありました。
後述しますが、Twitterがきっかけでリアルの交流も多く生まれて、単なる情報収集にとどまらない、期待以上のものが得られたと感じています。

1日1ACを軸に、AtCoderの過去問を埋めていった

AtCoder Problems に、Streak という指標があります。
AtCoderの問題を連続で何日新規ACしたか を表すのですが、2018年1月3日～2018年12月30日現在まで、362日継続中です
この 「Current Streak を切らさない」を1つの方針として、2018年は精進していました。
この方針の精進方法については、向き不向きというか、賛否両論がある10 のですが、結果として私にとっては良かったと思います。
理由としては、常に頭の中に解きかけの問題をいくつか置いておけるというのがあります。
どういうことかというと、Streakを長く続けるためには意外と戦略的に考える必要があって、例えば時間的・体力的に厳しい日なんかは軽めの問題で繋ぎたいので、軽めの問題は温存しときたいという気持ちになります。
すると、普段はできるだけ軽めの問題以外に目を通すようになって、それらの解法を考える習慣が生まれます
大体私は、新しい過去問に目を通したときに「すぐ解けそう」「ちょっと考えれば解けそう」「かなり大変そう」の3つぐらいに分類しています
時間的・体力的に余裕のある日は「かなり大変そう」な問題に挑戦しますが、そうでない日のほうが普段は多いので、「すぐ解けそう」「ちょっと考えれば解けそう」の問題は割とストックしてあります11。
その過程で多くの問題に目を通したり、実際にACしたり、「かなり大変そう」な問題の考察にチャレンジしたりしてきました。
このStreakという数字は今後もモチベーションを保つために生きる数字だと思っています。

PythonのLanguage Ownerになった

これは1日1AC以上... をコツコツやってきた結果の副産物ですが、2018年9月頃、「Pythonで一番AtCoderのAC数が多い人」になりました
(これまたAtCoder Problemsさんで言語別に集計されています12)

AtCoderの過去問は2000問以上あるうえ、「すぐ解けそう」に分類される問題も多く解いてきたので、個人的にはあまりすごい事と思っていないです。
でもこういう形で可視化されるのは非常にモチベーションになりました。

AtCoderコンテストには欠かさず出た

これは私ぐらいのモチベーションがあれば自然とそうなってしまうのですが、AtCoderのトップページ左側に「予定されたコンテスト」という一覧がありまして、 そこに表示されているコンテストには冠婚葬祭レベルの理由がない限り大体出ていました。
何なら旅行中にも出ていました^^;
休日は基本AtCoderコンテストに被らないように行動します。
(競プロerと遊ぶときはこの辺は共通認識になってたりして面白いです 13)

AtCoder以外のコンテストにもできるだけ出ようとした

AtCoderは土曜または日曜の21時～ で、日本人が参加しやすい時間帯に開催されます。
TwitterのTLを眺めると、AtCoder以外のコンテストの情報も流れてきて、自分もやろうかなーという気持ちになります。

yukicoder

これは金曜の21時か22時頃に開かれるので、これまた日本人に参加しやすい時間帯になっています。
日本の方が運営しているのでもちろん日本語です！
TLで情報が流れてきた際には大体参加するようにしています。

Codeforces

ロシアで運営されているコンテストサイトです。
曜日が固定されていなくて、頻繁にコンテストが開かれている印象があります。
英語が分かりづらいという評判14もあります...
海外コンの中では一番参加回数が多いです

TopCoder

歴史あるコンテストサイトです。
1度だけSRM(するめ、短期型)と、2回マラソンに出ました。

CS Academy

最近あまり聞かなくなった気がしますが、教育的なコンテストサイトです。
UIが格好いいです。

GCJ

年に一度のGoogleが主催する世界的にも大規模なコンテストです。
2018年はqualは突破できたのですが、Round1A～Cはいずれも通過できませんでした。
2019年はRound2まで行ってみたいですね...

Paiza

これはコンテストとは違う形態ですが、日本語の問題が充実していて、いつでも参加できます。
ただ、ネタバレ禁止の特性上、分からなかったときに復習する手段がないのが難点です。。
水色がSランク相当という情報を得ていたので、Sランクは取りました。

ゴリラジオ体操を始めた

2018年5月頃から、AtCoder Virtual Contest さんをお借りして、ゴリラジオ体操 なる早朝バーチャルコンテストを定期開催しました。
実は4月頃、上述のCodeforcesやCSAといった海外コンに積極的に出ようとした結果、深夜のコンテストが多くて寝不足になり、体調を崩してしまいました。
そんな経緯があって、海外コンに出るのは基本諦め、その代わりに普段の生活の中で無理なく精進できる方法はないだろうかと考えた結果、ラジオ体操形式にして毎朝バーチャルコンテストをやるのはどうかと思いつきました。
実際それがうまいこと普段の生活の中に習慣化できて、2018年年末時点で157回 15、いまだにこの習慣が続けられています。

有り難いことに、一緒に精進してくれるゴリラジ勢がいらっしゃって、毎朝10～20人ぐらいの人たちが参加してくれています 16
めちゃめちゃ朝早い(今は6:25～開始) のに、この人数に参加してもらえるのはビビります。
心理的には、これだけの人たちが参加してくれているから、ここまで続けられたという側面もありますね。
いずれにしても皆さんに感謝です。

ゴリラジ以外にも不定期にバチャを立てたり、他の人が立てたバチャを見つけたらお邪魔しているので、水色時代に軽く200回以上はバチャをしています。

オンサイトのイベントにもできるだけ出た

モチベーションの源です。オンサイトコンテストの機会は何度でも行きたいです。

DDCC2017 決勝

初めてのオンサイトでめちゃめちゃモチベーションを得られました。
詳細レポ→ DDCC2017本戦に参加してきました！！ - 30歳で競プロに目覚めた霊長類のブログ

RUPC2018

立命館大(滋賀県のキャンパス) に3日間、お邪魔しました。
年齢や所属の縛りがなかったので、社会人である私も参加できる貴重な機会でした。
(平日なので社会人は少なかったですが...) ICPC形式なので、3人1組のチームで問題を解きました。
これをきっかけにTwitterで接していた人たちと仲良くなったり色々出会いがありました。

ACPC2018

3日間会津大(福島県) にお邪魔しました。
RUPCと同様、年齢の縛りがないので私でも参加できました。
貴重な機会でとても刺激になりました。
RUPCのときは一人宿だったのですが、ACPCでは8人ぐらいで民泊しました。
また、この時もたくさんの出会い or 再会がありました。
帰りに温泉にも寄れて楽しかったです

Future Meets You Contest (ふみこん)

Future社にて、社会人限定のオンサイトコンテストがありました。
3時間でマラソン形式の問題を解くスタイルでした。
マラソン形式は慣れていないのですが、たまたま方針が良くて、20数名中4位の結果でした。
(賞金が3位からだったので惜しい)
懇親会でも交流させていただきました。
また、帰りにエントランスホールから皆でARCに参加したのもいい思い出です(笑)

競プロer達と交流した

交流の機会はできるだけ大事にしました！
競プロのモチベーションを得られる、人生の充実感を得られる... 等 様々な恩恵がありました

CombNaf, CombGig, CombMof

いずれも高校生が主催していて若い方が多く集まるLTイベントでしたが...
発表内容がどれもすごくて刺激になりました。
参加者がいずれも数十人規模で、二次会まで参加しています
GigとMofでは二次会の幹事をさせていただきました (自然とそんな流れになっていました)

ビアガーデン

企画としては初めての私主導だったので思い出深いです
Twitterで何気なく「ビアガーデン行きたいなー」と呟いたら、行きたい！という声が意外と上がったので決行の運びになりました

競プロキャンプ2018

8月末に、千葉へ競プロer達との交流キャンプに行ってきました。
これも外せない思い出の一つです。
競プロer達と泊ったのはこれが初めてでした。
たくさん交流できて良かったです。
何と2019年は私が幹事をやることになったので、うまく行きますよう、皆さんよろしくお願いします。

和歌山旅行

tatuyanさんが企画してくれました。
駅猫を見に行ったり、浜焼きバーベキューしたり、温泉入りまくったり... 素敵な思い出でした。
旅行の習慣がなかったのですごく新鮮で楽しかった！

...その他、書ききれませんが、勉強会、もくもく会、〇〇会、××会、その他たくさん交流の機会がありました
AtCoderを始める前はこんなに交友関係が広がるとは思いもしなかったので、(競プロのレートとは別の) 思わぬ収穫でした！！
2018年、(2017年も) 仲良くしてくださった皆さんありがとうございます。

ゴリラのぬいぐるみを買った

競プロキャンプ2018の行きにUSB扇風機を買おうと立ち寄ったドンキで出会いました
ゴリたろうと言います
競プロキャンプの後も何かと活躍してくれました。

青になるまでに学習したアルゴリズム、考え方

実は上のほうに挙げた、水色のときに学習したアルゴリズムたちで青色にはほぼ足りています
足りないのはスピードだとある時に認識して、毎朝のゴリラジオ体操で、早解き力を鍛えました。

以下は学んだけど類題を多く解いていないのであまり使いこなせていないかも (><)

  • 二部グラフの判定 →私の記事
  • 包除原理
  • LCA, ダブリング
  • 行列累乗
  • 最大流最小カット(フロー)
  • BIT, セグ木
  • 幾何いろいろ、文字列いろいろ

青色達成時のスナップショット色々

AtCoder Problems

AtCoder Problems

ABC-D, ARC-D(下の円グラフでB) がもうちょいなので埋めきりたかったです...
ARC-E(下の円グラフでC) をもっと解きます

f:id:prd_xxx:20181230225038p:plain
atcoder_problems

AtCoder Scores

AtCoder Scores

こちらも400を埋めきりたかったです...
500,600,700, それ以上... もまだ増やしていきたいです

f:id:prd_xxx:20181230225107p:plain
atcoder_scores

AtCoder Performances

ここ2ヶ月ぐらいは大きな失敗はなく、レートを上げることができました
今後は青パフォ、黄パフォの頻度を上げていきたいです。

AtCoder Performances

最後に

ここまで長々と書いてしまいましたが最後まで読んでいただきありがとうございました。

最後に2つメッセージがあります

灰色、茶色、緑色、水色で行き詰っている方へ

それぞれのステージで、違った大変さがあると思います。
そして私もそれをよく理解しています。
特に私は大学に入って最初の3年間はプログラミングで挫折していて、自分には向かないとさえ思っていました。
でも結局は好き、楽しいという気持ちが勝って、プログラミングを続けることができました。

私はレート上は、AtCoderと出会って4ヶ月で水色になれました。
よく「4ヶ月で水色ってすごいですね～」と言われます。
しかし、上で書いたように、(あるいは書ききれていないけど)、私には長い期間のバックグラウンドがあります。
実際に4ヶ月で水色になれる人は私から見て凄すぎる人です。

成長のペースは人ぞれぞれ違います。
これは持って生まれたものや、様々な置かれた環境が違うので、仕方ないことです。
ただ私は、今置かれた環境の中で手を尽くしたら、どこまで行けるだろう？ というところに興味を持ちました。

どうか、他人の成長速度に惑わされることなく、自分のペースで精進を続けてください。
そして、プログラミングが好きだという気持ちを忘れないでください。

黄色、橙色、赤色、、、を達成された方へ

競技プログラミングを極められていて、とても尊敬・憧れの念を持っています。
そこに至るまでに、現在までの私の数倍、数十倍... の努力を重ねられてきたことも知っています。
私はどこまで追いつけるか分かりませんが、少しでも追いつけるように精進していくので、見守っていてください！

はぁ～～年を越す前に書き終わって良かった、ゴリ～～(><)
皆さん、良いお年を、お過ごしください！！

脚注：

  1. 当ブログ最初の薄っぺらい記事です。長らく(後編)が書かれていませんが、当エントリが(後編)の役目を果たすつもりで書きます↩

  2. 留年した超過分は私が全部負担する約束で、ついこの間全額完済しました↩

  3. ずっと実装だけさせてくれるというわけでは全然ないですけど↩

  4. 当時はエラトステネスのふるいを座圧して定数倍高速化して喜んでいました ↩

  5. これは広義の競プロではあるので、30代になって競プロを始めたと宣言した気がしますが、厳密には嘘です (当時29歳)　まあそんなことは置いといて、当時の順位表を今見ると知っている名前が多くて楽しいですね↩

  6. と思いつつ、ずっと開催されないので首を長くして待っています↩

  7. もともとLL言語をさくーっと書ける人に憧れがあったので独学でPythonを始めていて、毎週のAtCoderでPythonに慣れることを最初は目的の一つと考えていました↩

  8. 初級編といっても、生半可な覚悟では読み切れない難しさですよね。。ちなみに青になった現在、中級編を読了していません。。2019年は全部読むぞ！！↩

  9. 皆さん、何にそんなに惹かれるんでしょう…？？ というのは自意識過剰ですかね。。理由はどうあれ、フォローいただいているのはありがたいことです。↩

  10. 否定的な意見の例… Streakを繋ぐことを目的にしてしまうと精進強度の低いAC(虚無と呼ばれたりします) をすることになり必ずしも役に立たない、AC継続にとらわれてしまい他のことができない、等↩

  11. 実はそうでもなくて最近カツカツしてきたかもしれない↩

  12. 裏話があって、初期のころは訳合ってPython2系で提出していたので、Python2とPython3で分けて集計されていたらこうはなっていませんでした。合算してくれてありがたいです↩

  13. 急にコンテストが生えることもあるので、土日の夜に企画を立てづらいというのはちょっとあります。。「予定されたコンテスト」欄にはできるだけ早めに予定を掲示してほしい… (願望)↩

  14. “Read"forces なんて呼ばれてたりしますね… 私も何度も誤読で時間を溶かしています (ただこれは私の英語力の問題な可能性がある)↩

  15. 土日祝日は好きな時間に起きたいので途中ではずしました。平日に、出社前にやるのを習慣化しました。↩

  16. 最近10名を切るぐらいに減りつつあります。(寒くなったし朝オフトンから出られないのは無理もないです) (というか出てる人すごい)↩