Haskellを主に使用。
Haskellで競技プログラミングをやるテクニックは「Haskellで競技プログラミングをやる」を参照。
abc/README.md を参照。
https://atcoder.jp/contests/tdpc
解いた問題:
- A - コンテスト
- B - ゲーム
- ゲーム
- C - トーナメント
- D - サイコロ
- E - 数
- 桁DP
- F - 準急
- G - 辞書順
- H - ナップザック
- 重さの他に色の制約がある
- I - イウィ
- 貪欲法で解けてしまった(
iiwi
やiwii
という形に遭遇したらそのiwi
は取り除いて良い)
- 貪欲法で解けてしまった(
- J - ボール
- K - ターゲット
- L - 猫
- M - 家
- N - 木
- O - 文字列
- P - うなぎ
- Q - 連結
- R - グラフ
- S - マス目
- T - フィボナッチ https://github.com/minoki/typical-dp-contest-t-fibonacci
- 解説記事:フィボナッチ数絡みの競プロの問題を解いてみた(Typical DP Contest T)
- 行列の固有多項式が既知なので多項式除算を使って高速に行列累乗ができる
https://atcoder.jp/contests/dp
解いた問題:
- A - Frog 1
- B - Frog 2
- C - Vacation
- D - Knapsack 1
- 01ナップサック問題。重さは比較的小さく(〜105)、価値は大きい(〜109)
- E - Knapsack 2
- 01ナップサック問題。重さは大きく(〜109)、価値は小さい(〜103)
- F - LCS
- Longest Common Subsequence
- G - Longest Path
- 有向閉路を含まない有向グラフ
- H - Grid 1
- 2次元DP
- I - Coins
- 確率
- J - Sushi
- 期待値
- K - Stones
- ゲーム
- L - Deque
- ゲーム
- M - Candies
- 飴の分配方法
- N - Slimes
- O - Matching
- P - Independent Set
- Q - Flowers
- Binary Indexed TreeかSegment Treeを使う
- R - Walk
- 頂点数が少ない(〜50)ので行列累乗
- S - Digit Sum
- 桁DP
- T - Permutation
- 桁DPの類似?
- U - Grouping
- ビットDP
- V - Subtree
- 全方位木DP
- W - Intervals
- X - Tower
- Y - Grid 2
- Z - Frog 3
https://atcoder.jp/contests/agc031
解いた問題:
- A - Colorful Subsequence
- B - Reversi
- C - Differ by 1 Bit
- D - A Sequence of Permutations
- E - Snuke the Phantom Thief
- F - Walk on Graph
https://atcoder.jp/contests/agc032
解いた問題:
- A - Limited Insertion
- B - Balanced Neighbors
- C - Three Circuits
- D - Rotation Sort
- E - Modulo Pairing
- F - One Third
https://atcoder.jp/contests/exawizards2019
解いた問題:
- A - Regular Triangle
- B - Red or Blue
- C - Snuke the Wizard
- D - Modulo Operations
- E - Black or White
- F - More Realistic Manhattan Distance
https://atcoder.jp/contests/agc023
解いた問題:
- A - Zero Sum Ranges
- 令和記念に解いた(2019年4月1日)
- B - Find Symmetries
- C - Painting Machines
- D - Go Home
- E - Inversions
- F - 01 on Tree
https://atcoder.jp/contests/tenka1-2019
解いた問題:
- C - Stones
- D - Three Colors
- E - Polynomial Divisors
- 素数と多項式
- 有限体 Fp 上で関数として恒等的に0になるような多項式は xp-x で割り切れる
- F - Banned X
https://atcoder.jp/contests/aising2019
解いた問題:
- A - Bulletin Board
- B - Contests
- C - Alternating Path
- D - Nearest Card Game
- E - Attack to a Tree
https://atcoder.jp/contests/xmascon18
解いた問題:
- J - Japanese Exponentation
https://atcoder.jp/contests/arc017/
解いた問題:
- A - 素数、コンテスト、素数
- B - 解像度が低い。
- C - 無駄なものが嫌いな人
- D - ARCたんクッキー
https://atcoder.jp/contests/diverta2019
解いた問題:
- A - Consecutive Integers
- B - RGB Boxes
- C - AB Substrings
- D - DivRem Number
- E - XOR Partitioning
- F - Edge Ordering
https://atcoder.jp/contests/m-solutions2019
解いた問題:
- A - Sum of Interior Angles
- B - Sumo
- C - Best-of-(2n-1)
- D - Maximum Sum of Minimum
- E - Product of Arithmetic Progression
- mod N での逆元や階乗の計算に帰着させる。
- F - Random Tournament
https://atcoder.jp/contests/agc034
解いた問題:
- A - Kenken Race
- B - ABC
- C - Tests
- D - Manhattan Max Matching
- E - Complete Compress
- F - RNG and XOR
https://atcoder.jp/contests/diverta2019-2
解いた問題:
- A - Ball Distribution
- B - Picking Up
- C - Successive Subtraction
- D - Squirrel Merchant
- E - Balanced Piles
- F - Diverta City
https://atcoder.jp/contests/agc035
- A - XOR Circle
- B - Even Degrees
- C - Skolem XOR Tree
- D - Add and Remove
- E - Develop
- F - Two Histograms
https://atcoder.jp/contests/agc036
- A - Triangle
- B - Do Not Duplicate
- C - GP 2
- D - Negative Cycle
- E - ABC String
- F - Square Constraints
https://atcoder.jp/contests/agc037
- A - Dividing a String
- B - RGB Balls
- C - Numbers on a Circle
- D - Sorting a Grid
- E - Reversing and Concatenating
- F - Counting of Subarrays
https://atcoder.jp/contests/jsc2019-qual
- A - Takahashi Calendar
- B - Kleene Inversion
- C - Cell Inversion
- D - Classified
- E - Card Collector
- F - Candy Retribution
https://atcoder.jp/contests/agc038
- A - 01 Matrix
- B - Sorting a Segment
- C - LCMs
- D - Unique Path
- E - Gachapon
- F - Two Permutations
https://atcoder.jp/contests/agc039
- A - Connection and Disconnection
- B - Graph Partition
- 2部グラフの判定と、無向グラフの直径
- C - Division by Two with Something
- D - Incenters
- E - Pairing Points
- F - Min Product Sum
https://atcoder.jp/contests/agc040
- A - ><
- B - Two Contests
- C - Neither AB nor BA
- D - Balance Beam
- E - Prefix Suffix Addition
- F - Two Pieces
https://atcoder.jp/contests/nikkei2019-2-qual
- A - Sum of Two Integers
- B - Counting of Trees
- C - Swaps
- D - Shortest Path on a Line
- E - Non-triangular Triplets
- F - Mirror Frame
https://atcoder.jp/contests/ddcc2020-qual
- A - DDCC Finals
- B - Iron Bar Cutting
- C - Strawberry Cakes
- D - Digit Sum Replace
- E - Majority of Balls
- F - DISCOSMOS
https://atcoder.jp/contests/judge-update-202004
- A - Walking Takahashi
- B - Picking Balls
- C - Numbering Blocks
- D - Calculating GCD
https://atcoder.jp/contests/practice2
- A - Disjoint Set Union
- Union Find
- B - Fenwick Tree
- Fenwick Tree, or Binary Indexed Tree
- C - Floor Sum
- D - Maxflow
- E - MinCostFlow
- F - Convolution
- G - SCC
- H - Two SAT
- I - Number of Substrings
- J - Segment Tree
- K - Range Affine Range Sum
- L - Lazy Segment Tree
https://atcoder.jp/contests/atc001
- A - 深さ優先探索
- B - Union Find
- C - 高速フーリエ変換
https://atcoder.jp/contests/arc033
- A - 隠れた言葉
- B - メタ構文変数
- C - データ構造
- D - 見たことのない多項式
https://atcoder.jp/contests/abc284
- A - Sequence of Strings
- B - Multi Test Cases
- C - Count Connected Components
- D - Happy New Year 2023
- E - Count Simple Paths
- F - ABCBAC
- G - Only Once
- Ex - Count Unlabeled Graphs