beet's soil

競プロのことなど

Mujin Programming Challenge 2017

賞金チャレンジ(そんなものはない)。

【A - Robot Racing】

1個おきに置いていくと前にある個数+1がそのロボットの順番の候補になる。
それぞれのロボットに対していい感じに独立なので前から順番にかけていけばいい。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  int x[n+1];
  for(int i=1;i<=n;i++) cin>>x[i];
  x[0]=-1;
  int ans=1,s1=0,s2=1,MOD=1000000007LL;
  for(int i=1;i<=n;i++){
    if(x[i-1]+2<=x[i]) x[i]=x[i-1]+2,s2++;
    (ans*=min(i-s1,s2))%=MOD;
    if(x[i-1]+2>x[i]) s1++,x[i]=x[i-1];
  }
  cout<<ans<<endl;
  return 0;
}
【B - Row to Column】

コンテスト中に書いたBFS解(部分点解法)。
やるだけ。

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef vector<string> vs;
typedef pair<int,vs> P;
signed main(){
  int n;
  cin>>n;
  vs s(n);
  for(int i=0;i<n;i++) cin>>s[i];
  if(n>3) return 0;
  bool f=0;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      f|=s[i][j]=='#';
  if(!f){
    cout<<-1<<endl;
    return 0;
  }
  int ans=1000;
  queue<P> q;
  q.push(P(0,s));
  set<vs> sv;
  while(!q.empty()){
    P p=q.front();q.pop();
    int d=p.first;
    vs t=p.second;
    if(sv.count(t)) continue;
    sv.insert(t);
    bool ff=1;
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
	ff&=t[i][j]=='#';
    if(ff){
      ans=d;
      break;
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	vs nx=t;
	for(int k=0;k<n;k++) nx[k][j]=t[i][k];
	q.push(P(d+1,nx));
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}


満点解法
ある行を真っ黒にしてしまえばあとはそれを白いマスがある列に対してコピーすればいい。
ある行を真っ黒にするためにはその行の白いマスの数に、
対応する列に黒がない場合は1を足した回数が必要になる。
なんかもっとうまくできそうな感じがするんだけどよく考えるとこれが最適だということがわかる。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  string s[n],t[n];
  for(int i=0;i<n;i++) cin>>s[i];
  bool f=0;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      f|=s[i][j]=='#';
  if(!f){
    cout<<-1<<endl;
    return 0;
  }
  int ans=2*n;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++) t[j]=s[j];
    bool ff=0;
    for(int j=0;j<n;j++)
      if(t[j][i]=='#') ff=1;
    int tmp=!ff;
    for(int j=0;j<n;j++)
      if(t[i][j]=='.') tmp++;
    for(int j=0;j<n;j++){
      bool fff=0;
      for(int k=0;k<n;k++) fff|=t[k][j]=='.';
      tmp+=fff;
    }
    ans=min(ans,tmp);
  }
  cout<<ans<<endl;
  return 0;
}
【全体】

1完+部分点 256th
1935 -> 1934 (-1)
Bの満点思いついてたけどそんなわけないやろと思ってしまった。
まあ解説見ながら書いたらバグったので実力が足りてないですね。
A取れたのは嬉しいけど900はない気がするなあ(調整されてそう。