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

hamayanhamayan's blog

パソコン甲子園 プログラミング部門 解説まとめ

前は傾向と対策とか書いていたけど、だいぶ無責任な記事になっている(しかも古かった)ことに気が付いたので、ただの解説まとめにした。

2020年

# 点数 題名            要求(白塗りしてあるので選択で見て)            解説
A 3 緯度経度 プログラムが書けるか 解説
B 4 商店街へのお出かけ 条件分岐 解説
C 5 あいさつまわり 貪欲法 解説
D 6 カラフル円盤通し 性質を見つけて実装 解説
E 7 写真の回転 シミュレーション高速化と実装 解説
F 8 テトラへドロン 性質を見つける 解説
G 9 加工機 差分計算, シミュレーション最適化 解説
H 10 高速道路網 DAG, トポロジカルソート, DP 解説
I 10 倉庫番ロボット DP 解説
J 12 Copy&Sum [:title=解説]
K 13 パスポート [:title=解説]
L 13 色付き山小屋 [:title=解説]

2019年

# 点数 題名            要求(白塗りしてあるので選択で見て)            解説
A 3 柴犬の数 プログラムが書けるか 解説
B 4 アスキー文字 条件分岐 解説
C 5 2の累乗 全探索 解説
D 6 集会所 全探索 解説
E 7 ねこのあな スタック 解説
F 8 シミュレーション、根性実装 解説
G 9 アカベコ20 bitで全探索、最小公倍数 解説
H 11 矢印 [:title=解説]
I 11 天空の城ツルカ [:title=解説]
J 12 トーナメントの記録 [:title=解説]
K 12 イワシロの祈り [:title=解説]
L 12 ダンジョン3 [:title=解説]

10位ラインは64点(9完)

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 木DP [: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=解説]