#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でまた会いましょう.

AOJ0595 - Schedule

DPが出来なさすぎてつらいので練習

AOJ0595(Schedule)

コード

// 8種類の選び方 N日のスケジュール
int dp[8][1010];
const int mod = 1e4 + 7;

int getid(char c)
{
  if (c == 'J') return 0;
  if (c == 'O') return 1;
  return 2;
}

// 責任者が居ない場合を除外
void exclude(int now, int id)
{
  REP(i, 8) {
    if ((i & (1 << id)) == 0) {
      dp[i][now] = 0;
    }
  }
}

signed main()
{
  int N;
  string s;
  cin >> N >> s;

  REP(i, N) {
    // 一日目はJの参加が必須
    if (i == 0) {
      REP(j, 8) dp[j][i] = 1;
      exclude(i, 0);
    } else {
      REP(j, 8) {
        REP(k, 8) {
          // 前日に居た人が一人でも居なければ飛ばす
          if (j & k) {
            dp[k][i] = (dp[k][i] + dp[j][i - 1]) % mod;
          }
        }
      }
    }
    exclude(i, getid(s[i]));
  }
  int ans = 0;
  REP(i, 8) {
    ans = (ans + dp[i][N - 1]) % mod;
  }
  print(ans);

  return 0;
}

メモ

分からなかったのでJOIの解説を見ながら実装した.
dp[出席状況][何日目] = スケジュールの場合の数 を表す.
dp[k][i] = (dp[k][i] + dp[j][i - 1]) % mod は前日までの場合の数( dp[j][i - 1] )を足していく処理.
REP(j, 8) REP(k, 8) の部分で昨日の出席状況に合わせ,ありうる今日の出席状況を全列挙している.(ここでは責任者がいない場合は考慮していない)
そのあとのexclude(i, getid(s[i])) で責任者がいない出席状況のときの場合の数を0 にしている.

出席状況をbitで管理するのは面白いなぁと感じた.

こんな感じで1 が立ってるところは出席していると判断する.

I O J
0 0 0 0
1 0 0 1
2 0 1 0
3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1

exclude() の中で責任者がいない場合を判断するために論理和を使っている.
if (j & k) は前日に居た人が居なかったら飛ばす(鍵が無いので出席できないから)ところでも論理和を使って上手く判定している.

また配るDPは最後に足す処理があることが多いらしい.覚えておこう.

SuperCon2016に参加した話

Supercomputing Contest - Supercomputing Programing Contest Official Site

SuperCon2016の本選に参加しました.

キャンパスを間違えた

SuperConの会場は豊中キャンパスだったのですが,ぼくの調査不足により吹田キャンパスに行ってしまい,無限に時間を溶かしました.申し訳ないです.

大阪大学の学食は美味い

安くて美味しかったです.

色んな人にあった

みんな「THE・オタク」と言った感じで面白かったです.
ゲ・ドリンクくんは過度のストレスにより禿げてました.(マジ)
つよっしーくんは本名が「つよし」ではなかったです.
KO氏はデレステを片手でしていました.
うぃんじー氏はプロでした.
らて氏はルマンドの黄色と紫色の違いが分かるイケメンでした.

内容

n個の頂点,c色に塗り分け,d次の正則グラフの最短経路長の総和(ASPL)をなるべく小さくしようという問題.
SuperConなので東工大の「TSUBAME」を使って高速化しようみたいな感じです.
ぼくはそもそもグラフに関して疎く,今回の問題で沢山の知識を得ました.(ダイクストラ,ワーシャルフロイド,焼きなましとか)
言語はC言語(CUDA)を使いました. CUDAはGPUプログラミングに必要な環境で,TSUBAMEを使うためにはこれが必要でした.

方針としてはRandomに生成したグラフを重みの和が小さくなるようにつけかえていき,これ以上良くならなかったらASPLアスパラを計算して良くしていくという感じです.

ASPLはnが2048くらいになると死ぬほど時間がかかったので辛かったです.

結果

優勝は久留米高専の「GhostDiv」でした. そしてぼくたち沖縄高専「tsuraMI」は7位でした.つらみ.

4問目はなぜかぶっちぎりで1位でしたが,6問目は18位(最下位)など問題によって順位のブレがありました.
また,「GhostDiv」はGPU不使用でした.GPUを使わないチームは強いみたいな風潮があります.

感想

今回はjin先輩にコーディングなど任せっきりだったので,ぼくがやったことと言えばASPL高速化を考える(失敗したが)くらいしかしてません.反省しています.
そのためにはもっと競技力をつける必要があります.PCK,JOIがあることですし,蟻本等読んで勉強していきたいです.
来年は今年以上の結果を出せるようリベンジしたいです.