読者です 読者をやめる 読者になる 読者になる

beet's soil

競プロのことなど

Google Code Jam 2017 Qualification Round

5869th 50p とりあえず通過。

【Problem A. Oversized Pancake Flipper】

S枚のパンケーキが裏か表かの状態が与えられる。
一回の操作でちょうどK枚の連続したパンケーキをひっくり返すことができる。
全て表にすることができるなら操作の最小回数、できないなら-1を出力する。

なんか前から貪欲。右端を固定した時に同じ箇所を二回以上ひっくり返すのは明らかに無駄なので。
O(SK).

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int T;
  cin>>T;
  for(int t=1;t<=T;t++){
    cout<<"Case #"<<t<<": ";
    string s;
    int k;
    cin>>s>>k;
    int n=s.size(),ans=0;
    for(int i=0;i<=n-k;i++){
      if(s[i]!='+'){
	ans++;
	for(int j=0;j<k;j++){
	  if(s[i+j]=='+') s[i+j]='-';
	  else s[i+j]='+';
	}
      }
    }
    bool f=1;
    for(int i=0;i<n;i++) f&=s[i]=='+';
    //cout<<s<<endl;
    if(f) cout<<ans<<endl;
    else  cout<<"IMPOSSIBLE"<<endl;
  }
  return 0;
}
【Problem B. Tidy Numbers】

各桁を項とする数列が講義単調増加列になっているような数をtidyであると定義する。
N以下の最大のtidyな数を求める。

下から貪欲。ある桁を1減らせばそれ以降の桁は全て9にできるのでそれがtidyになっているか調べればいい。
O(logN).

#include<bits/stdc++.h>
using namespace std;
#define int long long
bool check(string s){
  if(s[0]=='0') return 0;
  for(int i=0;i<(int)s.size()-1;i++)
    if(s[i]>s[i+1]) return 0;
  return 1;
}
string comp(string s1,string s2){
  return stol(s1)>stol(s2)?s1:s2;
}
signed main(){
  int T;
  cin>>T;
  for(int t=1;t<=T;t++){
    cout<<"Case #"<<t<<": ";
    int n;
    cin>>n;
    string s=to_string(n);
    if(check(s)){
      cout<<s<<endl;
      continue;
    }
    string ans;
    for(int i=0;i<(int)s.size()-1;i++) ans+="9";
    for(int i=0;i<(int)s.size()-1;i++){
      s[s.size()-1-i]='9';
      s[s.size()-2-i]--;
      if(check(s)) ans=comp(ans,s);
    }
    cout<<ans<<endl;
  }
  return 0;
}
【Problem C. Bathroom Stalls】

largeは解けず。

N+2個の椅子があって、両端には監視員が座っている。
ある人が新しくその場所に来た時、以下のルールで席に座る。

全ての座席について、左,右側に座っている人までの距離をそれぞれl,rとする。
min(l,r)が大きい順、同じものがある場合はmax(l,r)が大きい順、それも同じならなるべく左側に座る。

K人の人が来た時の最後に座った人のmax(l,r)とmin(l,r)を求める。

priority_queueで愚直にシミュレーション。
関係があるのは区間の長さだけで、長いものから選ばれるのは自明。
よって取り出して二つに分けて入れる操作を繰り返せばいい。
O(KlogK)

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int T;
  cin>>T;
  for(int t=1;t<=T;t++){
    cout<<"Case #"<<t<<": ";
    priority_queue<int> q;
    int n,k;
    cin>>n>>k;
    q.push(n);
    int p,l,r;
    for(int i=0;i<k;i++){
      p=q.top();q.pop();
      l=(p-1)/2;
      r=(p-1)-l;
      q.push(l);
      q.push(r);
    }
    cout<<r<<" "<<l<<endl;
  }
  return 0;
}