第17回 paizaの森練習問題コンテストに参加しました。これはその問題です。
「ユーザー同士で解答を教え合ったり、コードを公開して構わない」ということなので、鳩がどう考えてどんなコードを書いたのかを公開します。
Contents
最大値と最小値 (paizaランク D 相当)
3つの整数の中で一番大きな値と一番小さな値を出力してください。
入力されるデータ
a
b
c
（ただし -100 ≦ a, b, c ≦ 100）
3つの値をリストに格納してMaxメソッドとMinメソッドで最大値と最小値を取得して出力するだけです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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つずつあるかどうかを調べることにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
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。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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 となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
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 円以下である部分が終了するインデックスを求めるときに二分探索法を使う必要はないと思われます。愚直にループを回して境界部分を探しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
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 相当)
ぴったり卵を生産 – その 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通り）であればすべて調べることができます。
最初の15羽ですべての組み合わせをつくり、卵の総和がK個になるために足りない個数を求めます。これが残りの15羽を組み合わせのなかに存在するかを調べればよいのです。
最初の15羽でM個産ませる選び方がXとおりあり、後半の15羽でK-M個産ませる選び方がYとおりあるなら、答えに X × Y を足していけばよいということです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N; long K; { long[] vs = Console.ReadLine().Trim().Split().Select(_ => long.Parse(_)).ToArray(); N= (int)vs[0]; K = vs[1]; } long[] A = Console.ReadLine().Trim().Split().Select(_ => long.Parse(_)).ToArray(); long[] A1 = A.Take(N / 2).ToArray(); // 前半 long[] A2 = A.Skip(N / 2).ToArray(); // 後半 Dictionary<long, long> dic1 = CreateDictionary(A1); Dictionary<long, long> dic2 = CreateDictionary(A2); long ans = 0; foreach (var pair in dic1) { if (dic2.ContainsKey(K - pair.Key)) ans += pair.Value * dic2[K - pair.Key]; } Console.WriteLine(ans); } // arr の要素を組み合わせて卵を何個産むことができるか、またその組み合わせの数を辞書に格納する static Dictionary<long, long> CreateDictionary(long[] arr) { Dictionary<long, long> dic = new Dictionary<long, long>(); dic.Add(0, 1); // 0個産ませる組み合わせは1つ存在する foreach (long v in arr) { foreach (var pair in dic.ToList()) { long nkey = v + pair.Key; if (!dic.ContainsKey(nkey)) dic.Add(nkey, 0); dic[nkey] += pair.Value; } } return dic; } } |
問題はまあ簡単だけど制限時間が短い。タイピングの練習をしなければ・・・。
