ABC222 D問題

https://scrapbox.io/files/6161b1ed6cf2290020dfd75b.png

dpを使います！

＜考え方＞

（例）

a : 1 2 3 4 5 6

b : 1 4 9 16 25 36　が与えられる時

最初のc1の候補は1のみ -> 1番目まで確定した時の1で終わる通り数は1

次のc2の候補は、2 3 4 -> 2番目まで確定した時の2,3,4で終わる通り数は1

c3からが工夫いる。

c3の候補 -> 3 4 5 6 7 8 9

c1 <= c2 <= c3 より、 c3 = 3 はc2が2か3の時しか選べない。

3はc2が2か3のいずれかなので、c3が3で終わる通り数は1+1=2 　＊c2が2か3である通り数

こんな感じで行くと、

通り数テーブル

3番目　3 4 5 6 7 8 9

通り数 2 3 3 3 3 3 3

4番目　4 5 6 7 8 9 10 11 12 13 14 15 16

通り数 5 8 11 14 17 20 20 20 20 20 20 20 20

c4の4は、c3が3か4の時のみ。 2+ 3 = 5

c4の5以上9以下は、c3が3~9まであるためc3の通り数分増えていく。

しかし、10以上16以下は通り数は増えていかない。

この更新をN回行う。

code:swift

func main(){

let N = Int(readLine()!)!

let a = readLine()!.split(separator: " ").map{Int($0)!}

let b = readLine()!.split(separator: " ").map{Int($0)!}

}

for n in 1..<N{ //長さN

var tmp = 0

}

}

}

}

var sum = 0

sum += num

sum %= 998244353

}

print(sum)

}

main()