SRM428 Div.1 500 The Long Palindrome

個人的に好きなタイプの問題だったので久しぶりに解説を書きます。

問題

アルファベット小文字('a'-'z')からなる任意の文字列を考える。
長さN以下、含まれる文字の種類数K以下の回文の個数を求めなさい。
ただし、数が大きくなりうるので1234567891の剰余を返しなさい。

制約: 1<=N<=10^9, 1<=K<=26

解法

まずは高速なアルゴリズムを一旦無視して、答えを数式にしてみる。
p_{i,j}を、「長さがちょうどiで文字種類数がちょうどjの回文の個数」とする。
すると答えは、 \displaystyle \sum_{i=1}^{N} \sum_{j=1}^{K}p_{i,j} となるので、これを求めたい。

ここで、回文は前半が決まってしまえば後半は一意に定まるという特徴を考えると、
n/2文字の任意の文字列を作れば、その対称をとることで回文は漏れなく重複無く数え上げることができる。
よって、 s_{i,j}を、「長さがちょうどiで文字種類数がちょうどjの文字列の個数」とすると、
\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{K}p_{i,j} = \sum_{i=1}^{N} \sum_{j=1}^{K}s_{\lceil i/2 \rceil,j} = \sum_{i=1}^{\lceil N/2 \rceil} \sum_{j=1}^{K}s_{i,j} + \sum_{i=1}^{\lfloor N/2 \rfloor} \sum_{j=1}^{K}s_{i,j}と答えを書き直せる。

これで各 s_{i,j}を求めればよい問題になったが、それぞれO(1)で求められたとしても全部でO(NK)かかるため間に合わない。
しかしそれはそれとして、O(NK)で求めるDPを考える。
これは、 s_{i,j} = j \cdot s_{i-1,j} + (26-(j-1)) \cdot s_{i-1,j-1}という漸化式に基づくDPとなる。
式の意味は、前の項が「もし今まで使ったことがあるj文字のどれかをつかえば、新たに使った文字種類数が増えることはない」という意味で、後ろの項は「今まで使っていない(26-j)文字のうちどれかを使うと、文字種類数は1だけ増える」という意味である。
これを小さいi,jから順に計算して埋めていくことで、O(NK)で計算ができる。

しかし、前述の通り、これでは遅すぎなので、計算量を改善する。
ここで注目するのは、上記の漸化式にはiに依存する邪魔なパラメータは無く、すべてjのみに依存して更新されているという点だ。
この形のDPは、K×K行列を用いた行列積で、1つ次の項を求めることができる。これを利用すると、

によって、 s_{N,K}をO(K^3 logN)で求められるようになる。

しかし、求めたいのは s_{N,K}ではなく、その和である。
というようなことが蟻本の3-4にもそのまま書いてあるので、そのテクニックを用いる。
行列の累乗和を求めるのは、行列を4つ並べて2K×2Kの行列を作り、左上にA、右上に零行列、残り下半分をそれぞれ単位行列にして累乗計算することで求められる。詳しくは蟻本を読もう(布教活動)。
あとは、求めた累乗Sに(1, 0, ..., 0)^Tを掛けて出てくるベクトル要素の和が答え。modを取るのは忘れずに。

順列の問題で使えるかもしれない基礎知識

これはCompetitive Programming Advent Calendar Div201315日目の記事です。

今回は順列について少し扱おうと思います。
と言っても、僕はそこまで深く順列の知識があるわけでもないので、
こういったことを知っていると問題を順列に帰着したときに役に立つかなあ、
という基礎知識的な部分にサラッと触れる感じにしたいと思います。

ちなみに、内容が決まらなかった場合に予定していたD問題のモノマネも裏記事として書いたので、とてつもなく暇を持て余している人はどうぞ。

数列としての順列

