（競プロ）abc023のC問題を題材に勉強の仕方メモ

背景

Androidエンジニアになると言いましたが、実は状況的にアルゴリズムの実装力が必要です（転職と研究）。何度かチャレンジしては勉強の仕方がわからん…となっていた競プロをちょくちょくやろうと思います。特に最初の一歩って「AtCoder使おう」「問題集解こう」という記事が多くて、私のような弱いエンジニアはAtCoderは使えないし問題集は解けないしで幅が広がりません。そういう初心者（？）さんの取り組み方の助けになれば。

そもそもの勉強方針

方針としては

過去問に触れて典型パターンを知る
勉強は基本C,D問題（AtCoder Problems）を解く
だいたい解けないので「手法の理解」と「コードの理解」にわけて勉強し、1周目は理解、2周目以降で自力で解けることを目指す
あと細かい手法や基本的な考えの補完にleetcodeも使うかも

みたいな感じを想定しています。

abc023のC問題概要

収集王です。公式解説にあるように、この問題は典型的考え方（二分探索とかハッシュテーブルとか）というより、パズルみたいに問題を解けるか系の問題に見えます。こういう問題は「解説に近そうな他人のコードを持ってくる」「デバッガを使ってあるinputのときの変数を追いかける、特にテーブル作る系は手元に図を書く」という方法で読むと読めるかもしれません。

ときます

# for test
R, C, K = 3, 5, 3
N = 5
ameInfo = [[1, 2], [2, 1], [2, 5], [3, 2], [3, 5]]

# 行列と飴の個数
# R, C, K = map(int, input().split())  # 空行くぎりのstringで渡ってくる
# N = int(input())  # 飴情報の個数
# ameInfo = [list(map(int, input().split()))
#            for i in range(N)]  # N行分空行くぎりのstringがくる

# 飴マップを作る
row = [0]*R
column = [0]*C

for x, y in ameInfo:  # 飴座標1つずつについて、飴マップに情報を入れる。マスはインデックス+1なので-1に入れる
    row[x-1] += 1
    column[y-1] += 1


answer = 0


# カウント
# ここだけわからない
rowx = [0] * (K+1)  # Kはターゲットの飴の数 [0,0,0,0]みたいなのができる
columnx = [0] * (K+1)

for rowi in row:
    if rowi <= K:
        rowx[rowi] += 1  # K個以下獲得する場合、飴の個数インデックスのところに＋１。0もある
for columni in column:
    if columni <= K:
        columnx[columni] += 1
for i in range(K+1):
    answer += rowx[i] * columnx[K-i]#K個飴を取得組合せ。i=1でK=3ならrowから1個、columnから2個とれる場合…をかけている

# 余剰分をのぞく
for x, y in ameInfo:
    if row[x-1]+column[y-1] == K:
        answer -= 1
    elif row[x-1]+column[y-1] == K+1:
        answer += 1


print(answer)

C問題は解説読んで分かった気になったものの、コードにするの難しいよーと思ったので読めるコードを探しました。こんな感じで読めるコードをみつけたらVSCodeあたりで動かします。test用に一番シンプルなインプットを下手書きしちゃうといいと思います。競プロのコードは変数名とコメントの問題で可読性が低いので、ゴリゴリコメントをつけました。

今回のコードだと# カウントのコメントのあとくらいのロジックがわからなかったので、デバッグして追った結果が#にあるコメントです。配列の中がどうなっているのか、何をカウントしているのかをループごとに追います。手元に変数ごとの状態のメモを書きつつ追っています。

このあとどうするか

この手の問題は類題を解くというより発想の問題な気がするので、時間を置いた時に自力でコードがかけるかを試したいです。というわけで、1週間後のカレンダーに問題番号をメモして再チャレンジします。

今後の勉強

Androidなどの自分が手を出したい勉強の他に、ちょっとした仕事前の導入くらいな気持ちで取り組めるようにまずは心理ハードルを下げます。仕事前にC問題くらいの難易度を１問解いていこうかと思います。え？コンテスト？~~弱いし今参加したら心折れちゃうのであくまでも頭の体操として過去問を解くんです~~

ぴよまるの雑多な技術所

間違えて休職中ってずっと書いていて心配されていました。全部ちょっとずつ齧って好きって思える技術を見つけたい。研究分野は数理最適化。