Sat Sep 19 20:44:59 JST 2015

D問題 - 1 - AtCoder Beginner Contest 029

http://abc029.contest.atcoder.jp/tasks/abc029_d

概要

\(n\) が与えられる. 10進数で \(1\) から \(n\) を並べて記述したとき、 \(1\) という桁はいくつ出現するか

解答

naiive 関数はデバッグのための素朴な解法. 結果的にこれを部分的に用いる solve 関数を書いて通した.

int naiive(int m, int n) {
  stringstream ss;
  for (int i=m;i<=n;++i) ss << i;
  string s(ss.str());
  int ans = 0;
  for (char c: s) if (c == '1') ++ans;
  return ans;
}

/*
 * 1 .. n
 * を
 * [0..9], [10..19], [20..29], ...
 * にグルーピングして考える
 */
int solve(int n) {
  if (n < 100) return naiive(1, n);
  int ans = 0;
  int k = 1;
  while (n > 0) {
    int m = (n/10) * 10;
    if (m <= n) ans += naiive(m, n) * k;
    ans += (m/10) * k;
    n = (m/10) - 1;
    k *= 10;
  }
  return ans;
}

厚紙を買った

レシートと領収書が違うことを知った。

文房具屋にて、予め計算した面積に足りるだけ、 A2サイズの厚紙を3枚購入した。 支出を全て記録するために、レシートが欲しくて、 領収書をくれと、店主のおばあちゃんにいうと、 ただ数字を感熱紙に印字しただけの紙切れが欲しかったのに、 手書きで領収書を、断る暇なく、書いてくれた。 その頃の自分には、親友と呼べるような人が一人だけいた。 私は彼からかなり多くの影響を受けた。 その一つに、なんでも記録を取るというものがあった。 新聞で株価を読むという習慣を知って、 それでかつ、株価をノートに逐一、ローソク足を書き込むという習慣を身につけた。 それにしても本当に、 彼ほど、たった一日で、もう何年も前から知っていたような友達になれた人もいない。 それはやはり、中学生というものの性質なのだろう。 小学生ほどのシャイさは失われ、かわって思春期という別な種類のシャイがやってくる。 そこを中学生という未熟さと生意気さによって打ち明けてしまう。 我が悪友であった。 中学生の友達と、大人の友達とを較べてもしょうがないのかもしれないが、 親友は彼だけだったと思う。 毎週日曜日は必ず一緒に競馬の実況中継を見た。 これも彼の趣味であった。 毎週日曜日の新聞は一週間の株価がまとめて載ってある。 お互いにこれぞと思う銘柄を2つずつ選んで、 紙の上で為替取引をして勝負するのであった。 私は選んだシルバー精工が、ある時から「整理」としか表示されなくなったのを覚えている。 (いまWikipediaを見ると、2011年に上場廃止、同年破産となっている。 ただしここに書いてある思い出は、それよりずっと昔だ。) 「シルバー精工」なんて縁も馴染もない企業名を知ってるのは、ひとつ、思い出である。 そんなわけで、自分のお小遣い家計簿を事細かに記録する習慣も、 あくまでも数字を追うという趣味として確立したのだった。

しかしながら、子供独特の、あるつまらない事件によって、 彼とは一切連絡が取れない状態に陥ってしまった。 喧嘩別れしたということではない。 喧嘩はいくらでもしたが、その時ばかりはもっと深刻に思えて、 喧嘩が起きる直前のような、しかしどちらとも決して攻撃には踏み込まない、 そんなピリピリした状態だった。決して彼のことを恨んではいない。 その時だって別段、できれば、さっさと解決したい、だが、 解決に必要なのはただ、時間しかないのだと思った。 こんなネット社会だから、いつか会うことがあるかもしれない、と思い続けて、 そんなことは起こりそうにない。