Skip to content

Latest commit

 

History

History
110 lines (91 loc) · 20 KB

README.md

File metadata and controls

110 lines (91 loc) · 20 KB

競プロ典型 90 問 練習 (C++17)

「競プロ典型 90 問」を標準的な C++17 コードで解いていく、個人用勉強プロジェクトです。

C++17 標準ライブラリの機能を優先して使い、競技プログラミング固有のハックやスタイル(<bits/stdc++.h>, 大きな配列、マクロ、using namespace std 等)の使用を避けているため、一般的な C++ ソフトウェア開発で再利用できる、モダン C++ の標準を意識したコードになっています。

バグや改善案の報告は、このリポジトリの Issue をご利用ください。

★2

問題 タイトル (解答コードへのリンク) 難易度 公式解説 キーワード (公式解説から引用)
004 Cross Sum ★2 👨‍🏫 / 📝 扱いやすい形にして前計算しよう
010 Score Sum Queries ★2 👨‍🏫 / 📝 区間の総和は累積和
022 Cubic Cake ★2 👨‍🏫 / 📝 最大公約数はユークリッドの互除法
024 Select +/- One ★2 👨‍🏫 / 📝 パリティを考える
027 Sign Up Requests ★2 👨‍🏫 / 📝 map を使いこなそう
033 Not Too Bright ★2 👨‍🏫 / 📝 コーナーケースに気を付けよう
055 Select 5 ★2 👨‍🏫 / 📝 「定数倍」を見積もる
061 Deck ★2 👨‍🏫 / 📝 deque を知っていますか?
067 Base 8 to 9 ★2 👨‍🏫 / 📝 N 進法展開を理解しよう
078 Easy Graph Problem ★2 👨‍🏫 / 📝 グラフの基本を知ろう

★3

問題 タイトル (解答コードへのリンク) 難易度 公式解説 キーワード (公式解説から引用)
002 Encyclopedia of Parentheses ★3 👨‍🏫 / 📝 小さい制約は全探索を考えよう
007 CP Classes ★3 👨‍🏫 / 📝 要素の検索はソートして二分探索
014 We Used to Sing a Song Together ★3 👨‍🏫 / 📝 ソートして貪欲法
016 Minimum Coins ★3 👨‍🏫 / 📝 工夫した全探索
018 Statue of Chokudai ★3 👨‍🏫 / 📝 三角関数を使いこなそう
020 Log Inequality ★3 👨‍🏫 / 📝 整数で処理して誤差をなくそう
032 AtCoder Ekiden ★3 👨‍🏫 / 📝 小さい制約は順列全探索
038 Large LCM ★3 👨‍🏫 / 📝 オーバーフローに注意
044 Shift and Swapping ★3 👨‍🏫 / 📝 見かけ上の変化をメモ
046 I Love 46 ★3 👨‍🏫 / 📝 同じ意味のものをまとめて考える
048 I will not drop out ★3 👨‍🏫 / 📝 上界と下界を見積もる
050 Stair Jump ★3 👨‍🏫 / 📝 漸化式を立てて DP をしよう
052 Dice Product ★3 👨‍🏫 / 📝 因数分解をしよう
064 Uplift ★3 👨‍🏫 / 📝 階差を考えよう
069 Colorful Blocks 2 ★3 👨‍🏫 / 📝 a^b mod m は繰り返し二乗法
075 Magic For Balls ★3 👨‍🏫 / 📝 O(√N) での素因数分解
076 Cake Cut ★3 👨‍🏫 / 📝 円環を列にして二倍にする
079 Two by Two ★3 👨‍🏫 / 📝 操作順序によらない
082 Counting Numbers ★3 👨‍🏫 / 📝 部分問題に分解する / 数列の和の公式
084 There are two types of characters ★3 (1) 👨‍🏫 / 📝
(2) 👨‍🏫 / 📝
(解法 1) ランレングス圧縮
(解法 2) 累積的に計算しよう

★4

問題 タイトル (解答コードへのリンク) 難易度 公式解説 キーワード (公式解説から引用)
001 Yokan Party ★4 👨‍🏫 / 📝 答えで二分探索
003 Longest Circular Road ★4 👨‍🏫 / 📝 木の直径は最短距離計算を 2 回やる
008 AtCounter ★4 👨‍🏫 / 📝 状態 DP による高速化
012 Red Painting ★4 👨‍🏫 / 📝 連結判定は Union-Find
026 Independent Set on a Tree ★4 👨‍🏫 / 📝 二部グラフの性質を使おう
028 Cluttered Paper ★4 👨‍🏫 / 📝 領域加算は二次元いもす法
034 There are few types of elements ★4 👨‍🏫 / 📝 単調性を利用した尺取り法
042 Multiple of 9 ★4 👨‍🏫 / 📝 9 の倍数の性質
043 Maze Challenge with Lack of Sleep ★4 👨‍🏫 / 📝 拡張 BFS・ダイクストラ
058 Original Calculator ★4 👨‍🏫 / 📝 周期性を考える
063 Monochromatic Subgrid ★4 👨‍🏫 / 📝 変な制約に着目する / 状態数が少ない変量を全探索
070 Plant Planning ★4 👨‍🏫 / 📝 x, y 独立に考える
072 Loop Railway Plan ★4 👨‍🏫 / 📝 "何通りか" の感覚 / バックトラック
085 Multiplication 085 ★4 👨‍🏫, 👨‍🏫 / 📝 約数の個数は少ない / 工夫した全探索 / 約数列挙の復習

★5

問題 タイトル (解答コードへのリンク) 難易度 公式解説 キーワード (公式解説から引用)
006 Smallest Subsequence ★5 👨‍🏫 / 📝 辞書順最小は前から貪欲法
013 Passing ★5 👨‍🏫 / 📝 各頂点への最短経路はダイクストラ
021 Come Back in One Piece ★5 👨‍🏫 / 📝 強連結成分分解(SCC)をしよう
029 Long Bricks ★5 (1) 👨‍🏫 / 📝,📝
(2) 👨‍🏫 / 📝
(解法 1) 「座標圧縮」で効率化
(解法 2) 区間に対する処理は「セグメント木」
030
036 Max Manhattan Distance ★5 👨‍🏫 / 📝 マンハッタン距離は 45 度回転
037 Don't Leave the Spice ★5 👨‍🏫 / 📝 DP をセグメント木で高速化
039 Tree Distance ★5 👨‍🏫 / 📝 答えへの貢献度を考える
051
056
060 Chimera ★5 👨‍🏫 / 📝 両側から考える / 最長増加部分列
066 Various Arrays ★5 👨‍🏫 / 📝,📝 期待値の線形性
068
073
081
086
087

★6

問題 タイトル (解答コードへのリンク) 難易度 公式解説 キーワード (公式解説から引用)
019 Pick Two ★6 👨‍🏫 / 📝 列の操作は区間 DP

★7

問題 タイトル (解答コードへのリンク) 難易度 公式解説 キーワード (公式解説から引用)

参考リンク