競プロ典型 90問

atcoderの典型90問の解法集.

各論

javaに関しては、クラス名をMainに変更しないとatcoderでは機能しないので注意。

問題文	アルゴリズム等	ruby解	java解	kotlin解	解説
001 - Yokan Party（★4）	貪欲法, 二分探索法	ruby	java	kotlin	解説
002 - Encyclopedia of Parentheses（★3）	bit全探索	ruby	java	kotlin	解説
003 - Longest Circular Road（★4）	木の直径	ruby1, ruby2	java1, java2	kotlin1, kotlin2	解説
004 - Cross Sum（★2）	包除原理	ruby	java	kotlin	解説
005 - Restricted Digits（★7）	桁DP法, ダブリング	ruby			解説
006 - Smallest Subsequence（★5）	貪欲法	ruby1, ruby2	java	kotlin1	解説
007 - CP Classes（★3）	二分探索法	ruby	java	kotlin	解説
008 - AtCounter（★4）	状態DP法	ruby	java	kotlin	解説
009 - Three Point Angle（★6）	二分探索法, 偏角ソート, 真ん中決め打ち		java		解説
010 - Score Sum Queries（★2）	累積和	ruby	java	kotlin	解説
011 - Gravy Jobs（★6）	DP法, 締め切りが早い順	ruby	java	kotlin	解説
012 - Red Painting（★4）	Union-Find	ruby	java	kotlin	解説
013 - Passing（★5）	ダイクストラ法	ruby	java	kotlin	解説
014 - We Used to Sing a Song Together（★3）	ソート, 貪欲法	ruby	java	kotlin	解説
015 - Don't be too close（★6）	調和級数, 逆元, フェルマーの小定理	ruby		kotlin	解説
016 - Minimum Coins（★3）	工夫した全探索	ruby		kotlin	解説
017 - Crossing Segments（★7）	余事象, BIT(FenwickTree)	ruby		kotlin	解説
018 - Statue of Chokudai（★3）	三角関数	ruby			解説
019 - Pick Two（★6）	区間DP法	ruby			解説
020 - Log Inequality（★3）	整数	ruby			解説
021 - Come Back in One Piece（★5）	強連結成分分解	ruby1, ruby	java	kotlin1, kotlin2	解説
022 - Cubic Cake（★2）	ユークリッド互除法	ruby1, ruby2			解説
023 - Avoid War（★7）	bit全探索, bitDP法				解説
024 - Select +／- One（★2）	パリティ	ruby			解説
025 - Digit Product Equation（★7）	再帰関数	ruby		kotlin	解説
026 - Independent Set on a Tree（★4）	二部グラフ, 再帰関数	ruby		kotlin	解説
027 - Sign Up Requests （★2）	Hash(Set)	ruby	java	kotlin	解説
028 - Cluttered Paper（★4）	いもす法	ruby		kotlin	解説
029 - Long Bricks（★5）	座標圧縮, セグメント木				解説
030 - K Factors（★5）	エラトステネスの篩			kotlin	解説
031 - VS AtCoder（★6）	grundy	ruby	java		解説
032 - AtCoder Ekiden（★3）	順列全探索	ruby			解説
033 - Not Too Bright（★2）	境界条件	ruby			解説
034 - There are few types of elements（★4）	尺取法	ruby		kotlin	解説
035 - Preserve Connectivity（★7）	木DP, 最近共通祖先(LCA), 座標圧縮	ruby			解説
036 - Max Manhattan Distance（★5）	マンハッタン距離	ruby			解説
037 - Don't Leave the Spice（★5）	スライド最大値(最小値), DP法, 動的計画法	ruby			解説
038 - Large LCM（★3）	ユークリッド互除法	ruby			解説
039 - Tree Distance（★5）	貢献度, 再帰関数	ruby			解説
040 - Get More Money（★7）					解説
041 - Piles in AtCoder Farm（★7）					解説
042 - Multiple of 9（★4）	DP法	ruby		kotlin	解説
043 - Maze Challenge with Lack of Sleep（★4）	拡張BFS	ruby1, ruby2			解説
044 - Shift and Swapping（★3）	見かけ上の変化をメモ	ruby			解説
045 - Simple Grouping（★6）	bitDP法				解説
046 - I Love 46（★3）	同じものをまとめる, 剰余	ruby			解説
047 - Monochromatic Diagonal（★7）	ローリングハッシュ	ruby			解説
048 - I will not drop out（★3）	上界(下界)見積り	ruby			解説
049 - Flip Digits 2（★6）	最小全域木, Union-Find, クラスカル法	ruby		kotlin	解説
050 - Stair Jump（★3）	DP法	ruby		kotlin	解説
051 - Typical Shop（★5）	半分全列挙	ruby		kotlin	解説
052 - Dice Product（★3）	因数分解	ruby		kotlin	解説
053 - Discrete Dowsing（★7）					解説
054 - Takahashi Number（★6）	最短経路問題, 幅優先探索, グラフの辺数削減, エルデシュ数	ruby			解説
055 - Select 5（★2）	定数倍	ruby			解説
056 - Lucky Bag（★5）	動的計画法, DP法, DP復元	ruby		kotlin	解説
057 - Flip Flap（★6）	掃き出し法	ruby			解説
058 - Original Calculator（★4）		ruby			解説
059 - Many Graph Queries（★7）					解説
060 - Chimera（★5）	最長増加部分列(LIS), 二分探索法	ruby	java	kotlin	解説
061 - Deck（★2）	deque	ruby		kotlin	解説
062 - Paint All（★6）	幅優先探索, 後ろから考える	ruby			解説
063 - Monochromatic Subgrid（★4）	bit全探索	ruby		kotlin	解説
064 - Uplift（★3）	階差	ruby		kotlin	解説
065 - RGB Balls 2（★7）					解説
066 - Various Arrays（★5）	期待値の線形性	ruby			解説
067 - Base 8 to 9（★2）		ruby			解説
068 - Paired Information（★5）	クエリ先読み, Union-Find	ruby			解説
069 - Colorful Blocks 2（★3）	繰り返し2乗法	ruby			解説
070 - Plant Planning（★4）	マンハッタン距離, 独立で考える	ruby			解説
071 - Fuzzy Priority（★7）					解説
072 - Loop Railway Plan（★4）	バックトラック, 再帰関数, "何通りか"の感覚	ruby			解説
073 - We Need Both a and b（★5）	木DP, 動的計画法	ruby			解説
074 - ABC String 2（★6）	特殊ケースを考える, 不変量を考える	ruby			解説
075 - Magic For Balls（★3）	素因数分解	ruby		kotlin	解説
076 - Cake Cut（★3）	円環を列にして二倍にする(累積和), 尺取法	ruby			解説
077 - Planes on a 2D Plane（★7）					解説
078 - Easy Graph Problem（★2）	グラフの基本	ruby			解説
079 - Two by Two（★3）	操作順序によらない	ruby			解説
080 - Let's Share Bit（★6）	包除原理, bit全探索	ruby			解説
081 - Friendly Group（★5）					解説
082 - Counting Numbers（★3）	数列の和の公式, 部分問題に分解	ruby			解説
083 - Colorful Graph（★6）					解説
084 - There are two types of characters（★3）		ruby			解説
085 - Multiplication 085（★4）	全件探索, 約数列挙	ruby			解説
086 - Snuke's Favorite Arrays（★5	bit全探索, bit毎に独立に考える	ruby			解説
087 - Chokudai's Demand（★5）	ワーシャルフロイド法, 二分探索法	ruby			解説
088 - Similar but Different Ways（★6）	鳩ノ巣原理, DFS	ruby			解説