トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

競技プログラミングの履歴

[競技プログラミング,アルゴリズム]

AtCoder

  必要そうなアルゴリズム

アルゴリズムは数学でいう大道具という感じで、課題自体ではない気がしている。課題を別のトピックで整理すべきか?

  問われる課題

タイトル 解決のためのアルゴリズム要素 備考
評価関数をもつ二分探索 二分探索 AtCoder 版!蟻本 (中級編)
最小共通祖先 ダブリング セグメント木? ムズイ
辞書順最小 貪欲法?
桁に~を含む数字の数え上げ 桁DP?
ゲーム問題? 整理中…
シミュレーション? 整理中…
区間スケジューリング問題? 貪欲法?
括弧の整合性チェック スタック・キュー

  問題へのポインタ

ブログ等

書籍

  解答履歴

  • AtCoder Problems
    • ここでほぼ管理できる
    • キャッシュが更新されないので自分でも管理することにした

+ 2017年

+ 2018年

  • 次解けそうな問題(蟻本で学べるところを優先で)
    • abc011
      • 数学
    • abc015
      • ナップサック問題

  AtCoder Dレベル問題

001〜020

index タイトル URL アルゴリズム要素 解けた? 解き方
abc001 感雨時刻の整理 https://beta.atcoder.jp/contests/abc001/tasks/abc001_4 imos法・累積和 AC#1970899 条件がちょっと面倒だけどそれをクリアすれば累積和をやるだけ
abc002 派閥 https://beta.atcoder.jp/contests/abc002/tasks/abc002_4 全探索 AC#2865393 最大クリーク問題を深さ優先探索で解くのは難しい、N=12なので全探索でOK
abc003 AtCoder社の冬 https://beta.atcoder.jp/contests/abc003/tasks/abc003_4 場合の数? 包除定理 包除定理蟻本 4-1 p.264を見ること
abc004 マーブル https://beta.atcoder.jp/contests/abc004/tasks/abc004_4 動的計画法 AC#1935144 解説ページ: AtCoder Beginner Contest 004。マーブルの配置方法の探索を動的計画法で行う。
abc005 おいしいたこ焼きの焼き方 https://beta.atcoder.jp/contests/abc005/tasks/abc005_4 動的計画法 AC#1961658 解説ページ: AtCoder Beginner Contest 005。正方形の内部に取りうるすべての面積のパターンを動的計画法で探索する。
abc006 トランプ挿入ソート https://beta.atcoder.jp/contests/abc006/tasks/abc006_4 最長増加部分列 AC#1648990 最長増加部分列をやるだけ
abc007 禁止された数字 https://beta.atcoder.jp/contests/abc007/tasks/abc007_4 動的計画法(桁DP) AC#2753885 動的計画法(桁DP) をやるだけ(禁止文字列については 蟻本 4-7 p.327など参照)
abc008 金塊ゲーム https://beta.atcoder.jp/contests/abc008/tasks/abc008_4 メモ化探索? 区間DP? 座標圧縮
abc009 漸化式 https://beta.atcoder.jp/contests/abc009/tasks/abc009_4 排他的論理和? 行列累乗? 半環?
abc010 浮気予防 https://beta.atcoder.jp/contests/abc010/tasks/abc010_4 ネットワークフロー?
abc011 大ジャンプ https://beta.atcoder.jp/contests/abc011/tasks/abc011_4 数論 解説ページ: AtCoder Beginner Contest 011
abc012 バスと避けられない運命 https://beta.atcoder.jp/contests/abc012/tasks/abc012_4 ダイクストラ法 ワーシャルフロイド法 AC#1728053 ダイクストラ法 もしくは ワーシャルフロイド法
abc013 阿弥陀 https://beta.atcoder.jp/contests/abc013/tasks/abc013_4 ダブリング AC#2756669 あみだくじの結果を求める→ダブリングで指定された回数あみだくじを繰り返した結果を求める。テストケースの内容がちょっと意地悪かも(Mは0<=M<=2*10^5)。
abc014 閉路 https://beta.atcoder.jp/contests/abc014/tasks/abc014_4 ダブリング 最小共通祖先 木構造 TLE #1676182 解説: AtCoder Beginner Contest 014 ダブリングで木構造の親を先に計算しておく、もしくはセグメント木など使用する
abc015 高橋くんの苦悩 https://beta.atcoder.jp/contests/abc015/tasks/abc015_4 動的計画法 - ナップサック問題 解説ページ: AtCoder Beginner Contest 015。ナップサック問題の亜種なんだけど普通にTLEになるから困る
abc016 一刀両断 https://beta.atcoder.jp/contests/abc016/tasks/abc016_4 幾何?
abc017 サプリメント https://beta.atcoder.jp/contests/abc017/tasks/abc017_4 しゃくとり法? DP? 複数の解答方法があるかもしれない、調査中
abc018 バレンタインデー https://beta.atcoder.jp/contests/abc018/tasks/abc018_4 半分全列挙 XOR?
abc019 高橋くんと木の直径 https://beta.atcoder.jp/contests/abc019/tasks/abc019_4 グラフアルゴリズム
abc020 LCM Rush https://beta.atcoder.jp/contests/abc020/tasks/abc020_d 数論 最小公倍数? 解説を読んだけど結構複雑なので取り掛かるのは後のほうがいいかも(曰くAGCのD問レベル)

