NOMURAコンテスト振り返り

NOMURAプログラミングコンテストの振り返りをします。

結果は6分A,B2完でレートが少しだけ上がりました。

C問題が解けなかった敗北感しかなかったです。

A問題

A - Study Scheduling

起きている時間のうち最後のK分間以前に勉強を始めれば良いので、起きている時間からKを引くことでかけます。

int main(){
 ll a, b , c, d; cin >> a >> b >> c >> d;
 ll time = c * 60 + d - a * 60 - b;
 ll k; cin >> k;
 ll ans = time - k;
 cout << ans << endl;
}

B問題

B - Postdocs

‘?’を’P’ or ’D’に変更することで文字列’PD’と ‘D’の総和を最大化したいです。
全ての’?’を’D’にすることで条件を満たします。

もし’D’にしたところを’P’にして’PD’を増やしてもその分’D’が減ってしまうからです。

int main(){
 string s; cin >> s;
 ll N = s.size();

 ll cnt = 0;
 rep(i,N){
   if(s[i] == '?'){
     s[i] = 'D';
   }
 }
 cout << s << endl;
}

C問題

C - Folia

二分木のそれぞれの深さの葉の数が与えられる中で頂点の数を最大化したいという問題です。

出来るだけ頂点の数を増やしたいので、出来るだけ多くの頂点をそれぞれの深さで持ちたいです。

しかし、それぞれの深さでの頂点数は以下の2つによる制約を受けます。

1. 深さ0から最も効率よく頂点を増加させた時の値
2. 深さNから最も効率よく頂点を増加させた時の値

1に関しては葉でない頂点数の2倍を一つ先の深さに持ち越すことができ、2に関しては一つ前の深さの葉の数を持ち越すことができます。

int main(){
 ll N; cin >> N;
 vector<ll> a(N + 1); rep(i,N + 1) cin >> a[i];
 vector<ll> sum(N + 5);
 for(ll i = N + 1 ; i > 0 ; i --){
   sum[i - 1] = sum[i] + a[i - 1];
 }
 // 1こ上の深さでの葉でない頂点の個数の2倍
 vector<ll> v(N + 5 , 1e18); v[0] = 1;
 if(a[0] > 1){
   cout << -1 << endl;
   return 0;
 }
 rep(i,N){
   v[i + 1] = 2 * (v[i] - a[i]);
   if(v[i + 1] > 1e16) break;
   if( ( i + 1 < N and v[i + 1] < 1 ) or v[i + 1] < a[i + 1] ){
     cout << -1 << endl;
     return 0;
   }
 }

 ll ans = 0;
 rep(i,N + 1){
   ans += min(v[i] , sum[i]);
   // cout << i << " " << min(v[i]  , sum[i]) << " " << a[i] << endl;
 }
 cout << ans << endl;
}

アドバイスなどあればぜひお願いします。