Share
Download the
Global Threat
Intelligence Report
第 19日目は、SOC インフラエンジニア 竜田力の記事です。競技プログラミングの参加について紹介します。
--
SOCインフラエンジニアの竜田です。社内の競技プログラミングに参加するにあたって、その準備としてやってみたことと、競プロが実務にどう役立ったかついてお話します。
競技プログラミングとは
与えられた問題を解くプログラムを早く記述する競技です。簡単な数学のような問題からアルゴリズムを組み合わせないと解けないような問題まで、幅広い難易度の問題があります。私は最近になって競技プログラミングを始めたのですが、AtCoderのような常駐型のサービスや勉強の仕方をまとめた記事・書籍が豊富で、初心者にとっても楽しめる環境が整っているなと感じています。
社内コンテストに向けてやってみた
練習として、NTT データ数理システムの drken さんの記事である、「AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～」で紹介されている精選過去問10問をPythonでいくつか解いてみましたが、雰囲気をお伝えするために、1問だけ紹介させていただきます。
- 問題文
日本でよく使われる紙幣は、10000円札、5000円札、1000円札です。以下、「お札」とはこれらのみを指します。青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札がN枚入っていて、合計でY円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。
- 制約
- 1≤N≤2000
- 1000≤Y≤2×10<sup>7</sup>
- N は整数である。
- Y は 1000 の倍数である。
- 入力
入力は以下の形式で標準入力から与えられる。
N Y
出力
N枚のお札の合計金額がY円となることがありえない場合は、-1 -1 -1 と出力せよ。N枚のお札の合計金額Y円となることがありうる場合は、そのようなN枚のお札の組み合わせの一例を「10000円札x枚、5000円y枚、1000円札z枚」として、x、y、zを空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。
- コード
N, Y = map(int,input().split())
for x in range(N+1):
for y in range(N-x+1):
if 10000*x + 5000*y + 1000*(N-x-y) == Y:
print(x,y,N-x-y)
exit()
print(-1,-1,-1)- 考え方
別の問題であるABC 087B Coinsの問題と類似性があり、そこから発想していきましたが、制約が厳しくなっています。 3重ループを使うような実装では2000の3乗の計算量が必要となってしまうため、TLEとなってしまいます。 計算量についてのノウハウもしっかり理解しておくことが必要なのだなと思わされた問題でした。下記の記事が非常にわかりやすかったです。
計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜
頭を巡らせ、xとyの値が決めればY円の条件を満たすためのzが一意に決まるため、2重ループで実装できることに気づき、そこからは一気に解くことができました。
この他にも練習として難問も解いているのですが問題ごとに特色があり、そのたびに発見があり、非常に楽しんで取り組めました。
競技プログラミングをやってみて良かったこと
私は競技プログラミングを通じて、実務においても非常に良い効果があるなと感じました。特に「コードを理解する速度が向上した」ことが良かったなと感じています。
競技プログラミングをしていると、他の方々が書かれたコードを沢山読みます。同じ問題でも多種多様な書き方・解き方があり、私の実力不足で理解できないコードも多くあります。そのようなわからないコードに対して「自力で調べて理解し使えるようにする」を繰り返すことで自然とコードを理解する速度を向上させることができたのかなと思います。
インフラチームでは社内の自働化開発に注力しておりコードを書く機会はたくさんありますが、私の業務において頻度は多くないですが特に難しいと感じていた「前任者が書いたコードのバグを調査・修正する」といった対応において、見慣れないコードであっても問題箇所を早く切り分け、迅速に対応できるようになったと感じます。
最近では、新しく知ったコードの書き方などを周りに共有し、これはどこかで使えそうだなーみたいな雑談を楽しんでいます。今後、もっともっと競プロの楽しさを広めていければなと思っています。