ABC172E 類題: Complete permutation\(S_{N} := N\)次対称群， \(k \in N\) に対して，部分群 \(S_{N}^{k} := \{ \sigma \ \vert \ \sigma(k) = k \}\) をとる． 求めたいのは， \(\vert S_{N} - \cup_{k \in N} S_{N}^{k} \vert = \vert S_{N} \vert - \ver…

ABC166E 相異なる \(i,j \in N\) の組を数える． これは典型で，\(i < j\) として \(j\) の方を全探索する． それにより，今 \(j\) を探索しているとき，すでに \(i < j\) については すべて調べ終わった状態になるため． abs(j-i) = a[i] + a[j] より， j-i…

ABC181E 先生の身長を固定して考えて，\(h\) に追加しておく． このとき，ペアの作り方の最適解の一つは， ソートした \(h\) に対して先頭から貪欲に 2人ずつ組んでいく方法が挙げられる． それが解ければ，あとは先生の身長を全探索すれば OK. 前もって \(h…

ABC189E アフィン変換． 実装するときは，3次元の行列にした方が簡単． 行列は class にしておいた． 操作列は行列の列に対する積をとっておけばよい． つまり累積和を求めておけば，クエリ毎に O(3^3)で答えられる． ここで，3は行列の次数． 使っている記…