PCK2018よせん解説
解説を!!!するぞ！！！
難易度よそう 1?2?3<<4<<6<5,7,8<9,11<10<<<<<<(エアーズロック3個分)<<<<12
1~3本当にみてない。まあ適当にやって。
ではひどいので、相方が解説を書いてくれました。ありがとう！🙂http://kubokubokun.hatenablog.com/entry/2018/09/20/151529
4 ボトルを買うやつ
if文を頑張るのだが、工夫すると単純でバグりにくい。
変数名確認、aが1Lの値段、,bが500mLの値段、xミリリットル必要 だよね、解法はこうなる
x= (x+499)/500; //500で割って繰り上げしている
a=min(a,b ＊2); //これでa一本よりb二本が安いなら自動的にそうしている
if(x%2==0){cout＜＜a ＊ (x/2) ＜＜endl;}//端数がない
else{cout＜＜a＊(x/2)+b＜＜endl;}//B端数がある
5 でぅーどにー数
解は ,ある自然数zに対し、zのn乗の形になるので、zを全探索。するとO( 108 のn乗根 * 桁和を求めるlog ) なので、2<=nの条件により高速に解ける
6 ぼぞそーと
ソート済みの配列といくつ一致しているか持っておいて、それがnになったときがこたえ。
7 ワープ装置
星に入るのか装置に入るのかでinとoutがこんがりませんか?
各文字cについて、それまでcに入るのが何通り?でdp。典型。
8 たくしー
条件を整理すると、こうなる
乗せる客を選ぶ。ただし各i 1<=i<=nに対して、i番目以下の乗り場の合計には、i人以下しか載せられない。
この条件に変形したら、優先キューで低い人を自明においだすだけ。
9 直線状の点
これなぜか苦労した。点を固定して、同じ傾きを通る点がほかにK-1個ありますか?を既約分数とunordered_mapで確認した。
n<=3000で、O(n2)でunordered_map,こわくないですか？こわいね(一応5秒ぐらいあったはず).
10 ダンジョン2
ダンジョン2、JOIにも全く同じ問題名がある。問題になりすぎでは?
とりあえず通った場所は部分木、辺を通った回数は、それがスタートとゴールの間のパスなら1度、else 2度
それを変形をして、スコア=Σ(各部屋のスコア-2) + スタートtoゴールのパスの長さ +2にする。
解法 木dpをする。dp[a]=aの部分木でスタートとゴールが木の子の中にない
ep[a]=スタートゴールのパスの片方だけが子に含まれる場合の、dp[a]に対するスコアのボーナス
fp[a]=スタートゴールのパスの両方が子に含まれる場合の、dp[a]に対するスコアのボーナス
さいしょの提出ではfpがなくて、WAした。 おばか。(当社比)
11 円盤
操作がセグ木に乗ります。ではあまりにひどいので解説します。
まず見ると、flipした状態では通常に比べて操作が反対向きになる。
よって、struct sousa{bool flip;long long int rota;};を考える、flipはそのままの意味、rotaはその数だけ回転するということ。
ただし、回転させてからflipをすることにする。
すると、sousa L,R,X;があって、XにはLをしてからR を乗せるとする。すると
X.flip= L.flip ^ R.flip;
if(L.flip){X.rota= L.rota+R.rota;}else{X.rota=L.rota-R.rota;}
とすると、操作の合成ができる。これをセグ木に乗せて、出てきたものを適当に円盤の場所に対応させて完成。
12
PCKにおいて、予選最後にHL分解がくるの、去年もだった。
実装が重すぎて50分ではとてもとけない。さよなら～
