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

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

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

AtCoder

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

  必要そうなアルゴリズム

  その他

  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 グラフアルゴリズム - 深さ優先探索
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? 禁止文字列 蟻本 4-7 p.327 と 桁DP
abc008 金塊ゲーム https://beta.atcoder.jp/contests/abc008/tasks/abc008_4 メモ化探索?
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 数論
abc012 バスと避けられない運命 https://beta.atcoder.jp/contests/abc012/tasks/abc012_4 ダイクストラ法 ワーシャルフロイド法? AC#1728053 ダイクストラ法 もしくは ワーシャルフロイド法?
abc013 阿弥陀 https://beta.atcoder.jp/contests/abc013/tasks/abc013_4 ダブリング 阿弥陀の結果をグラフで求める→それを連結(この時連結した阿弥陀はすべて辿る必要は無く入り口と出口だけ考える)
abc014 閉路 https://beta.atcoder.jp/contests/abc014/tasks/abc014_4 グラフアルゴリズム 最小共通祖先 TLE #1676182 指定された2点の最短距離を幅優先探索で求め、それに追加の辺を+1する
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 imos法・累積和
abc018 バレンタインデー https://beta.atcoder.jp/contests/abc018/tasks/abc018_4 半分全列挙?
abc019 高橋くんと木の直径 https://beta.atcoder.jp/contests/abc019/tasks/abc019_4 グラフアルゴリズム
abc020 LCM Rush https://beta.atcoder.jp/contests/abc020/tasks/abc020_d 数論

021〜040

index タイトル URL アルゴリズム要素 解けた? 解き方
abc021 多重ループ https://beta.atcoder.jp/contests/abc021/tasks/abc021_d 場合の数?
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 数論
abc025 25個の整数 https://beta.atcoder.jp/contests/abc025/tasks/abc025_d 動的計画法
abc026 高橋君ボール1号 https://beta.atcoder.jp/contests/abc026/tasks/abc026_d 二分探索
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
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 動的計画法 - ナップサック問題 01ナップサック問題なのだが、そのまま出すとTLEを食らう。要素を分割しなければならないようだ。
abc033 三角形の分類 https://beta.atcoder.jp/contests/abc033/tasks/abc033_d
abc034 食塩水 https://beta.atcoder.jp/contests/abc034/tasks/abc034_d 動的計画法 - ナップサック問題 01ナップサック問題っぽいがV、Wがそのまま使えないのでそこの考慮が必要
abc035 トレジャーハント https://beta.atcoder.jp/contests/abc035/tasks/abc035_d ダイクストラ法
abc036 塗り絵 https://beta.atcoder.jp/contests/abc036/tasks/abc036_d
abc037 経路 https://beta.atcoder.jp/contests/abc037/tasks/abc037_d メモ化探索? AC #1988433 解説ページ: AtCoder Beginner Contest 037。ただの領域探索なのだが、メモ化+深さ優先探索の両方を使用しないとTLEになる、してもRubyだとTLEになる。ムリダナ。
abc038 プレゼント https://beta.atcoder.jp/contests/abc038/tasks/abc038_d 最長増加部分列
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
abc042 いろはちゃんとマス目 / Iroha and a Grid https://beta.atcoder.jp/contests/abc042/tasks/arc058_b
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 グラフアルゴリズム
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 グラフアルゴリズム
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 動的計画法
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
abc059 Alice&Brown https://beta.atcoder.jp/contests/abc059/tasks/arc072_b
abc060 Simple Knapsack https://beta.atcoder.jp/contests/abc060/tasks/arc073_b 動的計画法 - ナップサック問題 「この問題はナップザック問題として知られていて、効率良く解くアルゴリズムは存在しないと信じられています。ただし、特殊な制約がある場合はその限りではありません。」→とのことで、そのままのナップサック問題のコードを提出するとREになる。制約により条件が絞られていることに注目する。

061〜080

index タイトル URL アルゴリズム要素 解けた? 解き方
abc061 Score Attack https://beta.atcoder.jp/contests/abc061/tasks/abc061_d グラフアルゴリズム
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 競プロ数学 スタック・キュー? このような括弧の正当性をチェックする問題は「balanced parentheses」で検索できる。ちょっと数学に寄りすぎだと思った。
abc065 Built? https://beta.atcoder.jp/contests/abc065/tasks/arc076_b 最小全域木?
abc066 11 https://beta.atcoder.jp/contests/abc066/tasks/arc077_b 順列・組み合わせ
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 深さ優先探索?
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 ワーシャルフロイド法?
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
abc079 Wall https://beta.atcoder.jp/contests/abc079/tasks/abc079_d
abc080 Recording https://beta.atcoder.jp/contests/abc080/tasks/abc080_d

081〜

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 競プロ数学 AC #1907644 考察系の問題で、ちょっと今でも理解はできてない
abc084 2017-like Number https://beta.atcoder.jp/contests/abc084/tasks/abc084_d
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 グラフアルゴリズム まず 重み付き無向グラフ? を構築して、深さ優先探索か幅優先探索で距離を測る。難易度は易しめのはずだが解けず。
abc088
abc089
abc090

AOJ

お名前: コメント: