問題 atcoder.jp 解法 言われているままに、３つの数字の最大公約数を求めて、全合計を出す。 最大公約数は A = [i,j,k] # Aの最大公約数を求める gcd = functools.reduce(math.gcd, A) で求めることができる。 実装 参考 flytech.work

問題 atcoder.jp 解法 Pythonのitertools.combinationsで、取りうる全組み合わせの総当たりを生成。 全探索をかけるコードを書いてAC。 実行結果は Python(3.8.2) AC 89ms PyPy3(7.3.0) AC 79ms と、充分速い。 想定解は、制約がN <= 12 と低いことを利用し…

問題 atcoder.jp 解法 おそらく、大きい数から追加していくのが正解ではないかと思われる。 その前提で、数列A 8, 7, 6, 5, 4, 3, 2, 1 を円に追加してみる。 円に両隣を参照しながら追加していくと、2番目以降が二分木で追加され、数字が足されていく構造に…

問題 atcoder.jp A×Bの小数点以下を切り捨て、結果を整数として出力してください。 Bは小数第2位まで与えられる。 解法 Bを素直にfloatで読み込むと計算誤差でACでない。 Bを文字列として読み込んで、小数点.を置換。 これによってx100した数字としてintで読…

問題 atcoder.jp 1からNまでの3でも5でも割れない数字の合計を出す。 解法 基本素直に実装すれば良いんだけど、forループ範囲指定のうっかりミスに注意。 Pythonだと for i in range(1, N): と書いてしまいがちだけど、これだとN未満までのループになってし…

問題 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 ただし、答えは非常に大きくなる可能性があるので、(109+7)で割った余りを出力してください。 解法（実装） 解法については、公式解説などを読んでもらうとして、実装上の気付きをメモ。 この問題、(109+7)で割った余りを出力という指定があ…

問題 atcoder.jp 整数からなる公差 1の等差数列のうち、総和が Nであるものはいくつあるでしょうか？ 解法 等差数列の和の公式 初項が a，公差が d，項数が n Sn = n/2(2a + (n-1)*d) d = 1なので Sn = n/2(2a + (n-1)) 2Sn = n(2a + (n-1)) なので、nは2Sn…

問題 atcoder.jp 数列Aがあり、この数列の中の数字Aiを置き換えるクエリがある。 クエリを実行して、置き換え処理をしたあとの数列の合計をそれぞれ出力する。 解法 数列Aの中の数字の出現回数を数える配列を作成し、数える。 あとはクエリを実行するたびに…

問題 atcoder.jp 赤と白の石がランダムにある。 ・石を2個えらんで入れ替える ・石を1個えらんで、色を塗り替える この操作を行なって、赤い石の左隣に白い石がない状態を作る。 最小で何回の操作が必要でしょうか？ 解法 まず最終形を想定してみる。 石を1…

問題 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 解法 Union Findで友達グループの木構造を作成。 この友達グループを完全に解体したグループを作れば良い。 これには友達グループから一人ずつ割り振っていけば良い。 ゆえに友達グループの最大人数が、「元の友達グループを解体したグルー…

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

問題 atcoder.jp 2つの文字列 S, T が与えられます。 T が S の部分文字列となるように、S のいくつかの文字を書き換えます。 少なくとも何文字書き換える必要がありますか？ 実装 SよりTの方が長さが短いので、Sの何文字目から比較するかを決めて総当たりを…

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

問題 atcoder.jp 解法 defaultdictを使って、頭文字ごとの単語数を数える。 itertools.combinationsで、M, A, R, C, Hの中から3つを選んだ組み合わせを生成。 頭文字ごとの単語数の積を求めて、足し合わせる。 実装 参考 qiita.com note.nkmk.me

問題 atcoder.jp 解法 鉄の棒の長さLが例えば100のとき、分割できる地点は正整数となる地点だけなので、99箇所。 ここから11箇所の切断点を選ぶ。 つまり、99箇所から11箇所の切断点の選び方の組み合わせ数を計算すれば、答えになる。 組み合わせの公式nCrを…

問題 atcoder.jp 解法 数列Aの中のAiの倍数を配列fをつくって、あらかじめカウントしておく。 f[i]はIの約数の数が入る。 これができてしまえば、Aiの数値の約数はf[Ai]を参照すればわかる。 f[Ai]が1ならば、Aiの約数は自分自身しかないので、数列Aの中にAi…

問題 atcoder.jp 解法 1 〜 Nまでの約数を配列に保存する方針。 1の倍数、2の倍数、3の倍数……と各配列に1づつ足していく。 この約数を求める計算量は Nを外にだして Σ部分は調和級数になるので、だいたいlogNになる。 ゆえに計算量はO(NlogN)とのこと。 約数…

問題 atcoder.jp 解法 N人を運ぶのに、５つの交通機関の中で一番処理能力が低い交通機関をソートして求める。 ここがボトルネックになる。 このボトルネックになってる交通機関がN人を何分で処理できるかを計算。 他の４つの交通機関は、このボトルネックの…

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

問題 atcoder.jp 実装 この問題は、普通にACしてるんだけど、実装メモとして。 たまにAtCoderで、リスト内の要素がソートした結果、前から何番目か？という情報が必要になってくることがあるけど、その実装パターンとして残しておく。 A内の要素を、Bにソー…

問題 atcoder.jp 解法 フロイドワーシャルとかライブラリ叩けば良いんじゃね？と思ってたんだが、この問題で求められてる処理自体がフロイドワーシャルのアルゴリズムそのものですよ。 というアルゴリズム教養問題だった。 なるほど、こういう処理なのね。 …

問題 正整数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公式放送みたら、snukeさんが言ってたのでメモ。 TLEにならないのは、だいたいO(108)くらいまで。 簡単な処理ならO(109)までいけたりもする。 あ、そうなのね。 youtu.be

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