Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

2013-04-07

Codeforces 83E -- Two Subsequences

| 14:26 | Codeforces 83E -- Two Subsequences - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - Codeforces 83E -- Two Subsequences - Wrong Answer -- japlj Codeforces 83E -- Two Subsequences - Wrong Answer -- japlj のブックマークコメント

http://codeforces.com/problemset/problem/83/E

面白い問題だったので思考過程をメモ.

(当然ですが解法バレがありますので自分で考えて解きたい人は注意)


  • 問題内容自体は前に読んで知っていたので,まずは細部を思い出すために軽く読む.
  • 愚直に考えれば a の i 番目まで見ていて,b の最後のパターンと c の最後のパターンをもっておくとして状態数は n * 420 ぐらい必要そうだとわかる.
  • でもよく考えると a の i 番目まで見ているということは b, c どちらかの最後のパターンは ai なのだから,そうでないほうだけ覚えておけばよくて,そうすると n * 220 ぐらいにはなるけどまだ大きい.
  • b, c は対称だから,状態は (i, ai を入れてない方の最後のパターン) で表現できる.
  • i を小さい方から回すとすれば ai を入れてない方の最後のパターン,という 220 通りの状態に大して各 i ごとに答を更新していけばよいことになる → これでようやく持つべき状態がメモリに乗りそうな大きさになった.
  • とはいえまだ n * 220 であることに変わりはないが,ここで状態の更新について考えてみる.
  • ai+1 を入れる時,ai を入れた方に入れるかそうでない方に入れるかの 2 通りがある.
    • ai を入れた方に入れる時,状態はどう変わるか考えると,かかるコストは ai と ai+1 をつなげるときを考えれば良いのですぐわかる.で,このとき ai を入れてない方のパターンはもちろん変わらないままなので,すべてのパターン p について dp[i + 1][p] = dp[i][p] + cost とすればよいことがわかる.
    • そうでない方に入れる時,状態の変化は単純になる.というのは,この場合次の状態としてありうるのは (i + 1, ai) だけだから(aiが入ってない方に ai+1 を入れるので,次に ai+1 が入ってない方というのは ai になる).で,かかるコストというのを考えると,パターン p の下 k 桁と ai+1 の上 k 桁が一致しているときにコストは (各パターンの長さ) - k となる.それぞれの k (k ≧ 0)ごとに状態を更新することにして,ai+1 の上 k 桁が,その下 k 桁と一致しているようなパターン p すべてについて dp[i + 1][ai] = min{dp[i][p] + (パターンの長さ) - k} とすればよい.
  • さてもちろん,これを愚直にやれば n * 220 のままだが,この更新について考えると dp配列に必要なのは次の操作を備えることだとわかる.
    • すべての p に対し dp[p] += 一定値 を処理する.
    • ある p に対し dp[p] = 一定値 を処理する.
    • 長さ k と,長さ k のパターン x に対し,下 k 桁が x であるようなすべてのパターン p に大して dp[p] の最小値を求める.
  • 以上の操作を爆速で行えればよいが,これ自体は特に難しいデータ構造というわけではない(全体に対して足されている値というのを別にもっておけば一個目はできる,二個目はそもそもO(1)である,三個目は各 k, x についてクエリへの答となる配列 min[k][x] を用意しておけばよい).
  • 計算量は O(2^(パターン長) + n * パターン長) となった.これで解ける.

2012-04-06

CROC Champ 2012 - Round 1 (Unofficial)

| 02:57 | CROC Champ 2012 - Round 1 (Unofficial) - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - CROC Champ 2012 - Round 1 (Unofficial) - Wrong Answer -- japlj CROC Champ 2012 - Round 1 (Unofficial) - Wrong Answer -- japlj のブックマークコメント

A

普通に.

B

106 * hoge なグラフを作ろうとしてバグって時間食った.

103 * hoge で十分なことに気づいててきとうにやった.

C

図を見たらはまったのでそのまま書いた.

D

考えたらやり方がわかったので頑張って書いたが全然答が合わずに修正に苦労した.

E

どうみてもデータ構造っぽいのでこっちやればよかった.

結果

  • A 486/500 00:07
  • B 790/1000 00:40 (+1)
  • C 1090/1500 01:00 (+1)
  • D 1030/2000 01:55 (+1)
  • E -/- -

29位

実装力落ちすぎで悲しみに包まる.


