第16回日本情報オリンピック 2016/2017 予選に参加した話

結果

これと比較した感じだと380点でした.
提出ミスしてなければ幸いです.
(追記) 360点で予選通過してました.プロ各位宜しくお願いします.ちなみに5問目の1ケースにinputを投げてしまい,20点を失いました.

1問目

やるだけ.もうちょっとコンパクトなコードを書きたかった.無駄な部分が多い.

// テンプレ省略

signed main() {
  int a, b, c, d, e;
  cin >> a >> b >> c >> d >> e;

  int ans = 0;
  if (b == a) {
    print(ans);
    return 0;
  }
  if (a < 0) {
    ans += c * abs(a);
    a = 0;
  }
  if (a == b) {
    print(ans);
    return 0;
  }
  if (a == 0) {
    ans += d;
  }
  print(ans + (b - a) * e);

  return 0;
}

2問目

これもやるだけ.b は使わなくていい.

signed main() {
  int n, m;
  cin >> n >> m;
  int ans = 0;
  vi a(m);
  REP(i, m) {
    int b;
    cin >> a[i] >> b;
  }
  sort(ALL(a));
  reverse(ALL(a));
  REP(i, m - 1) {
    if (a[i] < n) {
      ans += (n - a[i]);
    }
  }
  print(ans);

  return 0;
}

3問目

D という長さになればいいのである地点から東西南北4方向を見て# でなければそこからdfsをして,深さがD になったら答えに1加える.方向を引数でもってやればいい.最終的に出た数は被りがあるので2で割ってやる.別にfor でやっても良かった.
例年の3問目よりかなり簡単なのでは.多分ここらへんまでで30~40分.

int n, m, d;
char s[128][128];
int ans;

void dfs(int y, int x, int dep, int ddy, int ddx) {
  if (dep == d) {
    ans++;
    return;
  }
  int ny = y + ddy, nx = x + ddx;
  if (!inside(ny, nx, n, m)) return;
  if (s[ny][nx] == '#') return;
  dfs(ny, nx, dep + 1, ddy, ddx);
}

signed main() {
  cin >> n >> m >> d;
  REP(i, n) cin >> s[i];

  REP(i, n) REP(j, m) {
    if (s[i][j] != '#') {
      REP(k, 4) {
        int ny = i + dy[k], nx = j + dx[k];
        if (!inside(ny, nx, n, m)) continue;
        if (s[ny][nx] == '#') continue;
        dfs(i, j, 1, dy[k], dx[k]);
      }
    }
  }
  print(ans / 2);

  return 0;
}

4問目

テストケース1~3まで通しました.bitDPらしいですね.わかりません.
脳を完全に停止してnext_permutation() をし,順列を全列挙した.順列は最大でm! 種類あるのでm が大きい値だと計算量がまずい.このコードだとO(n * m!)になりますかねえ.ひどいなこれ. 順列と元のぬいぐるみと比較して,違う種類だったらカウント.そしてmin をとる.1時間ぐらいずっと回してた.

signed main() {
  int n, m;
  cin >> n >> m;
  vi a(n), b(m), cnt(n + 1);
  REP(i, m) b[i] = i + 1;
  REP(i, n) {
    cin >> a[i];
    cnt[a[i]]++;
  }
  int res = INF;
  do {
    int c = 0;
    int idx = 0;
    REP(i, m) REP(j, cnt[b[i]]) {
        if (a[idx++] != b[i]) c++;
      }
    }
    chmin(res, c);
  } while (next_permutation(ALL(b)));
  print(res);
  
  return 0;
}

問題5

解法が思いつかず,適当にdfsしたら1ケース目は通った.残りはなんかセグフォが起きたので諦めた.

int h, w;
vvi a;
int sum = 0;
bool vis[1000][1000];

