ARC083 参加記録
レート爆上げ(のあとにやってくるのは...)
いつも急降下です。なふもん知ってるんだから!!!!!
さて、昨日の問題復習しましょう。
AtCoder Regular Contest 083
ですが、ABCのA、Bも一応書きます。
軽く感想
ABCのBが日本語読めず10分使って焦りました。
Cが全探索の機運でしたが溶けず(これは誤字ですが掛かったので良しとします)
Dをときました(31分)
もう一回言いますよ
500点問題のDを31分でコンテスト中に解きました!!!!!
半年前は無理無理とか言ってたくせに解けました!!!!
成長を感じました(調子に乗ってますごめんなさい)
...あとは下がるだけですね。
軽く解説
A問題:Bichrome Cells
N*Nマス-Aマスで答え。
B問題:Collecting Balls (Easy Version)
これ日本語難しすぎた(ながら作業してるのが悪い)
これ結局はロボットAとBのどっちがボールの位置に近いですかってそれだけの話しです。
距離なので差を取って絶対値 |A[i]-K|とA[i](0からの距離)を比べるといいですね。
ただこれは注意点があって、片道分しか計算してないので2倍しましょう。
ans+=std::min(abs(A[i]-K),A[i])*2;
C問題:Sugar Water
問題要約。
- 操作4つできます。
- 水を100*A or 100*B入れるもしくは砂糖をA,Bで入れる。
- これをやって一番濃い砂糖水を作りましょう!
- ただし100に溶ける量は決まってます、溶け残ってはいけません
- 重さ制限もあります。
中学受験かな!!!!!!
解法要約。
- A、Bの値をFの大きさを超えるまで全探索してSetにInsertします(重複の可能性があるので)
- C、Dについても同じことをします
- その中で各水の量、砂糖の量を全部回してみて、濃いものを保持して、お終い
- %を出すときの割り算掛け算、doubleにしないと死にますので気をつけて
- 砂糖を入れることが不可能な場合は適当に水を入れて、砂糖0とやるとうまくできます。
D問題:Restoring Road Network
概要。
- 全部の頂点に行くときの最短経路の和がほしいらしい。
解法
- ワーシャルフロイドを書きます。
- 二行追加しましょう。
- ワーシャルでminを取る時があると思いますが、そこで更新が起こったら-1です。
うまく弾きましょう。 - 次に、経由点がスタート地点、ゴール地点以外のところで、直接行く距離と同じ物があったらその頂点のFlagをtrueにします。
- それだけ書いたらあとはFlagがfalseのところだけ足して終わりです。
- (隣接行列なので三角形型に足しましょう)
ソースを見るとわかりやすいと思うので読んでいただきたさがある。
Submission #1597702 - AtCoder Regular Contest 083 | AtCoder
おまけ、レートのお話
959 -> 1041 (+82) Highest!!!
完全復活と思った時期がありました。
次でレートグラフはまたバスタブを描き始めますのでよろしくです。
(今回は二回目のバスタブが終わったところですね....)