A

LCM なんかいらんかったんや!

#include<cstdio>
#include<cstring>

int gcd(int m, int n)
{
  return m%n ? gcd(n, m%n) : n;
}

int lcm(int a, int b)
{
  return a / gcd(a, b) * b;
}

int main()
{
  int n, m, k, x, sa = 0, sb = 0, sola = 0, solb = 0;
  char A[1024], B[1024];
  scanf("%d%s%s", &n, A, B);
  m = strlen(A);
  k = strlen(B);
  x = lcm(m, k);
  for(int i=0; i<m; ++i)
    A[i] = (A[i]=='R' ? 0 : (A[i]=='S' ? 1 : 2));
  for(int i=0; i<k; ++i)
    B[i] = (B[i]=='R' ? 0 : (B[i]=='S' ? 1 : 2));
  for(int i=0; i<x; ++i) {
    if(i == n%x) { sola=sa; solb=sb; }
    if((A[i%m]+1)%3 == B[i%k]) sb++;
    if((B[i%k]+1)%3 == A[i%m]) sa++;
  }
  printf("%d %d\n", sola+sa*(n/x), solb+sb*(n/x));
}

B

ちゃんと 01BFS 書いてたほうが時間短くて済んだ説は悲しくなるのでやめろ

#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

int n, m;
char tbl[1024][1024];

bool v[2048];
vector<int> row[1024];
vector<int> col[1024];

int main()
{
  scanf("%d%d", &n, &m);
  for(int i=0; i<n; ++i) {
    scanf("%s", tbl[i]);
    for(int j=0; j<m; ++j)
      if(tbl[i][j] == '#')
	row[i].push_back(j), col[j].push_back(i);
  }

  queue<pair<int, int> > q;
  q.push(make_pair(n-1, 0));
  v[n-1] = true;
  while(!q.empty()) {
    int u = q.front().first, c = q.front().second; q.pop();
    if(u == 0) { printf("%d\n", c); return 0; }
    if(u < n) {
      for(int i=0; i<(int)row[u].size(); ++i)
	if(!v[n+row[u][i]])
	  q.push(make_pair(n+row[u][i], c+1)), v[n+row[u][i]]=true;
    }
    if(u >= n) {
      u -= n;
      for(int i=0; i<(int)col[u].size(); ++i)
	if(!v[col[u][i]])
	  q.push(make_pair(col[u][i], c+1)), v[col[u][i]]=true;
    }
  }
  puts("-1");
  return 0;
}

C

図がなかったら気づかなかったかも

#include<cstdio>
#include<cstring>

int A[512][512], S[512][512], P[512][512];

int main()
{
  int n, m;
  scanf("%d%d", &n, &m);

  for(int i=1; i<=n; ++i)
    for(int j=1; j<=m; ++j)
      scanf("%d", &A[i][j]), S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+A[i][j];

  for(int i=1; i+2<=n; ++i)
    for(int j=1; j+2<=m; ++j)
      P[i][j] = A[i][j]+A[i][j+1]+A[i][j+2]+A[i+1][j+2]+A[i+2][j]+A[i+2][j+1]+A[i+2][j+2];

  int sol = -1000000000;
  for(int k=3; k<=n && k<=m; k+=2) {
    for(int i=1; i+k-1<=n; ++i)
      for(int j=1; j+k-1<=m; ++j)
	if(sol < P[i][j]) sol = P[i][j];
    for(int i=1; i+k+1<=n; ++i)
      for(int j=1; j+k+1<=m; ++j)
	P[i][j] = S[i+k+1][j+k+1] - S[i+k+1][j-1] - S[i-1][j+k+1] + S[i-1][j-1] - A[i+1][j] - P[i+1][j+1];
  }

  printf("%d\n", sol);
  return 0;
}

D

ほんまよく通ったなこれ

#include<cstdio>
#include<cstring>

const int MAXV = 100050, MAXE = 200050;
int adj[MAXE], ptr[MAXV], next[MAXE], col[MAXV], deg[MAXV], sol[MAXV], used[MAXV], pair[MAXV][2];

void dfs(int u, int c)
{
  if(~col[u]) return;
  col[u] = c;
  for(int z=ptr[u]; ~z; z=next[z]) {
    int v = adj[z];
    dfs(v, 1-c);
  }
}

