AtCoderプロフィール

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ナップサック問題。重さは比較的小さく(〜10⁵)、価値は大きい(〜10⁹)
• E - Knapsack 2
  • 01ナップサック問題。重さは大きく(〜10⁹)、価値は小さい(〜10³)
• 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
  • 素数と多項式
  • 有限体 F_p 上で関数として恒等的に0になるような多項式は x^p-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