第18回 paizaの森練習問題コンテストに参加しました。問題は全部で6問。制限時間は40分。最後の問題以外は簡単な問題なので毎回全問正解を目指しているのですが、なかなかうまくいきません。
制限時間は40分と短いため途中でつっかえることなくコードを書くことができればいいのですが、「あれ？この問題どうやって解けばいいんだっけ？」とか正体不明のバグに捕まるとゲームオーバーです。今回も最後の問題で慌ててしまい全問正解ならずです。制限時間の設定が絶妙で「できそうでできない」のです。
「ユーザー同士で解答を教え合ったり、コードを公開して構わない」ということなので、鳩がどう考えてどんなコードを書いたのかを公開します。
Contents
値の整列 C#編（paizaランク D 相当）
第一問は「4つの整数が与えられるので小さな値から順に改行区切りで出力せよ」という問題です。
C#なら入力をリストに格納し、Linq拡張メソットを使ってソートして出力すればOKです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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 < 4; i++) list.Add(int.Parse(Console.ReadLine().Trim())); list = list.OrderBy(_ => _).ToList(); foreach (int v in list) Console.WriteLine(v); } } |
シープラスプラスプラス C#編（paizaランク D 相当）
シープラスプラスプラス C#編（paizaランク D 相当）
これは入力された値の回数だけ”C”の後ろに”+”を追加した文字列を出力せよという問題です。
文字列を連結するときに + を何回も使っていると動作速度が遅くなるのでStringBuilderクラスを使ったほうがよいのですが、問題の条件を見てみると最大で100回なのでそこまでしなくてもよいかと思います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
using System; class Program { static void Main() { int n = int.Parse(Console.ReadLine().Trim()); string s = "C"; for (int i = 0; i < n; i++) s += "+"; Console.WriteLine(s); } } |
StringBuilderクラスを用いるならこうなります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
using System; using System.Text; class Program { static void Main() { int n = int.Parse(Console.ReadLine().Trim()); StringBuilder sb = new StringBuilder(); sb.Append("C"); for (int i = 0; i < n; i++) sb.Append("+"); Console.WriteLine(sb.ToString()); } } |
大晦日 C#編（paizaランク D 相当）
日付を表す文字列がYYYY-MM-DD形式（年は4文字、月は2文字、日付は2文字、ハイフン区切りで全部で10文字）で与えられるので大晦日であるかどうか判定せよという問題です。
大晦日なら ????-12-31 となるので文字列”-12-31″があるかどうか調べればよいですね。入力される文字列がYYYY-MM-DD形式なので”-12-31″が行末以外のところに来る心配はしなくてよいです。文字列はIndexOfメソッドで探します。ある場合は先頭のインデックスが、ない場合は -1 が返されるので “Yes”または”No”を出力します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
using System; class Program { static void Main() { string s = Console.ReadLine().Trim(); if(s.IndexOf("-12-31") != -1) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } |
背の順に並んでいるか C#編（paizaランク C 相当）
これは入力されたn個の整数が小さい順に並んでいるかを調べよという問題です。入力されたn個の整数とそれらをソートした結果が一致しているかどうかを調べればよいです。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int n = int.Parse(Console.ReadLine().Trim()); List<int> list = new List<int>(); for (int i = 0; i < n; i++) list.Add(int.Parse(Console.ReadLine().Trim())); bool yes = true; List<int> sorted = list.OrderBy(_ => _).ToList(); for (int i = 0; i < n; i++) { if (list[i] != sorted[i]) { yes = false; break; } } if(yes) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } |
遠足のお菓子 C#編（paizaランク C 相当）
これは入力されたN個の整数の和がX以下であるかどうか調べよという問題です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, X; { int[] vs = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; X = vs[1]; } int sum = 0; for (int i = 0; i < N; i++) sum += int.Parse(Console.ReadLine().Trim()); if(sum <= X) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } |
陣取りゲーム C#編（paizaランク A 相当）
D問題が3問、C問題が2問のあとB問題がなくて最後の問題はA問題です。簡単な問題ばっかりででも最後は難しい問題。「問題を解くことができる喜びを味わわせてやる。しかし全問正解はさせない」ということでしょうか？ そして残念ながら時間以内にこの問題を解くことはできませんでした。
A さんと B さんで陣取りゲームをする。ルールは以下のとおり。
現在の陣地から上下左右に 1 マス移動することで到達できる、まだ誰の陣地でもない全てのマスを新たに陣地にする。ただし、障害物( ‘#’ )のマスは陣地にできない。
新たに陣地にできるマスが無い場合、何もしない。
2 人の操作によって盤面が変化しなくなったらゲームを終了する。盤面の情報と先攻のプレイヤーの名前が与えられるので、AとB、それぞれの陣地のマス数と勝った人の名前を出力せよ。
入力されるデータ
H W
N
S_0
…
S_(H-1)1 ≦ H, W ≦ 1000
N は ‘A’ か ‘B’
S は W 文字の文字列
S の各文字は ‘.’, ‘#’, ‘A’, ‘B’のいずれか
‘A’ , ‘B’ のマスは１つ
交互に着手するので獲得した陣地が増えていく様子を交互に処理しないといけないのかなと考えてしまい、変に長いコードを書いてしまいタイムオーバー。実際にはもっと簡単な方法がありました。
Aのみが着手しつづけた場合とBのみが着手しつづけた場合を考えます。そしてそれぞれのマスに陣地になるのは何手後なのかを記録します。これは幅優先探索で’A’と’B’が書かれているマスからそれ以外のマスまでの最短経路を考えればよいです。そのあと角マスに書き込まれている値を比較します。それぞれのマスは値が小さい側のものとなります。同じ場合は先手のものとなります（ただし到達不能のマスは除外すること）。
この場合は、Aが先手のときは7－4、Bが先手のときは6－5、いずれの場合もAの勝ちですね。
|
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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int H, W; { int[] vs = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray(); H = vs[0]; W = vs[1]; } string N = Console.ReadLine().Trim(); char[,] map = new char[H, W]; int srA = 0; int scA = 0; int srB = 0; int scB = 0; for (int row = 0; row < H; row++) { char[] vs = Console.ReadLine().Trim().ToArray(); for (int col = 0; col < W; col++) { map[row, col] = vs[col]; if (vs[col] == 'A') { srA = row; scA = col; } if (vs[col] == 'B') { srB = row; scB = col; } } } int[,] costsA = BFS(map, H, W, srA, scA); int[,] costsB = BFS(map, H, W, srB, scB); int A = 0; int B = 0; for (int row = 0; row < H; row++) { for (int col = 0; col < W; col++) { if (costsA[row, col] < costsB[row, col]) A++; else if (costsA[row, col] > costsB[row, col]) B++; else { if(costsA[row, col] == int.MaxValue) continue; if(N == "A") A++; if (N == "B") B++; } } } Console.WriteLine($"{A} {B}"); Console.WriteLine(A > B ? "A" : "B"); } static int[,] BFS(char[,] map, int H, int W, int sr, int sc) { int[,] costs = new int[H, W]; for (int row = 0; row < H; row++) { for (int col = 0; col < W; col++) costs[row, col] = int.MaxValue; } Queue<int> qRow = new Queue<int>(); Queue<int> qCol = new Queue<int>(); qRow.Enqueue(sr); qCol.Enqueue(sc); costs[sr, sc] = 0; int[] dx = { 1, -1, 0, 0 }; int[] dy = { 0, 0, 1, -1 }; while (qRow.Count > 0) { int r = qRow.Dequeue(); int c = qCol.Dequeue(); for (int i = 0; i < 4; i++) { int nr = r + dy[i]; int nc = c + dx[i]; if (nr < 0 || nc < 0 || nr >= H || nc >= W) continue; if(map[nr, nc] == '#') continue; if (costs[nr, nc] > costs[r, c] + 1) { costs[nr, nc] = costs[r, c] + 1; qRow.Enqueue(nr); qCol.Enqueue(nc); } } } return costs; } } |
最後にひとこと
結局今回も優勝できませんでした。ここにhatodemowakaruの文字が入るのはいつの日か？このかん優勝はいつも「匿名希望0」さんなんだよなあ。