int main()
{
  int n, m, e = 0;
  scanf("%d%d", &n, &m);

  memset(ptr, ~0, sizeof(ptr));
  for(int i=0; i<m; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--; b--;
    next[e] = ptr[a]; ptr[a] = e; adj[e] = b; deg[a]++; e++;
    next[e] = ptr[b]; ptr[b] = e; adj[e] = a; deg[b]++; e++;
  }

  memset(col, ~0, sizeof(col));
  for(int i=0; i<n; ++i)
    if(!~col[i]) dfs(i, 0);

  int on = 0;
  for(int i=0; i<n; ++i)
    on += col[i];

  if(on % 3 == 0) {
    puts("YES");
    int zs = 0, os = 0;
    for(int i=0; i<n; ++i) {
      if(col[i] == 0) printf("%d", 1+zs/3+on/3), zs++;
      if(col[i] == 1) printf("%d", 1+os/3), os++;
      putchar(i==n-1 ? '\n' : ' ');
    }
    return 0;
  }

  memset(sol, ~0, sizeof(sol));
  if(on % 3 == 1) {
    for(int i=0; i<n; ++i)
      col[i] = 1-col[i];
    on = n - on;
  }

  for(int i=0; i<n; ++i) {
    if(col[i] == 1) continue;
    if(on - deg[i] >= 2) {
      puts("YES");
      sol[i] = n/3;
      memset(used, ~0, sizeof(used));
      for(int z=ptr[i]; ~z; z=next[z]) used[adj[z]] = 1;
      for(int j=0, k=0; k<2; ++j) {
	if(col[j]==1 && !~used[j]) {
	  sol[j] = n/3;
	  k++;
	}
      }
      int zs = 0, os = 0;
      for(int i=0; i<n; ++i) {
	if(~sol[i]) printf("%d", sol[i]);
	else if(col[i] == 0) printf("%d", 1+zs/3+on/3), zs++;
	else if(col[i] == 1) printf("%d", 1+os/3), os++;
	putchar(i==n-1 ? '\n' : ' ');
      }
      return 0;
    }
  }

  int done = 0, trip = 0;
  memset(used, 0, sizeof(used));
  for(int i=0; i<n; ++i) {
    if(col[i] == 0) continue;
    if((n - on) - deg[i] >= 2) {
      sol[i] = 1 + done / 3;
      done++;
      memset(used, ~0, sizeof(used));
      for(int z=ptr[i]; ~z; z=next[z]) used[adj[z]] = 1;
      for(int j=0, k=0; k<2; ++j) {
	if(col[j]==0 && !~used[j]) {
	  sol[j] = 1 + done / 3;
	  done++; k++;
	}
      }
      trip++;
      if(trip == 2) break;
    }
  }
  if(trip < 2) {
    puts("NO");
    return 0;
  }
  for(int i=0; i<n; ++i) {
    if(col[i]==0 && !~sol[i]) {
      sol[i] = 1 + done / 3;
      done++;
    }
  }
  for(int i=0; i<n; ++i) {
    if(col[i]==1 && !~sol[i]) {
      sol[i] = 1 + done / 3;
      done++;
    }
  }

  puts("YES");
  for(int i=0; i<n; ++i)
    printf("%d%c", sol[i], i==n-1 ? '\n' : ' ');

  return 0;
}

2012-01-09

Codeforces Round #101 (Div.2 Only) E もう少し丁寧に

| 11:39 | Codeforces Round #101 (Div.2 Only) E もう少し丁寧に - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - Codeforces Round #101 (Div.2 Only) E もう少し丁寧に - Wrong Answer -- japlj Codeforces Round #101 (Div.2 Only) E もう少し丁寧に - Wrong Answer -- japlj のブックマークコメント

問題

n 頂点 m 辺のグラフがあり,それぞれの辺は白か黒の色がついている.

このグラフの全域木であり,白の辺と黒の辺の個数が等しくなっているものを一つ求めよ.

  • 1 ≦ n ≦ 1,000
  • 1 ≦ m ≦ 100,000

解法

不可能なのが自明な場合(nが偶数,辺が足りない)をまず処理しておく.

まず最初に与えられたグラフから黒い辺をすべて削除して白い辺だけになったグラフを考える.

このグラフが非連結な場合(k個の連結成分にわかれている場合),それらを連結にするため k-1 個の黒い辺を追加する必要がある.追加するべき k-1 個の黒い辺は白い辺だけのグラフから Union-Find を使って求められる.

