DISCO presents ディスカバリーチャンネルコードコンテスト2020 予選
当日参加だったのでまとめて記事書きます
時間は、コンテスト開始からの総計です
A提出AC 3:16
B提出AC11:14
C提出AC63:06 + 1WA (=68:16)
A問題
ちょっとめんどくさかった
int main() { cout <<setprecision(10); int x ; int y; cin >> x >> y; int three = 100000; int two = 200000; int one = 300000; int ans = 0; if(x <=3 ){ ans += (4-x) * 100000; } if(y <= 3){ ans += (4-y) * 100000; } if(x==1&&y==1) ans += 400000; cout << ans << endl; }
これ、 three two one みたいなのは、1位のときは one を使う みたいな感じにしたんですけど、使ってないです。
そこそこ綺麗なコードじゃないですか。
ちなみに他人のコード見て賢いと思ったのは
↓
ans += max(4-x,0); ans += max(4-y,0); ans *= 100000; //とさらに、両方1位だったら40万を足す
A問題解法
それぞれ3位以下なら賞金が貰える、
貰える額は1位なら30万 2位なら20万 3位なら10万ってかんじなので
10万の位は(4-x)（か、4-y)になっている
で両方1位なら40万を＋する。
B問題
int main() { cout <<setprecision(10); ll n; cin >> n; vector<ll> v(n); rep(i,n) cin >> v[i]; vector<ll> Left(n+1); vector<ll> Right(n+1); Left[0] = Right[0] = 0; rep(i,n){ Left[i+1] = Left[i] + v[i]; } rep(i,n){ Right[i+1] = Right[i] + v[n-1-i]; } reverse(Right.begin(),Right.end()); ll minlen = INF; rep(i,n+1){ ll thi = abs(Left[i] - Right[i]); chmin(minlen,thi); } cout << minlen << endl; }
B問題解法
切る前の棒の左側の部分と、きる前の棒の右側の部分が近くなるようにすればいい。
あるところまでの左側の長さは累積で求めると計算量が減らせていいね。
でぼ右からの累積（Rightの部分）も作ったんですけど、よく考えたらこれはいらないですね。
（なぜなら右側の長さは、全体の長さ - 左側の長さで求められるので）
累積を作成したら、全体の長さ - 左側の長さの絶対値が最小になるときが答えです。
で、この絶対値を k とかってしたら
片方をk伸ばすかk縮めるかなんですけど、コストはどちらも変わりませんね。
k縮めるってときも、絶対そのように棒を縮めることはできます。
ただこっちはちょっと「ん～？1より小さくできないんでしょう？本当にk縮めることはどんなときでもできるのかな？」ってなる人もいいるかもしれないですね。まあいけるんですけど
ただ、この縮めるが分からなかったら、小さい方をk伸ばすって考えればいいと思います。
そしたら絶対できるって分かると思う
C問題
nt main()
{
cout <<setprecision(10);
ll h , w, k;
cin >> h >> w >> k;
vector<string> field(h);
rep(i,h){
cin >> field[i];
}
vector<vector<ll>> ans(h, vector<ll> (w));
//入力ok.それぞれのfieldは、次の#が出てくる手前までの区画でやればいい
//イチゴがない場所を覚えておく
vector<bool> ichigo(h,false);
//ichigo[i] = true のとき、i行目には苺がある
ll firstLine = -1;
rep(i,h){
rep(j,w){
if(field[i][j] == '#' ){
if(firstLine==-1){
firstLine = i; //イチゴが最初に出てきたのは何行目か。
ichigo[i] = true;
}else{
ichigo[i] = true;
break;
}
}
}
}
ll count = 0 ;
for(int i = firstLine ; i < h ; i++){//イチゴが出てきたラインから作
bool onetime = false;//行ごとに2回目出てくるまでは前の行＋1
//行が変わったとき、その行にイチゴがあるんだったら＋1
if(ichigo[i]) count ++;
rep(j,w){
if(ichigo[i] ==false){//イチゴがないんだったら、上のものをそのまま使う
ans[i][j] = ans[i-1][j];
}else{
if(field[i][j] =='#'&&onetime){
count ++;
ans[i][j] = count;
}
else if(field[i][j] == '#'){
ans[i][j] = count;
onetime = true;
}
else{
ans[i][j] = count;
}
}
}
//行が変わるごとに、その行にイチゴがあるんだったらカウントを++する
}
//firstline より前を構築していく
for(int i = firstLine-1 ; i >= 0 ; i --){
rep(j,w){
ans[i][j] = ans[i+1][j];
}
}
rep(i,h){
rep(j,w){
cout << ans[i][j] <<" ";
}
cout << endl;
}
}
C解法
別に、苺が載ってる部分の大きさはどうでもいいので、小さくてもいいや！みたいな感じで切り分けます。
左上から順に切り分けていこうって考えました。
苺が最初に出現するまでは基本的に1で埋めればいいんですけど、長方形に切り分けるっていう制約から、それだけだと少しうまくいかない。
とりあえず横だけで見たとき、
...#..
なら
111111って感じで全部同じ区画にできる
.#..#.
111122
もしくは
112222
ってなる
僕は111122の解法です
苺が存在しない行について考えます
.#..#.
...... のとき
111122上の行
111122下の行
とやれば長方形に切り分けられています。
下の行は、苺が存在しない行で、これは上の行をコピーすればうまく長方形の区画に分けられることが分かりました。
ただし、これだけでは少し足りません。下の様なものを見てください
......
..#..
のとき、苺が出てこない行は、上のものをコピーできません。
そこで、2行目のをfirstLineとして、そこから区画を分けていくことにして、
firstLineよりも上の行については、下の行をコピー、つまりfirstLineの行をコピーすればいいです。
するとまず
??????
111222になり
そのあと
で
111222
111222
っていう風に作れます！！！