void dfs(int y, int x, bool fi = false) {
  bool flg = false;
  REP(i, 4) {
    int ny = y + dy[i], nx = x + dx[i];
    if (!inside(ny, nx, h, w)) continue;
    if (a[y][x] > a[ny][nx]) {
      flg = true;
      dfs(ny, nx);
    }
  }
  if (!flg && !fi && !vis[y][x]) {
    sum++;
    vis[y][x] = true;
  }
}

signed main() {
  cin >> h >> w;
  a = vvi(h, vi(w));
  REP(i, h) REP(j, w) cin >> a[i][j];
  int res = 0;
  REP(i, h) REP(j, w) {
    memset(vis, 0, sizeof(vis));
    sum = 0;
    dfs(i, j);
    if (sum > 1) res++;
  }
  print(res);

  return 0;
}

問題6

拡張dijkstraらしいですね.
「いい感じにするdijkstraやろ!w」
と思ったけど,ぼくはスーパー適当なdijkstraを書いてsampleが通らないけど取り敢えず出しました.全ケース落ちました.コードは載せません. まぁでも,去年はdijkstraという言葉すら知らかったので成長はしたのかなという感じです.

感想

つらいです.3問目までめっちゃ簡単で「いけるやろ~」と調子に乗ったら,難易度が跳ね上がりました.明らかに精進不足です. もし予選通ってたら,本選までにDPとか克服していきたいです.

あと3問目まで答えを格納する変数名がans なのに4問目からres なのウケますね.

あー ねんまつ

JOI予選お疲れ様です

疲れました.僕は多分380点です.

この記事はICT Advent Calender2016 11日目の記事です.

僕が今年出た大会まとめ

今年は,去年より大会に出たいという気持ちが大きかったからか,多くの大会に出てるような気がします.
この中では,パソコン甲子園2016プログラミング部門もう一つの本選で8位になれたことは印象に残っていて,「工藤忍北条加蓮というチーム名がPCKのホームページに載っているのが面白かったです.因みに,FirstACも取れてウケてます.来年は本選に行きたいと思います.

覚えた・習得したこと

  • C#(高専プロコンでGUIを作った)
  • 競プロ(去年からやっているが今年は結構成長出来たと思う)
  • vim(今年からプラグインとか入れてる)
  • 画像処理(高専プロコンでほんのすこし触った)

興味があること

  • マラソンマッチ系の大会(まだ出たことないのでCodingameとかやっていきたい)
  • CTF(少しだけやって結構面白かったのでやりたい)
  • 画像処理(面白そう)
  • バイル系アプリ開発(Androidとかやりたい)
  • Python(面白そう)

欲しいもの

今年なんかめっちゃオタクになったっぽい

もうちょっとでモバマスのほうもPLvが100超えそうですし,デレステも楽しいですし(絶対特権主張しますっ!がすき),佐々木千枝は心臓が痛くなるほど可愛いし,工藤忍はリンゴの皮を剥くのが上手いです.
CDも結構買ったような気もします.

あと最近は冴島清美ちゃんが僕の中でキテます.














逸れ!w話が逸れ過ぎてシルク・ド・ソレイユになった!w














そんなことはどうでもよくて

来年からどうなるんだろうという不安があります.
何でも出来る人@orisano先輩が卒業されるので,ICT委員会の技術力が著しく低下するのでは,ということがあります.

僕もorisano先輩には色々教わっていますし,他の人もそうだと思います.しかし,来年はいません.今度は僕らが後輩に教えないといけません.特に競技プログラミングは誰が引っ張っていくのでしょうか.今,一番出来る人は@37kt_先輩なので是非とも後輩教育をお願いしたいものです.僕もやりますけど.

来年の目標

  • 高専プロコン競技部門†優勝†
  • パソコン甲子園2017プログラミング部門本選出場
  • SuperCon2017本選で上位

この3つの目標を達成するために頑張っていきたいです.

最後に

以上です.

明日は@yagamian_sobaya先輩と@Luzhiledです.
昨日は@manae_manawayでした.

