読者です 読者をやめる 読者になる 読者になる

「っこ」のブログ

っこがプログラミングに関しての記事を書くブログ

JOI予選予想

この記事はprolab Advent Calendar 2016の12/4の記事として書かれています。
www.adventar.org

どんどん参加しよう!(特に1,2年生が少ない)
多分ふざけた内容でもいいぞ!(もしかしたら自分がもう一日どこかでふざけた内容でやるかも)
ゲームの攻略でもなんでもええんやで!(というか去年僕は、途中までjubeatの上達について書いた気がする)




目次
1.言い訳
2.一年間の振り返り
3.JOI予選予想


実験的にこの記事はですます調を極力避けている。
それについて感想があれば是非コメントで書いたり僕に教えたりしてほしい。


言い訳

記事が公開される直前までAdventCalendarの内容の欄には何が書いてあっただろうか?
「才能と努力について」だ。
そんな深いこと僕は語れない。
というか、本当は語ろうと思っていたし、語ろうと思えばいくらでも語れるのだが、まだ思想が安定していない程度の人生経験なので、
1年後自分の記事を見てうわはずかしい(/ω\)ってなる気がしたのでやめた。

ついでに
・競プロは結局大事
フリーエンジニアや個人アプリ開発者として働くために
スマホゲーのマーケティング
・開発で作ろうとしているもの
・家事を減らす手段の比較(結婚、(男と)同居、ホテル族、執事・メイドを雇う)
などの没案がある。
すごく読みたい!と思うものがあれば、ぜひ教えてほしい。書いたり、LTでやったりするかもしれない。


1年間の振り返り

簡単に自分の2016 1月~1今日までを振り返る。去年はここが長すぎた気がするので、短く。
1月:なんかあったっけ。
2月:JOI本選にいく。あと10点で春合宿に行けた。 DDPCに行く。チョコフォンデュ美味しいった。
3月:CODE VSの予選をやっていた気がする。 音ゲー用のタブレットをこの辺で買った気がする。
4月:3年生になる。 アイデア出しがつらい。
5月:高専プロコンのアイデア出しと資料作りで忙しい。
6月:😇🖐
7月:高専プロコン頑張る。
8月:SuperCon本戦に出て11位で泣く。
9月:PCK予選8完11位で落ちたの私だ。
10月:高専プロコン自由部門で優秀賞(準優勝)。
11月:部長になる。 PCKもうひとつの本選で優勝する。
といった感じである。
あきらかに1月と6月なまけすぎた感じがあるので、そういう時間に開発の勉強を進めたい。


JOI予選予想

もうすぐJOI予選である。
JOI予選を通過したい人のために、
適当に問題を予想しようと思う。

また、今回の予想が外れても、僕はいっさい責任を負わない。
今年の流行語大賞のように責められても僕は知らない。
信じ切って練習するのは、自己判断自己責任でお願いする。

過去の傾向
f:id:sujinkko:20161204021013p:plain
この表から僕は3つの出題パターンを考えた。


パターン1
1問目:プログラミングの基本(難易度1)
2問目:簡単なシミュレーション(難易度2上位)
3問目:円環、頭良くやるやつ(難易度4)
4問目:DP(難易度5上位)
5問目:最小全域木(難易度6)
6問目:セグ木等の木系のデータ構造+α(難易度8上位~9下位)
ボーダー:420


まず1,2問目のパターンは変わらないと思う。
そもそもパターンが変わったところで、難易度4以上にはならないと思うので、ボーダーにはほぼ影響しないだろう。

表にまとめてみると、本選に比べて、予選には円環の問題が少ないという印象を受けた。
今回3問目に出ると予想しておく。

4問目にはDPが戻ってくると予想する。
前回DPではなくなったのは、DPを外す流れではなく、DPを続けすぎたからなのだと思う。

5問目はダイクストラに関する問題が出る気がしている。
最小全域木やるだけみたいな問題が来ると思う。

6問目は、データ構造系がなんとなく来ると思う。
例年通り、予選通過には影響しないと思われる。
(ただし300+20+20+20などがボーダーになることもあるので、部分点はとろう。)

400+20あたりがボーダーか。


パターン2
1問目:プログラミングの基本(難易度1)
2問目:簡単なシミュレーション(文字列を扱う)(難易度2上位)
3問目:二次元配列上もしくは二次元配列そのものをなにかしらシミュレーションして、循環性を探す問題(難易度4上位)
4問目:DP(難易度5上位~6下位)
5問目:min-max法、ゲームで戦う系(難易度6上位)
6問目:やばめのDP(難易度8)
ボーダー:360~380


3問目について説明すると、
ただ単純にシミュレーションすると時間が足りない。しかし途中で同じ盤面に戻る(同じ座標に同じ向きで戻る)。
それを使って、2周目以降のシミュレーションを省略する。
といった問題である。
ずいぶんと大胆に予想してみた。

5問目はなんとなく今min-max法が流行ってる気がしたので入れてみた。PCKもうひとつの本選のせいだろうか。

6問目は、一見DPに見え無さそうなDP。二次元のフィールドを~~ 系ではないと予想する。

4完凡ミス勢(400-40、400-20)や300+20+20+20あたりがボーダーか。


パターン3
1問目:プログラミングの基本(難易度1)
2問目:シミュレーション(難易度3)
3問目:やるだけDP(難易度5下位)
4問目:貪欲、仮定して貪欲(難易度6)
5問目:平均最大化(難易度7下位)
6問目:累積和+六角座標座圧(難易度9)
ボーダー:340


大胆に3問目にDPが来ると予想する。
ただし、3問目にDPが来た場合、難易度はシルクロード程度かそれ以下だと思う。

4問目に考察がいるような貪欲が来ると予想する。

5問目に二分探索に関する問題が来ると予想する。
二重二分探索も来るかもしれないと言っておく。

6問目は自分でもよくわからない。適当に来そうなのをくっつけた。

ボーダーは300+20+20あたりか。


やるべきこと
まず、難易度5のDPは解けるようにして損はない。6もできたらやったほうがいいだろう。
というかDPに限らず難易度5~6下位をひたすら埋めたほうがいい。
また、難易度3~4を正確に高速に解くことも大事である。
JOI予選は実質提出が一回の一発勝負なので、正確さは大事である。
また。JOI予選は3時間6問。しかも入力ファイル、出力ファイルの準備、
ダウンロード、アップロードなどがあるので実質2時間45分である。
速く解けて悪いことはない。


まとめ
頑張れ!!!!