AtCoder記事まとめ

AtCoder投稿記事まとめリンク集

アルゴリズム整理

さ行

巡回セールスマン(総当たり)
巡回セールスマン(動的計画法)

ら行

累積和(2次元)

わ行

ワーシャルフロイド方法

解法

動的計画法

ABC011 C (diff:810)
ABC129 C (diff:796)
ABC220 C (diff:664)
ABC248 C (diff:787)
ABC261 D (diff:801)
ABC285 E (diff:1466)
ABC303 D (diff:778)
ABC355 D (diff:735)
ABC360 E (diff:1249)
ABC375 D (diff:1424)

ビットDP

ABC142 E (diff:1397)
ABC332 E (diff:1883)
巡回セールスマン(動的計画法)

BFS

ABC168 D (diff:804)
ABC332 D (diff:1175)
ABC361 D の準備 (diff:1202)
ABC361 D (diff:1202)
ABC373 D (diff:765)
ABC383 C (diff:750)

DFS

ABC146 D (diff:1192)
ABC184 D (diff:1276)

ダイクストラ法

ABC340 D (diff:784)

UnionFind

ABC264 E (diff:1229)
ABC285 D (diff:663)
ABC351 D (diff:974)

尺取法

ABC229 D (diff:745)

累積和

ABC337 D (diff:760)

二分探索

ABC146 C (diff:741)
ABC195 D (diff:945)
ABC217 D (diff:802)
ABC248 D (diff:793)
ABC255 D (diff:788)
ABC257 C (diff:678)
ABC299 D (diff:684)
ABC302 D (diff:682)
ABC304 D (diff:1015)
ABC305 D (diff:671)
ABC321 D (diff:806)
ABC360 D (diff:159)
ABC370 D (diff:1088)
ABC375 D (diff:658)
ABC374 D (diff:1504)

ビット全探索

ABC128 C (diff:805)
ABC197 C (diff:809)

素因数分解

ABC142 D (diff:842)
ABC254 D (diff:1191)

幾何学

ABC197 D (diff:831)

ビット演算

ABC261 E (diff:1261)

排他的論理和

ABC295 D (diff:939)

その他

ピラミッド数列

ABC336 D (diff:991)

グリッド走査

ABC241 C (diff:664)

モジュロ演算

ABC146 E (diff:1762)

スタック

ABC307 D (diff:666)

ヒープキュー

ABC141 D (diff:823)

境界問題

ABC180 D (diff:752)

未カテゴリ

ABC006 B (diff:813)
ABC035 B (diff:804)
ABC051 B (diff:784)
ABC061 C (diff:808)
ABC197 C (diff:809)
ABC245 D (diff:815)

AtCoder開催順

ABC006 B (diff:813)
ABC011 C (diff:810)
ABC035 B (diff:804)
ABC051 B (diff:784)
ABC061 C (diff:808)
ABC128 C (diff:805)
ABC129 C (diff:796)
ABC141 D (diff:823)
ABC142 D (diff:842), ABC142 E (diff:1397)
ABC146 C (diff:741), ABC146 D (diff:1192), ABC146 E (diff:1762)
ABC148 E (diff:818)
ABC168 D (diff:804)
ABC180 D (diff:752)
ABC184 D (diff:1276)
ABC195 D (diff:945)
ABC197 B (diff:96), ABC197 C (diff:809), ABC197 D (diff:831)
ABC217 D (diff:802)
ABC220 C (diff:664)
ABC229 D (diff:745)
ABC241 C (diff:664)
ABC245 D (diff:815)
ABC248 C (diff:787), ABC248 D (diff:793)
ABC250 D (diff:797)
ABC254 D (diff:1191)
ABC255 D (diff:788)
ABC257 C (diff:678)
ABC261 D (diff:801), ABC261 E (diff:1261)
ABC264 C (diff:758), ABC264 D (diff:414), ABC264 E (diff:1229)
ABC275 C (diff:760)
ABC285 D (diff:663), ABC285 E (diff:1466)
ABC287 D (diff:786)
ABC292 E (diff:792)
ABC295 D (diff:939)
ABC299 D (diff:684)
ABC302 D (diff:682)
ABC303 D (diff:778)
ABC304 D (diff:1015)
ABC305 D (diff:671)
ABC307 D (diff:666)
ABC313 C (diff:681)
ABC321 D (diff:806)
ABC332 D (diff:1175), ABC332 E (diff:1883)
ABC336 D (diff:991)
ABC337 D (diff:760)
ABC340 D (diff:784)
ABC351 D (diff:974)
ABC355 D (diff:735)
ABC359 C (diff:828)
ABC360 C (diff:36), ABC360 D (diff:159), ABC360 E (diff:1249)
ABC361 D (diff:1202)
ABC362 C (diff:521)
ABC368 D (diff:816), ABC368 E (diff:2140)
ABC369 D (diff:621), ABC369 E (diff:1301)
ABC370 D (diff:1088)
ABC371 C (diff:849), ABC371 D (diff:408), ABC371 E (diff:981)
ABC372 E (diff:1042)
ABC373 C (diff:75), ABC373 D (diff:765)
ABC374 C (diff:226), ABC374 D (diff:694), ABC374 D (diff:1504)
ABC375 C (diff:972), ABC375 D (diff:658), ABC375 D (diff:1424)
ABC383 C (diff:750)

