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

問題 atcoder.jp 解法 コンテスト参加中 「DFS(深さ優先検索)だろ！こりゃACもらった！」 と思ったら、TLEで解けなくてガッカリだったー。 ので復習。 この問題、DFSで木を上方向に戻る処理まで再帰関数で実装してしまったんだが、1に戻って終わるのが前提の…

問題 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 解法 最小値を計算量低く取り出すデータ管理構造、優先度付きキュー（priority queue）を使うことがポイント。 Pythonではheapqとして提供されている。 全体に対する玉の数の上下はoffset変数を作って管理。 玉を追加する時は、offset値を引…

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

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

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

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

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

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

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

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