ABC214 振り返りメモ

ABC214

• 問題 - AtCoder Beginner Contest 214

A問題からC問題まで。

ABC214A - New Generation ABC

• https://atcoder.jp/contests/abc214/submissions/25019207
• 素直に実装するだけ

ABC214B - How many?

• https://atcoder.jp/contests/abc214/submissions/25026590
• $a + b + c \le S$ なので、$a \le S = 100$ かつ $b \le S = 100$ かつ $c \le S = 100$
• よって、全探索すれば良い
• GoLandの補完でサラッと書いたが、=をつけ忘れて、1WA。もったいない。

ABC214C - Distribution

• https://atcoder.jp/contests/abc214/submissions/25059242
• 今後の反省
  • 非常に悔しい！ 終了5分後にAC！
  • 解法が思いつかないときは、ひとまずテストケースは先に並べておく
    • 時間ギリギリで解法を思いついたので手動テストしたが、目視チェックに誤りがあった(テストコードを書いておけばACできた可能性が高い！)
  • マジックナンバーは変数や定数として定義しておく
    • 雑に放置した結果、WAになってしまい時間切れ
  • ややこしい添字はちゃんと変数に抽出する。リファクタリングの基本！
    • i, j を使ったが、結構混乱してしまい時間を浪費した
    • 混乱したので、iの破壊操作をし、代わりに別のループカウンタを用意した感じ
      • https://atcoder.jp/contests/abc214/submissions/25056816
    • now, prev などにすればいい
• 愚直にやると、$O(N^2)$
  • それぞれの宝石に着目して、到着時間の最小値を調べる感じ
• ポイント
  • 問題の見方を変える → 重み付き有向グラフの問題として考える
  • 漸化式を見出す
    • 愚直な解法を紙に書き出しておくと気づきやすいと思う → 愚直な解き方で問題を整理するのは重要！
    • EDPCの練習も効果が出ている
  • ただし、1回のループではすべてをチェックできないので、工夫する。循環を考慮する。
    • 全部をチェックするので、ループ回数が$2N$回は必要になる
  • 循環は添字に注意する
    • $N$の次を$1$とするなら、$(x + 1) \ mod \ N$ でOK
    • 参考: https://zenn.dev/mohira/articles/atcoder-abc212#abc212b---weak-password
  • 循環する部分がややこしいので、一旦、循環しない($N-1$人目から、$N$人目で打ち切り)を考えると方針が見えやすい
    • 参考: https://youtu.be/NMSqfGG9O9k?t=602

abc214c.go

package abc214

func AnswerABC214C(N int, S, T []int) []int {
	// dp[i]: i番目のすぬけ君が宝石を持ったときの最小の時刻
	dp := make([]int, N)
	dp[0] = 1e+9 + 10

	for i := 0; i < N; i++ {
		dp[i] = T[i]
	}

	// i := 0; i < 2*N; i++ でも良いと思う(番兵を用意していた名残り) 
	for i := 1; i <= 2*N; i++ {
		// 添字がややこしいので変数に抽出したほうがいい
		now := (i + 1) % N
		prev := i % N

		dp[now] = Min(
			dp[now],
			dp[prev]+S[prev],
		)
	}

	// 出力に関してはmain関数で処理するの整数スライスを返している
	return dp
}

func Min(x, y int) int {
	if x < y {
		return x
	} else {
		return y
	}
}