【AtCoder】ADT EASY 2024/12/19 復習【Golang】

問題リンク：https://atcoder.jp/contests/adt_easy_20241219_3/tasks/abc256_b

YouTube解説を見て、スッゲーと思ったので、解説をもとに復習してみました。

最終状態から考えよう！

「全員の人数 - 最終的に塁に残っている人 = ホームに到達した人の数」となるので、最終状態を作ってあげて、引き算すれば良さそうだということです。

回答コード

C.go

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	A := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&A[i])
	}

	// 最終状態から考える
	// A[1 1 3 2]の場合、最終状態は[0 0 1 0]となる。
	// このことから、4人中1人がゴールできていないことがわかる
	// よって、p = 4人-1人 = 3人
	// 最終状態を作る処理
	var b int
	for i := 0; i < n; i++ {
		b |= 8     // マス0に駒を1個置く
		b >>= A[i] // 全ての駒を A[i] 分だけ右にシフトして移動
	}

	// 全体人数から残り人数を引く処理
	p := n
	for i := 0; i < 4; i++ {
		p -= b & 1 // 3塁にいる人を1減らす
		b >>= 1    // 次のマスに移動(まだ1塁、2塁に人がいるかもしれないので次の処理に移る)
	}

	fmt.Println(p)
}

説明のため、問題にある入力例1とは入力値を少し変えています。（[1 1 3 2]→[1 1 3 1]）

なんというシンプルさでしょうか。
解説を見ていて感動しました。

簡単なお絵描きをしてみたので、載せておきます。

※お絵描きでは、AND演算は2進数で、引き算は10進数で書いています。

1とAND演算することで、3塁に人がいた場合、結果が1になるはずです。
それを全体人数から引いていく処理を、塁に残っている人分、処理します。

最後に

この発想をできるようになりたいと思いました。（コードが簡潔でオシャレ）
確か、鉄則本にも処理後の状態を考えると見通しが良くなると、テックニックとして紹介されていた気がします。
これを機に、問題の見方も学んでいきたい思います。