よく出る思考パターン・覚えておきたいアイディアをメモしておきます． 問題の分類にもなっています．参考になるコードのリンクをメモしている問題もあります．【2022.01追記】最近は，このページではなく，タグで分類するようにしています． 入力 出力 改行…

解法1： 考え方 解法1：考え方（解放のみメモ） N〜1の橋を封鎖したときのツアーの長さを基準にして，順番に隣の橋を封鎖した場合を差分で計算する．$a これに気づくとimos法が使える．アライグマ「D問題は、1とNを結ぶ橋を封鎖したときを基準にすると、「ど…

解法1：dp 考え方 回答例 解法1：dp考え方Editorial - HHKB Programming Contest 2023(AtCoder Beginner Contest 327)アライグマ「E問題はDPなのだ！ 分子のところだけ見ると、コンテストに参加するたびに、新分子＝パフォ＋旧分子×0.9になるのだ。残りはkだ…

dp 考え方 回答例 dp考え方操作が終わる方から決まるので，$N$から小さい順に考える． $\mathrm{dp}[i]=i$が出たあとでもらえる給料の期待値． $\mathrm{dp}[N]=A[N]$ $\displaystyle \mathrm{dp}[i] = A[i] + \sum_{j=i+1}^{N}\mathrm{dp} [j] \times \frac…

解法1：頂点を倍にする 考え方 回答例 解法1：頂点を倍にする考え方フェネック「いま車に乗ってるのか電車に乗ってるのかで頂点を倍にして、1つのグラフで1回だけダイクストラをする解法もあるよ。ちょっと違うけどこういうイメージだねー」https://t.co/9au…

考え方 回答例 考え方DFSで帰りがけを見る． スタックで実装できる． 【関連】 非再帰 Euler Tour を Python でやる - Qiita ABC284E - Count Simple Paths - 競プロはじめました回答例DFSをするためのseenと，すでにansに加えたかを管理するseen2を使った．…

考え方 回答例 考え方止まるマスと訪れたマスを別に管理してBFSをする．回答例 from collections import deque N, M = map(int, input().split()) S = [input() for _ in range(N)] seen = [[False]*M for _ in range(N)] stop = [[False]*M for _ in range(…

考え方 回答例 考え方Editorial - freee Programming Contest 2023（AtCoder Beginner Contest 310） アライグマ「D問題はDFSの練習問題なのだ！ 1番目の選手から順に、何番目のチームにいれるかDFSで決めて、最後にチーム数をチェックすればいいのだ」 pic.…

考え方 回答例 考え方使ったクーポンの$D_{i}$の総和を最大化する．クーポン$i$は「(定価)$\geq L_{i}$」を満たす商品に適用できる．同じクーポンならなるべく定価が小さいものに使ったほうが有利． 商品の定価を小さい順に見ていき 定価$p$の商品に対して$S…

考え方 回答例 考え方$S_{i}S_{j}S_{k}=$MEXとなるとき，$(A_{i}, A_{j}, A_{k})$の値の組は$3^{3}$通りある． それぞれの出現回数$\mathrm{cnt}$をカウントできれば，答えは\begin{aligned} \sum_{a,b,c} \mathrm{cnt}(a,b,c)\times \mathrm{mex}(a,b,c) \e…

考え方 回答例 考え方アライグマ「D問題はスタックなのだ！ 「前から見て')'が来たら、直前の'('からここまでを削除」とすればいいのだ。今までに'('が何個あるかを覚えておいて、1個以上のときだけ'('を探せば全体でO(N)になるのだ！」— 競技プログラミング…