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

第17回 paizaの森練習問題コンテストに参加しました。これはその問題です。

「ユーザー同士で解答を教え合ったり、コードを公開して構わない」ということなので、鳩がどう考えてどんなコードを書いたのかを公開します。

Contents

1 最大値と最小値 (paizaランク D 相当)
2 神経衰弱 (paizaランク D 相当)
3 じゃんけん (忖度) (paizaランク C 相当)
4 n→10 進法 (paizaランク C 相当)
5 お菓子の価格帯 (paizaランク B 相当)
6 ぴったり卵を生産 – その 2 (paizaランク S 相当)

最大値と最小値 (paizaランク D 相当)

3つの整数の中で一番大きな値と一番小さな値を出力してください。

入力されるデータ
a
b
c
（ただし -100 ≦ a, b, c ≦ 100）

3つの値をリストに格納してMaxメソッドとMinメソッドで最大値と最小値を取得して出力するだけです。

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

class Program
{
    static void Main()
    {
        List<int> list = new List<int>();
        for (int i = 0; i < 3; i++)
            list.Add(int.Parse(Console.ReadLine()));

        Console.WriteLine(list.Max());
        Console.WriteLine(list.Min());
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

List<int> list = new List<int>();

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

list.Add(int.Parse(Console.ReadLine()));

Console.WriteLine(list.Max());

Console.WriteLine(list.Min());

}

神経衰弱 (paizaランク D 相当)

神経衰弱というトランプのゲームをします。
トランプのカードが4枚与えられるので、同じ値のカード2枚を順番に取り除いていったときに、カードをすべて取り除くことができるかどうか判定してください。

入力されるデータ
a b c d
（ただし a, b, c, d は4枚のカードの値。1 ≦ a, b, c, d ≦ 13）

4枚のカードをすべて取り除くことができる条件は4枚のカードがすべて同じ数か、同じカードが2枚ずつ存在する場合だけです。そこで入力された数を辞書に格納して、すべて同じか、同じ数が2つずつあるかどうかを調べることにします。

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

class Program
{
    static void Main()
    {
        int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

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

        foreach (int v in vs)
        {
            // dic[v] をインクリメントするがキーが存在しないかもしれないのでその場合は追加する
            if(!dic.ContainsKey(v))
                dic.Add(v, 0);
            dic[v]++;
        }

        // キーがひとつだけ、またはキーがふたつで値が2であれば "Yes"
        if(dic.Count == 1 || (dic.Count == 2 && dic.First().Value == 2))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

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

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

foreach (int v in vs)

{

// dic[v] をインクリメントするがキーが存在しないかもしれないのでその場合は追加する

if(!dic.ContainsKey(v))

dic.Add(v, 0);

dic[v]++;

}

// キーがひとつだけ、またはキーがふたつで値が2であれば "Yes"

if(dic.Count == 1 || (dic.Count == 2 && dic.First().Value == 2))

Console.WriteLine("Yes");

else

Console.WriteLine("No");

}

じゃんけん (忖度) (paizaランク C 相当)

あなたは子供に優しく他に厳しいじゃんけんプログラムを作ろうとしています。

じゃんけんをする相手の年齢と相手が出す手が与えられるので、相手が 10 歳未満の場合は相手に負ける手を、10 歳以上の場合は相手に勝つ手を求めてください。
ただし、プログラム上ではグー (Rock) を R、パー (Paper) を P、チョキ (Scissors) を S で表すことにします。

入力されるデータ
y h
ただし、y は相手の年齢 1 ≦ y ≦ 100
h は相手が出す手。 h は R, P, S のいずれか

y が 10未満かどうかで相手に負ける手または勝つ手を出せばOK。

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

class Program
{
    static void Main()
    {
        string[] vs = Console.ReadLine().Split();
        int y = int.Parse(vs[0]);
        string h = vs[1];

        string ans = "";
        if (h == "R")
            ans = y < 10 ? "S" : "P";
        if (h == "S")
            ans = y < 10 ? "P" : "R";
        if (h == "P")
            ans = y < 10 ? "R" : "S";

        Console.WriteLine(ans);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

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

int y = int.Parse(vs[0]);

string h = vs[1];

string ans = "";

if (h == "R")

ans = y < 10 ? "S" : "P";

if (h == "S")

ans = y < 10 ? "P" : "R";

if (h == "P")

ans = y < 10 ? "R" : "S";

Console.WriteLine(ans);

}

n→10 進法 (paizaランク C 相当)

整数 A が N 進法で与えられる時、A を 10 進法表記に変換してください。

入力されるデータ
N
A
ただし 2 ≦ N ≦ 10
A の入力の長さは最大で 10

N進数は簡単にいえば下の位のものがN個集まると次の位に繰り上がる数の表現方法です。下の位から見ていくと a0 * N^0 + a1 * N^1 + a2 * N^2 + … のように計算していけばよいです。2進法で書かれた 1010 であれば 0 * 2^0 + 1 * 2^1 + 0 * 2^2 + 1 * 2^3 なので 10進法に変換すると 10 となります。

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

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        char[] vs = Console.ReadLine().ToArray();

