💬

ABC214 振り返りメモ

2021/08/14に公開

ABC214

A問題からC問題まで。

ABC214A - New Generation ABC

ABC214B - How many?

ABC214C - Distribution

  • https://atcoder.jp/contests/abc214/submissions/25059242
  • 今後の反省
    • 非常に悔しい! 終了5分後にAC!
    • 解法が思いつかないときは、ひとまずテストケースは先に並べておく
      • 時間ギリギリで解法を思いついたので手動テストしたが、目視チェックに誤りがあった(テストコードを書いておけばACできた可能性が高い!)
    • マジックナンバーは変数や定数として定義しておく
      • 雑に放置した結果、WAになってしまい時間切れ
    • ややこしい添字はちゃんと変数に抽出する。リファクタリングの基本!
  • 愚直にやると、O(N^2)
    • それぞれの宝石に着目して、到着時間の最小値を調べる感じ
  • ポイント
    • 問題の見方を変える → 重み付き有向グラフの問題として考える
    • 漸化式を見出す
      • 愚直な解法を紙に書き出しておくと気づきやすいと思う → 愚直な解き方で問題を整理するのは重要!
      • EDPCの練習も効果が出ている
    • ただし、1回のループではすべてをチェックできないので、工夫する。循環を考慮する。
      • 全部をチェックするので、ループ回数が2N回は必要になる
    • 循環は添字に注意する
    • 循環する部分がややこしいので、一旦、循環しない(N-1人目から、N人目で打ち切り)を考えると方針が見えやすい
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
	}
}

Discussion