はまやんはまやんはまやん

hamayanhamayan's blog

日本情報オリンピック 予選の傾向と対策

競技プログラミング

自分は日本情報オリンピック出たこと無いし、運営という訳でもないので、参考程度にご覧ください。

はじめに

  • 概要と特徴
    • JOI: 日本情報オリンピック
    • 一人で実施する
    • 6問あり、全部100点満点であるが、部分点がある問題が多い
      • 部分点の付け方もJOI2017/2018を境に変わっている
      • それより前は入力データが5つあり、1つ20点として換算されてる？
    • JOI2017/2018から予選はAtCoderでやっているようで、フルフィードバックなんだろうか（要出典）
    • JOI2019/2020からも予選方式が変わり、1次2次という形になっているみたい
  • 目標
    • 予選突破の目標は3完+部分点。4完ならば、今の所突破できそう
    • 年々難しくなってる

対策

傾向

  • 前半3つ
    • 全探索、シミュレーション、貪欲法が中心
    • 特殊なアルゴリズムをあまり要求しないが、実装がちょっと大変なものもある
    • 全探索対象を探して、しっかり全探索する
    • ABCならCまで通していきたい。Dレベルも。
  • 後半3つ

年別統計

JOI2018/2019

# 題名 配点 要求（白塗りしてあるので選択で見て） 解説
A 40/60 ソーシャルゲーム 全探索、シミュレーション 解説
B 100 すごろくと駒 シミュレーション 解説
C 100 マルバツスタンプ 貪欲法（hamayanhamayan解説解法はDPだけどいらない） 解説
D 7/8/85 日本沈没 シミュレーション、座標圧縮 解説
E 10/30/30/30 イルミネーション 解説
F 6/14/80 座席 組み合わせ問題、高次元DP 解説

3完+部分点全部くらいがボーダー(391点)

JOI2017/2018

# 題名 配点 要求（白塗りしてあるので選択で見て） 解説
A 100 鉛筆 基本計算 解説
B 100 双六 全探索+シミュレーション（hamayanhamayan解説では幅優先探索してるけどいらない） 解説
C 10/90 幹線道路 全探索 解説
D 10/27/63 水ようかん 小課題は状態全列挙、完答も全探索 解説
E 15/28/57 森林伐採 3次元でのDP 解説
F 6/33/61 L番目のK番目の数 二分探索,累積和 解説

3完+部分点1つ目+部分点どれかの2つ目がボーダー（334点以上）

JOI2016/2017 第16回日本情報オリンピック 予選

# 題名 配点 要求（白塗りしてあるので選択で見て） 解説
A 100 電子レンジ 場合分け、基本計算 解説
B 100 ポイントカード 貪欲法、ソート 解説
C 100 休憩スペース 全探索、(2次元累積和) 解説
D 100 ぬいぐるみの整理 bitDP、累積和 解説
E 100 尾根 幅優先探索 解説
F 100 ヘビのJOi君 拡張ダイクストラ 解説

3完+一部解答がボーダー（340点以上）

JOI2015/2016 第15回日本情報オリンピック 予選

https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_b https://www.ioi-jp.org/joi/2015/2016-yo/index.html

# 題名 配点 要求（白塗りしてあるので選択で見て） 解説
A 100 科目選択 最大最小 解説
B 100 ゼッケンの交換 シミュレーション 解説
C 100 ロシアの旗 全探索 解説
D 100 JOI国のお散歩事情 事前計算 解説
E 100 ゾンビ島 複数始点BFS, ダイクストラ 解説
F 100 屋台 超多次元DP、大変な遷移 解説