keyword 組合せ C++ 概要 n( 硬貨の支払い方の問題だと思うとDPが思い浮かぶ。素朴にやるとdp[n][平方数の個数][一番大きな硬貨]で、計算量は(2^15*4*2^8)*2^8となって解けない。DPではなく、各クエリに対して丁寧に場合分けして数え上げる。4枚で4つとも異…

keyword 尺取り法 C++ 概要 正整数Sと正整数の数列が与えられる(長さは100000以下)。和がS以上になる連続した部分列の最小の長さを求める問題。 プログラミングコンテストチャレンジブックを参考にして解いた。 それとreadint()を自作してみた。やっぱりscan…

keyword シミュレーション C++ 概要 100*100以下のボードがあり、どれかのセルが当たりである。正方形の辺の長さと位置と、その正方形に当たりが入っているかどうかという情報がK( 各情報に対してシミュレーションを100*100の計算量で行えるので、愚直にシミ…

keyword C++ 概要 ほとんど完成している数独が与えられる。空升を埋める問題。 なにせほとんど完成しているので、単に実装するだけの問題。