東京海上日動プログラミングコンテスト 2020

2020-06-13

コンテスト中に挑戦した問題についての感想とか.

A - Nickname

与えられた文字列Sから3文字の(連続する)部分文字列をどれでも良いので取り出す問題.

sは3文字以上なのでこの操作はいつでも可能な設定. 先頭から3文字取れば良いだけ.

中学受験で出てきそうなタイプの問題で, 初期状態は離れている数直線上の2点が等速直線運動して, 与えられた時間内に2点が重なるかどうかを判定する.

問題を読み間違えてしまったのが痛かった. 与えられた初期位置の制限を数直線が閉区間であると読み間違えたので不要な条件を入れてしまった.

途中精度の問題と勘違いしたのもアレ.

問題分をよく読もう.

与えられた回数ある操作を行った結果を出力する問題.

まず, 速さ間に合わないと分かりつつ愚直に書いたところは良かった.

競技プログラミングでも今の私のレート帯だと, 簡単に作ってボトルネックを解除するというやり方は有効だと思う. (前回のARC級NOMURA2020はそれでうまく行った.)

その後時間短縮のために, 結果が収束する場合の判定を入れたのも良かった.

ここからが良くなかった. これで間に合わないことが提出してみて分かったので, さてどうするかとなった時に, 1回の操作の計算量が大きいことは分かっていたがこれをどうにかする方法をすぐに思いつかず敢え無くという結果.

どちらかと言うと思考が全体として計算量を減らすことを考えてしまったのが良くなかった.

ということで時間内に解けずだった.

なお解法としては, 累積和の考え方を用いる.

ネットの情報からは累積和という言葉が何を指しているかどうにもハッキリと分からなかったので, 以下で定義も与えておく.

ここでは, O(1)アクセス可能なシーケンシャルな構造aに対して, 累積和を録るという操作を

(loop :for i :from (1+ start) :to end
    (setf (aref a i) (+ (aref a i) (aref a (1- i))))

とする. (ここでは破壊的に書いた)

この操作後のaを累積和と呼ぶことにする.

i番目の要素は元のシーケンスのi番目以下の要素の和となるような操作である.

累積和を作っておくと, 元のシーケンスのi番目の要素からj番目の要素の和を求めたいなら累積和のj番目の要素から累積和のi - 1番目の要素を引くことでO(1)で求められる.

N個閉区間(重複可)に均等に値v_iを足す操作を長さM配列に行う場合は,

の様に処理することでO(M+N)で処理が出来る. もし愚直にやったら閉伊区間の長さの平均をLとしてO(LM)かかる.

解けなかったが, 解説を見て勉強になった問題であった.

当面はARC級はCまで解くことを目標にしたい.