久々にAOJをやった。 - はなちん C-x C-c

今日やったことまとめ。
久々にAizu Online Judgeをやった。
Problem setのVolume 0で解いてないやつを。
最後にやったのは2011-05-01なので、おおよそ8ヶ月ぶり。
くソースアップしときます。

0068: Enclose Pins with a Rubber Band

解法分かんなくてググて出たページで凸包というのを初めて知るなど…。
その単語だけ見てアルゴリズム書いてるページへ。
点集合の凸包-数学アルゴリズム演習ノート-
deq notesさんのベクトルのページ等を見てなんとか解けた。
超時間かかった。

#include <cstdio>
#include <complex>

using namespace std;

#define MAX_N 100

typedef complex<double> P;
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) (EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()))

double cross(P a, P b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}

int side(P start, P end, P point) {
  double arg = cross(end - start, point - start);
  if (arg > 0) return 1;  // left
  if (arg < 0) return -1; // right
  return 0; // center
}

int n;
P p[MAX_N];

int next_vertex(int start_index) {
  for (int i = 0; i < n; ++i) {
    if (start_index == i) continue;
    bool right = false;
    for (int j = 0; j < n; ++j) {
      if (i == j) continue;
      if (side(p[start_index], p[i], p[j]) == -1) right = true;
    }
    if (!right) return i;
  }
  return start_index;
}

int main() {
  while (1) {
    scanf("%d\n", &n);
    if (!n) break;
    
    for (int i = 0; i < n; ++i) {
      double x, y;
      scanf("%lf,%lf\n", &x, &y);
      p[i] = P(x, y);
    }
    
    int pm = 0;
    for (int i = 0; i < n; ++i) {
      if (p[pm].real() > p[i].real()) pm = i;
    }
    
    int start = pm;
    int current = next_vertex(start);
    int count = 1;
    
    while (start != current) {
      current = next_vertex(current);
      count++;
    }
    printf("%d\n", n - count);
  }
  return 0;
}

0069 Drawing Lots II

左右の横線の有無を確認するのを忘れてWAいっぱい出しちゃった。

#include <stdio.h>

int n, m, hit, d;
char dan[30][11];

int amida() {
  int i;
  int cur = m;
  for (i = 0; i < d; ++i) {
    // right
    if (cur < n && dan[i][cur - 1] == '1') {
      cur = cur + 1;
    }
    // left
    else if (cur > 1 && dan[i][cur - 2] == '1') {
      cur = cur - 1;
    }
  }
  return cur == hit;
}


void solve() {
  int i, j;
  if (amida()) {
    puts("0");
    return;
  }
  
  for (i = 0; i < d; i++) {
    for (j = 0; j < n - 1; j++) {
      if (dan[i][j] == '0') {
        if (j > 0 && dan[i][j-1] == '1') continue;
        if (j < n - 2 && dan[i][j+1] == '1') continue;
        dan[i][j] = '1';
        if (amida()) {
          printf("%d %d\n", i+1, j+1);
          return;
        }
        dan[i][j] = '0';
      }
    }
  }

  puts("1");
}

int main() {
  int i;
  while (1) {
    scanf("%d\n", &n);
    if (!n) break;

    scanf("%d\n%d\n%d\n", &m, &hit, &d);
    for (i = 0; i < d; i++) {
      scanf("%s\n", dan[i]);
    }
    solve();
  }
  return 0;
}

0078: Magic Square

魔方陣の問題。
return 0を忘れてRE

マス目に入る各数字は右詰4桁で出力してください。

を見落としPresentation errorでした。

#include <stdio.h>

#define MAX_N 15

int sq[MAX_N][MAX_N];
int n;

void reset() {
  int i, j;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      sq[i][j] = -1;
    }
  }
}

void fill(int count, int x, int y) {
  if (count > n * n) return;
  if (x < 0) x = n - 1;
  if (x >= n) x = 0;
  if (y >= n) y = 0;
  if (sq[x][y] != -1) {
    fill(count, x - 1, y + 1);
  } else {
    sq[x][y] = count;
    fill(count + 1, x + 1, y + 1);
  }
}

void printSq() {
  int i, j;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      printf(j ? "%4d" : "%4d", sq[j][i]);
    }
    puts("");
  }
}

void solve() {
  int center = n /  2;
  reset();
  sq[center][center + 1] = 1;
  fill(2, center + 1, center + 2);
  printSq();
}

int main() {
  while (1) {
    scanf("%d\n", &n);
    if (!n) break;
    
    solve();
  }
  return 0;
}

まとめ

やっぱり数学的な知識がないと辛いかも。
皆どうやって覚えてるんだろう。
あと解法分かんないときどしたらいい? 解法ググってでも解いたらいい?
僕頭固いからかなー。

とりえあずこんな感じで毎日解いていけるといいな。
次やるときは問題文をしっかり読んで重要なとこ見落とさないようにする。
目指せ一発Accept!