ICPC国内予選2013 A~D - Darseinのプロコン日記

2013年ICPC国内予選のA~Dまでの解説らしき何かを書きました。
問題はこちら

A

問題：
h×wの横長(h

対角線の長さが短い方が小さい
対角線の長さが等しければ、高さが短い方が小さい

与えられた長方形より大きい長方形の中で、最小のものを求めよ。

解法：
制約に「答えは150×150を超えない」とあるので、全探索すればよい。1ケースにつきO(150^2)。
pair p = make_pair(h*h+w*w (=対角線の二乗), h (=高さ));
とするとpairのデフォルトの<演算子が問題の大小関係に一致するので割と便利。
h

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;

typedef pair<int,int> P;

int main(){
  int h,w,answ;
  P ans,input;

  while(cin >> h >> w,h||w){
    input = P(h*h+w*w,h);
    ans = P(-1,-1);
    for(int i=1;i<=150;i++){
      for(int j=i+1;j<=150;j++){
	P tmp = P(i*i+j*j,i);
	if(input < tmp){
	  if(ans.first < 0 || tmp < ans){
	    ans = tmp;
	    answ = j;
	  }
	}
      }
    }

    cout << ans.second << " " << answ << endl;
  }
}

事前に全列挙しといてソートしておくことで二分探索する(upper_bound使う)方法もあるらしい。
頭いい。

B

問題：
ICPC形式のコンテストのログ(提出時間、チームID、問題番号、判定結果)がR(<=2000)個くらい流れてくるので、順位を出力せよ。

解法：
大まかに2パートに分けられて、前半が「ログから各チームの正答数とペナルティを復元する」、後半が「それらのデータから順位をつける」

「ログは時間順」かつ「正答後の問題へのサブミットはない」ので、前半はそのままログを読んでいき、各チームの各問題ごとの誤答数を記録しながら、正答したときにペナルティを計算して加算すればよい。

後半は比較関数をうまく作ればソートするだけ。
これも、vector team = {-solved, penalty, -id};としてこれの配列をソートしてやれば順位順に並ぶ。
出力形式が若干特殊だが、一個下の順位のデータと比較し、一致していれば"="、していなければ","を出力するだけでできて意外にお手軽。1ケースにつきO(TP + R + TlogT)。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef vector<int> vi;

int M,T,P,R;
int m,t,p,j;
vi team[60];
int pena[60][20];

int main(){
  while(cin >> M >> T >> P >> R,M){
    for(int i=0;i<T;i++){
      team[i].resize(3);
      team[i][0] = team[i][1] = 0; team[i][2] = -i-1;
      for(int j=0;j<P;j++)pena[i][j] = 0;
    }

    for(int i=0;i<R;i++){
      cin >> m >> t >> p >> j;
      t--; p--;
      if(j==0){
	team[t][0]--;
	team[t][1] += pena[t][p]*20 + m;
      }else pena[t][p]++;
    }

    sort(team,team+T);

    for(int i=0;i<T;i++){
      cout << -team[i][2];
      if(i==T-1)cout << endl;
      else{
	if(team[i][0] == team[i+1][0] && team[i][1] == team[i+1][1])
	  cout << "=";
	else
	  cout << ",";
      }
    }
  }
}

C

問題：
選挙が行われる。
選挙は選挙区ごとの投票からなり、各選挙区では過半数の得票を得た者が勝利する。
ただし、選挙区はグループの入れ子構造になっており、グループでの勝利者は、そのグループに含まれる過半数のグループで勝利した者である。
最終的に全体のグループで勝利するために必要な最小の得票数を求めよ。

解法：
選挙区情報は文字列で表されているので、構文解析を頑張る。

具体的には、ある選挙区情報を表す文字列sを入力として受け取り、その選挙区で勝つために必要な最小人数を求める関数が用意できればよい。
これを使うと、例えばsがs1,s2,...s(2n+1)という部分選挙区に分けられているとき、各結果r1,r2,...r(2n+1)をソートして前半n+1個を足した値がsに対する返り値になる、という再帰で書けることになる。

この手の構文解析では、僕は文字列の区間[l,r)を引数にした関数parse(int l,int r)を使い、文字列全体をグローバル変数sに置いておく、という実装をすることが多い。substrを使うかどうかとかはお好みで。
対応する括弧を求めるときに、「開いたままの括弧の数」カウンタ(ここではk)を用いるのは構文解析問題でよくやるテクニックなので覚えておくとよい。

制約上「すべての選挙区は奇数個の選挙区のみからなる」となっているので、過半数はv.size()/2+1で求まる。
計算量はちゃんと見積もってないけど、最悪時でもO(|s|^2)のはず。構文解析は計算量見積もらなくても大丈夫な(ように制約を調整している)問題が多いのであんま気にしてない。

#include<iostream>
#include<string>
#include<sstream>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;

typedef vector<int> vi;
int n;
string s;

int stoi(string x){
  stringstream ss(x);
  int res;
  ss >> res;
  return res;
}

int parse(int l,int r){
  bool f = true;
  for(int i=l;i<r;i++){
    if(!isdigit(s[i])){
      f = false;
      break;
    }
  }
  if(f)return stoi(s.substr(l,r-l))/2+1;

  int pos = l+1,k=1;
  vi v;

  for(int i=l+1;i<r;i++){
    if(s[i]=='[')k++;
    else if(s[i]==']')k--;
    if(!k){
      v.push_back(parse(pos,i));
      pos = i+2;
    }
  }

  sort(v.begin(),v.end());
  int res = 0;
  for(int i=0;i<v.size()/2+1;i++)res += v[i];
  return res;
}

int main(){
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> s;
    cout << parse(1,s.size()-1) << endl;
  }
}

