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