021〜040

index タイトル URL アルゴリズム要素 解けた? 解き方
abc021 多重ループ https://beta.atcoder.jp/contests/abc021/tasks/abc021_d 順列・組み合わせ 繰り返し2乗法 階乗のmod逆元? AC #2640520 abc066とほぼ同じアルゴリズム要素。解説では逆元も先に計算するように書かれているが、別にやらなくても間に合う。
abc022 Big Bang https://beta.atcoder.jp/contests/abc022/tasks/abc022_d 競プロ数学
abc023 射撃王 https://beta.atcoder.jp/contests/abc023/tasks/abc023_d 二分探索
abc024 動的計画法 https://beta.atcoder.jp/contests/abc024/tasks/abc024_d 数論 mod逆元?
abc025 25個の整数 https://beta.atcoder.jp/contests/abc025/tasks/abc025_d 動的計画法(bit DP)
abc026 高橋君ボール1号 https://beta.atcoder.jp/contests/abc026/tasks/abc026_d 二分探索 AC#2744991 これは本当に二分探索やるだけ
abc027 ロボット https://beta.atcoder.jp/contests/abc027/tasks/abc027_d 動的計画法
abc028 乱数生成 https://beta.atcoder.jp/contests/abc028/tasks/abc028_d 順列・組み合わせ
abc029 1 https://beta.atcoder.jp/contests/abc029/tasks/abc029_d 順列・組み合わせ 動的計画法(桁DP)
abc030 へんてこ辞書 https://beta.atcoder.jp/contests/abc030/tasks/abc030_d 順列・組み合わせ
abc031 語呂合わせ https://beta.atcoder.jp/contests/abc031/tasks/abc031_d
abc032 ナップサック問題 https://beta.atcoder.jp/contests/abc032/tasks/abc032_d 動的計画法 - ナップサック問題 半分全列挙 AC#3104480 半分全列挙を使うと部分点。動的計画法を使えば完解となる。とても奥が深い。LL言語では解けない。解説ページを作った:AtCoder Beginner Contest 032
abc033 三角形の分類 https://beta.atcoder.jp/contests/abc033/tasks/abc033_d 二分探索 しゃくとり法?
abc034 食塩水 https://beta.atcoder.jp/contests/abc034/tasks/abc034_d 二分探索 評価関数をもつ二分探索 AC#2972413 解説ページ: AtCoder Beginner Contest 034評価関数をもつ二分探索、蟻本を読んでプロコンに勝て
abc035 トレジャーハント https://beta.atcoder.jp/contests/abc035/tasks/abc035_d ダイクストラ法
abc036 塗り絵 https://beta.atcoder.jp/contests/abc036/tasks/abc036_d 木構造 ツリーDP?
abc037 経路 https://beta.atcoder.jp/contests/abc037/tasks/abc037_d メモ化探索? DAGDP? AC #1988433 解説ページ: AtCoder Beginner Contest 037。ただの領域探索なのだが、メモ化+深さ優先探索の両方を使用しないとTLEになる、してもRubyだとTLEになる。ムリダナ。
abc038 プレゼント https://beta.atcoder.jp/contests/abc038/tasks/abc038_d 二分探索 最長増加部分列 (動的計画法) AC #2744487 最長増加部分列の配列がハッシュになったら?という問題、解説ページ: AtCoder Beginner Contest 038。解説にはフェニック木(Binary Indexed Tree)が載っているが、実際誰も使っていないという…後味悪し。問題自体はほかにも応用できそう。
abc039 画像処理高橋君 https://beta.atcoder.jp/contests/abc039/tasks/abc039_d
abc040 道路の老朽化対策について https://beta.atcoder.jp/contests/abc040/tasks/abc040_d Union-Find木 AC #1754689 幅優先探索かと思ったが、それは罠で Union-Find木。計算量がシビア。アルゴリズムは正解だが、エッジの操作はO(1)で行わないといけないようだ → std.container.BinaryHeap 使うか

