日本情報オリンピック予選参加記
はじめに
この記事はプロコンゼミ(SPC同好会) その1 Advent Calendar 20189日目の記事です。
最近になって急に冷え込んできましたね。季節を感じます。みなさんお体のほうは大丈夫でしょうか、僕は元気にやらせてもらってます。ありがとうございます。
さて、この記事では、12/9に行われた日本情報オリンピックに参加した話を私自身の結果を交えて書いていこうと思います。
参加記
A
目標のコインに到達するまでシュミュレートしてやればよいです。%7とか使うと楽かも
B
駒がおいてある/ないのフラグをもってシュミレーション
C
ループをN-1まで回して長さ2のsubstringを考えます。それが"OX","XO"ならループさせる変数に+1して答えにも+1
for(int a = 0;a < N-1;a++){ string s = S.substr(a,2); if(s == "XO" || s == "OX"){ a++; ans++; } }
D
priority_queueで小さい順に処理、ある区画が沈む時に影響を与えるのはたかだかその両隣だけなので、島の端っこかどうかのフラグを持ってあげてなんかよしなに処理する。
E
セグ木を使いそう(ここで思考が止まる)
bit全探索をすると10点の部分点がもらえます。うれしいね。
F
N!とかnCrとかいろいろ試したけど無理だった。
next_permutationが使えると6点がもらえます。やったね。
おわりに
ということで、僕は総合で416点という結果でした。まあこの点数なら予選は通ったでしょう、やったね。:v:
各所でボーダーが400を超えると言われていて、通ってるかどうか心配です。こわい。
いろいろ調べたけど今年はいつボーダーが発表されるのかわからなかったので、知ってる人は教えてください。(去年は12/14だったっぽいので近日中にはありそう)