証明作業

数学的帰納法

ABC011 C (diff:810)
ABC261 D (diff:801)
ABC285 E (diff:1466)

エッセンス

BFS

ABC383 C (diff:750)

動的計画法

ABC011 C (diff:810)

動的計画法(文章説明)

ABC248 C (diff:787)

二分探索

ABC217 D (diff:802)

pythonモジュール

• from itertools import product

• from sortedcontainers import SortedList
  ABC141 D (diff:823)
  ABC217 D (diff:802)
  ABC355 D (diff:735)
  ABC370 D (diff:1088)

競技プログラミングを解いているときの感情

1. 30分以上かけてAC出来なければ諦めると決めていても、解けそうな感じがすると時間を忘れて解きにかかってしまう。
2. 苦労して解いた問題のdiffを見て、予想より低かったらACしてもガッカリする。
3. D問題を5問連続して解けたら、D問題レベル楽じゃね？って感じるものの、難問C問題に遭遇して勘違いだと思い知る。
4. 動的計画法の問題は解けても復元出来ないことがよくある。
5. 開発作業で、コードの中にDFS/BFS/UnionFind/DPを使うチャンスがないか考えてしまう。
6. ある程度慣れくると、diff:1000未満の問題は意地でも解いてやろうという気になって時間を忘れる。
7. TLEくらいまくって苦戦してた問題に対して、サクサクACが進むと脳汁が出る。
8. 初期は動的計画法に対し苦手意識を感じるが、慣れてくると(解ける解けないは別とし)楽しくなってくる。
9. D問題に慣れてきた時に、茶色コーダーの壁が妙に高いことに驚く。
10. C問題の中に難問が紛れ込んでいて、A→B→C→D→Eの順番で解かない方が良いと気づく。
11. diff75の問題がC問題にまぎれていると、本当に正しいのか不安になる。(AtCoder373 C問題)
12. 解き方にめちゃくちゃ苦労したのに驚くほどdiff値(36)が低くてショックを受ける。ABC360 C (diff:36)この問題がdiff36とかウッソだろ⋯？ABC360 D (diff:159)もdiff159の灰色問題って、言うほど簡単問題か？
13. 慣れ始めてくると、解けた喜びから、解けない(理解できない)苦しみに変わりスランプに陥る。スランプに陥ると競プロをサクサク解ける人間との差に絶望し、自己嫌悪する。
14. AtCoder300回以降って、難易度がそれ以前と比べて、高くなってない？AtCoder挑戦者のレベルが上ってるから？と感じる。

バックアップ(別解)

ABC217 D (diff:802)

復習

ABC011 C (diff:810)
ABC272 D (diff:804)

解の種

グラフ

DFS

ABC361 E (diff:1213)/木の直径計算

動的計画法

ABC362 E (diff:1225)/数列内の等差部分列の総数を動的計画法でカウント
ABC362 E (diff:1225)/数列内の等差部分列の総数(ざっくりイメージ)

数学

逆数

ABC362 E (diff:1225)/階乗と逆元の前計算

組み合わせ

ABC362 E (diff:1225)/要素の出現頻度に基づく組み合わせ数の計算

等差数列部分列判定問題

ABC362 E (diff:1225)/等差数列部分列判定問題

失敗事例

ABC003 B (diff:668)
ABC315 D (diff:1531)
ABC332 E (diff:1883)

その他(個人用覚書ページ)

【覚書】pythonコピペ関数(001)