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