まず始めに、ここで扱う順列について定義しておきます。
順列とは、n個の要素からなる数列a_1 a_2 ... a_nであり、以下の性質を満たすものです。

  1. 1 ≦ a_i ≦ n, for 1 ≦ i ≦ n
  2. a_i ≠ a_j, if i ≠ j

要は、1~nまでの数がちょうど1つずつ現れる数列です。
高校数学ではnPkのようなものを順列と言ったりしたかもしれませんが、ここではnPnに対応するもののみを順列として扱う、ということになります。
そういう意味では、順列というより置換です。

全探索

長さnの順列はn!通り存在します。これはとても大きな数で、2^nよりも大きいです。
2^20=1048576に対し、20!=2432902008176640000となり、64bit整数型で表すのもギリギリになってきます。
問題を解くとき、順列を総当たりで計算するようなアルゴリズムに帰着した場合、
たいていはそれぞれの順列の中身も見なければならないため、O(n・n!)以上の計算量になることが多いです。
こうなるとn=10を超えるとTLE 1secが怪しくなり始めます。
逆にいうと制約が厳しいため、nが小さすぎる場合は順列全探索などを簡単に予測することができます。
(罠の可能性もなくはないですが)

順列のDP

順列としての特徴、すなわち同じ要素が一度しか出現しないことを利用する場合のDPは、いわゆるbitDPになってO(2^n・f(n))のような計算量で解けることが割と多いです。

例えば、有名なハミルトンパス問題(ここでは、グラフ上の特定の始点sから終点tまで、全ての頂点を辿るような最短パスを求める問題とする。任意の始点・終点で存在判定をしたり、パスの総数を数え上げることもある)も、
「頂点をどの順番で辿って行くか」を考えているので順列の問題に帰着することができます。
この場合、例えば以下のように最短パスを求めることができます。

int ans = INF; //INFは十分大きな値
int edge[N][N]; //edge[i][j]はiからjへの辺の重みを表す
int a[N];
for(int i=0;i<N;i++)a[i] = i;

do{
  int sum = 0;
  if(a[0] != s || a[N-1] != t)continue;
  for(int i=1;i<N;i++)sum += edge[a[i-1]][a[i]];
  ans = min(ans, sum);
}while(next_permutation(a,a+N));

return ans;

この解法だとO(n・n!)です。
しかし、全ての順列を考える必要はなく、sからtへの有効なパスの数はもっと少ない可能性があるので、それだけ考えればよいです。
しかしこのパスの総数も完全グラフの場合に最悪で(n-2)!通り存在する*1ため、結局まだO(n・n!)です。
ここで、ある頂点vに辿り着いたとき、ここから先のパスの選び方に関してはそれまで実際にどのようなパスを辿ってきたかは重要ではなく、どの頂点を通ったかだけが重要であることに気づきます。
パスが違っても、通った頂点集合が同じであれば、これから先選べるパスは変わりません。
よって、同じ頂点集合を通り、ある頂点vに着く中で、最も短いパスのみを覚えて保持しておけば十分です。
これを利用すると、以下のようなbitDPが可能です。

int edge[N][N]; //edge[i][j]はiからjへの辺の重みを表す
int dp[1<<N][N]; //dp[今までに通った頂点集合][今いる頂点]

//INFで初期化
for(int i=0;i<(1<<N);i++){
  for(int j=0;j<N;j++)dp[i][j] = INF;
}
dp[1<<s][s] = 0;

for(int bit=0;bit<(1<<N);bit++){
  for(int v=0;v<N;v++){
    if( (bit>>v) & 1 == 0)continue;
    //今、頂点vにいるとする
    for(int u=0;u<N;u++){
      //次の行き先を頂点uにする。uにすでに訪れていればcontinue
      if( (bit>>u) & 1)continue;
      //今までに訪れた頂点集合がbit∪{u}で、いまuにいるときの最小パスを更新
      dp[bit | (1<<u)][u] = min(dp[bit | (1<<u)][u], dp[bit][v] + edge[v][u]);
    }
  }
}

