相変わらず趣味でプログラミングは続けているが、プログラムを自分で書くことは以前に比べて激減したと思う。言うまでもなく生成AIが原因だ。

生成AIを使うと圧倒的に頭の中で考えたことを実装するスピードが速い。一度これに慣れてしまうと、わざわざ手を使って書く理由は産まれにくい。明らかに自分が思いつかないような機能も書けるし、もはや質でもスピードでも敵わない。

しかしながら、たまに手組みプログラミングを無性にやりたくなる。それが不便であるとわかっているが、それ自体が楽しい。そういう行為は確かに存在する。車がある世の中でも趣味で馬に乗る人間はいる。生成AIが発達しようと手でプログラムを書く楽しみ自体は変わらないものだと信じたい。

AtCoder

何か書きたいと考えた時に思いついたのはAtCoderだった。自分は2023年頃までけっこう熱心に参加をしていて、当時は全面的に禁止されていなかった生成AIの助けを借りながら水色コーダーになるまで頑張った。

当時書いた入水エントリ。

AtCoderで入水したのでこれまでのことを振り返る

これは自分の中でも一つの大きな自信になった。公式によると以下のような水準であるらしい。

アルゴリズムの絡んだ開発が特技と呼べるような水準です。アルゴリズムの豊富な知識に加え、典型的な課題の言い換えも把握し始めており、多くの複雑な問題をアルゴリズム的な処理に落とすことが出来ます。

かなりのコーディング速度があります。課題を見てからロジックを考えるまでが早いので、上流工程において、ロジックをイメージしながら会話をする能力も高い事が想定されます。

Algorithm部門のレーティングと業務における期待できる活躍

そんなAtCoderだが、生成AIの性能があがるにつれてコンテストでの使用が禁止になっていった。

同時に自分も参加する意欲を失っていき、しばらくは離れていた。

だが、冒頭に書いたようにプログラムを自分の手で書きたい、という欲求をさいきん感じている。こういう時にAtCoderの問題に向き合う、というのはナイスな試みである気がする。意味はあまりないかもしれないが、純粋なプログラミングの世界が問題と向き合う時に開ける。

コンテストにリアルタイムで参加はしないまでも、久しぶりに問題を解いてみる。

なまっていた頭の中の部分が、コーディングを行う手の感覚が戻ってきた気がする。

というわけで前回のD問題を解いてみた。

D - Many Repunit Sum

https://atcoder.jp/contests/abc444/tasks/abc444_d

概要

i=1,2,…,N に対して、1 を Ai​ 個つなげた整数を Bi​ と表す。

与えられた全てのBiを求めよ。

回答の流れ

数式が多く意味がわからないがこういうときは、入力例をみる。

4
3 3 3 3

この入力で111 + 111 + 111 + 111 = 444が答え。

意味がわかった。ようは1が数字の数だけ並んだものを足せばいい。

入力のような小さい数字だったらそのまま実装すればいいけど、制約をみるとAiは10^5まである。

つまり10万桁程度の数字の足し算を行うわけで、これは普通のコンピューターで演算するのは不可能だ。

どうしたものかと考えていると、ちょうど小学校のときにやった筆算みたいな感じで解けることに気づいた。

つまり上の計算だったらこんな感じになる。

111
111
111
111
---
444

各桁の部分を順番に足していけば馬鹿でかい数字を扱わなくてすむ。

しかし筆算で厄介なのは「繰り上がり」があることだ。

1が10回足されたら、その桁は0になり、次の桁に足し合わせる必要がある。

これを管理するのは難しそうだ・・・と思ったが、Nの数は10^5が上限なので、最大で繰り上がる桁は5桁分くらいか？ということを考える。1が10万回足されたら100000になるが、これは5桁分繰り上がったと言える。

あとは各桁を愚直に足し合わせていくと時間が間に合わないので、いもす法で最後にまとめて、桁は後ろから埋めていくのは大変そうなので最後にひっくり返して・・・とやったら解けた。

一回Pythonで解いたけどせっかくなのでTypescriptで実装をしてみた。

function main() {
  const n = nextNum();
  const arr = nextNums(n);
  // 配列の最大値を取得
  const ma = Math.max(...arr);
  // ゼロ埋めで初期化 最大値＋10くらいとっておく
  const imos: number[] = new Array(ma + 10).fill(0);
  // imos法の要領で累積和を計算する
  for (const num of arr) {
    //1桁目を足す
    imos[0]++;
    //境界値を引く
    imos[num]--;
  }
  //累積和を取る
  for (let i = 1; i < ma + 10; i++) {
    imos[i] = imos[i] + imos[i - 1];
  }
  // 繰り上がりを計算する
  for (let i = 0; i < ma + 1; i++) {
    // 最大で5桁繰り上がる。安全を見て６桁でみる
    let num = imos[i];
    for (let keta = 6; keta > 0; keta--) {
      const wari = 10 ** keta;
      // 足す桁数
      const div = Math.floor(num / wari);
      imos[i + keta] += div;
      // numを余りで更新
      num = num % wari;
    }
    // 最後に残った数字で更新
    imos[i] = num;
  }
  // 末尾のゼロを取り除く。桁が繰り上がりきらなかった分
  while (imos.length > 0) {
    const lstIndex = imos.length - 1;
    if (imos[lstIndex] == 0) {
      imos.pop();
    } else {
      break;
    }
  }
  //順番が逆なのでひっくり返す
  imos.reverse();
  //答えを作る
  const ans = [];
  for (const num of imos) {
    ans.push(String(num));
  }
  console.log(ans.join(""));
}

main();
flush();

https://atcoder.jp/contests/abc444/submissions/73167704

１本問題を解くだけで色々な文法を調べながら手を動かした。最大値の取得、pop()して取り除く、配列の初期化、累積和、などなど。生成AIを使えば一瞬で終わるかもしれない問題だが自分の手を動かすと達成感がある。

こんな時代だからこそAtCoderのブームがくるかも。

ちなみにAtCoderをやるTypescriptの環境構築はClaude Codeにやってもらった。前だったらこの時点でつまづいていたので、これはたすかる。欲の皮が張っているかもしれないが、こういう良いところを享受して楽しみたい。ではでは。