情報オリンピック予選の解法早見表
情報オリンピック予選の季節ですね.
情報オリンピック予選突破を目指して頑張る人達のために,予選の問題の解法に使えそうなアルゴリズム・データ構造・アドバイスを適当にまとめておきます.
なし=やるだけ
空欄はうまい説明が思いつかないか,AOJで通してない問題です.
回 | タイトル | AOJでの問題番号 | 解法(アドバイス) |
---|---|---|---|
第5回 | (問題1) | 0500 | なし |
(問題2) | 0501 | 言語標準のハッシュ表か二分探索木を用いると簡単にかける | |
(問題3) | 0502 | なし | |
(問題4) | 0503 | ハノイの塔が参考になる | |
(問題5) | 0504 | ||
第6回 | 得点 | 0510 | なし |
未提出者はだれだ | 0511 | なし | |
シーザー暗号 | 0512 | ASCII文字コード表をみると... | |
カードの並び替え | 0513 | なし | |
品質検査 | 0514 | なし | |
通学経路 | 0515 | 再帰(DPでもよい) | |
第7回 | おつり | 0521 | なし |
JOIとIOI | 0522 | なし | |
カードゲーム | 0523 | なし | |
星座探し | 0524 | ハッシュ表または二分探索 | |
船旅 | 0525 | Warshall-Floyd法が参考になるかも | |
第8回 | タイムカード | 0532 | なし |
コンテスト | 0533 | なし | |
連鎖 | 0534 | なし | |
薄氷渡り | 0535 | 再帰 | |
シャッフル | 0536 | カードを区間で管理して頑張る | |
ビンゴ | 0537 | DP(漸化式をうまく書き換える.AOJではメモリの節約が必要) | |
第9回 | レシート | 0543 | なし |
すごろく | 0544 | なし | |
パーティー | 0545 | なし(入力例2においてあなたには友達はいない) | |
カード並べ | 0546 | 再帰 | |
通勤経路 | 0547 | DP(通学経路の応用) | |
方向音痴のトナカイ | 0548 | ビットDP(本番では再帰+枝刈りでもOK) | |
第10回 | 合計時間 | 0554 | なし |
指輪 | 0555 | なし | |
タイル | 0556 | なし | |
1年生 | 0557 | DP | |
チーズ | 0558 | 幅優先探索 | |
JOI旗 | 0559 | ビットDP | |
第11回 | ランチ | 0567 | なし |
サッカー | 0568 | なし(言語標準のソートがうまく使えると楽) | |
最高のピザ | 0569 | なし | |
パスタ | 0570 | DP | |
イルミネーション | 0571 | ラべリング(スタックオーバーフローに注意) | |
ジグザグ数 | 0572 | DP |