ABC 078-D ABS (Go) / CADDi 2018-D Harlequin (Java)
irisruneです。ゲーム理論系の問題で500点ばかり見るのは気のせいでしょうか。
今回は解いた問題の実装が軽かったのと、似たような問題が過去にあったので久々の2本立てです。
ABC 085-D ABS
あまり入出力例が多いとボロが出るから例3,4は自明なものを選んだのだと思いました。
package main
import (
"fmt"
"math"
)
func main() {
var n, z, w int
fmt.Scan(&n, &z, &w)
arrA := make([]int, n)
for i := 0; i < n; i++ {
fmt.Scan(&arrA[i])
}
ans := math.Abs(float64(arrA[n-1] - w))
if n > 1 {
if math.Abs(float64(arrA[n-2]-arrA[n-1])) > ans {
ans = math.Abs(float64(arrA[n-2] - arrA[n-1]))
}
}
fmt.Println(int(ans))
}
ACに至った発想としては、
- ゲーム理論的には石を何個でも取れる石取りゲームのようなもの。
- YさんはXさんにとっての最悪手を取る点では同じ。
- カードを全て引いてしまうか1枚残すかの手をXさんが取ることで、Yさんの取れる手はなくなる。
- 上記の2つの手を取った際のスコアは計算・比較可能。
- スコアの比較結果によって、最後の石を取った側が勝ちか負けかが変わる。
なので、（山札の初期枚数が1枚でなければ）Xさんが取れる手は2つに絞られるのでそれぞれのスコアを計算して、 スコアが高い方を出力すればよいと考えられます。
なお無証明ACです。解説ではちゃんと証明がされています。
CADDi 2018-D Harlequin
この頃JavaSilverの勉強をしていたので、この問題もJavaでやっていました。
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
String winner = "second";
for(long i = 0; i < n; i++){
long a = sc.nextLong();
if(a % 2 == 1){
winner = "first";
break;
}
}
System.out.println(winner);
}
}
先ほどの問題を石取りゲームに例えるのは少し強引な部分がありますが、この問題は石取りゲームそのものですね。
- N色のりんごが実っています
- →N個の山があります
- 一度に選ぶりんごは全て異なる色でなければならない
- →同じ山からは1個までしか石を取れない
なので、全ての山について石の個数が2(=1+1)の倍数の状態で手番が回ってくると負け、それ以外の状態なら勝ちということになります。
この問題はゲーム理論を少し学んでいればかなり簡単だと思います。300点くらいなのでは。
雑記
- PythonエンジニアとJavaSilverを同時期に取りましたがPythonはよくわからないです。
- コンパイル言語の機械学習の本とかほとんど見かけないのが辛いですね。
