こんにちは。倉内です。
プログラミング学習中の方で、言語の基礎文法を習得したあとは練習問題を解いてみるという方は多いですよね。
ただ、四則演算や単純なif文・for文を使った問題は解けても、少し複雑な条件が提示されると「なかなか自力で解くのは難しい…」と感じている方もいるのではないでしょうか。
paizaでも「スキルチェック」というサービスで難易度別にプログラミング問題を公開しており、学習中の腕試しとして挑戦してくださる方も多いのですが、そのような悩みをお聞きすることがあります。
そこでスムーズに問題に取り組んでいただくためにコーディング方針の立て方や実装方法などを解説した講座「スキルチェック入門編」を公開しています。
今回は、難易度がやや高い問題をJavaで解く「スキルチェック入門編6: 神経衰弱」が新しく追加されましたので、こちらをご紹介しつつ、問題を解いてみます。単に解答コードを示すだけでなく、難しい問題の考え方・解き方を詳しく解説します。
また、先日paizaのスキルチェックでKotlinを使っての解答ができるようになりました!KotlinはJavaと互換性がある注目のプログラミング言語です。Kotlinについても後半で少し紹介しますので気になる方はチェックしてください。
「スキルチェック入門編6: 神経衰弱」の問題内容
「スキルチェック」では問題の難易度がS・A・B・C・Dに分かれており、今回の問題はBランクなので問題文は少し複雑ですね。
神経衰弱と呼ばれるトランプゲームのシミュレーションをしましょう。
今回は数字が書かれたトランプのみを考え、ジョーカーは考えません。まず、トランプを縦 H 枚、横 W 枚の長方形の形に並べた状態でスタートします。
H × W 枚のトランプには 1 〜 13 の数字のうちどれか1つが書かれています。
また、同じ数字が書かれたトランプが複数あります。プレイヤーが N 人おり、それぞれ 1 〜 N で番号付けられています。
ゲームが始まると、1番の人から、このような手順でプレイしていきます。・並べられたトランプから2枚のトランプを選び、めくります。
・めくった2枚のトランプに異なる数字が書かれていれば、次のプレイヤーの手番となります。同じ数字であれば、次の操作をおこないます。
・まず、2枚のトランプはめくったプレーヤーのものとなり、取り除かれます。
・トランプがすべて取り除かれた場合、ゲームは終了となります。
・トランプが残っている場合、同じプレーヤーがまた最初の手順に戻り、トランプをめくります。ここで、N 番のプレイヤーの次のプレイヤーは 1 番のプレイヤーであるとします。
ゲームの初期状態におけるトランプの配置と、ゲームが終わるまでにめくられたトランプに関する時系列順の記録が与えられます。
その記録を用いて、各プレイヤーが取り除いたトランプの枚数を求めてください。
文章だけだと難しいので、入力例のイメージ図も掲載しています。
入力される値
入力は以下のフォーマットで与えられます。
H W N
t_{1,1} t_{1,2} ... t_{1,W}
t_{2,1} t_{2,2} ... t_{2,W}
...
t_{H,1} t_{H,2} ... t_{H,W}
L
a_1 b_1 A_1 B_1
a_2 b_2 A_2 B_2
...
a_L b_L A_L B_L1行目には3つの整数 H, W, Nが入力されます。
H と W はそれぞれ並べられたトランプの縦方向の枚数と横方向の枚数で、N はプレイヤーの数を表します。続く H 行には、配置されたトランプに書かれた数字が入力されます。
t_{i,j} は i 行 j 列に置かれたトランプに書かれた数字を表します。次の行には、記録の長さ L が与えられます。
続く L 行には、めくられたトランプの記録が時系列順で与えられます。
これは、a_i 行 b_i 列のトランプと A_i 行 B_i 列のトランプがめくられたことを表します。入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。
期待する出力
i 行目には i 番目のプレイヤーが取り除いたトランプの枚数を出力してください。
各行の最後は改行し、余計な文字、空行を含んではいけません。
条件
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ H, W ≦ 13
・H × W は52以下の2の倍数
・2 ≦ N ≦ 10
・t_{i,j} は 1, ... ,13 のいずれか
・並べられたトランプの中に、同じ数字が書かれたトランプは2枚または4枚ある
・1 ≦ L ≦ 200
・1 ≦ a_i, A_i ≦ H
・1 ≦ b_i, B_i ≦ W
・a_i 行 b_i 列および A_i 行 B_i 列のトランプは取り除かれていない
講座では、まずこれらの情報を整理し、コーディングの方針をどう立てていくかを考えていきます。
「問題を見て分かりそうだから自分で解いてみたい!」という方は、レベルアップ問題集のスキルチェック過去問題から解答できますので、ぜひチャレンジしてみてください。
問題をJavaで解くための方針を立てる
チャプター「02: コーディングの方針」では、入力例1と2を図解しながら入力値の扱い方、実装しなければいけない処理などについて説明します。
入力例1は、以下の通りです。
2 3 2
1 2 3
2 1 3
5
1 1 2 1
1 1 1 2
1 1 2 2
1 3 2 3
1 2 2 1
少し補足しておくと、1行目の「2 3 2」は順に「並べられたトランプの縦方向の枚数」「同じく横方向の枚数」「プレイヤー人数」を示します。
つづいて2行目と3行目の「1 2 3」「2 1 3」は「配置されたトランプに書かれた数字」です。この例では縦2枚×横3枚の計6枚が場にあります。
次の「5」は記録の長さ、つまり何手目までゲームをしたかを表しています。そのあとの行は実際にプレイヤーがめくったカードです。
たとえば5行目の「1 1 2 1」は、配置された1行・1列にあるトランプと2行・1列にあるトランプを引いたという意味です。この場合、1枚目が「1」、2枚目が「2」となります。
…というのを動画で分かりやすく説明しています。
まとめると、以下の方針で実装していけばよさそうです。
入力値の受け取り方:
- トランプの縦の枚数(H)、横の枚数(W)、プレイヤー人数(N)を受け取る
- H行・W列のトランプの配置をH×Wの二次元配列で受け取る
- ゲームの記録の長さ(L)を受け取る
- L行のゲームの記録を受け取る
ゲームの処理:
- 現在のプレイヤーを記録する変数を用意する
- 各プレイヤーが取り除いたトランプを記録する長さNの配列を用意する
- 一手ずつ順に処理をする
- 引いたカードの1枚目と2枚目が同じか・異なるかをチェックする
- 2枚のカードの数字が同じ場合は、トランプを取り除いて、当てたことを記録し、続いて同じプレイヤーが引く
- 2枚のカードの数字が異なる場合は、次のプレイヤーに移る
- 本来は当てたカードを場から取り除く必要があるが、めくられたトランプの値が時系列順に与えられるので考慮しなくてもよい(取り除かれたカードが別の手で選ばれることはない)
Javaでコードを書いて問題を解く
さきほどのコーディングの方針をもとに処理を書いていきましょう。
チャプター「03:問題を解く」では、動画を見ながらブラウザ上でコードを書けるようになっているので、自分でも手を動かしてみると理解が深まりますよ。
まずは与えられる値を取得する処理です。
1行目のトランプの縦の枚数(H)と横の枚数(W)、プレイヤー人数(N)は以下の処理で取得します。
// H と W と N を受け取る int H = sc.nextInt(); int W = sc.nextInt(); int N = sc.nextInt();
つづいてトランプの配置をH×Wの二次元配列tで受け取ります。
// トランプの並び方を表す t を受け取る int[][] t = new int[H][W]; for (int h = 0; h < H; h++) { for (int w = 0; w < W; w++) { t[h][w] = sc.nextInt(); } }
ゲームの記録の長さ(何手目までゲームをしたか)Lを受け取ります。
// 時系列の長さ L を受け取る int L = sc.nextInt();
長さLのゲームの記録を配列に格納します。
// ゲームの手順の記録を受け取る int[] a = new int[L]; int[] b = new int[L]; int[] A = new int[L]; int[] B = new int[L]; for (int l = 0; l < L; l++) { a[l] = sc.nextInt(); b[l] = sc.nextInt(); A[l] = sc.nextInt(); B[l] = sc.nextInt(); }
ここまでで与えられる値の取得は終わりました。
次に現在のプレイヤーと各プレイヤーが取り除いたトランプの枚数を覚えておく変数を定義します。
// 手番を持つプレーヤーを表す変数 int player = 1; // 各プレーヤーが取り除いたトランプの枚数 int[] count = new int[N];
ここまで来たらあとはゲームの記録をもとに引いたカードが一致しているとき・異なるときの処理を書いて、最終的にプレイヤーが取り除いたカードの枚数を出力すれば完成です。
for (int l = 0; l < L; l++) { // 1枚目のカードと2枚目のカードを特定 // 配列のインデックスは0から始まることに注意 int firstCard = t[a[l] - 1][b[l] - 1]; int secondCard = t[A[l] - 1][B[l] - 1]; if (firstCard == secondCard) { // 一致したときは2枚取り除かれる count[player - 1] += 2; } else { // 一致しなかったら次のプレイヤーへ player += 1; // 最後のプレイヤーの次は最初に戻る if (player == N + 1) { player = 1; } } } // 最後に各プレイヤーが何枚カードを取り除いたかを出力 for (int n = 0; n < N; n++) { System.out.println(count[n]); }
一気にやろうとすると難しく思えましたが、分解してそれぞれ考えてみると特別なアルゴリズムなどを使う必要はなく解くことができました。
作成した全コードは以下のとおりです。
import java.util.*; public class Main { public static void main(String[] arg) { Scanner sc = new Scanner(System.in); // H と W と N を受け取る int H = sc.nextInt(); int W = sc.nextInt(); int N = sc.nextInt(); // トランプの並び方を表す t を受け取る int[][] t = new int[H][W]; for (int h = 0; h < H; h++) { for (int w = 0; w < W; w++) { t[h][w] = sc.nextInt(); } } // 時系列の長さ L を受け取る int L = sc.nextInt(); // ゲームの手順の記録を受け取る int[] a = new int[L]; int[] b = new int[L]; int[] A = new int[L]; int[] B = new int[L]; for (int l = 0; l < L; l++) { a[l] = sc.nextInt(); b[l] = sc.nextInt(); A[l] = sc.nextInt(); B[l] = sc.nextInt(); } // 手番を持つプレーヤーを表す変数 int player = 1; // 各プレーヤーが取り除いたトランプの枚数 int[] count = new int[N]; for (int l = 0; l < L; l++) { int firstCard = t[a[l] - 1][b[l] - 1]; int secondCard = t[A[l] - 1][B[l] - 1]; if (firstCard == secondCard) { count[player - 1] += 2; } else { player += 1; if (player == N + 1) { player = 1; } } } for (int n = 0; n < N; n++) { System.out.println(count[n]); } } }
Kotlinで解いてみる
冒頭で述べたとおり、Kotlinがスキルチェックで選択できるようになりました!(これまではβ版として再チャレンジ時のみ選択可能でした)
「神経衰弱」の解説はJavaでしたが、他の言語でも方針は同様かつKotlinはJavaと文法が似ているため、Javaで問題を解いたあとに挑戦するにはちょうどよいと思います。
「Javaの文法、ちょっと忘れている部分があったな…」という方は、「Java入門編」を受講してみてくださいね。
Kotlinで問題を解くには、さきほども紹介したレベルアップ問題集のスキルチェック過去問題を使うとよいでしょう。スキルチェック本番と違いランクの取得はできませんが、時間制限なしで何度でも解き直すことができます。
標準入力や配列の記述の仕方がJavaとは少し異なりますが、だいたい参考にしながらコードを書けるのでぜひチャレンジしてみてください。
ちなみに『エンジニアでも恋がしたい!』*1でもプログラミング問題を解く際にKotlinを選択可能です。
paizaが提供しているその他のプログラミングゲームでもKotlinで解答できますのでたくさん書いて慣れたいという方は覗いてみてください!
まとめ
「スキルチェック入門6: 神経衰弱」の講座でBランク問題の解き方を学び、JavaとKotlinで問題に挑戦しました。
BランクはC、Dランクの問題に比べると問題文が長くなり、条件も少し複雑になるためなかなか手が出せないという声もお聞きしますが、まずは問題内容の整理と解答の方針を立ててみましょう。
いろいろな問題を練習で解きたいときは、ぜひレベルアップ問題集を活用してくださいね。テストケースの入力値、一部問題の解答例コードも参照可能となっています。
「自信がついたのでスキルチェックの本問題を解いてみたい」という方は、こちらから挑戦してみてください。
「paizaラーニング」では、未経験者でもブラウザさえあれば、今すぐプログラミングの基礎が動画で学べるレッスンを多数公開しております。
詳しくはこちら
そしてpaizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。
スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。
詳しくはこちら
*1:通称『エン恋』は、プログラミング問題を問いてストーリーを読み進める参加型のイベントです。