xxxasdfghjk999のブログ

iroiro

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

感想

難しい.

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コードでも書いて実験して改良点を探す, ということができてないように思えた. 愚直解がだめとわかっていてもとりあえず作ってみてそこから考えてみる, というのが重要だと感じた.
あと個人的に累積やしゃくとりなどを用いて計算量を減らす問題が苦手だと感じた. 演習を増やしたい.