AtCoder, 実装

問題方針

\( d_i \) を上位から \( i \) 桁目の数字とします。\( d \) を \( -1 \) で初期化し、条件を満たすように数字を決めた時、\( d_i \) が異なる数字を取るときは整数が存在しません。また、\( ...

AtCoder, 数え上げ, 数学

方針方針

部屋 \( i \) にいる人の数を \( a_i \) とすると、

\

が成り立ちます。このとき、\( a_i \geq 0 \) を満たす整数解は、\( {}_{2n – 1} \mat ...

AtCoder, 数学

問題方針

二項係数の剰余に関する問題です。二項係数の和は、

\

となるので、花束の種類は \( 2^n – 1 \) 通りあります。したがって、求める答えは、\( 2^n – 1 R ...

AtCoder, 数学

問題方針

問題は最小二乗法に関するものなので、最適な座標は平均値となります。最小二乗法の解説が詳しいです。

コード

 

AtCoder, 桁DP

問題方針

\( N \) を数値として扱うと制約が大きすぎるので、桁DPを行います。上位 \( i \) 桁目までの数字に対して、\( d(i, 0) \) を \( i \) 桁目の数字の分だけお札を使ったときの最小値とし、\( d( ...

AtCoder, 二分探索, 尺取り法

問題方針

\( A_i = 0 \) となる個数を \(N_0 \) とし、\( A_i < 0 \) となる数列を新たに \( B \) とし、\( A_i > 0 \) となる数列を新たに \( C \) とします。この ...

AtCoder, 整列

問題方針

マップを使って文字のカウントをし、最多得票の文字列を辞書順に出力します。自作の比較関数を定義すれば整列を楽に行えます。

コード

 

AtCoder, 動的計画法, 桁DP

問題方針

見るからに桁DPの問題なので動的計画法を行います。

\( d(i, j, 0) \) を \( N \) の上位 \( i \) 桁目まで一致する数字で、\( 0 \) でない数字の個数が \( j \) 個である ...

AtCoder, 数学, 累積和

問題方針

サイコロの出る目が \( a \) まであるとき、このサイコロの出る目の期待値は、

\

となります。したがって、累積和などを用いて最大となる値を全探索します。

コード

 

AtCoder, セグメント木, 二分探索, 整列

問題方針

モンスターの順序は問題に影響を与えないので、モンスターの座標について昇順に並び替えて考えます。

最適な攻撃方法

最適な攻撃方法は、モンスターの先頭から爆弾を使っていくやり方です。爆弾の位置は、爆弾の範囲の最も左を今注 ...