AtCoder Beginner Contest 060 - AtCoder
バチャ参加、3完
A
a[(int)(a.size())-1]==b[0]
&&b[(int)(b.size())-1]==c[0]
の判定するだけ、簡単なお仕事
.back()を使う方が楽かもしれない
どちらにしろ大して時間は変わらない
O(1)
B
これは逆に考える
x=b+cとおいて、xにbを何度も足した時、aで割りきれるかを検証すれば良い
ここで重要なのがどこでそのループを切るかだが、最初のx%aを記録しておき、同じものがもう一度出てきたら切れば良い
これは、(a+1)b+c≡b+c(mod a)ということから証明ができる。すなわち、計算量はO(a)となる
ただ、想定解はaからbaループだったらしい
まあどちらでもよいということで
C
前のとの差がTを越えるならTを、そうでないなら差を合計にプラスしていくだけ
最後にTを足すのを忘れずに
O(N)
D
解けなかった、理解はしておく
よくあるナップザック問題
だが、重さDP、価値DPともに桁が大きすぎるので不可能、ありえへん制約
ここでw1<=wi<=w1+3という制約があるので重さが4種類しかないことがわかる、従って、kの種類という考えでいくと0<=k<4でおける
さらにNが100個しかないので、恐らくDPもしくは全探索に使える、ここでは重さの組み合わせが最悪でも25^4で4*10^5くらいなので全探索も余裕
よって、あり得る重さの組み合わせについて全列挙し、それらの中からもっとも価値が高いものを選べば良い
重さの組み合わせについて、同じ重さの中では価値の高い順に抽出していく、従ってソートした方がいいかもしれない(まだ実装してない)
何か酷いこと？があったとしてもO(10^7)くらいなので間に合う、えでぃとりあるに書いてあったのを見るにそれぞれの重さについて累積和を求めておけばそれこそO(4*10^5)で終わるみたいね
展望
Cまで16分で解けたのでまあ簡単なのは頑張りたい
Dとか解けるようになりたい
