naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Regular Contest 090

起きてたので久しぶりにARCに出た
二完でレート落ちるかと思ったけど微増(1607→1616)
パフォーマンス的には1686
f:id:n4_t:20180129030938p:plain

C - Candies

この問題なんでこんなに制約ゆるいんだろうと思いながら
1行目accumulate
2行目左からと上からの良い方を取りながらのDP
編集距離みたいな計算で
AC
https://beta.atcoder.jp/contests/arc090/submissions/2027640

D - People on a Line

Union-Findで島分けして
隣接リストを作って
未訪問ノードをキューに入れて整合性をチェックしていった
島ごとにvector<int>(100000) をアロケートしていて最悪ケースでTLEしてた
それ1回でいいしグローバルに置いてしまって
AC
https://beta.atcoder.jp/contests/arc090/submissions/2030899
(島分けしなくても行けるはず)

E - Avoiding Collision

グラフー最短経路ーすれ違いー
パス

F - Number of Digits

可能性は感じたけど
時間内には辻褄が合わなかった

L桁からH桁まで、というのをL=1から順に考えていく感じ
k桁の数字はp(k)=9\cdot10^{k-1}個ある
L<Hの場合、L側とH側でいくつずつ使うか
\displaystyle Lx+Hy=S-\sum_{k=L+1}^{H-1}p(k)
の解が 1≦x≦p(L), 1≦y≦p(H) の範囲に何通りあるかを求める関数を書いててそこで終わった。(拡張ユークリッド互除法まではライブラリにあるけど)
その後バグを1つ潰して計算は合うようになったんだけど
S=10^8で8秒かかる
LについてはSを整数で割って行って可能性のあるところだけ見ればいい
あれ計算合わなくなった
ああ同じLを何回も見てた
そこ直したら計算が合うようになったので投げた
AC
https://beta.atcoder.jp/contests/arc090/submissions/2036531