プロフィール
AtCoder PR

【AtCoder ABC113C Typescript】問題解説「ID　市ごとの認識番号を生成する方法」

 
記事内に商品プロモーションを含む場合があります
Contents
  1. 問題の概要
  2. 解法のポイント
  3. 学びポイントまとめ（PREP）
  4. 改善のヒント
  5. 最後に

問題の概要

AtCoder国には N 個の県があり、そこに M 個の市が属しています。
それぞれの市には 誕生年 Y_i と 所属県 P_i が与えられます。

目的は、以下のルールに基づいて 12桁の認識番号を生成することです：

  • 認識番号の上6桁：県番号（6桁に0埋め）
  • 認識番号の下6桁：その県に属する市の中での誕生順（6桁に0埋め）

同じ年に誕生する市は存在せず、誕生順が一意に定まります。

解法のポイント

この問題のキモは、「各県ごとに市の誕生順を記録しながら、元の順に認識番号を出力する」ことです。

ステップで整理すると：

  1. 市データを年順でソートする（誕生順を知るため）
  2. 県ごとの市数をカウントして、何番目の市か記録
  3. 認識番号を作成（padStart(6, '0') で0埋め）
  4. 元の順番に戻して出力

🧪 入力例

2 3
1 32
2 63
1 12

このとき、県ごとに誕生順を振り分けて、以下の認識番号が出力されます：

000001000002
000002000001
000001000001

import * as fs from "fs";

function Main(input: string) {
  const lines = input.trim().split("\n");
  const [N, M] = lines[0].split(" ").map(Number);

  const data = lines.slice(1).map((line, i) => {
    const [pref, year] = line.split(" ").map(Number);
    return { index: i, pref, year };
  });

  // 誕生年でソート（誕生順を確定）
  data.sort((a, b) => a.year - b.year);

  const counter: Record<number, number> = {};
  const result: string[] = [];

  for (const item of data) {
    counter[item.pref] = (counter[item.pref] ?? 0) + 1;

    const id =
      String(item.pref).padStart(6, "0") +
      String(counter[item.pref]).padStart(6, "0");

    result[item.index] = id; // 元の順に戻す
  }

  console.log(result.join("\n"));
}

const inputData = fs.readFileSync("/dev/stdin", "utf8");
Main(inputData);

学びポイントまとめ（PREP）

  • Point：市の誕生順を管理し、県ごとに通し番号を振る
  • Reason：県ごとの誕生順に応じてIDが変わるため
  • Example：県1における2番目の市 → 000001000002
  • Point：padStart(6, "0") を使えば簡単にゼロ埋めできる

改善のヒント

  • padStart() を使うとゼロ埋めの実装がすっきり！
  • ソート後に index を残しておけば、出力順の復元がラク
  • Map を使っても良いが、Record<number, number> でも十分高速でシンプル

最後に

この問題は、「ソート + カウント + 出力順の復元」という典型パターンが問われます。
競技プログラミングではよくある構造なので、ぜひ定着させたいテクニックです。

RELATED POST