return dp[(1<<N)-1][t];

このように、今まで使ったかどうかをbitで保持することで、O(n^2・2^n)で解くことができました。
順列であれば同じ要素の出現回数が高々1回なので、このように使う/使わないの2値に落とすことができます。
もちろん、同じ頂点を高々k回まで通ってよい、など同じ要素が複数回現れる場合も、同様にO(n^2・(k+1)^n)で解くことができます。

部分列の順列判定

ICPC Asia Regional Tehran 2010のG問題は、2つの順列について、同じ長さの連続する部分列のうち、一方が他方の並べ替えになっているような部分列の個数を数え上げる問題です。
それぞれの同じ長さの部分列をすべて比較するナイーブな方法だと、長さがn通り、長さkの部分列がn-k+1通り、一致判定にO(n)でO(n^4)かかります。
n=3000なので間に合いません。計算量的にO(n^2)程度が求められます。
1つの順列の連続部分列の個数がO(n^2)なので、Aの連続部分列それぞれに対し、A'に対応する連続部分列が存在するかどうかをO(1)で判定できればよさそうです。

要素xがA'に出現する位置をpos_xとします。すなわち、A'[pos_x] = xです。
このとき、A[i]からA[i+k]までの長さkの連続部分列について、pos_A[i]からpos_A[i+k]までが全てある値jからj+kに収まっていると、A'[j]からA'[j+k]までがA[i]からA[i+k]までの連続部分列の並べ替えになっていることがわかり、これが必要十分条件です。
また、ある値jはpos_A[i]からpos_A[i+k]の最小値であり、j+kは最大値であることもわかります。
よって、A[i]からA[i+k]までの連続部分列に対応するA'の連続部分列が存在するかを判定するには
pos_A[i]からpos_A[i+k]までの最小値と最大値を覚えておけばよく、これはA[i]からA[i+k-1]までの結果からO(1)で更新できるため、1つの区間につきO(1)で判定ができます。
このアルゴリズムを実装したものが以下のコードです。

int n;
int a[3030],b[3030],pos[3030];
int ans = 0;

for(int i=0;i<n;i++)pos[b[i]] = i;
 
for(int i=0;i<n;i++){
  int r = i+1;
  int minv = pos[a[i]], maxv = pos[a[i]];
  while(r<n){
    minv = min(minv,pos[a[r]]);
    maxv = max(maxv,pos[a[r]]);
 
    if(maxv - minv == r-i)ans++;
    r++;
  }
}
return ans;

これはA,Bともに順列になっており、ある要素の場所が1通りに定まることを利用しています。

反転数

順列には反転というものが定義されています。
これはa_i>a_jかつi

全単射としての順列

長さnの順列a_1 a_2 ... a_nは1~nまでの要素がちょうど1つずつ現れます。
これは見方を変えると関数aによってiをa_iに写像していると考えることができ、
このとき関数aは正の整数集合Nについて*2、a:N→Nの全単射関数です*3。
こうなってくるとまさに置換ですがあえて順列と呼び続けます。

順列を全単射として見る場合は二行記法が用いられることがあります。
例えば5 2 1 4 3という順列は、
$\Big( \begin{matrix} 1~2~3~4~5 \\ 5~2~1~4~3 \end{matrix} \Big)$
などと表記します。
まどろっこしいように思えるかもしれませんが、こうすることで1行目から2行目への写像であることがわかりやすくなったり、逆写像を考えるとき2行目から1行目への写像であると見ればよいので楽になったりします。

順列を関数と考えるのは、並べ替えの問題でしばしば有効です。
並べ替えを表す順列を関数のように合成することで、複数回の並べ替えの繰り返しを1つの順列として表現できるからです。

巡回と周期

JOI模擬予選2012 問題6は、M回のシャッフルを1セットとして、昇順に並んだカードがまた昇順に並び直されるまでにかかるセットの回数を求める問題です。