D

問題：
1~mまでの数が渦巻き状に配置されている(さすがにこれ以上は文で説明しづらいので問題の図を見てください)
nから出発し、現在地の左下・真下・右下の3カ所に移動を続けることができる。
素数の位置に最大何回辿り着けるか。また、もしそのような経路が複数ある場合、最後に訪れた素数が最大になるような経路を求めよ。

解法：
基本的に3パートに分かれる。「素数判定の前処理」「渦巻き配置の作成」「最大値を求めるDP」

素数判定の前処理は、適当にエラトステネスの篩とかでboolの表を作っておく。O(m loglogm)。
この前処理はすべてのテストケースで共通なので、入力を受け取る前にm=10^6に対し作ってしまって使い回せばよい。

渦巻き配置はいろいろと方法があると思われるが、僕は「現在の進行方向左手を見て、まだ値が割り当てられていなければ左に曲がる、そうでなければ直進する」というコードを書いた。
盤面はだいたいsqrt(m)×sqrt(m)になるので、g[1010][1010]くらいの配列を使えば十分。ただし、初期位置を真ん中(=505)くらいにすることを忘れずに。忘れるとせぐふぉる。そのままO(m)。

最大値を求めるDPは、メモ化再帰を使った人が多いみたいだけど、僕はループで書いた。
pair dp[i][j] = i行j列目の位置にいるときに今まで辿ってきた素数の個数の最大値と、そのとき最後に見た素数のペア。
こうするとまた<演算子がそのまま答えの大小比較に使える。
現在地から[i+1][j+k-1](0<=k<=2)に対する所謂「配るDP」スタイル。
vis[i][j]で配られたところかどうかを判定することで、無駄な計算を省いた。O(m)。

#include<iostream>
#include<algorithm>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

typedef pair<int,int> P;

const int M = 1010, G = M/2;
int m,n;
int grid[M][M];
bool vis[M][M];
P dp[M][M];
int dy[] = {1,0,-1,0}, dx[] = {0,1,0,-1};

bool pt[M*M];

int main(){
  for(int i=0;i<M*M;i++)pt[i] = true;
  pt[0] = pt[1] = false;

  for(int i=2;i<=M;i++){
    if(pt[i]){
      for(int j=2*i;j<M*M;j+=i)pt[j] = false;
    }
  }
  
  while(cin >> m >> n,m){
    rep(i,M)rep(j,M){
      grid[i][j] = -1;
      vis[i][j] = false;
      dp[i][j] = P(0,0);
    }

    int y = G, x = G, d = 0;
    int sy,sx;
    rep(i,m){
      if(i+1==n){sy = y; sx = x;}
      grid[y][x] = i+1;
      int nxt = grid[y+dy[(d+1)%4]][x+dx[(d+1)%4]];
      if(nxt<0)d = (d+1)%4;
      y += dy[d]; x += dx[d];
    }

    vis[sy][sx] = true;
    dp[sy][sx] = P(pt[n],(pt[n]?n:0));

    P ans = dp[sy][sx];
    rep(i,M)rep(j,M){
      if(!vis[i][j])continue;
      rep(k,3){
	if(grid[i+1][j+k-1]<0)continue;
	vis[i+1][j+k-1] = true;

	P tmp = dp[i][j];
	int val = grid[i+1][j+k-1];
	if(pt[val]){
	  tmp.first++;
	  tmp.second = val;
	}

	dp[i+1][j+k-1] = max(dp[i+1][j+k-1],tmp);
	ans = max(ans,tmp);
      }
    }

    cout << ans.first << " " << ans.second << endl;
  }
}

総括

全体的にみると、慣れてる人には易化しているように思える。
比較をうまくやってソートしましょうね〜みたいな問題が多かった。
実装の慣れが要求されている感じがした。