問題 ABC129-D_Lamp 問題概要 任意のマスから光線が上下左右に伸びる（ただし、障害物は透過しない）。 明かりによって照らされるマスの個数を最大値を計算する。 解法 障害物のあるグリッドなので、幅優先探索などの方法が考えられるが、上下左右にしか光線…

問題 ABC128-equeue 問題概要 宝石が$N$個横一列に並んでいる。 以下の４操作を$K$回まで行う。 操作A: 左端の宝石を取る。 操作B: 右端の宝石を取る。 操作C: 持っている宝石から１個左端に置く。 操作D: 持っている宝石から１個右端に置く。 方針 全探索す…

問題 ABC127-Integer Cards 問題概要 カードが$$N$$枚あり、それぞれ整数$A_i$が書かれている。 $M$回以下の操作を行う。 カードを$B_j$枚まで選ぶ。選んだカードを$C_j$に書き換える カードに書かれた数字の合計の最大値は？ 解法 小さい数字のカードを書き…

問題 ABC172-D_SumofDivisors 問題概要 Xの正の約数の個数をf(X)とするとき、∑K×f(K) 解法 ポイント 整数問題は書き出して規則を捉える 1から始まるときは（ある特定の区間でないときは）特に、一発で答えが出たりする 横に集計しても、縦に集計しても同じ -…

問題 ABC172-C_Tsundoku 問題概要 机が二つ。それぞれに本が積まれている。上から順に読んでいく。k分を超えない範囲で、何冊読めるか。 解法(1) ポイント 2つの変数の和の（条件下での）最大値を探す -> 一つを固定して、二分探索 or 尺取り法 <- 単調増加…

問題 ABC132-D_RedandBlueBalls 考え方 ポイント 場合の数 区別がない組み分け コンビネーションの計算はフェルマーの小定理 解法 n, k = map(int,input().split()) MOD=10**9+7 def comb(n,k): if n<k: return 0 if n<0 or k<0: return 0 k=min(n-k,k) ans=1 inv=[1]*(k+1) if k>=1: ans*=(n-k+1)%MOD for i in range(2,k+1): inv[i]=MOD</k:>…

問題 ABC167-D_Teleporter 考え方 ポイント 考察大事。サンプルを書き出す。 flag系は、はじめにリストを用意しておく seen = [-1]*(n+1) indexと○個目の対応は、メモを書きながらミスらないようにする a_list = [0] + list(map(int,input().split())) roop_…

はじめに いつかE問題も解けるようになりたいなー -> E問題ってどのカテゴリーの問題がよく出ているんだろう -> AtCoder Tagsという素晴らしいサイトがあったので、雑にスクレイピングして集計してみた 結果（新ABCのみ集計。126-163） A問題 [('Easy', 35),…

はじめに しゃくとり法について復習してみました アルゴリズム概要 しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ 英語でいうとtwo pointersらしい O(n2) をO(n)にするテクニックの1つであるしゃくとり法 「連続する部分列」で使う 「条件」…

DFS / BFSについて DFS: 到達可能かを探る。全探索。 BFS: 最短経路を探る。見つかったら打ち切ったり。 ※seenという名前だが、todoに入れたらseenに入る DFSも、全部BFSでいいのでは？（BFSで打ち切らなければ同じ？） DFS 例題 A - 深さ優先探索 解法 from…

はじめに 二分探索について復習してみました アルゴリズム概要 Weblio辞書から引用 2分探索法とは、検索対象がソートされている場合に適用できる高速な検索手法のことである。 2分探索法は、具体的には次のようなアルゴリズムで検索を行う。まず、検索の開始…

問題 ABC153-E_Crested Ibis vs Monster ポイント i番目の魔法を使うと、モンスターの体力をAi減らすことができますが、トキの魔力をBi消耗します -> ナップサックの大きさが決まっている条件の元で、ものの大きさを考慮しつつものの価値の合計を最大化する …

問題 D - Bouquet ポイント 組み合わせ、109+7で割った余り -> フェルマーの小定理 MOD=10**9+7 def comb(n,k): if n<k: return 0 if n<0 or k<0: return 0 k=min(n-k,k) ans=1 inv=[1]*(k+1) if k>=1: ans*=(n-k+1)%MOD for i in range(2,k+1): inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD ans=ans*(n-k+i)*inv[i]%MOD return ans comb(4,2) # -</k:>…

問題 ABC155-D_Pairs ポイント 小さい順に並べ替えたとき、K番目にくる数... -> ある条件を満たすものの最小値（最大値）を求める -> 二分探索 AtcorderABC-Dより先へ行くために代表的なアルゴリズムを勉強した-その1-（DP、累積和、UnionFind木、bit関係、…

問題 ABC151-D_MazeMaster ポイント 迷路の最短経路問題 -> BFS -> AtcorderABC-Dより先へ行くために代表的なアルゴリズムを勉強した-その3-（DFS、BFS）.md -> 上記は、スタートとゴールが決まっている版。今回は、『ゴール決めずに全部調べる+距離の最…

問題 ABC150-C_CountOrder ポイント 順列の要素の洗い出し n = 3 for permutations_i in itertools.permutations((range(1, n+1))): print(permutations_i) # 実行結果 (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1) 解法 n=int(input()) p_…

はじめに ABC-Dを解くために、下記のアルゴリズムを勉強しました。 1. 優先度付きキュー 2. 貪欲法 3. しゃくとり法 アルゴリズム 1. 優先度付きキュー 参考 【Python】優先度付きキューの使い方【heapq】 いつ使うか 優先度付きキュー（Priority queue）は…

はじめに ABC-Dを解くために、下記のアルゴリズムを勉強しました。 1-1. DFS（再帰） 1-2. DFS（スタック） 2. BFS(キュー) アルゴリズム 1-1. DFS（再帰） 参考 深さ優先と幅優先でディレクトリ探索 深さ優先探索と幅優先探索 競プロ覚書：深さ優先探索，幅…

はじめに ABC-Dを解くために、競プロにありがちな典型数学問題を勉強しました。（C以下でも出ますが。） 手法 素数判定 def is_prime(n): if n == 1: return False for i in range(2,int(n**0.5)+1): if n % i == 0: return False return True is_prime(4) #…

はじめに 友人に勧められてたまたまKyoto University Programming Contest 2019のB問題を解いたので、備忘までにブログに書いておきます。 問題と解法 問題 ナップサック問題 参考 PythonでのUnion-Find（素集合データ構造）の実装と使い方 動的計画法(ナッ…

はじめに ABC-Dを解くために、Atcoder Beginner Contest D埋めしたので初心者向け学習法とか色々書くを参考に、下記のアルゴリズムを勉強しました。 1. DP 2. 累積和 3. UnionFind木 4. bit関係 5. 二分探索 アルゴリズム 1. DP 参考 動的計画法（Dynamic Pr…

はじめに AtCoderを始めました。かの有名なAtCoder過去問精選10問をPythonで解いたので、何番煎じかも分かりませんが、そのときのメモを残します。 AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選10 問 ～ エレガントに短く書く…