AtCoder Contest 初参戦記録
いつもLeetCodeを解いている私ですが、どうやらAtCoderという競技プログラミングサイトでの"色"がプログラマーとしてのスキルの一端を表すものであるらしいと聞き、せっかくなので参戦してみることにしました。
参戦前準備
参戦前準備というのは会員登録だとかのことを言っているだけではなく、（私にとっては）LeetCodeとの仕様の違いに慣れるところから始める必要がありました。
LeetCodeで操作できるのは、以下画面のように「関数を定義する欄」と「関数への入力値を決定する欄」の2つです。
我々がやるべきこととしては、返り値を返す関数を定義するだけでOKです。
一方でAtCoderでは、標準入力を読み取って処理にかけ、回答は標準出力で返す、というコードを書く必要があります。
この違いに慣れるのになかなか時間がかかりました。
とはいえ、5~10分くらい手間取ったくらいなので、最終スコアには影響はなかったと思います。
慣れのBiasも入っているかもしれませんが、私はLeetCode方式の方が好きではあります。
ちなみに、success/failの判定対象が「関数の返り値が正解かどうか」「処理が時間・空間計算量の制限内に完了したかどうか」なのは共通です。
コンテスト内容
参戦したコンテストはAtCoder Beginner Contest 137というものでした。
これはABCなどと称され、AtCoderのBeginner向けに、毎週土or日曜日の21時から開催されているものだそうです。
コンテスト時間になると問題が開示され、制限時間内（今回は1時間40分）に正しいコードをsubmitできればスコアを獲得できます。
submitしたコードが誤った値を返すものであったり、処理時間が制限を超えたりするとfailとなり、1度のfailにつき持ち時間5分削減のペナルティが与えられます。
問題数は6問。簡単なものから難しいものまでA-Fの問題があり、獲得できるスコアにも差があります。
問題の傾向は、まだコンテストに1度しか参加していないので私の感想はあまり参考にならないと思いますが、
A, B : プログラミングの勉強がきちんと身についているかチェックする問題
C, D : プログラマーとして独り立ちしてやっていきたいなら解答必須な問題
という感覚でしょうか。
個人的には、Dまで確実に解けるレベルを目指したいところです。
本記事では、私が制限時間内に解けたCと解けなかったDの問題の2つを、問題例として紹介します。
問題内容・解法
C - Green Bin
アナグラム（文字の入れ替えを行うと合致する文字列）になっている文字列の組み合わせ数を計算する問題です。
アナグラムかどうかを判定できるように、文字列は
s = ''.join(sorted(input()))
として各文字を要素に持つsortされたリストsに変換します。
次に、sを格納する辞書dを用意します。
アナグラムになっている文字列の群は、辞書dにおける1つのkeyとして扱うこととします。
loopを回し、アナグラムになっている文字列群の中の文字列の数を辞書のvalueとします。
一方で、最終的に解答したいアナグラムの組み合わせの数を変数ansで計算します。
例えば文字列A, B, Cが互いにアナグラムになっていたら、組み合わせの数は3となります。
そこで、dのkeyにアナグラムになっている文字列が既に存在したら、そのvalueをansに足します。
例を挙げると、s = ['a','b','c'], d[s] = 2のときに文字列'cba'が現れたら、ansに+2してやるということですね。
n = int(input()) ans = 0 d = {} for i in range(n): s = ''.join(sorted(input())) if s not in d.keys(): d[s] = 1 else: ans += d[s] d[s] += 1 print(ans)
D - Summer Vacation
M日後に得られる報酬を最大化する問題で、A日後に報酬Bを得られるアルバイトN件から適切なものを選ぶ必要があります。
解説pdfによれば、
この問題は後ろ (M 日後から 1 日前) から見ていくと、まず Aj ≤ 1 となる j の中で Bj が最大のもの(j1 とする) を選び、次に Aj ≤ 2 かつ j ̸= j1 となる j の中で Bj が最大の> ものを選び、…としていくのが最適です。
とのこと。
私は解けなかったので、以下に今回のコンテスト順位1位のconvexineqさんの解法を示します。
コードの意味についてはコード中のコメントを参照いただければと思いますが、heapというデータ型を利用している点だけ補足します。
heapとは、Wikipediaによれば
「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ木構造
のことを指します。
常に最初の要素が最小値となるようなリストが必要な場合、heap構造を用いることで最小値（最大値）の取り出しをO(1)、要素の追加をO(log n)の時間計算量で行うことができるのがheapの利点です。
import sys sys.setrecursionlimit(10**6) readline = sys.stdin.readline from heapq import * n,m = [int(i) for i in readline().split()] ab = [[int(i) for i in readline().split()] for _ in range(n)] ab.sort(reverse = True) # 報酬をもらえるまでの日数の降順に並べ替えておく（例：[[2, 3], [2, 1], [1, 4], [1, 3], [1, 2]]） q = [] ans = 0 # 報酬の合計値 for i in range(m-1,-1,-1): # m-1日後から順に行うべきアルバイトを決めていく（未来から現在に遡っていく） while ab and ab[-1][0] + i <= m: # ab[-1][0]は報酬をもらえるまでの日数。ab[-1][0]+iがmを超えてしまうと報酬をもらうのが間に合わない (a,b) = ab.pop() heappush(q,-b) # -bが小さい=bが大きい、つまり報酬が大きいということ。heapは最小値を取得するのに適しているため、マイナスにして取り出している if q: ans -= heappop(q) # qの最小値を取得。マイナスを掛け直してプラスの値として報酬に加算 print(ans)
heapについては、同じ優先度付きキューの仲間として、LeetCodeでも何度か出てきたstack, queueとの比較で解説されている分かりやすい記事を見つけたので、貼っておきます。
いつ何時どれを使えば良いのか、1度整理したいところ…
評価
AtCoderではコンテストの戦績によってratingが付き、プログラマーとしてのスキルの証明である"色"が付与されます。
"色"と実務におけるスキルレベルの関係は、AtCoder社長の高橋さんが以下のように説明してくれています。
ちなみに私のratingは以下の通り。
参加回数が少ないとratingは非常に低く計算される傾向があるようなので、今の時点ではうわっ低。。。としか言えません。
ratingとは別に、「パフォーマンス」という各コンテスト単体で見たときの評価があります。
これは、「このレベルのパフォーマンスを続けていればこのくらいのratingになるよ」という指標と考えれば良いようです。
私のパフォーマンスは745だったので、色で言うと"緑"には及ばない"茶"相当になるようです。
私はプログラマーとして生きていきたいわけではないですが、経営者としてでも一定のスキルがないと説得力がないので、"緑"までは到達することを目指したいと思います。
