点Nの軌跡

競プロの話または日記

AtCoder Beginner Contest 179 感想

AtCoder 競プロ

前回とはうってかわって激冷え回

Problem A
- 考察
Problem B
- 考察
Problem C
- 考察
Problem D
- 考察
Problem E
- 考察
あとがき

Problem A

英単語の末尾がs以外ならs,sならesをつけよ

考察

C++では文字列Sの末尾はS.back()で抽出できる
はい

Problem B

2個のサイコロをN回振りましたが、ゾロ目を3連続で出すことに成功しましたか？

考察

実装するだけじゃん
0初期化済み配列を長めに用意してゾロ目なら1を書く
連続する3要素の和が3になってるところがある？

Problem C

$A \times B + C = N$ を満たす正整数A,B,Cの組の総数は？

考察

Cは正整数
$A \times B \lt N$ を満たす正整数A,Bの組と同じこと
Aをループで回す
サンプルではNの最大ケースでも答えが10⁷ぐらい、Bも回して直接数えても間に合いそう？
Aのループの中でBを小さい順にみていって、N以上になったら以降の判定を省略する

Problem D

マス1からNに移動する方法の総数は？一度の移動では好きなiに対して[Li,Ri]マスのうち好きなだけ動ける

考察

ナップサックみを感じる
多分DPで解ける
単純にやるとO(N²)で無理
区間の数がK<=10で少ないのでそれを使いそう
dp[x] = Σ（マスxへの移動を[Lk,Rk]マスの移動によって実現する）
dp[x-Rk]からdp[x-Lk]までの総和を高速に求めたい
累積和使えばいい

Problem E

$A _ 1 = X, A _ {n+1}={A _ n}^2 mod \ M$ のときの $\displaystyle \sum _ {i=1} ^ N A _ i$

考察

N項目までだけど、N<=10¹⁰
mod MのMは小さいので周期性が現れる
どこかでループするのでその開始地点と一周の長さとループ数と最後余計に周回する分とそれらに対する各区間の和を
求めるだけなのになんで通らないんですか
なんで通らないんですか

F問題は見てないのでまたいつか（いつ）

あとがき

緑パフォで50ぐらい下がった。前回がなかったらと思うと怖いですね