だま、競プロなど

プログラミング、主に競技プログラミングについて書きたい

JOI2018/2019 予選

はい。
f:id:yootaamath:20181209201335p:plain

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~を解いてる人すごいですね…精進します