問題 atcoder.jp 解説 生成できる最小値と最大値を計算すれば、間の組み合わせ数は、おのずと割り出せる。 実装 参考 youtu.be

問題 atcoder.jp 解法 1 <= N <= 4000 なのでO(N3)だと、43 * 109 でTLEのはず。 なので、R, Gの二つの要素を固定。 すると O(16 * 106) くらい？ あとは、計算でBの要素から何個採用できるかを出す。 この方針でTLEは出ないはず。 R, Gのある場所のインデッ…

問題 atcoder.jp 解法その1 numpy + njitを使ったO(N3)解法 なんと、何も考えずに問題通り、総当たりコードを書くとACしてしまうという解法。 マジですか。 AtCoderのPythonではnumpyが使用できるが、njitを使って関数の実行速度を高速化。 実行すると、1731…

問題 atcoder.jp 数学問題。 解法 水の体積が、水筒の半分以下か以上かで処理が異なる。 水の体積が水筒の半分以下のとき 半分以下の時、水は三角柱の形でこぼれる。 水の体積が半分以下 θの角度が求める答え。 水の面積 x / a 水の底辺yの値を求める。三角…

問題 atcoder.jp 解説 A5 - B5 = X で、Xの制約条件が 1 <= X <= 109 ゆえに、Aは大体1000くらいまでだろ？ という当たりをつける。 Bは負の値もありえるので、-1000から1000までの範囲で総当たりをかける。 実装 素直に計算したのが、実行時間70ms。 はまや…

問題 atcoder.jp 解法 計算式を関数に実装し、試しに数値を入れてみて答えに規則性があるかどうかを見てみる。 すると、mod Bでループしていることがわかる。 よって、最大値の候補はx = Nかx = B-1。 それぞれの値の答えを求めて比較。 答えとする。 B-1 <=…

問題 atcoder.jp 解法 計算式を関数に実装し、試しに数値を入れてみて答えに規則性があるかどうかを見てみる。 すると、mod Bでループしていることがわかる。 よって、最大値の候補はx = Nかx = B-1。 それぞれの値の答えを求めて比較。 答えとする。 B-1 <=…

問題 atcoder.jp 解法 数列 7, 77, 777, 7777, ....は 漸化式 10+7 で表現できる。 これはmod（余り）をとった値でも同様。 7%K の次の77%K も 10+7の関係にある。 それを利用して、K回この処理を繰り返せば、とりうる余りは１ループする。 この余りのループ…

問題 atcoder.jp 解法 26進数で素直に考えれば良いのか。 と思ったら、一捻りして1引いた値を26進数にしていくという解法。 0をどの文字に変換したら良いか書いてない。 入力例2が27がaa。26=10が、どうすれば良いかよくわからない。 など、歪な26進数になっ…

問題 atcoder.jp 解法 解説によると制約条件がゆるいので総当たりで解けてしまうようだ。 自分は２次方程式で、式たてて解いてしまったが。 実装 解説 blog.hamayanhamayan.com

問題 三角形を作ることのできるような長さの異なる3本の棒を選ぶ方法は何通りあるでしょうか。 atcoder.jp 解法 三角形には、2つの辺の長さを足し合わせると残りの1つの辺の長さより長くなる。 という成立条件があるので、これで三角形が成立するかを判断す…

問題 atcoder.jp 解法 移動回数Kの制約が 1 ≤ K ≤ 1015 なので、シミュレーションするとO(1015)。 O(108)を超えるとTLEなので、計算で出す問題だということがわかる。 処理としては * XがDより小さくなるまで移動。移動回数Kを使い切ってるなら、ここで終わ…

問題 atcoder.jp 三角形の頂点A(Xa, Ya), B(Xb, Yb), C(Xc, Yc)が与えられる。 面積を求めよ。 解法 三角形の頂点座標から面積を求めることができる「符号付面積の公式」というのがあって、それを使う。 3点 A(a,b),B(c,d),C(e,f) が与えられたとき abs((ad+…

問題 atcoder.jp 解法 制約が N ≤ 2×105なので、普通にシミュレーションするとO(108)超えるのは目に見えてる。 なので、計算量を減らす工夫をする必要があるんだけど、これは解法みないとわからなかったー。 数列A = { 3, 1, 4 } とする。 答えは 3 x 1 + 3 …

問題 atcoder.jp 解法 カコモンジムに行くと強さがA倍、経験値+1 AtCoderジムに行くと強さが+B、経験値+1 強さXとして、A * XとX + Bを比較して小さい方を行えば良いが、制約条件から愚直にシミュレーションすると計算量がO(108)を超えてしまう。 まず、カコ…

問題 atcoder.jp 解法 とにかく入力例とか問題の内容読むと「これ約数の問題っぽくない！？」と悟れという問題のよう。 最大公約数がモンスターのHPの最小値になるので、これを求めればよい。 3つ以上のパラメータの最大公約数の求め方が実装例(Python3.8系)…

問題 正整数Nが与えられます。A x B + C = Nを満たす正整数の組 (A,B,C)はいくつありますか？ atcoder.jp 制約 2 ≤ N ≤ 106 入力はすべて整数 解法 A, B, C はすべて1以上。 A x B + C = N この式を展開していく。 C = N - A x B Cは1以上なので 1 ≤ N - A x…

問題 atcoder.jp 解法 約数列挙問題。 たとえば20の約数を調べるときに、20%2は余り0。 よって約数とわかるが、20/2 = 10もついでにわかる。 こうしておくと、ループは20の平方根までで済み、だいぶ計算量をおさえることができる。 ループ最後あたりで、答え…

問題 atcoder.jp 解法 入力例１のデータを元に、具体的に考えてみます。 2 5 10 12 1 2 14 数列Xを、まずはソート。 1 2 10 12 14 このXiのとなりの値との差を計算する。 この数列をDとする。 1 8 2 2 ここまでの状態を図にしてみる。 ABC117_C 区間を表す数…

問題 相違なる整数 があります。 となるような整数 を出力してください。 そのような整数が存在しなければ、代わりに IMPOSSIBLE を出力してください。 atcoder.jp 解法 atcoder ABCのA問題って、基本的には問題に書いてある文言通りにコード書けばACできる…

問題文読んで自分なりに考えてみたが、解説みたらシンプル過ぎで驚き。 atcoder.jp 解法 はまやんさんの解説より引用。 この問題はある種の構築問題である。 構築問題の典型テクとして「理論値の最大値を実はいつも達成可能」というのがある。 今回もそうで…

atcoder.jp 解法 各条件について考えてみる。 これを満たす数列の個数(ア) = 10N なるが存在する(イ)。 これを満たす数列の個数 = 10N - 9N 9Nはを満たす個数 なるが存在する(ウ)。 これを満たす数列の個数 = 10N - 9N 9Nはを満たす個数 abc178_c 問題の答え…

AtCoder Problemsが茶diffと判定した問題から重点的にやっておこう。 という方針を立てました。 このレベル帯の問題が出来ないことが多いと感じるんですよ。 問題に書いてある通りに実装するとTLEで、実は数学的に計算量減らせますよ。 系の問題が多い、この…