問題 atcoder.jp 問題概要 N人が円周上に並んでいる． i番目の人は時刻tに宝石をもらうとSi時間後にその宝石を(i+1)番目の人に渡す． ただし，(N+1)=1とする． また，高橋君は時刻Tiにi番目の人に宝石を渡す． すべてのiについて，i番目の人が初めて宝石をも…

問題 atcoder.jp 解法 数列A、数列Bが2 x 105なので、A,Bの全要素に対して総当たりだと、2 x 105の2乗なので108越えでTLE確実。 なにか最適化する必要がある。 おそらく二分探索だろうと、検索したところ、そういえばbisectという便利ライブラリがPythonには…

問題 atcoder.jp 解法 素直に書く。 展望台とつながっている隣の展望台と高さを素直に比較。 より高い展望台が無いかを調べる。 実装としては、無向グラフ。 実装

問題 atcoder.jp 解法 いわゆる「しゃくとり法」で解ける問題。 数列cの中からK個の連続した数値を選び、その種類が最大になる範囲を総当たりで調べる。 わけだけど、ベタに作ると計算量が多すぎる。 範囲の左端と右端を決定し、色数を計算。 色数が最大か？…

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

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

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

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

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

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

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

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