問題 atcoder.jp 考察と解法 世の中には2種類の頂点が存在する。白色の頂点と黒色の頂点である。 by トコロテン はい、そうですかといった感じですね。 さて、今回の問題を整理すると以下のようになります。 N個の頂点を持つ重み付きの木構造のデータが入力…

問題 atcoder.jp 考察と解法 メリークリスマス！………ではないですね。 なぜクリスマスにハンバーガーなのかはわかりませんがとりあえず問題と真剣に向き合うことにします。 まずはじめに、ハンバーガーの生成規則について確認しておきます。 ハンバーガーは'P…

問題 atcoder.jp 考察と解法 今回は結構考察パートが長めです。 問題としては以下の関数の値を最小化するbを求め、それを代入したの値を求めるといったものです。 は入力として与えられるのでbの値だけを考えれば良いです。 まず、(-1, -2, ..., -N)が定数に…

問題 atcoder.jp 考察と解法 まず、全探索を行う場合を考えます。 1回の呪文ごとにゴーレムの移動をシミュレートするのに最大N体のゴーレムを移動させる必要があり、全部で呪文をQ回唱えるため、最悪時間計算量はとなります。 もちろんなので一生計算が終わ…

問題 atcoder.jp 考察と解法 まずはじめに、すべてのがすべてのの最大公約数で割り切れることに気づきました(それはそう)。 を満たすの最大公約数をとするとであるから 自然数を用いて (式1) となり、はMの約数であることがわかります。 したがって、Mの約数…

問題 atcoder.jp 考察と解法 この問題は以下の2つを達成することで解決できます。 風向の角度から方位を表す文字列(N, NNE, ..., NNW)への変換 風速から風力への変換 変換自体は特にアルゴリズムを要求されることがなく、問題文に示されたルールに従うだけで…