JOI2018/2019 予選
はい。
1問目
1週間まとめてえいってやろうとしたらWAしたので、1日1日ログインボーナスを取っていきました。
2問目
シュミレーションしていきましょう。
3問目
脳死でDPしました。
後で気づきましたが、貪欲で行けますね。
4問目
日本出現をしました。上から見ていきました。
■…陸 □…海だとして
□□□→□■□のときは島の数が1増え、■□■→■■■のときは島の数が1減り、それ以外は増減しません。
5問目
めっちゃバグをはやしまくって時間を溶かしました。2時間溶かしてます。ひどい。
とりあえず問題の区間を整理してソートして、DPをしていきました。
6問目
500点で通るやろ~~と思っていたし、時間もなかったのでなにもしませんでした。
感想
実装はやっぱり無理。
AGC027 B - Garbage Collector
考察
移動コストが\((k+1)^2\)なのが特徴的。
\((k+1)^2=1+3+5+\cdots+2k+1\)と変形してみる。
すると最初のごみがコスト5、次もコスト5、次は7、9、11、…
各ゴミについてそれをコストいくつで運ぶかは、何回捨てるかを決めると愚直にできる
あとは累積和を使って高速に計算
(long longでオーバーする場合があるのでそういう場合は排除しないとWA、なにそれ)
コード
#include <bits/stdc++.h> #define ll long long #define FOR(i,a,b) for(int i=a;i<b;i++) using namespace std; int f(int k){ if(k==0) return 5; else if(k==1) return 0; else return 2; } ll x[200001], x2[200001]; int main(){ int n,X; cin>>n>>X; FOR(i,0,n) cin>>x[i]; x2[0]=x[0]; FOR(i,1,n) x2[i]=x2[i-1]+x[i]; ll m=1e18; FOR(k,1,n+1){ int t=0; ll ans=0; while(n-1-t*k>=0){ ans+=f(t)*x2[n-1-t*k]; if(ans>m) break; t++; } if(ans>m) continue; ans+=(ll)X*(n+k); m=min(ans,m); } cout<<m<<endl; }
PCK予選2018
初めての記事です。
競技プログラミングを今年の4月から始めたので、それらについて書ければと思います。
パソコン甲子園(PCK)予選に参加しました。
問1~5を相方がやって、問6~8の考察を僕がやって、問9を2人で考えるみたいな感じでした。
問1~5
やるだけ
(問4でWAをたくさん生やした。。。)
問6
あってる個数をカウントする形でやればいい
問7
普通にDP
問8
後ろからpriority_queueに突っ込むだけ
問9
2点を通る直線を全部列挙してソートして確かめる
一回mapでやってTLEしてソートにしたら通った
結局9完9WAでした(WAが多い)
問10~を解いてる人すごいですね…精進します