第14回 paizaの森練習問題コンテストに参加しました

第14回 paizaの森練習問題コンテストが開催されていたので参加してみました。この記事はその感想文です。

開催日時 3/28(木) 20:30 – 21:10
D, C ランクの問題が数問出題されます。

どれくらいできるか試しに参加してみました。

Contents

1 参加した感想
2 どんな問題が出題されたのか？
3 復習してみて思ったこと

参加した感想

スタップが2人くらいいて話している声が聞こえます。まだ鳩は1問もできていないのに「おー、早くも1問正解した方がいらっしゃいますねー」なんて実況が聞こえるとけっこう焦ります。おかげで完全にペースを乱され、あまり良い結果にはなりませんでした。

途中で作戦変更。問題は簡単な順に並べられているのですが、順番にやっていっては間に合わないのでもっとも配点が高い問題からやることに。正解したとき実況の人が「おっとダークホースが現れました」と言ったときはちょっと嬉しかったです。

どんな問題が出題されたのか？

このコーナー内の問題については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。授業や研修にもご利用いただけますので、ぜひ教材などにもお使いください。

ということなので、どんな問題が出題されたのか？鳩はどのようにして問題を解き、そして解けなかったのかを書くことにします。

第1問

回文

回文とは、その文字列の順番を前後逆に並べてできる文字列が元の文字列と同じになるような文字列のことです。
与えられた文字列が回文であるかを判定するプログラムを作成してみましょう。

文字列 s （最長で長さ1000）が与えられるので、s が回文である場合は ‘Yes’、そうでない場合は ‘No’ を出力してください。

例：文字列 s が ‘abcba’ なら’Yes’, ‘abcbc’ なら’No’

文字列の最初の文字と最後の文字、2番めの文字と最後から2番めの文字を比較するのを繰り返す方法でもいいのですが、鳩はこう考えました。

文字列をひっくり返してもとの文字列と比較し、同じであれば回文である。同じでないなら回文ではない。

そして以下のようなコードを提出しました。

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        string s = Console.ReadLine();
        char[] chars1 = s.ToArray();
        char[] chars2 = chars1.Reverse().ToArray();
        string str = new string(chars2);
        if (s == str)
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");

    }
}

using System;

using System.Linq;

class Program

{

static void Main()

{

string s = Console.ReadLine();

char[] chars1 = s.ToArray();

char[] chars2 = chars1.Reverse().ToArray();

string str = new string(chars2);

if (s == str)

Console.WriteLine("Yes");

else

Console.WriteLine("No");

}

第2問

区間の三分割

区間の両端がそれぞれ l と r であるときに、区間を 3 等分したときの、中央 2 つの端点を求めるプログラムを作成してみましょう。

l + (r – l) / 3 と r – (r – l) / 3 を計算して、それぞれ小数で出力してください。相対誤差または絶対誤差が 10^-6 以下であれば正解とみなします。

これは l + (r – l) / 3 と r – (r – l) / 3 を計算するだけです。int型とint型を計算すると割り算であっても計算結果は整数にしかならないので小数にするには少なくとも片方をdouble型にキャストしてから割り算すればOKです。これも簡単な問題でした。

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int l, r;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            l = vs[0];
            r = vs[1];
        }
        double d = ((double)r - l) / 3;
        Console.WriteLine($"{l + d} {l + 2 * d}");
    }
}

using System;

using System.Linq;

class Program

{

static void Main()

{

int l, r;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

l = vs[0];

r = vs[1];

}

double d = ((double)r - l) / 3;

Console.WriteLine($"{l + d} {l + 2 * d}");

}

第3問

割り切れる数の個数

a 以上 b 以下の整数のうち 2,3 のいずれかで割り切れるものは何個あるか求めてください。

入力される値
a b
ただし 1 ≦ a ＜ b ≦ 10000

例：入力が ‘5 10’ であれば ‘4’ を出力する
（5～10で 2,3 のいずれかで割り切れるものは 6, 8, 9, 10 の4つなので）

a と b が巨大な数の場合はちんたらループを回していては間に合わない場合もあるのですが、この場合は最大で10000なので普通にループを回して考えればよい問題です。

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int a, b;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            a = vs[0];
            b = vs[1];
        }
        int ans = 0;
        for (int i = a; i <= b; i++)
        {
            if (i % 2 == 0 || i % 3 == 0)
                ans++;
        }
        Console.WriteLine(ans);
    }
}

using System;

using System.Linq;

class Program

