AOJ0595 - Schedule
DPが出来なさすぎてつらいので練習
コード
// 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の本選に参加しました.
キャンパスを間違えた
キャンパス間違えた!w
— kurokoji@SuperCon (@kuro__koji__) 2016年8月22日
SuperConの会場は豊中キャンパスだったのですが,ぼくの調査不足により吹田キャンパスに行ってしまい,無限に時間を溶かしました.申し訳ないです.
大阪大学の学食は美味い
@gedorinku pic.twitter.com/CkeYxLXZVb
— kurokoji@SuperCon (@kuro__koji__) 2016年8月22日
@gedorinku 進捗どうですか pic.twitter.com/rlC4SMPGfX
— kurokoji@SuperCon (@kuro__koji__) 2016年8月23日
@gedorinku pic.twitter.com/RH99VnZFWL
— kurokoji@SuperCon (@kuro__koji__) 2016年8月24日
安くて美味しかったです.
色んな人にあった
みんな「THE・オタク」と言った感じで面白かったです.
ゲ・ドリンクくんは過度のストレスにより禿げてました.(マジ)
つよっしーくんは本名が「つよし」ではなかったです.
KO氏はデレステを片手でしていました.
うぃんじー氏はプロでした.
らて氏はルマンドの黄色と紫色の違いが分かるイケメンでした.
内容
n個の頂点,c色に塗り分け,d次の正則グラフの最短経路長の総和(ASPL)をなるべく小さくしようという問題.
SuperConなので東工大の「TSUBAME」を使って高速化しようみたいな感じです.
ぼくはそもそもグラフに関して疎く,今回の問題で沢山の知識を得ました.(ダイクストラ,ワーシャルフロイド,焼きなましとか)
言語はC言語(CUDA)を使いました.
CUDAはGPUプログラミングに必要な環境で,TSUBAMEを使うためにはこれが必要でした.
方針としてはRandomに生成したグラフを重みの和が小さくなるようにつけかえていき,これ以上良くならなかったらASPLアスパラを計算して良くしていくという感じです.
ASPLはnが2048くらいになると死ぬほど時間がかかったので辛かったです.
結果
はいじゃないが pic.twitter.com/k6Va7Tgxua
— winjii(non-native) (@wing3196) 2016年8月26日
優勝は久留米高専の「GhostDiv」でした. そしてぼくたち沖縄高専「tsuraMI」は7位でした.つらみ.
4問目はなぜかぶっちぎりで1位でしたが,6問目は18位(最下位)など問題によって順位のブレがありました.
また,「GhostDiv」はGPU不使用でした.GPUを使わないチームは強いみたいな風潮があります.
感想
今回はjin先輩にコーディングなど任せっきりだったので,ぼくがやったことと言えばASPL高速化を考える(失敗したが)くらいしかしてません.反省しています.
そのためにはもっと競技力をつける必要があります.PCK,JOIがあることですし,蟻本等読んで勉強していきたいです.
来年は今年以上の結果を出せるようリベンジしたいです.