M回のシャッフルはすべて並べ替え、すなわち順列です。
これは実際にシャッフル操作を行って得ることもできますし、シャッフルによって定義される順列を全単射として合成することでも得られます。
(この問題ならたぶん普通にシャッフルをシミュレートする方が実装が楽です)
全単射としての合成と言うと難しく感じるかもしれませんが、
実際コード上での順列AとBの合成Pは、

int P[N],A[N],B[N];
for(int i=0;i<N;i++)P[i] = B[A[i]];

のように書くだけなので、そんなに難しいことではありません。
このコードでは、A[N]は最初i番目のカードがシャッフルAによってA[i]番目に行くことを表していて、
B[ A[i] ]がシャッフルAの後にシャッフルBをするとき、最初i番目のカードがB[ A[i] ]番目に行くことを表しています。
(注意：このコードの場合、長さnの順列は0~n-1までの要素で構成されています)

さて、M回のシャッフル1セットによる並び替えを表す順列Pが得られたので、
後はこの並び替えを何回繰り返せば昇順に戻るのか、を求める必要があります。
すなわち、Pをk個合成することをP^kと表記し、昇順の順列をeとすると、P^k = eとなるkを求める必要があります。
このkは順列の周期と呼ばれることもあります。つまり、この問題は順列の周期を求める問題です。
順列の周期を求めるためには順列のサイクル表記を知っていると理解の一助になります。

順列3 5 1 4 6 7 2の写像の様子をグラフにしたものが下図です。

このように見ると、写像がいくつかの独立なサイクルを構成し、各要素は高々1つのサイクルに含まれていることがわかります。
このサイクル分解を利用した表記がサイクル表記で、上の例をサイクル表記にすると、
(1 3)(2 5 6 7)
となります。これは、1→3→1、2→5→6→7→2というサイクルを表しています。
4→4は冗長なので通常書きませんが、あえて書くなら(4)です。

