JOI 2015 予選 問題予想

予選で出る問題のアルゴリズムについて予想してみる。
アルゴリズム全部列挙すれば当たるってはっきり分かるけれども。
詳しい予選問題過去問の分析については予選終わってから書く。
問題3からは出そうな順で書いていきます。

• 問題1

変数と四則演算、値の入出力ができれば解ける問題。
ぶっちゃけ電卓でもできなくはない。

• 問題2

配列の扱い
ソート
簡単な文字列（文字列の検索など）
ができれば解ける問題。

• 問題3

1. 考察系で、実装は軽い問題
2. 貪欲法
3. 文字列を扱う問題
4. シミュレーション問題（実装重くなる傾向）
5. (DP)

問題3からDPを持ってくるのはさすがにないと思う...

• 問題4

1. DP

問題4はDP(Dynamic Programming)が出ます。JOI予選はアルゴリズムの特別な知識がなくても解ける問題が出やすいのでJOIはDPが大好きです。過去4年ぐらい連続でDPが出ています。
(DPが解けなくても予選を通過することはできなくはないけど,DPが解けたら予選通過はほぼ確実と言ってもいいんじゃないかなぁ)

• 問題5

1. 全探索（深さ、幅）
2. 最短路問題（ダイクストラ法、ワーシャルフロイド法、ベルマンフォード法）
3. Union-Find
4. 二分探索
5. 最小全域木
6. (計算幾何の簡単な問題)

問題5は、3年ぐらい前までは全探索がほとんどだったのですが去年はダイクストラ法が出たりと、特定のアルゴリズムの知識を要求する問題が出るかと思います。

• 問題6

1. 難しいDP
2. 難しい全探索

問題6は部分点は容易にとれても満点をとるのが難しい問題がでます。まぁ部分点とれればいいんじゃないかなぁ（プロは除く）

• まとめ

問題4のDPはとても重要なので予選通過したい人はDPやりまくりましょう。
とある事情でデータ構造の問題はほぼ出ないと考えていいと思います。
正直おれも予選通過できるかわかんねえな感はある。

※2015/01/26 20:41 追記
予選なんとか通りました。
予想についての結果ですが、概ねあっていたと思います。
問題3と6が若干違ったけど。
ボーダー420点から察するに、易化した&&参加者の全体的なれヴぇるが上がったと考えられます。
私はJOI2016予選の参加資格はありませんが、どのような問題がでるのか非常に楽しみです。