ABC226 参加記録
コンテスト中AC:A〜E
こちらの解説は独自の見解であり、間違った情報を含む場合があるのでご注意ください。
B - Counting Arrays
公式解説の方法をC++のstringで実装したところTLEしました。色々な処理が必要な場合、stringはかなり遅いようです。
第一選択はvectorとしておくのが良さそうだと思いました。
提出コード:https://atcoder.jp/contests/abc226/submissions/27113166
C - Martial artist
技を頂点、を有向辺とみなしたグラフをDFSすることで解けます。
具体的には、
技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による値の挿入が、最大公約数を求める部分が、になると思うので、全探索のを考慮しても間に合います。
提出コード:https://atcoder.jp/contests/abc226/submissions/27100607
E - Just one
長くなったので別記事へ。