        vs = vs.Reverse().ToArray();

        long ans = 0;
        for (int i = 0; i < vs.Length; i++)
            ans += int.Parse(vs[i].ToString()) * (long)Math.Pow(N, i);

        Console.WriteLine(ans);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

char[] vs = Console.ReadLine().ToArray();

vs = vs.Reverse().ToArray();

long ans = 0;

for (int i = 0; i < vs.Length; i++)

ans += int.Parse(vs[i].ToString()) * (long)Math.Pow(N, i);

Console.WriteLine(ans);

}

お菓子の価格帯 (paizaランク B 相当)

N 個のお菓子があり、それぞれのお菓子の価格は A_i 円(1 ≦ i ≦ n)です。ここで Q 個のクエリが与えられます。それぞれのクエリに対して、パイザ君は価格が L_i (1 ≦ i ≦ Q)円以上, R_i 円以下であるようなお菓子をできるだけ多く購入したいです。それぞれのクエリに対してパイザ君が購入するお菓子の個数を求めてください。

入力されるデータ
N
A_1 … A_n
Q
L_1 R_1
…
L_Q R_Q

ただし、
1 ≦ N ≦ 100
1 ≦ A_i ≦ 1000 (1 ≦ i ≦ N)
1 ≦ Q ≦ 100
1 ≦ L_i ≦ R_i ≦ 1000 (1 ≦ i ≦ Q)

L_i円以上, R_i 円以下であるようなお菓子をできるだけ多く購入するためにはすべてのお菓子のなかからL_i円以上, R_i 円以下であるお菓子をすべて選択すればよいです。そこでAをソートしてL_i円以上, R_i 円以下である要素の数を数えればよいです。Nが小さいので配列のなかのL_i円以上である部分がはじまるインデックス、R_i 円以下である部分が終了するインデックスを求めるときに二分探索法を使う必要はないと思われます。愚直にループを回して境界部分を探しています。

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

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray();

        A = A.OrderBy(_ => _).ToArray();

        int Q = int.Parse(Console.ReadLine());
        List<int> rets = new List<int>();
        for (int q = 0; q < Q; q++)
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int min = vs[0];
            int max = vs[1];
            int ans = 0;

            foreach (int v in A)
            {
                if (min <= v && v <= max)
                    ans++;
                if (v > max) // A[i] > max になったら用はないのでさっさとループを抜ける
                    break;
            }
            rets.Add(ans);
        }

        foreach(int ret in rets)
            Console.WriteLine(ret);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

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

A = A.OrderBy(_ => _).ToArray();

int Q = int.Parse(Console.ReadLine());

List<int> rets = new List<int>();

for (int q = 0; q < Q; q++)

{

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

int min = vs[0];

int max = vs[1];

int ans = 0;

foreach (int v in A)

{

if (min <= v && v <= max)

ans++;

if (v > max) // A[i] > max になったら用はないのでさっさとループを抜ける

break;

}

rets.Add(ans);

}

foreach(int ret in rets)

Console.WriteLine(ret);

}

ぴったり卵を生産 – その 2 (paizaランク S 相当)

ニワトリが N 羽います。各々のニワトリは A_i 個 (1 ≦ i ≦ N)卵を産みます。それぞれのニワトリを自由に選択し、（この場合選び方は全部で 2 ^ N 通りあります）選んだニワトリが産む卵の総和が K 個になる選び方は何通りあるか求めてください。

