問題 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の平方根までで済み、だいぶ計算量をおさえることができる。 ループ最後あたりで、答え…

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

問題 atcoder.jp 解法 文字を処理するクエリの * 先頭に追加 * 末尾に追加 という特性をみて、dequeでデータ管理すれば良いという点に気がつくかがポイント。 文字の反転も、馬鹿正直にクエリでるたびに行うと計算量がかなり増えるので反転をフラグ管理して…

問題 atcoder.jp 解法 Pythonのdictionaryで、Aiのインデックス番号を管理する変数noを作成。 Aをソートして、Aの中身をループさせてnoから元のインデックス番号を引っ張ってきて表示。 実装

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

atcoder.jp 解法 再帰関数を使ったDFS (深さ優先探索)でアッサリ解けた。