10/17: 初めてのcodeforces
@ecasdqina に誘われてcodeforcesに初参戦しました。20:05~22:00とかそんなんだった。珍しい
Div2のABCを通したのですが、システムテストでBがTLEしました...
結果Div2のA, Cでレートは1442になりました。いきなり水。
B解けたらもうちょっと上だったのかな〜。
Bは
- 配列を昇順にソート
- 決めた一番はじめの数(p)から各要素を見ていって、pとの差がmの倍数になったら逐次答えに入れる・・・k個になったら出力して終了
- pを0~nまでループさせる
という工夫のない解法をしました。O(N2) ???
Cはというと、
n = kの各桁の和 + k
になるk
を求めるんだよね(Readforces)- まず
k < n
になるのでこれを使いたいなあと思った - 各桁の最大値は9なので、例えば
k = 1000p + 100q + 10r + s
かつk = 9999
とすれば、n = p + q + r + s + k = 9 + 9 + 9 + 9 + k
となり、kになりうる最小値はn - 9*4
とわかる - 逆に、
k = 1000
のとき、各桁の和は1なので、kになりうる最大値はn - 1
とわかる - 問題より、nの桁数はたかだか9なので、
n - 9*(桁数)
からn - 1
のループをしてうまく行くかチェックすればOK
もうちょっと計算量減らせそうだけどACしたし、まあいっか。
他には、Arduino LeonardoでNキーの代用品を作ったりしていました。
単純にタクトスイッチ(ボタン)で入力したり、手を振り上げるのを超音波センサで検知して入力したり楽しいです。
秋葉原でいろいろ買っておいてよかった。
はじめ使っていたmicroUSBケーブルが給電専用ということに気づかずハマりました...