連結にするための黒い辺が足りない場合や,必要な辺が多すぎる場合(k-1 > (n-1)/2)は求める全域木が存在しない.

適切に k-1 個の黒い辺を追加できた場合,さらに黒い辺を追加して黒い辺が合計 (n-1)/2 個になるようにすることを考える.

このとき残りの (n-1)/2 - (k-1) 個の黒い辺をどのように選ぶかは,実は黒い辺がループを作らなければどのように選んでも良い.

というのは,任意の黒い辺の選び方に対して,白い辺を用いて全域木が作れるかどうかというのは「連結なグラフのうち何本かの辺が固定されている(ただし固定されている辺だけのループは存在しない)とき,固定されていない辺だけを適切に削除して全域木が作れるかどうか」という問題になるが,これが常に可能であることが簡単にわかる.

なぜなら固定されている辺(要は選ばれた黒い辺)で結ばれた2頂点を繰り返し縮約して白い辺だけが残るようにすると,連結性を保ったまま白い辺だけからなるグラフが得られるからである.

したがって問題の全域木を求めるにはまず k-1 個の必要な黒い辺を追加した後,黒い辺だけでループができないように黒い辺を合計 (n-1)/2 個になるまで追加する(これは黒い辺だけ考えた Union-Find を使って求められる).

次に黒い辺だけ考えた Union-Find をそのまま使って,クラスカルの最小全域木を求めるアルゴリズムと同じ形で白い辺を追加していくとよい.

よってこのアルゴリズムは(Union-Findを適切に実装していれば) O( (m+n)α(n)) 時間で動く(n ≦ 100,000 にしなかったのは何故だろう?).

2012-01-08

Codeforces Round #101 (Div.2 Only)

| 02:46 | Codeforces Round #101 (Div.2 Only) - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - Codeforces Round #101 (Div.2 Only) - Wrong Answer -- japlj Codeforces Round #101 (Div.2 Only) - Wrong Answer -- japlj のブックマークコメント

あと n 日でセンター試験なんですがそれは大丈夫なんですかね……

A

やるだけ.

B

やるだけ.

a が奇数の時だけ通るコードを書いて死ぬ.死ぬ.死ぬ.死ぬ.死ぬ.

C

挿入していくだけ.

D

逆からダイクストラするだけ.

なぜか落ちる.死ぬ.

E

Sの辺だけあるグラフを考えて,もしそのグラフが非連結なら,それが連結になるようにMの辺を加える.という感じの処理をまず行う.

その後はMの辺とSの辺を普通に見ていってループができないように追加していくと何故か通る.嘘仮定が正しかったらしい.

↓Eのソースだけ


#include<cstdio>

int U[1024];
void init(int n) { for(int i=0; i<n; ++i) U[i] = i; }
int find(int x) {
  if(U[x] != x) U[x] = find(U[x]);
  return U[x];
}
void uni(int x, int y) { U[find(x)] = find(y); }

int sx[100000], sy[100000], si[100000], su[100000];
int mx[100000], my[100000], mi[100000], mu[100000];

int main()
{
  int n, m, S = 0, M = 0;
  scanf("%d%d", &n, &m);
  for(int i=0; i<m; ++i) {
    int x, y;
    char t[2];
    scanf("%d%d%s", &x, &y, t);
    x--; y--;
    if(t[0] == 'S' && x!=y) { sx[S]=x; sy[S]=y; si[S]=i+1; S++; }
    if(t[0] == 'M' && x!=y) { mx[M]=x; my[M]=y; mi[M]=i+1; M++; }
  }
  if(n % 2 == 0 || S+M < n-1 || S < (n-1)/2 || M < (n-1)/2) { puts("-1");  return 0;}
  init(n);
  for(int i=0; i<S; ++i) uni(sx[i], sy[i]);
  int used[1024], X=0;
  for(int i=0; X<(n-1)/2 && i<M; ++i) {
    if(find(mx[i]) != find(my[i])) {
      uni(mx[i], my[i]);
      used[X++] = mi[i];
      mu[i] = 1;
    }
  }
  init(n);
  for(int i=0; i<M; ++i)
    if(mu[i]) uni(mx[i], my[i]);
  for(int i=0; X<(n-1)/2 && i<M; ++i) {
    if(mu[i]) continue;
    if(find(mx[i]) != find(my[i])) {
      uni(mx[i], my[i]);
      used[X++] = mi[i];
      mu[i] = 1;
    }
  }
  if(X < (n-1)/2) {puts("-1"); return 0;}
  for(int i=0; i<S; ++i) {
    if(find(sx[i]) != find(sy[i])) {
      uni(sx[i], sy[i]);
      used[X++] = si[i];
      su[i] = 1;
    }
  }
  if(X < n-1) { puts("-1"); return 0; }
  printf("%d\n", n-1);
  for(int i=0; i<n-1; ++i) printf("%d%c", used[i], i==n-2?'\n':' ');
  return 0;
}

