更新日時で差をつけろ

差をつけられそう

10/17: 初めてのcodeforces

f:id:sei0okun:20171017080210p:plain

@ecasdqina に誘われてcodeforcesに初参戦しました。20:05~22:00とかそんなんだった。珍しい
Div2のABCを通したのですが、システムテストでBがTLEしました...
結果Div2のA, Cでレートは1442になりました。いきなり水。
B解けたらもうちょっと上だったのかな〜。

Bは

  1. 配列を昇順にソート
  2. 決めた一番はじめの数(p)から各要素を見ていって、pとの差がmの倍数になったら逐次答えに入れる・・・k個になったら出力して終了
  3. pを0~nまでループさせる

という工夫のない解法をしました。O(N2) ???

Cはというと、

  1. n = kの各桁の和 + kになるkを求めるんだよね(Readforces)
  2. まず k < n になるのでこれを使いたいなあと思った
  3. 各桁の最大値は9なので、例えばk = 1000p + 100q + 10r + sかつk = 9999とすれば、n = p + q + r + s + k = 9 + 9 + 9 + 9 + kとなり、kになりうる最小値は n - 9*4 とわかる
  4. 逆に、k = 1000のとき、各桁の和は1なので、kになりうる最大値はn - 1 とわかる
  5. 問題より、nの桁数はたかだか9なので、n - 9*(桁数)からn - 1のループをしてうまく行くかチェックすればOK

もうちょっと計算量減らせそうだけどACしたし、まあいっか。

他には、Arduino LeonardoでNキーの代用品を作ったりしていました。
単純にタクトスイッチ(ボタン)で入力したり、手を振り上げるのを超音波センサで検知して入力したり楽しいです。
秋葉原でいろいろ買っておいてよかった。
はじめ使っていたmicroUSBケーブルが給電専用ということに気づかずハマりました...