ABC006C
考えたこと
全員2だとして、余った数を+1もしくは+2を最大N個組み合わせて作る問題
素朴に二重にループすると間に合わない
余りがN以下ならその数の1を出せば良い
余りがNを超えるなら全員3にして、その余を4に割り振ればいい
定数オーダー
公式解説
なんだか全然違う話をしてるな
一つ決めれば鶴亀算になるから1つについてだけ全探索、とか、老人は0/1だとわかるから残りを全探索するとか
探索しなくても上記の解法でACする
pythondef solve(N, M):
IMPOSSIBLE = (-1, -1, -1)
x = M - 2 * N
if x < 0:
return IMPOSSIBLE
if x <= N:
return (N - x, x, 0)
x -= N
if x <= N:
return (0, N - x, x)
return IMPOSSIBLERelated Pages
- →僕のatcoderの学び方(〜水色)×僕のatcoderの学び方(〜past上級)×abc187×past過去問練習202012×変形テクニックに名前をつける×頂点数18の制約×辺が10^5の制約×行列の半分×二項定理×足し算の順序の変更×辺が10^5ならダイクストラ使える×典型力×問題変換×問題分割×認知の解像度×概念のハンドル×atcoder失敗リスト×atcoderentrypoint×アルゴリズム実技検定×第五回_アルゴリズム実技検定×最小費用流に帰着×帰着訓練→
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×arc106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×unionfind×mod_pでの組み合わせ×educational_dp_contest×動的計画法×atcoder_library_practice_contest×atcoder_library×帰着する力×帰着訓練→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]