041〜060

index タイトル URL アルゴリズム要素 解けた? 解き方
abc041 徒競走 https://beta.atcoder.jp/contests/abc041/tasks/abc041_d トポロジカルソート? AtCoder 版!蟻本 (中級編)? でヒントを得た。これ難しくね?
abc042 いろはちゃんとマス目 / Iroha and a Grid https://beta.atcoder.jp/contests/abc042/tasks/arc058_b 順列・組み合わせ 繰り返し2乗法 階乗のmod逆元? AC#2867064 組み合わせの計算量問題。よくある最短経路の問題だが数え上げ方がちゃんとしてないと不正解になる。
abc043 アンバランス / Unbalanced https://beta.atcoder.jp/contests/abc043/tasks/arc059_b
abc044 桁和 / Digit Sum https://beta.atcoder.jp/contests/abc044/tasks/arc060_b
abc045 すぬけ君の塗り絵 / Snuke's Coloring https://beta.atcoder.jp/contests/abc045/tasks/arc061_b 全探索
abc046 AtCoDeerくんと変なじゃんけん / AtCoDeer and Rock-Paper https://beta.atcoder.jp/contests/abc046/tasks/arc062_b ゲーム問題?
abc047 高橋君と見えざる手 / An Invisible Hand https://beta.atcoder.jp/contests/abc047/tasks/arc063_b
abc048 An Ordinary Game https://beta.atcoder.jp/contests/abc048/tasks/arc064_b ゲーム問題?
abc049 連結 / Connectivity https://beta.atcoder.jp/contests/abc049/tasks/arc065_b Union-Find木 AC #2832990 全点対間最短経路かと思わせつつそれは罠でUnion-Find木、O(α(N))の実装で計算量を削減する必要がある
abc050 Xor Sum https://beta.atcoder.jp/contests/abc050/tasks/arc066_b
abc051 Candidates of No Shortest Paths https://beta.atcoder.jp/contests/abc051/tasks/abc051_d ワーシャルフロイド法 AC #2781886 ワーシャルフロイド法 やるだけ。問題は無向グラフなのでそこだけ注意。
abc052 Walk and Teleport https://beta.atcoder.jp/contests/abc052/tasks/arc067_b
abc053 Card Eater https://beta.atcoder.jp/contests/abc053/tasks/arc068_b 考察系の問題に見える、ソートの方法を先読みする?
abc054 Mixing Experiment https://beta.atcoder.jp/contests/abc054/tasks/abc054_d 動的計画法 解説ページ: AtCoder Beginner Contest 054 DPやるだけらしい
abc055 Menagerie https://beta.atcoder.jp/contests/abc055/tasks/arc069_b 動的計画法 - ビットDP? これはチーター本にあった気がするBIT DPか
abc056 No Need https://beta.atcoder.jp/contests/abc056/tasks/arc070_b 動的計画法 二分探索 数値の集合を求める処理は01ナップサック問題の類題でそこから要素を間引くときに2分探索を使う感じ
abc057 Maximum Average Sets https://beta.atcoder.jp/contests/abc057/tasks/abc057_d 順列・組み合わせ
abc058 井井井 / ### https://beta.atcoder.jp/contests/abc058/tasks/arc071_b 動的計画法 動的計画法領域分割? AtCoder Beginner Contest 005と同じか?
abc059 Alice&Brown https://beta.atcoder.jp/contests/abc059/tasks/arc072_b ゲーム問題?
abc060 Simple Knapsack https://beta.atcoder.jp/contests/abc060/tasks/arc073_b 全探索?

061〜080

