7K12 blog

猫でも分かるアルゴリズム解説

ABC152 D - Handstand 2

f:id:tkr987:20200718015931p:plain

https://atcoder.jp/contests/abc152/submissions/15125443

  • 条件X∧Yを満たす値の個数を二次元配列[X][Y]で管理する

f:id:tkr987:20200718020246p:plain

先頭X末尾Yとなる値の個数をbcount[X][Y]とする。1からNまで線形処理すればbcount[1][1]からbcount[9][9]までの個数は得られる。あとは先頭S末尾TとなるAの値とペアになれるBはbcount[T][S]個あるので、A=1からA=Nまで線形に見ていきペアとなるbcountを加算していけば答えが得られる。計算量は O(N)になる。