CODE THANKS FESTIVAL 2018(Parallel)
残念ながらCODE FESTIVALの本戦には参加できなかったのでオープンコンテストに参加しました。300点以下しか解けずA, B, C, Dの4完でした。
使用言語: C++
A - Two Problems
配点が なので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)とする。
- のときを考える。
箱を空にする方法があるとき(1)は(2)より 回多く行う。残りは(1)と(2)を同じ回数だけ行って取り出す。
なので が偶数かをまず調べる。そして が4で割り切れるか判定すればよい(コンテスト中は念のため についても調べた)。
- のときも同様。
#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
絶対値が消えそうなのでとりあえず を昇順にソートする。求めるコストを とすると
と書けるので(差分計算か累積和を用いると) で求められる。
#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; }