大爆死したり試験期間中だったりして、前回・前々回と参加記が書けなかった。 今回は試験期間も終わり遅い夏休みに突入し、なおかつ超好成績だったので参加記が書ける。
結果
16分5完1ペナで254位という超好成績。 ここまで早解きが極まると凡ミスによるペナルティ1つによってタイムが1.3倍にもなってしまう。 ペナルティ覚悟でバンバン提出しているからこそのこのタイムでもあるのだが、少し慎重にならないといけない。
A - Don’t be late
$D/S\leq T$を判定すれば良いのだが、誤差が怖いので式変形して$D\leq ST$にする。
提出 #16305153 - AtCoder Beginner Contest 177
B - Substring
$S$の長さ$|T|$の部分文字列ひとつを取り上げて、それが$T$になるためには何文字書き換えればいいか？ という問題は部分文字列と$T$の各文字を比較すれば$O(|T|)$で解ける。 その問題を$S$の長さ$|T|$の部分文字列全てに対して解いて、答えの最小値を求めればよい。
計算量は$O(N^2)$であり、文字列の長さが最大$10^3$なので間に合う。 $S$の部分文字列を列挙する部分をバグらせてペナルティを出してしまった。
提出 #16316230 - AtCoder Beginner Contest 177
C - Sum of product of pairs
答えの$\sum_{i=1}^{N-1} (\sum_{j=i+1}^N A_iA_j)$は、$\sum_{i=1}^{N-1} (A_i\sum_{j=i+1}^N A_j)$と式変形できる。 $\sum_{j=i+1}^N A_j$を$O(1)$で計算する方法を考えれば$A_i\sum_{j=i+1}^N A_j$が$O(1)$で計算できるようになる。 これは累積和を使うことで実現できる。 各$i$について、$\sum_{j=i+1}^N A_j$の答えを累積和で求めて$A_i$を掛けてやればよい。 これで全体の計算量が$O(N)$に落とせる。
提出 #16314461 - AtCoder Beginner Contest 177
D - Friends
友達関係にあるグループを全員違うグループに分けないといけない。 友達関係の連結成分の頂点数の最大値だけグループを作れば、 どの連結成分にいるメンバーも同じグループの中に友達がいない状況を作れる。 逆に、それより1つでもグループ数だと鳩の巣原理により最大連結成分のメンバーを割り振ることができない。 したがって、最大連結成分の頂点数を求めればそれが答えになる。 集合のサイズを求める機能の付いたUnionFindを使えば連結成分の頂点数を求められる。
提出 #16319699 - AtCoder Beginner Contest 177
E - Coprime
$GCD(A_i,A_j)=1$となる条件は、各数字を素因数分解したときに出てくる素数が被らないということである。
${A_i}$がpairwise coprimeなら、どの数字も他の数字と違う素数を使っているはずである。
$count[x] = 素因数にxが含まれるA_iの個数$のようなものを求めて、
すべての$x$に対して$count[x]\leq 1$なら${A_i}$はpairwise coprimeである。
$count[x]$を連想配列long[long]で実現したが、出てくる素因数は$10^6$以下になるし配列でも良かったかもしれない。
setwise coprimeの判定は定義どおり計算してやればいい。
計算量は各数字の素因数分解をするところがボトルネックとなり、だいたい$O(N\sqrt{N})$。
提出 #16326968 - AtCoder Beginner Contest 177
F - I hate Shortest Path Problem
どんなケースに対しても計算量を減らせるようなアイデアが出てこなかった。 16分でEまで解き終わった後に時間がたっぷりあったのでこの記事を書きながら考えていたがやはりわからない。