index タイトル URL アルゴリズム要素 解けた? 解き方
abc061 Score Attack https://beta.atcoder.jp/contests/abc061/tasks/abc061_d ベルマン–フォード法 AC#2797025 負数を含む最短経路、いろいろハマりポイントあり。アルゴリズムのページにtipsを記載
abc062 3N Numbers https://beta.atcoder.jp/contests/abc062/tasks/arc074_b 優先度つきキュー アルゴリズム方式よりも数学的な部分を考えておいたほうがよさそう
abc063 Widespread https://beta.atcoder.jp/contests/abc063/tasks/arc075_b 競プロ数学 二分探索
abc064 Insertion https://beta.atcoder.jp/contests/abc064/tasks/abc064_d 競プロ数学 スタック・キュー AC#2902340 このような括弧の正当性をチェックする問題は「balanced parentheses」で検索できる。定石を知らないと解けない感じ。参考:Insertion - AtCoder Beginner Contest 064 D
abc065 Built? https://beta.atcoder.jp/contests/abc065/tasks/arc076_b 最小全域木? 最小全域木?を素直に実装してしまうと間に合わない。必要のない辺を省く。
abc066 11 https://beta.atcoder.jp/contests/abc066/tasks/arc077_b 順列・組み合わせ 繰り返し2乗法 階乗のmod逆元? AC #2632348 考察&高速な組み合わせの算出 解説ページ: AtCoder Beginner Contest 066
abc067 Fennec VS. Snuke https://beta.atcoder.jp/contests/abc067/tasks/arc078_b グラフアルゴリズム - 幅優先探索 グラフアルゴリズム - 深さ優先探索
abc068 Decrease (Contestant ver.) https://beta.atcoder.jp/contests/abc068/tasks/arc079_b 考察? 競プロ数学
abc069 Grid Coloring https://beta.atcoder.jp/contests/abc069/tasks/arc080_b 考察?
abc070 Transit Tree Path https://beta.atcoder.jp/contests/abc070/tasks/abc070_d 最小公倍数? ツリーDP?
abc071 Coloring Dominoes https://beta.atcoder.jp/contests/abc071/tasks/arc081_b 考察?
abc072 Derangement https://beta.atcoder.jp/contests/abc072/tasks/arc082_b 考察?
abc073 joisino's travel https://beta.atcoder.jp/contests/abc073/tasks/abc073_d ワーシャルフロイド法 AC#3140601 解説:AtCoder Beginner Contest 073 ワーシャルフロイド実行後に組み合わせを全列挙して移動距離の最小値を求める。まともにワーシャルフロイドするとLL言語では通りません(初!)。D言語に翻訳したら通った。
abc074 Restoring Road Network https://beta.atcoder.jp/contests/abc074/tasks/arc083_b ワーシャルフロイド法
abc075 Axis-Parallel Rectangle https://beta.atcoder.jp/contests/abc075/tasks/abc075_d
abc076 AtCoder Express https://beta.atcoder.jp/contests/abc076/tasks/abc076_d 動的計画法
abc077 Small Multiple https://beta.atcoder.jp/contests/abc077/tasks/arc084_b グラフアルゴリズム - 幅優先探索
abc078 ABS https://beta.atcoder.jp/contests/abc078/tasks/arc085_b ゲームDP?
abc079 Wall https://beta.atcoder.jp/contests/abc079/tasks/abc079_d ワーシャルフロイド法 AC#3141758 ワーシャルフロイド法やるだけ。問題文をよく読めば解くことは可能かと…(オンサイトで解けるとは言っていない)
abc080 Recording https://beta.atcoder.jp/contests/abc080/tasks/abc080_d imos法・累積和 AC#2861626 累積和とちょっとした考察ができれば簡単なのだが、解答に半年かかった

081〜100