N K
A_1 … A_N

ただし、
2 ≦ N ≦ 30
0 ≦ K ≦ 3000000000
0 ≦ A_i ≦ 100000000

ナップサック問題のような問題ですが、A_iとKが大きいため動的計画法で使う二次元配列を生成することができません。これは半分全列挙の問題です。

最大30羽いるニワトリを選択する組み合わせは全部で 2^30通りと非常に多いため、これらをすべて全探索することはできません。しかし30の半分である15ならどうでしょうか？ 2^15通り（32,768通り）であればすべて調べることができます。

配列Aを前半 N/2 個とそれ以外の後半にわけます。そして辞書を生成します。

CreateDicメソッドに渡された配列aの長さをnとします。0から2^n-1の二進法表記された数をつくります。二進法表記された数のi桁が1であればi番目の鶏は選択されていると考えます。そして選択された鶏が生んだ卵の総和を計算します。計算したらこれを辞書に格納します。これで鶏 N/2 羽を組み合わせることで産まれる卵の数とその組み合わせの数を取得することができます。

class Program
{
    static Dictionary<long, int> CreateDic(int[] a)
    {
        int n = a.Length;
        Dictionary<long, int> dic = new Dictionary<long, int>();
        for (int b = 0; b < 1 << n; b++)
        {
            long count = 0;
            for (int i = 0; i < n; i++)
            {
                if (((b >> i) & 1) == 1)
                    count += a[i];
            }
            if (!dic.ContainsKey(count)) // 辞書内にキーが存在しないなら作る
                dic.Add(count, 0);
            dic[count]++;
        }
        return dic;
    }
}

class Program

{

static Dictionary<long, int> CreateDic(int[] a)

{

int n = a.Length;

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

for (int b = 0; b < 1 << n; b++)

{

long count = 0;

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

{

if (((b >> i) & 1) == 1)

count += a[i];

}

if (!dic.ContainsKey(count)) // 辞書内にキーが存在しないなら作る

dic.Add(count, 0);

dic[count]++;

}

return dic;

}

前半後半それぞれで辞書をつくり、一方の辞書からキーを取り出します。そしてこれに対応するキーがもう片方の辞書のなかにあるかどうかを調べます。一方の辞書から取り出したキーがMであるならもう一方の辞書から探すキーは K – M です。もしこれが見つかった場合は答えを示す変数に dic1[M] × dic2[K-M] を加算していけばよいのです。

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

class Program
{
    static void Main()
    {
        string[] vs = Console.ReadLine().Trim().Split();
        int N = int.Parse(vs[0]);
        long K = long.Parse(vs[1]);

        int[] A = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray();
        int[] A1 = A.Take(N / 2).ToArray();
        int[] A2 = A.Skip(N / 2).ToArray();

        Dictionary<long, int> dic1 = CreateDic(A1); // 前半
        Dictionary<long, int> dic2 = CreateDic(A2); // 後半

        int ans = 0;
        foreach (var pair in dic1)
        {
            if (dic2.ContainsKey(K - pair.Key))
                ans += pair.Value * dic2[K - pair.Key];
        }
        Console.WriteLine(ans);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

string[] vs = Console.ReadLine().Trim().Split();

int N = int.Parse(vs[0]);

long K = long.Parse(vs[1]);

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

int[] A1 = A.Take(N / 2).ToArray();

int[] A2 = A.Skip(N / 2).ToArray();

Dictionary<long, int> dic1 = CreateDic(A1); // 前半

Dictionary<long, int> dic2 = CreateDic(A2); // 後半

int ans = 0;

foreach (var pair in dic1)

{

if (dic2.ContainsKey(K - pair.Key))

ans += pair.Value * dic2[K - pair.Key];

}

Console.WriteLine(ans);

}

問題はまあ簡単だけど制限時間が短い。タイピングの練習をしなければ・・・。

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

最大値と最小値 (paizaランク D 相当)

神経衰弱 (paizaランク D 相当)

じゃんけん (忖度) (paizaランク C 相当)

n→10 進法 (paizaランク C 相当)

お菓子の価格帯 (paizaランク B 相当)

ぴったり卵を生産 – その 2 (paizaランク S 相当)

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

コメントについて

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

コメントをどうぞ