7K12 blog

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

AOJ ITP1_7_B 組み合わせの数

f:id:tkr987:20200611203516p:plain

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4570639

  •  O(N^3)を減算で O(N^2)に落とす定跡は低dif帯で頻出

f:id:tkr987:20200611204918p:plain

制約が緩いので3重ループ O(N^3)でもTLEしないと思うが、3個目の数は減算で確定するので2重ループ O(N^2)に減らす工夫も出来る。重複なしなので1個目の数iをrep(i, 0, N)でループさせたら2個目の数jはrep(j, i+1, N+1)までループさせる。重複なしなので各ループ開始インデックスと終端インデックスが1だけズレるので注意する。重複なしなので3個目の数が2個目の数jより大きいかどうか、n以下かどうか、の判定も必要。