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

hamayanhamayan's blog

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

競技プログラミング

自分は日本情報オリンピック出たこと無いし、運営という訳でもないので、参考程度にご覧ください。
最新の2019/2020年度は予選の形式がガラっと変わってるのでまだどうなるか分からないです。

はじめに

  • 概要と特徴
    • JOI: 日本情報オリンピック
    • 一人で実施する
    • 1次予選と2次予選がある
      • 1次予選：全部で3回あり、いずれかで突破すれば2次予選に招待される
      • 2次予選：全1回で、ここからが本番。5問ある。
    • 【2018/2019年度以前】6問あり、全部100点満点であるが、部分点がある問題が多い
      • 部分点の付け方もJOI2017/2018を境に変わっている
      • それより前は入力データが5つあり、1つ20点として換算されてる？
      • JOI2017/2018から予選はAtCoderでやっているようで、フルフィードバックなんだろうか（要出典）
  • 目標
    • 結果を見ると400点くらいが合格ライン。4完くらいが要求される
    • 5問中4完なので、網羅的に勉強しておかないといけない
    • 年々難しくなってる

対策

  • 一次予選
    • AtCoderのABC3完くらいが要求ラインかと思う。プログラミングの基礎的な部分の確認や、全探索を色々な条件でできるか、シミュレーション問題を実装できるかといったことが要求されている
      1. まずはけんちょんのAtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～を5章まで進めよう
      1. AtCoder Beginner ContestのA,B埋め（結構果てしないので、最新から十分かな？ってとこまでやろう。昔のは結構難しいので、最新半分くらいをとりあえずやると良いかも）
      1. JOI予選の過去問をやってみる（とりあえず前半3つ）
    • 二次予選突破を目指すなら、一次予選は楽勝くらいにならないといけない
  • 二次予選
    • 序盤3問はABCの4完レベル（かちょっとだけ上）
    • 高速4完を狙っていくのが良いかもしれない
    • 最近ICPCみたいな問題も出るようになった？傾向が分からない

傾向

  • 一次予選
    • AtCoderのABCの3完くらいの問題が揃っている
    • 全探索を考えて解く問題がある
    • 問題にかかれていることを実装するシミュレーション問題もある
    • 基礎的な実装が素早くできるようになっておこう
  • 二次予選
    • 序盤はABCのCDレベル（かちょっとだけ上）
    • 中盤でDPっぽいものが出てきた（想定解は違っていたけど）
    • 2問目と3問目の間で難易度が上がってる
    • 5問目は難しい（構文解析出てきた）

【2018/2019年度以前】対策

【2018/2019年度以前】傾向

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

年別統計

JOI2019/2020

# 題名 配点 要求（白塗りしてあるので選択で見て） 解説
A 100 ポスター シミュレーション 解説
B 100 いちご シミュレーション、最適手法を考える 解説
C 100 桁和 動的計画法 解説
D 30/70 テンキー 解説
E 20/20/60 じゃんけん式 構文解析 解説

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、大変な遷移 解説