文章と機械学習の自学ノート

プログラミングとか機械学習とか推しとか百合とかの話をする．

AtCoder体験記01～登録と過去問～

プログラミング

概要

AtCoderに登録して過去問をいくつか解いた．

本文

プログラミング能力を磨いて，あわよくばポートフォリオとして提出したいという気持ちをモチベーションに，AtCoderを始めることにした．
正直なところ，ここ2，3年はtensorflowのコードと睨めっこしてばかりだったので，一般的なプログラミング能力はガタ落ちしている気がする．

AtCoder とは

AtCoderは、オンラインで参加できるプログラミングコンテスト(競技プログラミング)のサイトです。リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問にいつでも挑戦することが出来ます。

引用：https://atcoder.jp/home

引用文でだいたいのことは分かる．
こちらがすることは，出題された要件を満たすプログラムを書いて，提出するだけ．
ジャッジの結果，正答なら嬉しい，誤答なら悔しい．という感じ．

レーティング制度が用意されていて，週末の午後9時から行われるコンテストに参加することで上がったり下がったりする．
つまり，この数値がプログラミングスキルの評価指標の一つになる．
また，レーティングとは別にパフォーマンスというものがあり，これはコンテスト毎にどれくらいできたかを示す指標のようだ．

コンテストにはいくつか種類があるらしいが，初心者は基本的にAtCoder Beginner Contest(ABC)に参加していくことになる．
A問題からF問題まで計6問あり，アルファベットが大きいほど難易度が高く，正答した時の点数も高い．
制限時間は100分，正答数が多い→正答が早いという順番で評価され順位がつく．
レーティングやルールの詳細を詳しく知りたい場合は以下の記事が参考になる．

qiita.com

chokudai.hatenablog.com

www.pc-gear.com

とりあえずやってみよう

AtCoderのサイトにアクセスして，アカウントを作成．
コンテスト内にpractice contestがあるので，「参加登録」を押すと問題にアクセスできるようになる．
このコンテストはレーティングに影響せず，制限時間もない．
まずは問題タブから，「A - Welcome to AtCoder」をクリック．
問題ページには，実行制限時間，メモリ制限，問題文，制約，入力と出力の形式，複数の入出力例，注意や補足などが表示される．
このA問題では各言語での解答例も載っている．Python3だとこんな感じ．

# -*- coding: utf-8 -*- 
# 整数の入力 
a = int(input()) 
# スペース区切りの整数の入力 
b, c = map(int, input().split()) 
# 文字列の入力 
s = input() 
# 出力 
print("{} {}".format(a+b+c, s))

解答する場合はソースコードを記述するか，ファイルを開いて「提出」ボタンを押せばよい．
提出すると提出結果タブへと遷移する．
ジャッジのステータスがAC（正答）であれば，得点を得ることができる．
その他のステータスとして，WA（誤答）やTLE（実行制限時間超過），WJ（ジャッジ待機中）などもある．
また，実行時間やメモリなど，その他の情報も確認できる．

より詳細な情報は，各コンテストページのフッターにあるルールや用語集で確認が可能．

初心者向けの問題を解く

practice contestのA問題*1で流れは理解した．
次はAtCoder Beginners Selectionに挑戦するといいらしい．

このコンテストは、「AtCoderに登録したけど何をしていいか分からない・・・！」という人に向けて作られた、初心者向け問題集です。

引用：https://atcoder.jp/contests/abs

ということでやってみる．

A問題

「ABC086A - Product」
問題：
二つの正整数a, bの積の偶奇判定（1≦a, b<≦10000）
解答：

a, b = map(int, input().split())
 
if a % 2 == 0 or b % 2 == 0:
  print("Even")
else:
  print("Odd")

mod 2が0かどうかで判定すればよい．
1との論理積でも判定が可能．

「ABC081A - Placing Marbles」
問題：
3つの数s1s2s3の内，1の数を出力する．（s1, s2, s3は'0' or '1'）
解答：

a = int(input())
 
c = 0
for _ in range(3):
  c += a % 10
  a //= 10
  
print(c)

mod 10の結果が1ならカウント，10で切り捨て除算して桁を減らす．
上を3回繰り返す．

B問題

「ABC081B - Shift only」
問題：
N個の正整数A1, …, Anを2で割る操作を繰り返す．A1, …, Anのうち，どれか1つでも2で割り切れ無くなった時の操作回数を出力する．
解答：

N = int(input())
A = list(map(int, input().split()))
 
is_all_e = True
count = -1
 
while is_all_e:
  count += 1
  for i, ai in enumerate(A):
    if ai % 2 == 1:
      is_all_e = False
      break
    A[i] = ai / 2
  
print(count)

mod 2で偶奇判定．
2で除算して値を更新．
どれか一つでも奇数なら終了してループ回数を出力．

「ABC087B - Coins」
問題：
A, B, C, Xが与えられたときに500×a+100×b+50×c=Xになるa, b, cの組み合わせが何通りあるかを出力する．
ただし0≦a≦A, 0≦b≦B, 0≦c≦C．
解答：

import itertools
 
A = int(input())
B = int(input())
C = int(input())
X = int(input())
 
count = 0
for a, b, c in itertools.product(range(A+1), range(B+1), range(C+1)):
  if 500*a + 100*b + 50*c == X:
    count += 1
    
print(count)

itertools.product()で総当たりして条件式に当てはまるものをカウント．
競プロではACこそ正義なので，必ずしも数学的に解く必要はない．
とはいえ，C問題以上となるとただの全探索では通用しなくなるそうだ．

「ABC083B - Some Sums」
問題：

1以上N以下の整数のうち、10進法での各桁の和がA以上B以下であるものの総和を求めてください。

解答：

N, A, B = map(int, input().split())
count = 0
 
for n in range(N+1):
  t = n
  d = 0
  while t != 0:
    d += t % 10
    t //= 10
  if A <= d <= B:
    count += n
    
print(count)

0～Nまで，以下を繰り返す．
　ループ回数をtに代入
　tが0になるまで以下を繰り返す．
　　t mod 10の結果をdに足し合わせて更新．
　　tを10で切り捨て除算して桁を減らす．
　dがA以上B以下ならnを足し合わせて更新．

やってみての所感

とりあえず5問やってみたが，確かに初心者向けのちょうどいい問題だったように思う．
入出力，条件分岐，反復処理，数値計算，それらの基本が分かっていれば解ける問題だ．

お腹がすいたので，残りの5問（B2問，C3問）は次の機会にする．

さいごに

今週末(7月18, 19日)はコンテストが無い．理由は以下の通り．

ICFP Programming Contest 2020が開催されます。72時間で超難問を解く、チーム戦のプログラミングコンテストです。

引用：https://atcoder.jp/posts/504

次に開催されるコンテストは，7月25日の「M-SOLUTIONS プロコンオープン 2020」で，コンテスト名にもあるM-SOLUTIONS株式会社が主催するようだ．
問題の点数はまだ（7月19日8時時点）公表されていないが，コンテスト時間100分，レーティング更新対象が～1999なところはABCと一緒なので，同程度の問題だろうか．
せっかくなので挑戦する予定．
atcoder.jp


長々と書いたが，あくまで初心者の体験記なので，間違っているところもあると思う（特にプログラムとか……）．
真剣に勉強したい人は，必要な項目が全部まとまっててしかも分かりやすい，以下の記事を読んだ方が良いだろう．
qiita.com

*1:問題ページにも書いてあるが，B問題は初心者向けではない