SuperCon2018予選[参加記]

5月30日正午から、6月15日正午まで開催されていた、Supercomputing Contest2018予選に参加しました。
SuperConの参加記ついでに、どんなコンテストかも知ってもらおうと思います。

＜競技プログラミングって何？＞

あまり知られていない競技なので、ここから説明します。

「競技」なので、競うわけですよ。
何を競うかはコンテストの形式によっていろいろです。
早く解くのを良しとしたり、正確に解くのを良しとしたりが一般的です。

プログラミングコンテスト(通称：プロコン)って、大きく2種類に分類できると思います。
(1)短時間で、5〜10問程度を解く
(2)長期間で、1問を突き詰める(ランニング形式っていうこともあります)

プロコンというと、(1)がほとんどです。
ほぼ毎週プロコンを開催しているAtcoder、大会だとPCK(パソコン甲子園)やJOI(情報オリンピック)はこのタイプです。

(2)は、とても少ないです。
Atcoderで、年に2~3回あるのかなぁくらいに少ない。
大会だと、今回参加したSuperConとかICFP-PCくらいしか私は知りません。

[追記]
海外サイトだと、(2)はもっと頻繁に行われているそうです。
また、(1)も海外サイトがいくつかあります。

二つに共通しているのは、「プログラミングをして、問題を解く」ってことです。
まあ、競う要素を抜きにすると、それだけの競技です。

Atcoderなんかは、気軽に登録して、気軽に参加できますし、過去の問題も解くことができるので、オススメです。

AtCoder

＜SuperConについて＞

先ほども言った通り、「ランニング形式」のコンテストです。
指定された期間内にプログラムを完成させるタイプのものなんですけど、「正しい答えにより近い値を出せるように頑張る」とか、「速く正しい答えを出せるように頑張る」とかをします。
とにかく考察ゲーか、とにかく実装ゲーみたいなところがあります。

今回の問題は、「速く正しい答えを出せるように頑張る」タイプのものでした。

また、この大会、2〜3人のグループでやるんですよね。
コミュ力必須。

問題はこちら。「予選・認定問題」ってやつみてください。
一級認定兼予選問題ってやつが、今回私たちの取り組んだ問題です。

SupercomputingContest2018 - Supercomputing Programing Contest Official Site

2週間という期間があるので、時間をどう使うかも割と大切でした。
確実に、最初から最後まで真面目に考察や実装をし続けるのは難しいです。

ここからは、実際の様子を。

＜開始前＞

N高にきてから、そんなにたくさんの人との関わりを持ってなかったので、メンバーが決まるかが心配だった。
…しかし、スパコン参加者募集をかけてたので、手をあげたら参加できてよかった。

ただ、やっぱり関わりが薄い人たちだったので、グループが決まってもドキドキだった…

＜初日＞

問題が出た直後なので、「予選通るぞおおおおお」みたいな勢いだけはめちゃくちゃあった。(アホか)
浜工・情報処理部の顧問の先生に「スパコン通れよ」って言われてますし。

まあ問題を読んで、理解するのに精一杯だった感。
日本語難しいね。

＜2日目＞

とりあえず、「ひとりで書けるところまで書いてみるか」って、書きました。
しかし、小さめの手計算で答えを確認したケースを入れてみると、答えが合わない。
2日目は、「なんでぇぇぇぇぇ…」と思いながら、1日を終えました。

＜3日目＞

なんか、昨日のソースをいじっていたら、正しい答えが出るソースができた気が。(うろ覚え)

＜中頃＞

チームのリーダーをあみだくじで決めた。
最後まで色々やってくれたリーダーさんに感謝……><

チームメイトさん①が、私より早いソースを製作。
やっぱすげぇなぁ…と思いながら、さりげなく抜かそうとしていた。

＜予選終了3〜5日前くらい＞

相変わらず、チームメイトさん①のソースを抜かそうとしていた。
新しく、二人のやってることを掛け合わせて書いてみたけれど、全く勝てない。(悲しい)

そうこうしていたら、チームメイトさん②が、めちゃくちゃ強いソース(未完成)を出してきた。驚いた。

＜終了前日＞

チーム名会議をした。チーム名の制約がさりげなく厳しくて、つらい。
でも、なんだかんだかっこいい名前ができた。

チームメイトさん②のソースの完成が厳しそうなので、チームメイトさん①のソースを出すことに。
夜中に提出してくれた。(本当にありがとうございます。)

＜終了後＞

とりあえず、校内ではまあまあ強そうな感じだった。
予選通過できるかはなんとも言えないけれど、答えはちゃんと出せていそうなので、とりあえず一安心。

私の書いたソースはこんなんでした。かなり遅いです。
最初に幅して、スタート地点からの距離を求めておきます。
そのあと深さして、行けない時はreturn 0するみたいなことをひたすらしてます。高速化も何もないです。←
答えは正しく出ると思います。

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stdio.h>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include"sc1.h"
using namespace std;

const int INF = (1 << 30);
const int MAX_N = 22;
const int nx[] = { 1, 0,-1, 0};
const int ny[] = { 0, 1, 0,-1};

typedef pair<int, int> P;

int n;
int path[MAX_N*2][MAX_N*2];
int trap[MAX_N*2][MAX_N*2];

int slv(int y, int x, int cnt);
void dfs();

int main(){
  ios_base::sync_with_stdio(false);
  
  int ans = 0;

  for(int i=0;i<MAX_N;i++){
    for(int j=0;j<MAX_N;j++){
      trap[i][j] = INF;
      path[i][j] = 0;
    }
  }
  
  scInput();

  n = scN;
  for(int i=0;i<scM;i++){
    int x = scB[0][i];
    int y = scB[1][i];
    if(x < -n || y < -n || x > n || y > n)continue;
    trap[x+n/2][y+n/2] = -1;
  }
  
  n /= 2; 

  dfs();
  ans = slv(n, n, n+n); 

  scOutput(ans); 

  return 0;
}

int slv(int y, int x, int cnt){
  
  if(y == n && x == n && cnt == 0) return 1;
  if(cnt < 0)return 0;
  if(y < 0 || x < 0 || y > n*2 || x > n*2)return 0;
  if(path[y][x] == 1)return 0;
  if(trap[y][x] == -1)return 0;
  if(trap[y][x] > cnt)return 0;

  int t = 0; 
  path[y][x] = 1;
  for(int i=0;i<4;i++){
    t += slv(y+ny[i], x+nx[i], cnt-1);
  } 
  
  path[y][x] = 0;
  return t;
}
void dfs(){
  
  queue<P> que;
  que.push(make_pair(n, n));
  trap[n][n] = 0;

  while(!que.empty()){
    P now = que.front(); que.pop();
    int y = now.first;
    int x = now.second;
    
    for(int i=0;i<4;i++){
      int xx = x + nx[i];
      int yy = y + ny[i];
      if(xx > 0 && yy > 0 && xx < n*2 && yy < n*2 && trap[yy][xx] == INF){
        trap[yy][xx] = trap[y][x] + 1;
        que.push(make_pair(yy, xx));
      }
    }      
  }

  return;
}