xxxasdfghjk999のブログ

iroiro

yukicoder No.390 最長の数列

問題

No.390 最長の数列 - yukicoder

解法

DPをします.
$dp[i] = x_iを最後の要素としたときのよい数列の最大の長さ$
としておきます. 遷移は,
$dp[i] = \max(dp[j] + 1, dp[i]) x_i は x_jの倍数$
です. 右の $dp[j]$ を固定して配るDPにすると,
計算量は $O(\max{x_i}\log N)$ なります.
左を固定すると約数の列挙に $O(\sqrt{\max{x_i}})$ かかるため $O(N \sqrt{\max{x_i}})$ となり, ギリギリ間に合います.

提出

#279345 No.390 最長の数列 - yukicoder

感想

難しかったです.

No.462 6日知らずのコンピュータ

問題

No.462 6日知らずのコンピュータ - yukicoder

解法

まず, $k$ が $0$ であるときを考えます
このとき, $0$ 〜 $N$ 桁のビットまで, ビットを立てる順番の場合の数がそのまま場合の数になります. 一度立てたビットは元に戻さないため, これらの数列たちはすべて異なるものになり, 答えは $N!$ となります.
$k > 0$ のときを考えます.
目的の数列は, それぞれの要素を2進数で表したときのビットが立っている数でソートし, 立っているビットの数をみると , $0, 1, 2.. N$ となり, ビットの数にかぶりはありません.
また, ビットの立て方から, この立っているビットの数でソートした数列( $B$ とします)の性質として, $B_i | B_{i+1} = B_{i+1}$ が成り立っている必要があります. (ここで $|$ はビットごとの論理和)
言い方を変えると, ある要素より１つ大きな添字を持つものは, ビットを要素としてみたときに左の要素を部分集合として持っている必要があります. これらの性質を与えられた $a$ が満たしていないならば, 数列を作ることはできません. また, 立っているビット数が等しいものが存在しないことも必要ですが, (等しいとき, 両方の数を数列内に入れることはできない), これはすでに上の必要条件となっています, これらの制限をクリアできないものは0を出力します.
条件を満たした数列の場合の数は, 各 $(a_i, a_{i+1})$ の間のビットの埋め方の積となります. $(a_i, a_{i+1})$ のハミング距離の階乗を順次かけていくと答えです.

提出

#279325 No.462 6日知らずのコンピュータ - yukicoder

感想

ビットシフトをする際, (1<< N) -1 と書くと, 1がint型として認識され, Nがint型を超えるような値となっていると望み通りの計算結果が得られないことがわかった. 次のように記述するとうまくいく.
(1LL << N) - 1
また, MODのとり忘れに気をつけたい.

yukicoder No.491 10^9+1と回文

問題

No.491 10^9+1と回文 - yukicoder

解答

$10^9+1$ の性質に着目します. $10^9+1$ にたとえば123456をかけると, $123456000123456$ になります. ほかの数値に対しても, 数値が左側と右側にコピーされているような感じになります. これに着目すると, $10^9+1$ が回文となる場合は, 回文を掛け算した場合のみであることがわかります.
与えられた $N$ に対して $M = \frac{N}{10^9+1}$ (小数点切捨)
とした $M$ が, $N$ までの $10^9+1$ の倍数の数となります.
『 $M$ 以下の自然数であって回文であるようなものの数』が答えとなります.
回文の数を手元で概算すると, それほど多くないことに気づいたのですべてを列挙してソートし, 二分探索で数を数えることにしました.
回文の列挙は,
1桁, 2桁は自明
K桁目は, K-2,K-4,..(1 or 2)桁の回文を真ん中に置いて両サイドに1~9を置くことで生成することができます.
詳しいことは提出を見てください.

提出

#279226 No.491 10^9+1と回文 - yukicoder

感想

C++において10E8は浮動小数点扱いされるので, 定数で割り算をして商を取りたいようなときに用いるとdouble型にすべてキャストされてしまい, 特に大きな数になってくると整数計算に誤差が出てしまいます. これをやらかし, なぞのWAに苦しんでいました.
これはなかなか気づかないので, 気を付けたいです.

yukicoder No.496 ワープクリスタル (給料日前編)

問題

No.496 ワープクリスタル (給料日前編) - yukicoder

解法

dpします. どんなdpかというと,
$dp[i][j] = ((i,j)までの最短コスト)$
です. まずこのdpテーブルに $(i,j)$ まで徒歩でいったときのコストを入れておきます.
このdpテーブルに対し, ワープクリスタルを１つずつ使っていき, コストが小さくなる部分を小さくしていきます.
具体的には
$dp[i][j] = min(dp[i][j], dp[i-x[k]][j-y[k]] + c[k])$
をすべてのワープクリスタルに対して検査すれば $dp[G_x][G_y]$ が答えです.
しかし, 同じワープクリスタルは二度使えないため, ゴールから更新していくか, 別の配列に結果を一時保存しておいてあとでまとめて更新するかのどちらかが必要です. (これをせずに順次スタート地点から更新すると, 更新された地点を経由する路で再びワープクリスタルを用いる可能性がある.)