index タイトル URL アルゴリズム要素 解けた? 解き方
abc081 Non-decreasing https://beta.atcoder.jp/contests/abc081/tasks/arc086_b
abc082 FT Robot https://beta.atcoder.jp/contests/abc082/tasks/arc087_b
abc083 Wide Flip https://beta.atcoder.jp/contests/abc083/tasks/arc088_b 競プロ数学 XOR? AC#1907644 考察系の問題で、ちょっと今でも理解はできてない
abc084 2017-like Number https://beta.atcoder.jp/contests/abc084/tasks/abc084_d imos法・累積和 エラトステネスのふるい AC #2792189 エラトステネスのふるい を応用して素数テーブルを高速に構築する必要がある
abc085 Katana Thrower https://beta.atcoder.jp/contests/abc085/tasks/abc085_d
abc086 Checker https://beta.atcoder.jp/contests/abc086/tasks/arc089_b 二次元累積和 解説ページ: AtCoder Beginner Contest 086。二次元累積和の問題なのだが、ターゲットの選び方に考察が必要。
abc087 People on a Line https://beta.atcoder.jp/contests/abc087/tasks/arc090_b Union-Find応用? AtCoder 版!蟻本 (初級編) 情報をもとに調査中
abc088 Grid Repainting https://beta.atcoder.jp/contests/abc088/tasks/abc088_d グラフアルゴリズム - 幅優先探索
abc089 Practical Skill Test https://beta.atcoder.jp/contests/abc089/tasks/abc089_d
abc090 Remainder Reminder https://beta.atcoder.jp/contests/abc090/tasks/arc091_b
abc091 Two Sequences https://beta.atcoder.jp/contests/abc091/tasks/arc092_b
abc092 Grid Components https://beta.atcoder.jp/contests/abc092/tasks/arc093_b
abc093 Worst Case https://beta.atcoder.jp/contests/abc093/tasks/arc094_b
abc094 Binomial Coefficients https://beta.atcoder.jp/contests/abc094/tasks/arc095_b 順列・組み合わせ 競プロ数学 AC#2904720 これも組み合わせの計算量削減問題と見せかけて数学。nCrが最大値をとるのはrがnのちょうど半分に近づくとき。それを使用すれば正解できる。
abc095 Static Sushi https://beta.atcoder.jp/contests/abc095/tasks/arc096_b
abc096 Five, Five Everywhere https://beta.atcoder.jp/contests/abc096/tasks/abc096_d
abc097 Equals https://beta.atcoder.jp/contests/abc097/tasks/arc097_b Union-Find木
abc098 Xor Sum 2 https://beta.atcoder.jp/contests/abc098/tasks/arc098_b しゃくとり法?
abc099 Good Grid https://beta.atcoder.jp/contests/abc099/tasks/abc099_d
abc100 Patisserie ABC https://beta.atcoder.jp/contests/abc100/tasks/abc100_d

101〜

index タイトル URL アルゴリズム要素 解けた? 解き方
abc101 Snuke Numbers https://beta.atcoder.jp/contests/abc101/tasks/arc099_b
abc102 Equal Cut https://beta.atcoder.jp/contests/abc102/tasks/arc100_b
abc103 Islands War https://beta.atcoder.jp/contests/abc103/tasks/abc103_d 区間スケジューリング問題? AC#2898819 蟻本にも載っている典型的な問題でした。ただ、蟻本だと「いくつのジョブまで同時に実行できるでしょう?」だったのが、「島から島への連絡を切断するためにはいくつ橋を切断すればいいでしょう?」に変わる。本質を見抜かないと難しい。
abc104 We Love ABC https://beta.atcoder.jp/contests/abc104/tasks/abc104_d 動的計画法 or 順列・組み合わせ 解き方は複数ありそう
abc105 Candy Distribution https://beta.atcoder.jp/contests/abc105/tasks/abc105_d imos法・累積和 AC#3010336 アルゴリズム要素はわかりそうなもんだが考察できまへん…。「連続する区間」は、「累積和をとった配列上の 2 点」と同一視することができる」…参考:ABC 105 D - Candy Distribution (400 点) - けんちょんの競プロ精進記録
abc106 AtCoder Express 2 https://beta.atcoder.jp/contests/abc106/tasks/abc106_d
abc107 Median of Medians https://beta.atcoder.jp/contests/abc107/tasks/arc101_b

AOJ

  解答履歴

  • AOJ修行
    • いやな名前だがここでほぼ管理できる

  AOJ問題

解けたもの

index タイトル URL アルゴリズム要素 解けた? 解き方
0067 The Number of Island http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0067 グラフアルゴリズム - 深さ優先探索 AC#3078834 深さ優先探索の練習用
1160 How Many Islands? http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160&lang=jp グラフアルゴリズム - 深さ優先探索 AC#3078786 深さ優先探索の練習用
お名前: コメント: