geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC226 参加記録

コンテスト中AC:A〜E

こちらの解説は独自の見解であり、間違った情報を含む場合があるのでご注意ください。

B - Counting Arrays

公式解説の方法をC++のstringで実装したところTLEしました。色々な処理が必要な場合、stringはかなり遅いようです。

第一選択はvectorとしておくのが良さそうだと思いました。

提出コード:https://atcoder.jp/contests/abc226/submissions/27113166

 

C - Martial artist

技を頂点、A_{i,j}を有向辺e=(i,j)とみなしたグラフをDFSすることで解けます。

具体的には、

dp[u]:=技uを習得するのに必要な時間

とすると、

dp[u] \leftarrow dp[A_{u,1}]+dp[A_{u,2}]+...+dp[A_{u,K_u}]+T_u

なので、頂点Nから探索を開始し、dfs(u)でuの習得にかかる時間を計算した後、その値を親に返すことで解を得られます。

 

提出コード:https://atcoder.jp/contests/abc226/submissions/27096989

提出コードの276行目は不要です。なぜか、技Nに必要な技だけに訪問するような実装にしようとしていました。

 

D - Teleportation

問題文を解釈すると、全点対間の傾きを求め、重複の無いように記録していくことで解を得ることができます。しかし、傾きを実数で管理するのは誤差の問題から避けたいところです。

 

このような場合、例えばC++ではpairを使い、分子、分母をペアとして記録しておけば良いです。留意する点として、既約分数にしておく必要があります。例えば、(+4, +6)の移動は、(+2, +3)の移動を2回することで実現できますが、既約分数としていないと異なるペアとして記録されてしまいます。

既約分数を得る方法は、分子と分母の最大公約数gをユークリッドの互除法で取得し、分子/g、分母/gとすれば良いです。

 

傾きの記録はC++ならsetを使用できます。

計算量は、setによる値の挿入がlog(N^2)、最大公約数を求める部分が、log(min(|x_i-x_j|,|y_i-y_j|))になると思うので、全探索のN^2を考慮しても間に合います。

 

提出コード:https://atcoder.jp/contests/abc226/submissions/27100607

 

E - Just one

長くなったので別記事へ。