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

問題 atcoder.jp 解答 周期性を利用したコードでAC。 なかなか難しかった。 感想 dpを使ったダブリングが想定解答。 こっちもやってみたいが、一回力尽きたので後ほど。 実装 参考 blog.hamayanhamayan.com

問題 atcoder.jp 解答 BFS(幅優先探索)で、あっさり解ける。 BFSの探索をかけて、ans[i]に部屋iの一個前の部屋番号を記録。 ansが一通り揃っているなら、"Yes"の後にまとめて表示。 感想 問題読んで、dfsかbfsだろうな？とは思うが、どっちだろう感ある。 は…

問題 atcoder.jp 解法 辺の重みが全て1であることから、この問題はBFS(幅優先探索)を用いる。 実装 参考 atcoder.jp www.youtube.com

問題 atcoder.jp 解法 DP（動的計画法）で解く。 公式動画で最初に説明されている、貰うDPのパターンで実装してみた。 dp[i][j]を、「Sのi文字目までを使って、chokudaiのj文字目まで選択する方法」と定義。 dpを解いていく。 実装 参考 www.youtube.com atc…

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

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

問題 atcoder.jp 解法 defaultdictを使って、数列Aの数値の出現回数をカウント。 Aの各数値の組み合わせ数nCrも計算してa_tmpに保存。 組み合わせ数の公式nCrを、真面目に計算してしまうと計算量が多くてTLEになってしまう。 問題は２つのボールを選び出す方…

問題 atcoder.jp 解法 整数Nを素因数分解する。 公式のpdfより引用。 N = p1e1 × ... × pkek と素因数分解されるとします。このとき、各 pi に対して、 z = pi1, pi2, ... と順番に選んでいくのが最適です。 素因数分解は、検索すればやり方はすぐわかるのだ…

問題 atcoder.jp 解法 街がN、経路がN-1であることから木構造であることがわかる。 木構造の頂点間の最短距離が奇数なら道で。 偶数なら街で出会う。 最短距離の偶奇を求めるために、各頂点の深さを計算。 深さから、頂点間の距離がわかる。 途中に共通の祖…

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

問題 atcoder.jp 解法 街がN、経路がN-1であることから木構造であることがわかる。 木構造の頂点間の最短距離が奇数なら道で。 偶数なら街で出会う。 最短距離の偶奇を求めるために、各頂点の深さを計算。 深さから、頂点間の距離がわかる。 途中に共通の祖…

問題 atcoder.jp 難しい問題。 解法 動的計画法で解く。 線路のコスト計算はC x (|i - i'| + |j - j'|)円。 この計算式から絶対値を外していく。 i' <= i, J' <= jとすれば C x i - C x i' + C x j - C x j' = C x i + C x j - C x i' - C x j' = C ( i + j …

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

問題 atcoder.jp 解法 数列A, Bを、それぞれ先頭から何個目まで使用することができるか？という問題。 数列A, Bを、しゃくとり法で走査する。 数列Aはゼロから。 数列Bは最後尾から条件を満たす位置を走査して、最大値を調べる。 実装

問題 atcoder.jp 解法 しゃくとり法という単語をAtCoderの解法でよく聞くが、やったことなかったので、やってみる。 ある条件を満たす数列の範囲を、しゃくとり虫のように長さを変えながら探索するアルゴリズムで 条件〇〇を満たす区間 (連続する部分列) の…

問題 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 解法 三平方の定理、sin、cos理解してるか問題。 sin、cosの計算で時針、分針の位置を計算。 あとは、それぞれの位置の距離を計算すれば良い。 実装

問題 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つの辺の長さより長くなる。 という成立条件があるので、これで三角形が成立するかを判断す…