【備忘録】ABC149のD問題について

ABC149にバーチャル参加してきたので、最後に解いた問題の備忘録としてこれを残しておきます。ちょっと自分でもよく理解できてないけど解けたって感じのやつなので、解説とかそういうのは期待しないでください。

1. 問題の内容

D - Prediction and Restriction

ざっくり説明すると以下の通り。

* 機械とN回ジャンケン
* プレイヤーは機械の出す手を事前に知ることができるので基本的に負けることがない
* しかしプレイヤーはK回前に出した手と同一の手で勝利することはできない（つまり、あいこになるか負けるかする）
以上の条件において、プレイヤーは何回勝てるか？

実際にはプレイヤーが獲得しうる最高得点を求める問題ですので、細かい話をすればグーで勝利した時、チョキで勝利した時、パーで勝利した時に獲得できる得点をそれぞれ入力として受けとり、それによって得点を計算する必要があるのですが、まあその辺は楽に実装できるので割愛。

重要なのは、「プレイヤーはK回前に出した手と同一の手で勝利することはできない」というところです。

2. 提出したコード

ご覧の通り、言語はJavaです。String型使ってたらLTEになりそうな所はStringBuilder型使ってます。

Submission #13268193 - AtCoder Beginner Contest 149

import java.util.Scanner;

public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int N = sc.nextInt();
   int K = sc.nextInt();
   final int R = sc.nextInt();
   final int S = sc.nextInt();
   final int P = sc.nextInt();
   final String T = sc.next();
   sc.close();
   StringBuilder byK = new StringBuilder();
   int point = 0;
   for(int i=0;i<K;i++) {
   	switch(T.charAt(i)) {
		case 'r' :
			point += P;
			byK.append("r");
			break;
		case 's' :
			point += R;
			byK.append("s");
			break;
		case 'p' :
			point += S;
			byK.append("p");
			break;
		}
   }
   for(int i=K;i<N;i++) {
   	if(byK.charAt(i-K) == T.charAt(i)) {
   		point += 0;
   		if(byK.length()<i+1) {
   			byK.append("c");
   		}
   		byK.setCharAt(i-K, 'c');

   	}else {
   		switch(T.charAt(i)) {
   		case 'r' :
   			point += P;
   			byK.append("r");
   			break;
   		case 's' :
   			point += R;
   			byK.append("s");
   			break;
   		case 'p' :
   			point += S;
   			byK.append("p");
   			break;
   		}
   	}
   }
   System.out.println(point);
 }
}

こんな感じのやつです。なんというかまあ、けっこう力技な解き方してる気がしますね。一応、これは貪欲法ということになるのでしょうか。

DP(Dynamic Programming)による解法ではTにmod Kしてなんか色々やるみたいですが、理解できてないので割愛。

確認用のSystem.out.printlnがコメントアウトで入ってるのはご愛嬌。

3. 提出コード作成にあたって考えたこと

とりあえずK回目までは全戦全勝できるので、for文でK回目まで回して得点計算します。ついでに、保存用の変数byKにその時の機械の出した手を保存しておきます。（byKは「Kまで」の意。はじめ、1～K回目に出した手だけ保存しておけば十分だと誤解していたのでこの名前になった。今更になって、そういう意図ならuntilKとかのが良かった気がしてる）言うまでもなく、ジャンケンはある手に対して勝利できる手が一意に定まるので、保存するのは機械が出した手でも構わないという判断です。

で、それ以降はN回目までforループ。この時、K回前と同じ手を機械が出して来たかを判定。違えばポイントを加算、同じなら、ポイントの変動なし。（何も書かないのも落ちつかないのでとりあえずpoint+=0しとく）この時、Out of rangeなどのインデックスエラー防止のためにbyKの要素数が次のループのiの値よりも小さければbyKに文字cを追加。cはジャンケンに勝てなかったことを表す文字。こうすれば問題の入力例2もちゃんと処理できる。

なんて書いてはみたものの、この辺も完全に理解して書いているわけでなく、「頭捻ってコード書いてたらなんか上手くいった」程度の理解度。要するに自分でもよく分かってません。精進せねば。

3. 総括（反省）

自分がいかに理解しないでプログラムを書いているのかがよく分かりました。あれこれ手を動かす前にじっくり腰を据えて考えてから書くようにしたいですね。