2011-03-02

Codeforces Problem 2B -- The least round way

| 23:10 | Codeforces Problem 2B -- The least round way  - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - Codeforces Problem 2B -- The least round way  - Wrong Answer -- japlj Codeforces Problem 2B -- The least round way  - Wrong Answer -- japlj のブックマークコメント

よくあるDP。0に注意。


#include<cstdio>
#include<algorithm>

using namespace std;

int m[1024][1024], dp[1024][1024][2], left[1024][1024][2];

int main()
{
  int n, p[2] = {2, 5}, zx=0, zy;
  scanf("%d", &n);
  for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
      scanf("%d", &m[i][j]);
  for(int i=2; i<=n; ++i)
    dp[i][0][0]=dp[i][0][1]=dp[0][i][0]=dp[0][i][1]=1<<29;
  for(int i=1; i<=n; ++i) {
    for(int j=1; j<=n; ++j) {
      if(!m[i][j]) zx=j, zy=i;
      for(int k=0; k<2; ++k) {
	dp[i][j][k] = min(dp[i-1][j][k], dp[i][j-1][k]) + !m[i][j];
	left[i][j][k] = dp[i-1][j][k] > dp[i][j-1][k];
	for(int x=m[i][j]; x&&x%p[k]==0; x/=p[k]) dp[i][j][k]++;
      }
    }
  }
  int k = dp[n][n][0]>dp[n][n][1] ? 1 : 0, way[2000];
  if(zx>0 && dp[n][n][k]>0) {
    puts("1");
    for(int i=1; i<zx; ++i) putchar('R');
    for(int i=1; i<zy; ++i) putchar('D');
    for(int i=zx; i<n; ++i) putchar('R');
    for(int i=zy; i<n; ++i) putchar('D');
    puts("");
    return 0;
  }
  printf("%d\n", dp[n][n][k]);
  for(int i=2*n-3, x=n, y=n; i>=0; --i, left[y][x][k]?--x:--y)
    way[i] = left[y][x][k];
  for(int i=0; i<2*n-2; ++i) putchar("DR"[way[i]]);
  puts("");
  return 0;
}

Codeforces Problem 2A -- Winner

| 22:47 | Codeforces Problem 2A -- Winner - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - Codeforces Problem 2A -- Winner - Wrong Answer -- japlj Codeforces Problem 2A -- Winner - Wrong Answer -- japlj のブックマークコメント

やるだけ。


#include<cstdio>
#include<map>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
  int n, m;
  vector<string> info_s;
  vector<int> info_p;
  map<string, int> pt, round;
  scanf("%d", &n);
  for(int i=0; i<n; ++i) {
    char s[40];
    int p;
    scanf("%s%d", s, &p);
    info_s.push_back(s);
    info_p.push_back(p);
    pt[s] += p;
  }
  m = -1;
  for(map<string, int>::iterator it=pt.begin(); it!=pt.end(); ++it)
    m = max(m, it->second);
  pt.clear();
  for(int i=0; i<n; ++i) {
    pt[info_s[i]] += info_p[i];
    if(pt[info_s[i]] >= m && round.find(info_s[i]) == round.end())
      round[info_s[i]] = i;
  }
  string sol;
  int k = n;
  for(map<string, int>::iterator it=round.begin(); it!=round.end(); ++it)
    if(pt[it->first]==m && k>it->second) k=it->second, sol=it->first;
  puts(sol.c_str());
  return 0;
}

Codeforces Problem 1C -- Ancient Berland Circus

| 22:33 | Codeforces Problem 1C -- Ancient Berland Circus - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - Codeforces Problem 1C -- Ancient Berland Circus - Wrong Answer -- japlj Codeforces Problem 1C -- Ancient Berland Circus - Wrong Answer -- japlj のブックマークコメント

