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

hamayanhamayan's blog

パソコン甲子園 プログラミング部門 予選の傾向と対策

パソコン甲子園は地域枠というのがあるので、地方ならばかなり有利です!!
あと、自分自身パソコン甲子園出たこと無いし、運営という訳でもないので、参考程度にご覧ください。

はじめに

  • 目標
    • 都市にお住まいの方→6割くらい必要(8,9問解く)で10位以内に入る
    • 地方にお住まいの方→4割くらい必要(7問くらい)
      • 地域枠は出場者が偏らないように全国からバランスよく取ってくるので点数が低くても出場できる場合がある
      • 自分の県で周りに出てるとこないなら、狙い目
  • 概要(2018年)
    • 3時間
    • 競技中はインターネット使用禁止
    • 電子的な事前準備不可(ちゃんとライブラリを紙に印刷して持っていかないと場合によって終わる)
    • 時間より先に誤答回数でソートされてしまうので、誤答しないことが要求される
  • 本戦に行くには
    • 10位以内に入る(100点中55点くらいがボーダー?)
    • そうでなくても地域枠が15チームあるので、地方なら点数が結構無くても行ける

対策

1. まずは10点未満の問題を解けるようになろう(地域枠狙える)
 1.1. まずはけんちょんのAtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~を5章まで進めよう
 1.2. AtCoder Beginner ContestのA,B,C埋め(結構果てしないので、最新から十分かな?ってとこまでやろう。昔のは結構難しい)
 1.3. AOJ-PCK(パソコン甲子園過去問)の10点未満埋め
2. 10点以上の問題を狙っていく(だんだんとアルゴリズムを勉強することが求められる、都会向け)
 2.1. AtCoder Beginner ContestのC,D埋め(Dは結構難しいのも多い)
 2.2. アルゴリズム勉強(動的計画法、BIT、セグメントツリー、UnionFind、BFS、累積和、imos法、ダイクストラ、ワーシャルフロイド、しゃくとり法、半分全列挙)

傾向

  • 4点以下
    • プログラムの基礎を要求(入出力、ループ、条件分岐)
  • 5~9点
    • 何かを全探索
    • 面倒な実装問題(実装問題はICPC予選の最初の方も練習になるかもしれない)
    • 貪欲法
    • 簡単な数学的問題
    • ソート
    • 差分計算
    • シミュレート
  • 10~13点
    • 基本的なデータ構造(累積和とかセグメントツリーとかUnionFindとか)
    • DP(普通のDP, bitDP, 文字列系DP)
  • 14点~

年別統計

問題はここから

  • 2018年
# 点数 題名            要求(白塗りしてあるので選択で見て)            解説
A 3 摂氏華氏 プログラムが書けるか 解説
B 3 赤とんぼ abs関数か条件分岐 解説
C 4 ケーキパーティー 総和を取る、切り上げ 解説
D 5 熱中症対策 全探索 解説
E 6 デュードニー数 全探索 解説
F 7 ボゾソート 差分計算 解説
G 10 ワープ装置 DP 解説
H 10 タクシー 貪欲法、priority_queue 解説
I 10 直線上の点 幾何 解説
J 14 ダンジョン2 [:title=解説]
K 14 円盤 [:title=解説]
L 14 待ち合わせ [:title=解説]

10位ラインは58点(9完)
9完はや解きで10位以内
地域枠を狙うなら7完くらいあると安心な感じがする

  • 2017年
# 点数 題名            要求(白塗りしてあるので選択で見て)            解説
A 3 お年玉 プログラムが書けるか 解説
B 4 お買い物 条件分岐が求められる 解説
C 4 9月X日 実装問題。剰余を使う 解説
D 5 予約システム 区間が重複しているかを判定。imos法でも解ける 解説
E 6 電線 gcdが要求される。数学的考察が難しい 解説
F 11 トランポリン 単調性を理解しないと難しい。DPとも捉えられる 解説
G 11 積み荷の配置 bitDP 解説
H 11 ダンジョン 累積和みたいな考え方。片方を全探索して、もう片方は貪欲 解説
I 14 人気のユーザ名 BIT、貪欲構築 解説
J 14 道路網改修 SCC 解説
K 17 ネットワークの課金システム HL分解(想定解)、クエリの平方分割 [:title=解説]

10位以内だと58点必要(8完) 55/100

  • 2016年
# 点数 題名            要求(白塗りしてあるので選択で見て)            解説
A 3 ワード プログラムが書けるか 解説
B 4 日の出と日の入り 条件分岐が求められる 解説
C 5 日本の暦 実装問題。ループと分岐でコード量を減らす 解説
D 8 ニュータウン ある部分に注目して全探索。gcdでの解法が想定解 解説
E 8 形状データ処理 ソートが要求される。集合という考え方も必要 解説
F 10 パンケーキの焼き上がり 貪欲法。DPを活用しても解ける。 解説
G 10 イワシロ・イッツァ 文字列系DP 解説
H 14 村の道路計画 凸包、クラスカル法(UnionFind) 解説
I 18 プログラミングコンテスト2 クエリ先読み、座標圧縮、二分探索(根性実装系) [:title=解説]
J 20 ゲームの攻略 [:title=解説]
  • 2015年
# 点数 題名            要求(白塗りしてあるので選択で見て)            解説
A 3 パソコン甲子園の参加者数 プログラムが書けるか 解説
B 4 猪苗代湖の魚釣り競争 切り捨て。条件分岐。 解説
C 6 カエルはまっすぐ帰る 貪欲法 解説
D 8 極秘調査 数学的問題 解説
E 9 プログラミングコンテスト 答えを全探索 解説
F 12 品質管理 差分だけ再計算 解説
G 13 部活動調査 データを保持したUnionFind 解説
H 15 石版 [:title=解説]
I 15 ヒバラ海に沈む遺跡 数学(三平方)、実数の三分探索 解説
J 15 滑降競技 [:title=解説]
  • 2014年
# 点数 題名            要求(白塗りしてあるので選択で見て)            解説
A 3 椅子の総数 プログラムが書けるか 解説
B 4 お風呂メタボ診断 切り捨て。条件分岐。実装問題 解説
C 4 残り物には福がある while文。シミュレーション。 解説
D 5 路線バスの時刻表 実装。ソート、重複削除。特殊な出力。 解説
E 8 鉄道路線 全探索、循環する配列の扱い、mod 解説
F 10 フロッピーキューブ 強実装、BFS、全探索 解説
G 12 バトンリレーゲーム 双方向リスト、シミュレート 解説
H 16 天体観測 ソート、lower_bound, セグメントツリー 解説
I 18 力持ち 区間DP 解説
J 20 学食 [:title=解説]