プログラミング初心者の加藤です。勉強会の時に、とりあえずやってみたらいいよと言われたので、よく分からないままやってみました。その概要と雑感です。

AtCoderとは？

まず始めにAtCoderの説明から。AtCoderとは、オンライン上で競技プログラミングのコンテストを提供しているサイトのことです(https://atcoder.jp/?lang=ja)。

定期的にコンテストを主催していたり、企業から(広告や人材獲得戦略の一環として) コンテストが開かれることもあります。コンテストに参加する以外にも、コンテストで使用された問題を解くこともでき、初心者でも、「プログラミング勉強したいけど本をなぞるだけじゃつまらない！」っていう僕みたいなわがままな人にはちょうどいいモチベーションアッパーになると思います。

AtCoder Beginners Selectionを解こう！

チュートリアルを読むと、「何をすれば良いか分からない人は、AtCoder Beginners Selectionから、まずいくつかの問題を解いてみましょう。」と書いてあります。ページに飛んでみると、さらに、「このコンテストは、『AtCoderに登録したけど何をしていいか分からない・・・！』という人に向けて作られた初心者向け問題集です。」とも書いてます。

何も分かってない子羊ちゃんは素直に優しい言葉に付いて行くのでした。 以下いくつかの問題をピックアップしてみます。

問題０：はじめてのあっとこーだー

わざわざ平仮名で表記しちゃってまあどんな接待をしてくれるのやら...。問題文を読みます。

問題文

高橋君はデータの加工が行いたいです。 整数 \(a,b,c\)と、文字列 \(s\) が与えられます。整数 \(a+b+c\) の計算結果と、文字列 \(s\) を並べて表示しなさい。

制約

• \(1\leq a, b, c \leq 1,000\)
• \(1\leq | s | \leq 100\)

入力

入力は次の形式で与えられる。

出力

\(a+b+c\)と\(s\)を空白区切りで1行に出力せよ。

ん？入力ってなんだ？(競プロ初心者並感) いや入力はinputを使えばいい、でも「b c」はどうやって入力するんだ？(Python初心者並感)

そもそも複数行の入力ってどうするんだ？(プログラミング初心者並感)

......(思考停止)

数問解いた後の話ですが、気付きました。 ああこれが競技プログラミングなのか。 あれです、初心者あるあるの「思ってたのと違う」ってやつです。今回のは悪い意味ではないのですが。言語つながりで、例えば英語の問題なら、文法や読解、和文英訳など受験でさんざんやった形式のものが思い浮かびます。てっきりそういう類いの問題が出るのかなと思っていたら、完全に実践形式の問題で驚きました。英語始めたばっかりで、いきなり英会話しようと言われたら誰だってそうなるでしょう。

このように競技プログラミングでは答えが決まってはなく、かなりのバリエーションがあり、独自に考えたプログラムが答えになり得るというのが面白みの一つですね。また、同じ方針でも表記の仕方がたくさんあって、まるで方言のようです。

まとめっぽくなりましたが問題に戻ります。考えても分かる訳なさそうなので、この問題にだけついている解答例を見ます。

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

いまさらですが言語はPython3です。 なるほど、入力が複数行に分かれているのは文字列にエンターが含まれているからなのか、input１回だけで全て読み込めるのではないのだな。行が分かれているというのは本質的ではなく、入力をそのまま表示した結果なのか。いつものインタプリタと同じだ。というのがこの問題で一番印象に残った事です。

map とかフォーマットとか、多分見るのが２ヶ月ぶりとかで、ああそういえばそんなのあったな状態です。

問題４：Coins

コンピューターっぽくて印象的な問題です。よくみる整数問題ですね。これは簡単に解けると思いきや...？こういう問題は受験数学的にはパパッと場合分けが浮かびますが、その条件分けを実装するのは面倒です。そう、受験問題では入力が１つだけですが、競技プログラミングでは複数の入力がなされるため、全ての場合分けに対応しないといけません。できないことはないですが、正直言ってかなり面倒です。

問題文

あなたは、500円玉を\(A\)枚、100円玉を\(B\)枚、50円玉を\(C\)枚持っています。これらの硬貨の中から何枚かを選び、合計金額をちょうど\(X\)円にする方法は何通りありますか。 同じ種類の硬貨同士は区別できません。２通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

制約

• \(0 \leq A, B, C \leq 50\)
• \(A+B+C \geq 1\)
• \(50 \leq X \leq 20,000\)
• \(A,B,C\) は整数である
• \(X\)は50の倍数である

入力

入力は以下の形式で標準入力から与えられる。

出力

硬貨を選ぶ方法の個数を出力せよ。

a, b, c, x = map(int, [input() for i in range(4)])
ans = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if i * 500 + j * 100 + k * 50 == x:
                ans += 1
print(ans)

(http://delta114514.hatenablog.jp/entry/2018/03/15/014555 より引用)

しばらく場合分けを考えていましたが、ギブアップして答えを検索。ABSは有名らしく色んな人が色んな言語で解答をあげています。 このコードはつまるところ、総当たりをして条件を満たすものをカウントしてるんですね。なるほど！ヒトが計算するならこんな面倒なことはしないけれどコンピューターならできる。はっとしました。

問題７：Kagami Mochi

問題文

\(X\)段重ねの鏡餅(\(X\geq 1\)) とは\(X\)枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。 例えば、直径10、8、6センチメートルの餅をこの順に下から積み重ねると3段重ねの鏡餅になり、 餅を一枚だけ置くと1段重ねの鏡餅になります。 ダックスフンドのルンルンは\(N\)枚の円形の餅を持っていて、そのうち\(i\) 枚目の餅の直径は\(d_i\)センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、 最大で何段重ねの鏡餅を作ることができるでしょうか。

制約

• \(1 \leq N \leq 100\)
• \(1 \leq d_i \leq 100\)
• 入力値は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

出力

作ることのできる鏡餅の最大の段数を出力せよ。

普通の解法

n = int(input())
print(len(set(map(int, [input() for i in range(n)]))))

(http://delta114514.hatenablog.jp/entry/2018/03/15/014555 より引用)
入力をリストにしてからセットにして要素数を数える。当然ですね。僕はセットの存在を思い出せなかったので、次のようにしました。

僕の解法

ソートしてからリストのままでなんとか数えあげました。明らかに汚いですね。長いですし、n=1で場合分けしてますし。こんな初心者じみた答えでも合ってたらいいんです。

n = int(input())
a = sorted(list(map(int, [input() for i in range(n)])))
ans = 1
if n != 1:
    for i in range(n-1):
        if a[i] < a[i+1]:
            ans += 1
print(ans)

問題９：Daydream

問題文の通りに、後ろから４単語のどれかを検索していくのが一番わかりやすいと思われます。が、わざわざeraseという単語を選んできたということは、こういうことでしょう。

問題文

英小文字からなる文字列\(S\) が与えられます。 \(T\)が空文字列である状態から始め、 以下の操作を好きな回数繰り返すことで \(S=T\) とすることができるか判定してください。 - \(T\)の末尾にdream dreamer erase eraser のいずれかを追加する。

制約

• \(1\leq |S|\leq 10^5\)
• \(S\)は英小文字からなる。

入力

入力は以下の形式で標準入力から与えられる。

出力

\(S=T\)とすることができる場合'YES'を、そうでない場合'NO'を出力せよ。

僕の解法

s = input()
a = s.replace("eraser"," ")
b = a.replace("erase"," ")
c = b.replace("dreamer"," ")
d = c.replace("dream"," ")

if d.strip() == "":
    print("YES")
else:
    print("NO")

文字列の後ろからだけでなく、途中から抜いても、抜く単語の順番をうまく決めれば問題ないはずです。
変数をいちいち置いているのが恥ずかしいですが、通ればいいんです。

別解答

s = input().replace("eraser","").replace("erase","").replace("dreamer","").replace("dream","")
if s:
    print("NO")
else:
    print("YES")

(http://delta114514.hatenablog.jp/entry/2018/03/15/014555 より引用)
通ればなんでもいいはずなんですが、これはどうでしょう。この解答例だと、'd erase r erase e erase a erase m' という文字列(スペースは抜いてください)もYESになってしまうはずなのですが、試しにこのコードを提出してみるとacceptされました。(嘘解法なんでしょうか？にしては同じような答えを書いてる人が大勢います。)

初学者にとっての競技プログラミング

解いてみた感想ですが、やはり考えるのは楽しいです。久々に数学的な頭の使い方をして懐かしさも覚えました。 また、何より、競技プログラミングは初学者にかなり便利なものだと感じました。ほんとに基礎的な部分しか学習してなくても解けるというのは取り組みやすいですし、結果がだせることは嬉しいです。過去問ならネット上にたくさん解説があるのでつまってもなんとかなります。

他の人のコードを見ることができ、考え方の幅も広がります。上手く書けなかったコードを見直したり、異なった方針で書かれたコードを見るのはいい刺激になります。 特に基礎の文法に慣れるという点では一番だと思います。基礎を洗練させることは必ずこの先モジュールやパッケージを使っていくにしても、理解して扱えることができ役に立つことでしょう。

もちろん万能ではありません。競技プログラミングの内容はプログラミング一般から見て偏っているらしいです。「競技プログラミング　デメリット」で調べると批判がたくさん出てきます。

でも少なくともPython会に入ってる初心者の人は、ソフト開発のような能力ではなく、プログラミングをツールとして扱える能力を求めている人がほとんどでしょうから、うってつけの教材だと思います。

簡単なブロック崩しのゲームを作ったことがありますが、今回の方がよっぽど練習になりました。もし興味があれば皆さんも是非試してみてください。