やるだけ。


#include<cstdio>
#include<cmath>

int main()
{
  const double eps = 1e-6;
  double x[3], y[3];
  for(int i=0; i<3; ++i)
    scanf("%lf%lf", &x[i], &y[i]);
  x[1]-=x[0]; x[2]-=x[0]; y[1]-=y[0]; y[2]-=y[0]; x[0]=y[0]=0;
  double cx = (y[2]*(x[1]*x[1]+y[1]*y[1])-y[1]*(x[2]*x[2]+y[2]*y[2])) / (x[1]*y[2]-x[2]*y[1]) / 2;
  double cy = (x[2]*(x[1]*x[1]+y[1]*y[1])-x[1]*(x[2]*x[2]+y[2]*y[2])) / (x[2]*y[1]-x[1]*y[2]) / 2;
  double dx[3], dy[3];
  for(int i=0; i<3; ++i)
    dx[i] = x[i]-cx, dy[i] = y[i]-cy;
  double sin_t1 = (dx[0]*dy[1]-dx[1]*dy[0]) / (dx[0]*dx[0]+dy[0]*dy[0]);
  double cos_t1 = (dx[0]*dx[1]+dy[0]*dy[1]) / (dx[0]*dx[0]+dy[0]*dy[0]);
  double sin_t2 = (dx[0]*dy[2]-dx[2]*dy[0]) / (dx[0]*dx[0]+dy[0]*dy[0]);
  double cos_t2 = (dx[0]*dx[2]+dy[0]*dy[2]) / (dx[0]*dx[0]+dy[0]*dy[0]);
  for(int n=3; n<=100; ++n) {
    for(int i=1; i<n; ++i) {
      if(fabs(sin_t1 - sin(2*M_PI/n*i)) > eps ||
	 fabs(cos_t1 - cos(2*M_PI/n*i)) > eps) continue;
      for(int j=1; j<n; ++j) {
	if(fabs(sin_t2 - sin(2*M_PI/n*j)) > eps ||
	   fabs(cos_t2 - cos(2*M_PI/n*j)) > eps) continue;
	printf("%.9f\n", (dx[0]*dx[0]+dy[0]*dy[0])*sin(2*M_PI/n)*n/2);
	return 0;
      }
    }
  }
  return 0;
}

Codeforces Problem 1B -- Spreadsheet

| 21:58 | Codeforces Problem 1B -- Spreadsheet - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - Codeforces Problem 1B -- Spreadsheet - Wrong Answer -- japlj Codeforces Problem 1B -- Spreadsheet - Wrong Answer -- japlj のブックマークコメント

やるだけ。


#include<cstdio>

int main()
{
  int n;
  scanf("%d", &n);
  while(n--) {
    char s[32];
    scanf("%s", s);
    int typ = 0;
    for(int i=0; s[i]; ++i)
      if('0'<=s[i]&&s[i]<='9'&&typ==0) typ=1;
      else if(s[i]=='C'&&typ==1) typ=2;
    if(typ==2) {
      int r=0, c=0, k=1;
      while('0'<=s[k]&&s[k]<='9') r=r*10+s[k++]-'0'; k++;
      while('0'<=s[k]&&s[k]<='9') c=c*10+s[k++]-'0';
      for(c--, k=0; c>=0; c/=26, c--) s[k++]=c%26+'A'; s[k]='\0';
      while(k-1>=0) putchar(s[--k]);
      printf("%d\n", r);
    } else {
      int r=0, c=0, k=0;
      while('A'<=s[k]&&s[k]<='Z') c=c*26+s[k++]-'A'+1;
      while('0'<=s[k]&&s[k]<='9') r=r*10+s[k++]-'0';
      printf("R%dC%d\n", r, c);
    }
  }
  return 0;
}

Codeforces Problem 1A -- Theatre Square

| 21:40 | Codeforces Problem 1A -- Theatre Square - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - Codeforces Problem 1A -- Theatre Square - Wrong Answer -- japlj Codeforces Problem 1A -- Theatre Square - Wrong Answer -- japlj のブックマークコメント

やるだけ。


#include<cstdio>

int main()
{
  int n, m, a;
  scanf("%d%d%d", &n, &m, &a);
  printf("%I64d\n", 1ll*(n/a+!!(n%a))*(m/a+!!(m%a)));
  return 0;
}