{

static void Main()

{

int a, b;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

a = vs[0];

b = vs[1];

}

int ans = 0;

for (int i = a; i <= b; i++)

{

if (i % 2 == 0 || i % 3 == 0)

ans++;

}

Console.WriteLine(ans);

}

第4問

パイプを切る

残り時間が少なくなっているなか慌ててしまいパスをした問題です。実は簡単な問題でした。

n 本のパイプがあり、長さはそれぞれ A_1, A_2, …, A_n です。今、n 本のパイプから同じ長さ k のパイプを切り出すことを考えます。パイプを切って分割することはできますが、つなげることはできません。切り出すことができる長さ k のパイプの数の最大値を答えてください。

入力される値
n k
A_1 A_2 … A_n

ただし、1 ≦ n, k ≦ 100, 1 ≦ A_i ≦ 10,000 (1 ≦ i ≦ n)

パイプを切る問題といえば二分探索法を使った問題があります。

長さが異なる複数のパイプがあり、そこからK本の同じ長さのパイプを切り出したい。切り出す長さを最大にするにはどうすればよいか？

早とちりをしてこの問題と勘違いしてしまい、残り時間が少なくなっていたことと二分探索法が苦手なのでパス。ところがいまこの問題を読み直してみるとそうじゃないわけですね。二分探索法は関係ない簡単な問題でした。

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int n, k;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            n = vs[0];
            k = vs[1];
        }
        int[] values = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        int ans = 0;
        foreach (int v in values)
            ans += v / k;

        Console.WriteLine(ans);
    }
}

using System;

using System.Linq;

class Program

{

static void Main()

{

int n, k;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

n = vs[0];

k = vs[1];

}

int[] values = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int ans = 0;

foreach (int v in values)

ans += v / k;

Console.WriteLine(ans);

}

第5問

好みのピザ

とあるピザ屋さんでは n 種類のピザのメニューがあります。m 人の客がそれぞれ種類 a_i のピザを注文した時、何種類のピザを作る必要があるかを求めてください。

入力される値
n m
a_1 … a_m

ただし　1 ≦ n, m ≦ 100000, 1 ≦ a_i ≦ n

これは a_1 … a_m の整数が何種類あるかを答えればよい問題ですね。そこで以下のようなコードを提出しました。

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int n, m;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            n = vs[0];
            m = vs[1];
        }
        int[] values = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        int count = values.Distinct().Count();
        Console.WriteLine(count);
    }
}

using System;

using System.Linq;

class Program

{

static void Main()

{

int n, m;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

n = vs[0];

m = vs[1];

}

int[] values = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int count = values.Distinct().Count();

Console.WriteLine(count);

}

Linq拡張メソッドのDistinctを使って重複を排除して、残った要素の個数を出力しているわけです。これで合っているはずなのですがなんと不正解。

最初の2つを除いてランタイムエラー続出で全滅です。

なぜでしょうか？　コンテストのときは見ることができなかったのですが、いまだとどのような入力が与えられたときにエラーが出たのか確認できます。すると・・・

これはランタイムエラーになったときに与えられた入力をダウンロードしてテキストエディタで開いたときのものです。ファイルの最後の部分に半角スペースが入っているのがわかります。これがランタイムエラーの原因です。ランタイムエラーを回避するためには最後にある余分な半角スペースをとればOKです。コードでいえばTrim()を追加すればOKです。

// × int[] values = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
int[] values = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray();

1 2	// × int[] values = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] values = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray();

ただPaizaさん、これって出題ミスだと思うのですがどうでしょうか？

第6問

家計の収支

paiza 君は n ヶ月前から家計簿をつけ始めました。月ごとの収入および支出がそれぞれ a_i 円, b_i 円 (1 ≦ i ≦ n) で与えられる時、家計簿をつけ始めたときの貯金が k 円とすると現在の貯金額がいくらになるかを求めてください。

入力される値
n k
a_1 … a_n
b_1 … b_n

1 ≦ n ≦ 100
-100000 ≦ k ≦ 100000
0 ≦ a_i, b_i ≦ 100000 (1 ≦ i ≦ n)

どうやってでもできます。毎月の収入を足して支出を引くでもいいし、収入は収入でまとめて足し、支出は支出でまとめて引くでも構いません。

この問題もTrim()がないとランタイムエラーになります。これまで解いてきた問題はなくてもエラーはでなかったのにおかしいな。レベルアップ問題集ではなくプログラミングスキルチェックコーナーではランクアップのためのチャレンジは一度しかありません。本番でこういうところでエラーを出してチャンスを逃さないためにもTrim()はつけておいたほうが無難といえます。

