もふふろぐ

DDCC 2016 参加記

atcodercompetitivecppeventprogram

先週のCODE FESTIVALで疲れたと言いながらも、今日はDDCC 2016へ参加してきました。参加可否回答の締め切りがCODE FESTIVALより前だったので……。

受付ではDDCCのテーマカラーより少しきつい青のTシャツを受け取りました。テレビカメラの撮影が行われていることもあってか、Tシャツの着用は義務。コンテスト前の待ち時間には何人かの参加者がカメラを向けられ取材されており、自分のところに来てしまわないかひやひやしながら座っていました。

本戦

DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦

問題は全部で5問（300, 700(300), 700(300), 1000, 1500）。A問題から配点が大きめだったので解けるか不安でしたがさすがに大丈夫でした。しかし、B問題の満点解答とC問題の部分点解答で出したWAを取り切れず、600点81:18で100人中89位に。

A 正方形のチップ

円を格子状に分割したときの正方形の個数を求める問題。数えます。

#include <iostream>
#include <cmath>
using namespace std;

int main() {
  int r, c;
  cin >> r >> c;
  int n = 0;
  for (int i = c; i < r; i += c) {
    float jj = sqrt(r * r - i * i);
    for (int j = c; j <= jj; j += c) {
      n++;
    }
  }
  cout << n * 4 << endl;
  return 0;
}

B デュアルカット

総カット長が最小となるようにウェーハをカットする問題。後の社内見学で分かったのですが、実際の加工機械でも刃の消耗を最小にするために、このようなことを考慮しているそうです。

部分点解答は2本のカットラインの間隔に制限がないので、両端から同じ長さのラインを組んでいくだけ。

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
  int r, n, m;
  cin >> r >> n >> m;
  double l = 0.0;
  if (m != 1) {
    return 1;
  }
  for (int i = 1; i <= n / 2; i++) {
    double a = r * fabs(i - n * 0.5) / (n * 0.5);
    l += sqrt(r * r - a * a) * 2;
  }
  cout << fixed << setprecision(7) << l << endl;
  return 0;
}

満点解法も単純で、内側から順にできるだけ長いカットラインを選んでいけば解けます。……と意気揚々とコーディングしたのですが、提出してみたらいくつかのケースがWAに。if文を多用しながら配列を回しており何が何だか分からなくなったので、帰宅後に書き直しました。

#include <iostream>
#include <iomanip>
#include <cmath>
#include <list>
using namespace std;

int main() {
  int r, n, m;
  cin >> r >> n >> m;
  list<int> c;
  for (int i = 0; i < n / 2; i++) {
    c.push_back(i);
    c.push_back(-i);
  }
  if (n % 2 == 0) {
    c.pop_front();
  }
  double l = 0.0;
  while (!c.empty()) {
    int f = c.front();
    c.pop_front();
    for (auto it = begin(c); it != end(c); it++) {
      if (abs(f - *it) + n % 2 >= m) {
        c.erase(it);
        break;
      }
    }
    double a = r * (abs(f) + n % 2 * 0.5) / (n / 2.0);
    l += sqrt(r * r - a * a) * 2;
  }
  cout << fixed << setprecision(7) << l << endl;
  return 0;
}

特別講演

昼食後にはお笑い芸人でもある厚切りジェイソン氏による講演が行われ、自身の経験や日米のIT企業観についてのお話を聴きました。テレビなどで活躍されていることもあって話がとても上手です。時折挟まれる持ちネタに笑いも起きました。

社内見学

社内見学では福利厚生スペースを見て歩いた後、ウェーハをカットする機械を実際に作動させて見せていただけました。なんと機械のモニターの表示がB問題デュアルカットの解答そのもの。楽しくてためになる見学でした。

帰宅

先週のCODE FESTIVALに続く形となり、人生で2回目のオンサイトコンテストでした。DDCCは1日のみの日程だったので参加しやすかったと感じます。成績は相変わらずだったので精進したいところです。

終始テンションの高いディスカバリーチャンネル公式アカウント。