問題に戻ります。長さkのサイクル(a[i_1] a[i_2] ... a[i_k])に注目すると、a[i_x]がまたa[i_x]に戻ってくるには、k回かかることがわかります。
すなわち、長さkのサイクルに含まれるすべての要素は、一周するのにk回かかることになります。
つまり、すべての要素が元の位置に戻るためには、すべてのサイクルが整数周する必要があり、このような最小の整数が求める順列の周期です。
これは全てのサイクルの長さの最小公倍数に等しく、簡単かつ高速に求めることができます。
2つの正整数A,Bの最小公倍数はO(log(max(A,B))で求めることができ、
この問題では答えが2^63-1に収まることからこれは定数(高々63程度)と考えることができます。

よって、この問題はM回のシャッフル1セットの並び替えを求めるのにO(NM)、サイクルに分解するのにO(N)、周期を求めるのにO(1)の最小公倍数演算をO(N)回行う、となります。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;

int c[100100],tmp[100100];
int n,m;
int op,k;

ll gcd(ll a, ll b){ return b?gcd(b,a%b):a; }
ll lcm(ll a, ll b){ return a/gcd(a,b)*b; }

void riffle(void){
  for(int i=0;i<n/2;i++)tmp[2*i+1] = c[i];
  for(int i=n/2;i<n;i++)tmp[2*(i-n/2)] = c[i];
  for(int i=0;i<n;i++)c[i] = tmp[i];
}

void put(void){
  for(int i=0;i<k;i++)tmp[n-k+i] = c[i];
  for(int i=k;i<n;i++)tmp[i-k] = c[i];
  for(int i=0;i<n;i++)c[i] = tmp[i];
}

int main(){
  cin >> n >> m;
  for(int i=0;i<n;i++)c[i] = i;
  
  //シャッフルのシミュレーション
  for(int i=0;i<m;i++){
    cin >> op;
    if(op == 1)riffle();
    if(op == 2)reverse(c,c+n);
    if(op == 3){ cin >> k; put(); }
  }

  //サイクル分解
  vector<int> v;
  bool use[100100];
  for(int i=0;i<n;i++)use[i] = false;

  for(int i=0;i<n;i++){
    int now = i, cnt = 0;
    while(!use[now]){
      use[now] = true;
      cnt++; now = c[now];
    }
    if(cnt)v.push_back(cnt);
  }

  //最小公倍数の計算
  ll ans = v[0];
  for(int i=1;i<v.size();i++)ans = lcm(ans,v[i]);
  cout << ans << endl; 
}
その他写像を用いる問題

The First KMCMonthly ContestのH問題やanta's LAST CONTESTのC問題などでも順列を写像とみることによって並べ替え問題を解いています。
が、都合上これらの問題の解説は割愛させていただきます*4。
興味のある方は解説を読んだりしながら考えてみるとよいでしょう。

まとめ

なんかもっとよいことが言えればよかったんですがごちゃごちゃと順列の問題をやるだけになってしまい申し訳ないです。
今回取り上げた問題のポイントは、

  • O(n!)はたいてい遅すぎなので、順列の特徴をうまいこと利用して計算量を落とす必要がある
  • 各要素が1つしか現れないことを利用すると、
    • DPでは、すでに使った/使わないを利用したbitDPと相性がよい
    • 区間判定では、最大値-最小値 = 長さになることを利用するとよい

あたりだと思います。
個人的には後半の並べ替えを全単射として扱ってごにょごにょする感じが好きなので、そういう問題を他にも知っている方はぜひ教えてください。

ここまで読んでくださった方、ありがとうございました。
明日の担当はsnukeさんとsuneさんです。楽しみですね。綴りが似てますね。

*1:始点・終点が固定されているので、2点は順列に含めない

*2:別に非負で定義してもよいです

*3:n

*4:単に自分がまだ解いていないだけ

D問題のモノマネ

これはCompetitive Programming Advent Calendar Div201315日目の裏記事です。

どうも〜、Darseinでーす！
今までに出題されたD問題のモノマネしま〜す！

まずはじめは、会津合宿2013 Day3 D 「Change」

























ディー氏「ハフハフハフハフハフハフハフハフ」






続きまして、JAG夏合宿2010 Day2 D 「僕の友達は小さい」

























これはあずにゃん Advent Calendarの記事ではありませんがあずにゃんぺろぺろ。






続きまして、JAG夏合宿 2012 Day2 D 「ほそながいところ」

























ほそながくなかった……(はらぽよ)






続きまして、ICPC国内予選 2010 D 「ぐらぐら」

























UNSTABLE





最後に、JAG夏合宿 2011 Day2 D 「Dangerous Tower」

























危ない(確信)






お見苦しいところばかりで申し訳ありませんでした。
最後まで見てくださった忍耐力の強い方、どうもありがとうございました〜！

まったりあずにゃん

これはあずにゃん Advent Calendar14日目の記事です。

いつもあずにゃんあずにゃん言ってますが実はあずにゃんグッズは「あずにゃんまったりぬいぐるみ」しか持っていないです。

家族とかに見られるの恥ずかしいなーというタチなので、そもそもがアニメグッズはあまり持っていません。
そんな僕ですが、あずにゃんまったりぬいぐるみを初めて見たときは衝撃でした。
ただでさえかわいいあずにゃんがこんなにも気を抜いてくつろいでいる最上に天使な表情。
ときめきました。かわいすぎる。恥など気にせず手に入れたい衝動に駆られました。

しかし、けいおんコラボ時はローソンがやばいらしいというのは知っていたので、ためらって12時凸のようなことはしませんでした。ちきん。
次の日のお昼ごろに行くと、グッズはいくつか残っていたのですが、あずにゃんはそこにはいませんでした。

結局、僕はamaz○nで未開封あずにゃんを買いました。
かわいいしかわいいしかわいいので毎日愛でていますが、
やはり初日にあずにゃんを家に迎え入れられなかったことは後悔しています。

今後はもっと貪欲にあずにゃんを手に入れて行きたいです。

あずにゃんとツインテール

これはあずにゃんAdventCalendar12日目の記事です。ぺろぺろ。
(プロコン日記と言ってるけど他にブログ持ってないのでここに書きます。ごめんなさい。)

さて、あずにゃんのかわいさの象徴といえばツインテールですよね。
日本ツインテール協会によると、
あずにゃんのツインテールはラビット・スタイルのホーステールらしいです。

また、ツインテールというのは和製英語で、英語ではAngel Wingsとも言われるそうです。
あずにゃんマジ天使。
アニメ二期のけいおん！！劇中歌として、卒業する先輩4人からあずにゃんに贈られた「天使にふれたよ！」という曲で
あずにゃんが天使と形容されていたのはこのAngel Wingsから来ているのではないかと勝手に予想しています。
(情弱なので既出だったり棄却されたりしていたらごめんなさい)

まあ髪型がツインテールでも日本人形モードでも、
あずにゃんが僕のマイスウィートエンジェルであることに変わりはないですけどね！！！
はあ、あずにゃんを膝に乗せて髪を梳きながら頭なでなでしたい……

ACPC Day1 D

会津合宿Day1のD問題に「与えられた真理値表に対応するBDDを構築し、頂点数を求めよ」という問題が出ました。
想定解法は「二分決定木作って頑張って簡約化」らしいですが、これはBDDを構築しなくても解けます。

変数をx1,x2,...,xn、与えられた真理値表を表す文字列をsとします。

ここで、sの前半2^(n-1)個はx1を0に固定したとき、後半2^(n-1)個はx1を1に固定したときの真理値表を表していることに注目します。
これをBDD上で考えると、変数がx1のノードで、前半が左の子、後半が右の子に対応する部分BDDを表している、と考えることができます。
ということはまず、前半と後半が一致する場合は、左のエッジも右のエッジも同じ部分BDDを指している、すなわち、冗長なノードの削除ルールに当てはまるため、前半が表すBDDの頂点数だけが分かれば良いことになります。

また、この長さ2^(n-1)の01文字列がそれぞれ部分BDDである、という発想から逆に、同じ01文字列であれば、同じBDDを表している、と見ることが出来ます。
よって、今までに現れたことがある長さ2^xの01文字列であれば、それは すでに調べた部分BDDであるので、数を数える必要はありません。これは等価なノードの共有にあたります。

ということで、結論としては、与えられた文字列をどんどん半分に区切っていく過程で現れた文字列の中で、その文字列の前半と後半が一致しないような文字列の種類数がBDDサイズに等しい、ということになります。

この、

  • 長さ2^nの2進文字列
  • 前半と後半が一致しない

を満たす文字列はBeadsと呼ばれ、BDDと一対一対応したハッシュ関数のようなものとして機能することがKnuthのThe Art of Computer Programming 4-1で述べられています。
BDDサイズの上界を見積もるのにも用いられていたと記憶しています。

D問題に対するACコード例は、以下の通りです。

#include<iostream>
#include<string>
#include<set>
using namespace std;

set<string> hash;

int parse(string s){
  if(s.size()==1)return 0;
  if(hash.find(s) != hash.end())return 0;

  string a = s.substr(0,s.size()/2), b = s.substr(s.size()/2);
  int res;
  if(a==b)res = parse(a);
  else res = parse(a) + parse(b) + 1;

  hash.insert(s);
  return res;
}

int main(){
  int n;
  string s;
  cin >> n >> s;
  cout << parse(s) << endl;
}

ICPC国内予選2013 A~D

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

A

問題：
h×wの横長(h

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

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

解法：
制約に「答えは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;
  }
}

総括

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