以下のコードは毎月の収入を足して支出を引く処理を繰り返しています。

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int n, k;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            n = vs[0];
            k = vs[1];
        }

        int[] As = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray();
        int[] Bs = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray();

        int ans = k;
        for (int i = 0; i < n; i++)
        {
            ans += As[i];
            ans -= Bs[i];
        }
        Console.WriteLine(ans);
    }
}

using System;

using System.Linq;

class Program

{

static void Main()

{

int n, k;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

n = vs[0];

k = vs[1];

}

int[] As = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray();

int[] Bs = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray();

int ans = k;

for (int i = 0; i < n; i++)

{

ans += As[i];

ans -= Bs[i];

}

Console.WriteLine(ans);

}

以下のコードは収入は収入でまとめて足し、支出は支出でまとめて引いています。こちらのほうがコードが短くてすみます。n, k, a_i, b_i の値の制約より途中でint型からオーバーフローする可能性を気にする必要もありません。

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int n, k;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            n = vs[0];
            k = vs[1];
        }
        int income = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).Sum();
        int expenditure = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).Sum();
        Console.WriteLine(k + income - expenditure);
    }
}

using System;

using System.Linq;

class Program

{

static void Main()

{

int n, k;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

n = vs[0];

k = vs[1];

}

int income = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).Sum();

int expenditure = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).Sum();

Console.WriteLine(k + income - expenditure);

}

第7問

野球世界大会 1 次ラウンドの順位

5 チームが総当たり戦をおこない、勝ち数に応じて順位が決定されます。まず 5 チームの参加国名が与えられ、その次に全ての試合結果（勝ち負けのみ）が与えられるとき、上位 2 チームを順位が上から順に求めてください。ただし、勝率が同じチーム同士の場合は国名が辞書順で小さい方のチームを上の順位にします。

入力される値
c_1
…
c_5
s_1
…
s_10

c_i はアルファベットの大文字小文字のみからなる文字列 (1 ≦ i ≦ 5)
s_i “A-B 1″と入力された場合は A 国が B 国に勝利したことを示しており、 “C-D 0″と入力された場合は C 国が D 国に敗北したことを示します。組み合わせに重複はないものとします。例えば、”A-B 1”, “B-A 0″のような入力が共に含まれることはありません。

c_i が重複することは絶対にないことが保証されているので辞書を使いました。c_iをKeyにして勝数をValueにします。最後にValueが大きい順にソートし、「勝率が同じチーム同士の場合は国名が辞書順で小さい方のチームを上の順位」なのでさらにKeyが小さい順にソートします。そして最初の要素と2番めの要素を出力します。

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

class Program
{
    static void Main()
    {
        Dictionary<string, int> dic = new Dictionary<string, int>();
        for (int i = 0; i < 5; i++)
            dic.Add(Console.ReadLine(), 0);

        for (int i = 0; i < 10; i++)
        {
            string[] strings = Console.ReadLine().Split();
            bool isLeftWin = int.Parse(strings[1]) == 1;
            string[] teams = strings[0].Split('-');
            if (isLeftWin)
                dic[teams[0]]++;
            else
                dic[teams[1]]++;
        }
        List<string> rets = dic.OrderByDescending(_ => _.Value).ThenBy(_ => _.Key).Select(_ => _.Key).ToList();
        Console.WriteLine(rets[0]);
        Console.WriteLine(rets[1]);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

Dictionary<string, int> dic = new Dictionary<string, int>();

for (int i = 0; i < 5; i++)

dic.Add(Console.ReadLine(), 0);

for (int i = 0; i < 10; i++)

{

string[] strings = Console.ReadLine().Split();

bool isLeftWin = int.Parse(strings[1]) == 1;

string[] teams = strings[0].Split('-');

if (isLeftWin)

dic[teams[0]]++;

else

dic[teams[1]]++;

}

List<string> rets = dic.OrderByDescending(_ => _.Value).ThenBy(_ => _.Key).Select(_ => _.Key).ToList();

Console.WriteLine(rets[0]);

Console.WriteLine(rets[1]);

}

復習してみて思ったこと

タイピングが遅いのか全部解くのに40分ちょっとかかりました。コンテストで全問正解するにはタイピングの練習も必要みたいです。

第14回 paizaの森練習問題コンテストに参加しました

参加した感想

どんな問題が出題されたのか？

第1問

第2問

第3問

第4問

第5問

第6問

第7問

復習してみて思ったこと

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