オンサイトで未確認

ukuku09の活動記録。

AtCoder Beginner Contest 023 D: 射撃王

ABC埋め。

 

問題文

abc023.contest.atcoder.jp

解法

制約的に $O(NlogN)$ くらいかなぁってなるので、二分探索をする。

風船のペナルティの最大値を x とすると、各風船がそこに到達するまでの時間は、

$$T_i = (x - H_i) / S_i$$

で求められる。あとは、この時間が短い順に全ての風船を N 秒間で割っていった時に、各風船 i を Ti 秒以内に割ることができるかどうかを見てやるだけでいい。

解の取りうる最大値が大きいので一見やばそうに見えるけど二分探索は神なので余裕。

結局 $O(Nlog(max(H_i+S_i*N)))$ くらい。

 

AtCoder Beginner Contest 051 D: Candidates of No Shortest Paths

ABC埋め中。

 

問題文

abc051.contest.atcoder.jp

解法

Warshall-Floyd で全頂点間の最短経路を求めて、与えられたエッジの端点間の最短経路重みがエッジの重みより小さくなっているかどうかを判定するだけで、そのエッジがグラフ上のいずれかの最短経路上に含まれているかどうかがわかる。

ある辺 i の端点を ai, bi、辺の重みを ci とすると、ai-bi 間の最短経路の重みは $x \leq c_i$ を満たす。$x = c_i$ の時、辺 i は ai-bi 間の最短経路になりうる。$x < c_i$ の時、明らかに ai-bi 間の最短経路に辺 i は含まれない。また、グラフ上のある2頂点 ui, vi 間に辺 i を含む最短経路がある仮定すると、その重みはある整数 w を用いて $w + c_i$ と表すことができる。しかし、ai-bi 間の最短経路の重みは $x < c_i$ より、 $w + x < w + c_i$ なので、辺 i を ai-bi 間の最短経路に置き換えることでより短い経路を得ることができる。これは仮定に反するので、ai-bi 間の最短経路が辺 i を含まない時、グラフ上のどの2頂点間の最短経路上にも辺 i は含まれないと言える(数学ができないのでガバガバ証明でごめんなさい)。

計算量は Warshall-Floyd が一番重くて $O(N^3)$。最後の判定の仕方が頭悪くてN2回してるのは秘密。

 

AtCoder Beginner Contest 054 D: Mixing Experiment

2月なのでABC埋め。記事は自分用なのであんまりタメにならなそう。

 

問題文

abc054.contest.atcoder.jp

 解法

制約がそんなに大きくないので01ナップザックっぽく解いた。

dp[i][j][k]:=薬品 i-1 まででタイプAが j グラム、タイプBが k グラムの溶液を作る最小金額としてDPする。01ナップザックだから、配列を使いまわすと遷移が

$$dp[j][k] = min(dp[j][k], dp[j-a[i]][k-b[i]] + c[i])$$

みたいに書ける。あとは j:k=Ma:Mb を満たす dp[j][k] のなかの最小金額を求めて終わり。ただし、j=0, k=0 に気をつける(自明。 $O(N^3max(A_i)max(B_i))$ で $1 \leq N \leq 40$、$1 \leq a_i,b_i \leq 10$ なので十分間に合う。

実装は面倒臭かったので $Nmax(A_i)$ と $Nmax(B_i)$ の取りうる最大値(=400)でぶん回した。

 

余談

$N \leq 40$ を見たら半分全列挙というのがあるらしいけど、頭が悪かったのでその発想には至らず。まあ制約が小さかったし多少わね?

ごどく部活動記録【海外遠征編】ACM-ICPC 2016 バンコク大会 参加記

初海外!初海外ですよ!!(ひきこもり並感

 

ということで、ごどく部の遠征も兼ねて、ICPCバンコク大会に参加してきました。

 

バンコクの黒板w」

「なんかそれすごく惜しい感じがする」

「はい。」

www.acm-icpc.eng.chula.ac.th

 

続きを読む

ACM-ICPC 2016 国内予選 敗戦記

先日のICPC国内予選に、チームmochinochaの一員として参加しました。

結果は4完26位、惜しくも予選敗退でした。。。

 

国内予選の順位表はこちら↓

順位と結果 | ACM-ICPC 2016 Asia Tsukuba Regional

 

続きを読む