💬
ABC214 振り返りメモ
ABC214
A問題からC問題まで。
ABC214A - New Generation ABC
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
の破壊操作をし、代わりに別のループカウンタを用意した感じ -
now
,prev
などにすればいい
-
- 愚直にやると、
O(N^2) - それぞれの宝石に着目して、到着時間の最小値を調べる感じ
- ポイント
- 問題の見方を変える → 重み付き有向グラフの問題として考える
- 漸化式を見出す
- 愚直な解法を紙に書き出しておくと気づきやすいと思う → 愚直な解き方で問題を整理するのは重要!
- EDPCの練習も効果が出ている
- ただし、1回のループではすべてをチェックできないので、工夫する。循環を考慮する。
- 全部をチェックするので、ループ回数が
回は必要になる2N
- 全部をチェックするので、ループ回数が
- 循環は添字に注意する
-
の次をN とするなら、1 でOK(x + 1) \ mod \ N - 参考: https://zenn.dev/mohira/articles/atcoder-abc212#abc212b---weak-password
-
- 循環する部分がややこしいので、一旦、循環しない(
人目から、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