初めて競技プログラミングのコンテストに出た


以前から競技プログラミングには興味があったのですが, 私は絶望的に数学が苦手(私立文系大卒)で, 醜態を晒すのが怖くて参加せずにいましたが,
昨日は AtCoder社 の 初心者向けコンテスト『第29回 AtCoder Beginner Contest』があったので, 勇気を出して参加しました!
この記事中に, 実際に提出した私の書いたコードも載せています. (C#)


↑ コンテスト開始時刻1分前のツイート

目次

  1. コンテスト概要
  2. 私の成績
  3. 出題された問題について
    1. A問題
    2. B問題
    3. C問題
    4. D問題

コンテスト概要

初心者向けコンテストです.
タスク(「こういう入力されたらこういう出力するプログラム書いて」)が 4つ 出題されて,
それらを『どれだけ早く』『いくつ』『正解した(=正しい挙動をするプログラムを提出した)か』で, 順位が決まるようです.

項目
コンテスト名 AtCoder Beginner Contest 029
開催日時 2015/09/19 21:00 ~ 2015/09/19 23:00
URL abc029.contest.atcoder.jp
参加登録者 550人
1問でも解いた人 469人
問題数 全4問 (A問題 〜 D問題. Aが簡単でDが難しい)

私の成績

項目
使用言語 全問 C#
獲得点数 320 / 400 (点)
順位 193 / 469 位

楽しかったです

出題された問題について

私の成績:

問題 問題名 状況 点数
A問題 『複数形』 Accepted 100
B問題 『カキ』 Accepted 100
C問題 『Brute-force Attack』 Accepted 100
D問題 『1』 TimeLimitExceeded 20

D問題だけ部分点がありました.

↓ コンテスト終了時刻7分前のツイート. どうしても最後の問題だけが解けなかったのでつらまってる.

A問題

私のような初心者にやさしい, サービス問題でした.
本当にあまりに簡単だったのでコード載せるのは省略します.

B問題

項目
タイトル 『B – カキ』
問題概要 特定の文字の出現数をカウント
問題ページURL abc029.contest.atcoder.jp/tasks/abc029_b

入力文字列が全部で 12 個 ってのを見落としていて, ちょっと時間かかってしまいました.

問題文
英小文字からなる 12 個の文字列 S1, S2, …, S12 が入力されます。
これらの文字列のうち、文字 r が含まれるものの個数を数えてください。

入力例

january
february
march
april
may
june
july
august
september
october
november
december

出力例

8

書いたコード (C#) :

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
 
namespace ChomadoAtCoder
{
	class Chomado
	{
		public Chomado() {}
		public static int Main()
		{
			new Chomado().Calc ();
			return 0;
		}
 
		void Calc()
		{
			var inputs = InputValues;
			var count = inputs
				.Where (i => i.Contains ('r'))
				.Count ();
			Console.WriteLine (count);
		}
 
		// 入力された文字列を List<string> にして返す
		List<string> InputValues
		{
			get 
			{ 
				var inputs = new List<string> ();

				// 入力が終わるまで全行読み込む
				while (true)
				{
					string input = Console.ReadLine ();
					if (input == null)
						break;
					else
						inputs.Add (input);
				};
				return inputs;
			}
		}
	}
} 

やはり C# は LINQ が 強いですね!
コードの, 入力値(String型のListになってる)の中に ‘r’ が含まれている回数を返す処理で

var count = inputs
	.Where (i => i.Contains ('r'))
	.Count ();

こうやって書けるのはすごく気持ち良い!!!

C問題

項目
タイトル 『C – Brute-force Attack』
問題概要 組み合わせ全列挙
問題ページURL abc029.contest.atcoder.jp/tasks/abc029_c

組み合わせ全列挙に再帰関数を書きました. なんとか通した.

この問題は Haskell でやればよかったと思いました.

問題文

あなたはスーパーハッカーです。高橋君を攻撃対象に定めたあなたは、
高橋君のパソコンのパスワードに関して次の事実を突き止めました。

長さは N 文字である。
a, b, c 以外の文字は含まれない。
高橋君のパソコンのパスワードの候補として考えられる文字列をすべて列挙してしまいましょう。

入力例

2

出力例

aa
ab
ac
ba
bb
bc
ca
cb
cc

書いたコード (C#) :

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace ChomadoAtCoder
{
	class Chomado
	{
		public Chomado() {}

		public static int Main()
		{
			new Chomado ().Calc ();
			return 0;
		}

		void Calc()
		{
			var MAX_LENGTH = int.Parse (Console.ReadLine ());
			Dive ("", MAX_LENGTH);
		}

		// 再帰関数
		void Dive(string prefix, int level)
		{
			if (level == 0)
			{
				// 指定の文字数に達したので出力
				Console.WriteLine (prefix);
			}
			else
			{
				foreach (var c in new char [3] { 'a', 'b', 'c' })
				{
					// 再帰呼び出し
					Dive (prefix + c, level - 1); 
				}
			}
		}
	}
} 

というのを出しました!

ちなみに Haskell だと, こんなに簡単にきれいに書けるようです!

↓ @fumieval さんの書いた Haskell のコード

import Data.Monoid
import Control.Monad
 
main = do
  n <- readLn
  putStr $ unlines $ replicateM n "abc"

abc029.contest.atcoder.jp/submissions/497509

D問題

項目
タイトル 『D – 1』
問題概要 桁DP
問題ページURL abc029.contest.atcoder.jp/tasks/abc029_d

難しかった… Accepted 貰えなかった…

問題文

高橋君は 1 以上 N 以下のすべての整数を十進表記で一回ずつ紙に書きました。
この作業で、高橋君は 1 という数字を何個書いたでしょうか。

入力例

12

出力例

5

1, 10, 11, 12 の十進表記に合計で 5 個の 1 という数字が含まれます。

書いたコード (C#):

注意 これは部分点(20点)だけ貰えたコードです. アルゴリズムが良くないです.

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
 
namespace ChomadoAtCoder
{
	class Chomado
	{
		public Chomado() {}
 
		public static int Main()
		{
			new Chomado ().Calc ();
			return 0;
		}

		void Calc()
		{
			var MAX = int.Parse (Console.ReadLine ());
 
			var all_list = new List<string> ();
 
			for (var i = 1; i <= MAX; i++)
			{
				all_list.Add (i.ToString());
			}
			int point = 0;
 
			foreach (var value in all_list)
			{
				foreach (var c in value)
				{
					if (c == '1')
						point++;
				}
			}
			Console.WriteLine (point);
		}
	}
}

ツイート