#procon27 でホントの魅力はミエなかった(競技)

皆さんお疲れ様でした.
初めてのプロコン参加です.

結果

僕達,沖縄高専「罪深さ優先探索」は準決勝敗退でした.
悔しい,というかスッキリとしない結果になってしまいました.

というのも

今回の競技部門は

「ホントの魅力がミエますか?」

というタイトルで,概要としては

(1) 1 つの図形から切り出した複数の「ピース」と1つの「わく」が与えられます。
(2) 「わく」の内にすべての「ピース」を早く並べるパズルです。余分な「ピース」はありません。
(3) 競技終了後,「ピース」が重なっていたり,「わく」からはみ出していた場合には,審判がその「ピ ース」を取り除きます。取り除いた「ピース」はカウントされません。
(4) 「わく」の内にすべての「ピース」を並べ,かつ最も回答時間が早いチームが勝ちとなります。
すべての「ピース」が並べられない場合は,多くの「ピース」を並べたチームの勝ちとなります。
第27回プロコン募集要項

です.

去年の「石畳職人Z」と大きく違い,解答するときに提出するものがアナログであることに違和感を覚えました.
またピースやわくの情報もデジタルで与えられず,自分らでそれを取得する必要があるのも驚きました.

チームの方針

当初はスタンドスキャナでピースやわくを撮影し頂点座標を取得する予定でしたが,いざやってみると画像の歪みが発生してしまうこと,環境固定が面倒なことから,本番1週間前くらいにバスパワー駆動するフラッドヘッドスキャナで撮影する,というふうになりました.
もっと早い段階でこのことに気づけば結果は変わったんですかね(?) 画像処理担当はコーヤ先輩でした.詳しい話は後々上がると思います.

ソルバはorisano先輩でした.こちらも詳しい話は後々上がると思います.

ちなみに僕の担当はGUIで.ピースやわくの表示,それらをソルバに渡すなどのパイプ的役割の部分を担っており,割と重要な部分でした.フォームなどの作りやすさから,言語はC#を選択しました.実際に使ったやつ↓

github.com

本番

本番の1回戦
枠のマージに失敗してしまい,完全に人力になりました.(通過)

準決勝
ピースに0角形が含まれていてバグる.
手動で修正して,枠を撮影せずにorisano先輩が作ったいい感じの組み合わせを作ってくれるやつに流し込んだ.
それをほんのちょっと参考に(本当か?)しながら人力でやっていました.(敗退)

準決勝の結果(沖縄は第1試合)を見てもらえば分かると思いますが,通過した3チームは全て3分以内で提出しており(人力),尚且つmax-1なので,ピースの読み込みに4分くらい掛かる僕達のシステムではどうあがいても無理でした.

つらい

ひたすら題材がつらいイメージの競技部門でした.
あと,運営が決めたレギュレーションに運営自身が違反するというなんともいえないことも起き,めちゃくちゃでした.

極めつけは
優勝が人力
であることです.

これは一体何コンテストなんだろうか...
運営さん.三重のホントの魅力はミエましたか?僕はミエませんでした.

来年はまともな出題であることを祈っています.

反省

やはり一通りシステムを動かすというのは大切です.動かさないと見えない問題などもあるからです.
実は通しをしたのが当日のAM4:00で,そりゃ本番で動かないよなと納得できてしまいました.
これは毎年言われてるそうなので,改善すべき一番のポイントなのかなと感じます.
また,ソルバを書く人が一人しか居なかったことも問題でした.
マラソンマッチ的な競技では,複数のアルゴリズムを実装すべきでしたが今年はソルバを書く人がorisano先輩しかおらず非常に申し訳ないという気持ちと自分の実力不足が身にしみて分かりました.
そのためにはマラソンマッチに慣れる必要があるので,今日以降からは積極的に取り組んでいきたいと思っています.

高専プロコンに出場された皆様,及び関係者の皆さんお疲れ様でした. #procon28でまた会いましょう.