提出

#279217 No.496 ワープクリスタル (給料日前編) - yukicoder

感想

ナップザック風です.

yukicoder No.314 ケンケンパ

問題

No.314 ケンケンパ - yukicoder

解法

ケンケンパの生成について, 3つの状態があります.

パで終わっている
末尾にケンが1回連続で出現して終わっている
末尾にケンが2回連続で出現して終わっている

遷移しうる状態は
1 → 2
2 → 1 , 3
3 → 1
よりDPを組み立てると, (0-indexedで組みます)
$dp[i][j] = (長さiまでの生成パターンについて, パターンjに含まれるもの)$
として, 右辺を固定して配るdpをすると,

初期値

$dp[0][0] = 1$

$j = 0 のとき$

$dp[i+1][j+1] += dp[i][j]$

$j = 1 のとき$

$dp[i+1][j+1] += dp[i][j] \\ dp[i+1][j-1] += dp[i][j]$

$j = 2 のとき$

$dp[i+1][j-2] += dp[i][j]$
これを $0 \leq i < N , \space 0 \leq j \leq 2$ について回すと,
$\sum_{j=0}^{2} dp[N][j]$ が答えです.

提出

#279160 No.314 ケンケンパ - yukicoder

感想

前後のみを見るdpなので, 領域を節約できないかとi%2 でインデックスしたもので実装してもみたものの, なんでかバグって正しい答えが出力されませんでした... どうしてでしょう.

ABC 076 D - AtCoder Express

問題

D - AtCoder Express

解法

まず, サンプルをみると速度・時刻が0.5刻みで決まっていきそうなことがわかるので, 時刻・速度ともに２倍に引き伸ばします. これで多少は考えやすくなります.
前方向から順に速度を決めていくと, 減速しきれない区間が現れたりしてうまくいかないので, 到着する場所から, とりうる最大の速度をdpします.
(各区間ごとの最高速度)と(一秒後の最高速度+1)の小さい方が, とりうる最大の速度となるのでこれをすべての時刻について回します.
あとは, スタート地点からゴール地点までにおいて, 取りうる最大の速度について, 貪欲に加速しながら台形の面積を加算していくと答えが求まります.
時刻と速度を2倍に引き延ばしているので, 面積を4で割る必要があります.

提出

Submission #3042568 - AtCoder Beginner Contest 076

感想

先に各時点での最大速度を求めるのは発想としては自然だと思います(思いつきませんが). しかし, 各時点での最大速度を求めるときに区間 $[T_i , T_{i+1}]$ の境目においてはちょっと処理がややこしく, そこだけ分けて考えるとよいです. ( $T_i$ は $[T_{i-1},T_i], [T_i, T_{i+1}]$ に含まれているため, 双方の速度制限を満たしている必要があります. )

ABC 086 Checker

問題

解法

まず愚直な解法について考察します.
この問題の１辺が大きさ $K$ の市松模様について, まずどこかの黒い正方形の左下に座標 $(0,0)$ を置きます.
市松模様は無限に続いているので, この黒い正方形について右に1から2K-1, 上に1から2K-1ずらしていけば, すべての場合を取りつくせることになります. このずらしを行ったときに, $N$ 個の要望が満たされている数を調べ, 最大値をとると答えが出ます. しかし, 計算量は $O(NK^2)$ となり, 制約から間に合いません.

入力の $x_i , y_i , c_i$ について, あるマス $(x_i , y_i)$ が白だとしたら, $(x_i , y_i + K)$ は必ず黒になります. これを利用すると, 白の希望をすべて黒の希望に変換でき, $c_i$ を死にパラメータにすることができます.
また, 同じ性質より $x_i , y_i$ について $2K$ の周期があるため, それぞれ
$x_i := x_i \space mod \space 2K$
$y_i := y_i \space mod \space 2K$
としてよいことがわかります. よって, $2K * 2K$ のマスのみを考えればよいこともわかります.

マスをずらしていったときに高速で希望と一致しているマスを数える方法を考えます.
そこで, 二次元の累積和を考えます.
二次元の累積和によって $(0,0) から (i,j)$ までの正方形領域に含まれる希望の数を $2K*2K$ 個計算します. これは, まずそれぞれの希望について, $sum[x_i][y_i]++$ としたあと,
$sum[i][j] += sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]$
とすることで計算できます.
あとはこの累積和をこねくりまわすと, 各ずらしについて $O(1)$ で要望の数を求めることができます. (計算式がちょっとめんどうです).

また, 実は $2K*2K$ 回ずらして計算する必要はなく, 縦横それぞれ $K$ 回ずらしてかなわなかった要望の数も最大値として更新するようにすると, $K^2$ 回で済みます. 全体の白黒を反転すれば, 対応する市松模様があるからです.

提出

Submission #3041317 - AtCoder Regular Contest 089

感想

難しい.