xxxasdfghjk999のブログ

iroiro

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

感想

難しい.

yukicoder No.607 開通777年記念

問題

https://yukicoder.me/problems/no/607

解法

駅に到着するごとに条件を満たしているかを調べる必要があります.
駅に到着してからの人員の増減を配列に入れて管理し, その都度累積和を取り直します.
$1 ~ N$ までの累積和のなかで2つ選ぶと, その差分を見ればその区間内の人数の和がわかります. ここで選ぶ区間の片側(右側)を固定し, 『もう一方の端をうまく選んで区間内の乗客を777人にできるか？』という問題を考えます. 累積和は単調増加であるため, いま注目している添字 $i$ に対し, $sum[i] - 777$ を二分探索で高速に調べることができます.
これが見つかったとき, "YES"を出力し, 見つからなかったときは最後に"NO"を出力します.
これをクエリの数 $M$ 回だけやるので, 全体の計算量の見積もりは $O(NM\log N)$ となり, この制約では間に合います.

提出

#278968 No.607 開通777年記念 - yukicoder

ABC 106 反省

A問題

問題

A: Garden - AtCoder Beginner Contest 106 | AtCoder

解法

道を端っこに移動させると $(A-1)\times(B-1)$ の面積になります.

提出

Submission #3027981 - AtCoder Beginner Contest 106 | AtCoder

B問題

問題

B: 105 - AtCoder Beginner Contest 106 | AtCoder

解法

制約が小さいので $1からN$ までの奇数について約数をすべて調べ, 8個のものをカウントします.

提出

Submission #3028942 - AtCoder Beginner Contest 106 | AtCoder

C問題

問題

C: To Infinity - AtCoder Beginner Contest 106 | AtCoder

解法

回数が十分大きいので, $K$ 番目まで1が続くかどうかを調べ, 1でないものが出現したらその数を出力し, 1が続いていたときは1を出力します.

提出

Submission #3031422 - AtCoder Beginner Contest 106 | AtCoder

D問題

問題

D: AtCoder Express 2 - AtCoder Beginner Contest 106 | AtCoder

解法

まず愚直な解法を考えます. ある配列 $memo[N][N]$ をすべて0に初期化して用意しておき, すべての $L_i , R_i$ について $memo[L_i][R_i]++$ とし, それぞれの数をカウントしておきます.
あるクエリ $p_k , q_k$ に対しては,
$p_k \leq i \leq q_k かつ i \leq j \leq q_k$ なる $i , j$ に対し,
$\sum_{i,j} memo[i][j]$
が答えとなります.
この解法の計算量は $O(QN^2)$ となり, TLEします.

この解法において,
$\sum_{i,j} memo[i][j]$
を計算する部分は, あらかじめ配列 $memo[]$ の累積和をとっておくことでループを１つ減らすことができます.

具体的には, 下の式が成り立ちます.
$\sum_{i,j} memo[i][j] = \sum_i (sum[i][q_k] - sum[i][p_k-1])$
これで $O(QN)$ となるので, 間に合います.

提出

Submission #3040635 - AtCoder Beginner Contest 106 | AtCoder

感想

コンテスト中はいろいろ解法がごっちゃになり, ややこしいコードを書いていたらコンテストが終わっていました.
あきらかなTLEコードでも書いて実験して改良点を探す, ということができてないように思えた. 愚直解がだめとわかっていてもとりあえず作ってみてそこから考えてみる, というのが重要だと感じた.
あと個人的に累積やしゃくとりなどを用いて計算量を減らす問題が苦手だと感じた. 演習を増やしたい.

yukicoder No.523 LED

問題

No.523 LED - yukicoder

解法

LEDをポチポチする順番を順列にして考えてみると, 例えばN=3のとき, ①①②②③③の並べ方を数える問題になります. このとき, 同じ番号のものは区別せず, 場合の数は $\frac{6!}{2^3} = 90$ となります. 一般のNに対して答えは次の式で表されることがわかります.
$P_N = \frac{(2N)!}{2^N}$
制約から $(2N)!$ はループを回しながら剰余をとっても間に合います. $2^N$ は, まず繰り返し二乗法を用いて $k = 2^N \space mod \space p$ となる $k$ を求めた後, さらに繰り返し二乗法を用いてフェルマーの小定理
$k^{-1} \space \equiv \space k^{p-2} \space mod \space p$
から $k$ の逆元を求め, $k^{-1}(2N)!$ を計算して答えです.

提出

#278769 No.523 LED - yukicoder

その他

実は答えの式 $P_N = \frac{(2N)!}{2^N}$ は
$(2N)! = \prod_{k=1}^n (2k-1)2k$
より
$\frac{(2N)!}{2^N} = \prod_{k=1}^n (2k-1)k$
と変形できるため, 一回のfor文で求めることもできます. ｽｺﾞｲ