izumo’s diary

主に競プロの精進記録

CODE THANKS FESTIVAL 2018(Parallel)

残念ながらCODE FESTIVALの本戦には参加できなかったのでオープンコンテストに参加しました。300点以下しか解けずA, B, C, Dの4完でした。

使用言語: C++

A - Two Problems

問題

配点が B \leq D なので1, 2問目を解く場合、2問目を解く場合、1問目を解く場合について時間内に解き終わるか調べる。

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t, a, b, c, d;
	cin>>t>>a>>b>>c>>d;
	int ans=0;
	if(a+c<=t){
		ans=b+d;
	}
	else if(c<=t){
		ans=d;
	}
	else if(a<=t){
		ans=b;
	}
	cout<<ans<<'\n';
	return 0;
}

B - Colored Balls

問題

問題文の上の操作を(1)、下の操作を(2)とする。

  • X \leq Y のときを考える。

箱を空にする方法があるとき(1)は(2)より k \left( \geq{0} \right) 回多く行う。残りは(1)と(2)を同じ回数だけ行って取り出す。
k=\frac{\left( Y-X \right)}{2} なので Y-X が偶数かをまず調べる。そして X-k が4で割り切れるか判定すればよい(コンテスト中は念のため Y についても調べた)。

  • X > Y のときも同様。
#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int x, y;
	cin>>x>>y;
	bool ok=true;
	if(x>y){
		swap(x, y);
	}
	int z=y-x;
	if(z&1){
		ok=false;
	}
	else{
		int k=z>>1;
		x-=k;
		y-=k*3;
		if(x<0 || y<0){
			ok=false;
		}
		if(x&3 || y&3){
			ok=false;
		}
	}
	cout<<(ok ? "Yes" : "No")<<'\n';
	return 0;
}

C - Pair Distance

問題

絶対値が消えそうなのでとりあえず \{x_i\} を昇順にソートする。求めるコストを C とすると
\begin{eqnarray} \begin{split} C &=& \left( x_N-x_{N-1} \right) + \left( x_N-x_{N-2} \right) + \ldots + \left( x_N-x_1 \right) \\ &\quad& + \left( x_{N-1}-x_{N-2} \right) + \left( x_{N-1}-x_{N-3} \right) + \ldots +\left( x_{N-1}-X_1 \right) \\ &\quad& \vdots \\ &\quad& + \left( X_2-X_1 \right) \\ &=& \sum_{i=2}^{N} \{ \left( i-1 \right) \times x_i - \sum_{j=1}^{i-1}x_j \} \end{split} \end{eqnarray}
と書けるので(差分計算か累積和を用いると) O(N \log{} N) で求められる。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(int i=0; i<(n); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	ll x[114514];
	cin>>n;
	ll sum=0;
	REP(i, n){
		cin>>x[i];
		sum+=x[i];
	}
	sort(x, x+n);
	ll ans=0;
	FORR(i, 1, n){
		sum-=x[i];
		ans+=i*x[i]-sum;
	}
	cout<<ans<<'\n';
	return 0;
}

D - Concatenation

問題

Sの前から元の文字列で先頭になるか見ていくだけ。これは200点では

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	cin>>s;
	int top=s[0]-'a', ans=1;
	FOR(i, 1, s.size()){
		if(top>=s[i]-'a'){
			top=s[i]-'a';
			++ans;
		}
	}
	cout<<ans<<'\n';
	return 0;
}

E~H

E問題を30分くらい考えたがさっぱり分からず。順位表をみるとF以降はさらに難しそうなのでここで撤退。

E問題
F問題
G問題
H問題