この記事では、AtCoder で提供される次の問題を題材に、
TypeScript を使って解く方法を丁寧に解説します。
https://atcoder.jp/contests/abc130/tasks/abc130_b
この記事では、TypeScript で AtCoder 問題を解くポイントや、初心者の方がつまずきやすい部分にフォーカスしつつ、サンプルコードとともに手順を解説します。特に「普段 JavaScript/TypeScript でプログラミングしない人でも、AtCoder のような競技プログラミングにチャレンジしたい」という方に向けて書いています。
問題概要
数直線上を N+1N+1 回跳ねるボールがあり、11 回目は 座標 D1=0D1=0, ii 回目は 座標 Di=Di−1+Li−1(2≤i≤N+1)Di=Di−1+Li−1(2≤i≤N+1) で跳ねます。
数直線の座標が XX 以下の領域でボールが跳ねる回数は何回でしょうか。
制約
入力は全て整数である
1≤N≤1001≤N≤100
1≤Li≤1001≤Li≤100
1≤X≤100001≤X≤10000 Contents
この記事のポイント
- 問題の本質
- ボールが跳ねるごとに座標を累積していき、座標が与えられた閾値 Xを超えたら「これ以上カウントしない」ことに注意して実装する。
- 「座標が X以下」という条件を満たす回数をシンプルに数え上げればよい。
- TypeScript での実装ポイント
- 標準入力を受け取って文字列として読み込む → 一度にまとめて読み込み、改行で split する。
- 数列 L1,L2,…,LNをまず
number[]にパースしておくとループ内のparseIntを減らせる。 - ループ処理では、インデックスがずれるミス（オフバイワン）に注意する。
- 既定の制約（N≤100 Li≤100, X≤10000）の範囲では計算量は十分小さいので、素直に for ループを書いて OK。
- 競技プログラミング初学者向けの注意点
- 入力の受け取り方法（Node.js +
fs.readFileSync）は慣れが必要。 - TypeScript のときは型注釈を活用して、配列や変数の型を明確にしておくとトラブル防止になる。
- 「条件を満たす間だけループを続ける」という考え方を競技プログラミングではよく使う。
- 入力の受け取り方法（Node.js +
問題の詳しい解説
1. 問題文の読み解き
- 「N+1 回跳ねる」
最初の跳ねは必ず座標 0 で行われる（D1=0）。
つまりボールは合計でD1,D2,…,DN+1 の座標で跳ねる。 - 「i 回目は座標 Di=Di−1+Li−1」
- i=2i=2i=2 のとき：D2=D1+L1=0+L1。
- i=3i=3i=3 のとき：D3=D2+L2。
- 以降、最後は DN+1=DN+LN。
- 質問は「座標が X 以下の領域で跳ねる回数」 count=#{i∣Di≤X, 1≤i≤N+1}.
最初の D1=0は必ず X 以下（X≥１）なので、少なくともカウントは 1 から始まる。
2. サンプルで考える
サンプル 1
N = 3, X = 6
L = [3, 4, 5]
- 跳ねる座標：
- D1=0
- D2=0+3=3
- D3=3+4=7
- D4=7+5=12
- これらのうち、X=6以下なのは D1=0, D2=3。
よって答えは 2 回。
サンプル 2
N = 4, X = 9
L = [3, 3, 3, 3]
- 跳ねる座標：
- D1=0
- D2=0+3=3
- D3=3+3=6
- D4=6+3=9
- D5=9+3=12
- これらのうち、X=9 以下なのは 0,3,6,9。
よって答えは 4 回。
3. 解法のアルゴリズム
- 入力をパースする
- 1 行目で N,Xを取得する。
- 2 行目で L1L2…LN のリストを取得する。
- 累積位置を管理する変数
posを 0 で初期化- ただし最初の跳ね位置 D1=0 はあらかじめカウントしておく。
count = 1で（最初の 0 をカウントして）スタート- i = 1 から N までのインデックスをループ
- 毎回
pos += L[i]（TypeScript の 0-index に合わせると注意） - もし
pos > Xなら、それ以上跳ねられないのでループをbreak - それ以外なら
count++
- 毎回
- 最後に
countを出力する。
これで座標が X以下の跳ね回数を正しく数えられる。なお、ループを途中で抜ける理由は「次の跳ね位置がすべて Xを超えてしまうため、それ以降はカウントできない」からである。
TypeScript 実装例
以下に、先ほどのアルゴリズムに則った TypeScript のコード例を示します。
AtCoder の Node.js/TypeScript 環境で動かすために、エントリポイントとして Main 関数を定義し、fs.readFileSync で標準入力を一度に読み込んでいます。
// ---------------------------------------------
// Main.ts
// AtCoder 問題: 数直線上を跳ねるボール (N + 1 回跳ねる)
// TypeScript で わかりやすく実装
// ---------------------------------------------
// Node.js で標準入力を一括読み込み
import * as fs from "fs";
function Main(input: string) {
// 1. 改行で分割して行ごとに分ける
const lines: string[] = input.trim().split("\n");
// 2. 1 行目から N, X を取得
// 例: "3 6" → [ "3", "6" ]
const [nStr, xStr] = lines[0].split(" ");
const N: number = parseInt(nStr, 10);
const X: number = parseInt(xStr, 10);
// 3. 2 行目以降から L 配列を取得し、数値配列（number[]）に変換
// 例: "3 4 5" → [ "3", "4", "5" ] → [3, 4, 5]
const L: number[] = lines
.split(" ")
.map((s) => parseInt(s, 10));
// 4. カウントの初期化：最初に D_1 = 0 で跳ねるので 1 回とする
let count: number = 1;
// 5. 現在の累積跳ね位置
let pos: number = 0;
// 6. N 回分ループして、新しい跳ね位置 pos を更新
for (let i = 0; i < N; i++) {
// L[i] を足して i+2 回目の跳ね位置を計算
pos += L[i];
// pos が X を超えたらそれ以上カウントしない
if (pos > X) {
break;
}
// X 以下ならカウントを増やす
count++;
}
// 7. 結果を出力
console.log(count);
}
// AtCoder の場合、以下のように書くのが定番
const inputData: string = fs.readFileSync("/dev/stdin", "utf-8");
Main(inputData);
コードの各ポイント説明
fs.readFileSyncでまとめて入力を読む- 競技プログラミングでは、複数行の入力を
readFileSync("/dev/stdin", "utf-8")で一括で文字列として取得し、後からsplit("\n")して行ごとに扱う方法がよく使われる。 - これにより、逐次
readlineのような面倒な処理を自前で書かなくて済む（実質的に高速）。
- 競技プログラミングでは、複数行の入力を
lines[0].split(" ")で 1 行目からNとXを取得- ここで返ってくるのは文字列なので、
parseInt(..., 10)して数値に変換する。 - TypeScript では型注釈をしっかり書くことで、自身のバグ防止につながる。
- ここで返ってくるのは文字列なので、
linesで.split(" ").map(parseInt)Lの配列を数値に変換parseIntをmapに直接渡すと第 2 引数にインデックスが来てしまうことがあるので、ここでは(s) => parseInt(s, 10)のようにラップして確実に 10 進数で文字列を数値に。- こうしておくことで、ループの中では毎回
parseIntを呼ばずに済み、可読性・保守性が向上。
- 最初の跳ね位置を「1 回」としてカウントする
- 問題文の「1 回目は座標 0 で跳ねる」は必ずカウントするので、
count = 1としておく。 - もし将来 X<0\,X<0X<0 みたいな極端なケースが入る競プロでは乗らないが、本問題だと X≥1X \ge 1X≥1 が保証されているので安心して 1 から始められる。
- 問題文の「1 回目は座標 0 で跳ねる」は必ずカウントするので、
- 累積位置を
posに保存し、ループごとに更新posは最初 0 なので「D1=0」の役割を担っている。- ループのたびに
pos += L[i]して、次の跳ね位置D_{i+2}を求める（配列Lは 0-index だが、問題文では L1から始まるため、インデックスのずれに注意）。 if (pos > X)になったらもう座標が X を超えているのでループを止める。
- 最後に
console.log(count)で答えを出力- 出力は数値だけで問題ない。
解説ポイント
ここからは、TypeScript 初学者や AtCoder への挑戦が初めてという方向けに、もう少しかみ砕いて解説します。
標準入力の捉え方
- AtCoder の Node.js/TypeScript 環境では、C++ の
cin/coutのように簡単に逐次読める方法がない。 - その代わりに、「一度にすべての入力を文字列として読み込み」→「行ごとに
splitする」 というテクニックを覚えよう。// 一度に読み込むconst raw: string = fs.readFileSync("/dev/stdin", "utf-8");// 改行で区切って配列にするconst lines: string[] = raw.trim().split("\n"); trim()を使っておくと、最後の余分な改行があっても空文字列要素を減らせるので便利。
文字列から数値への変換
- TypeScript では、
"123"のような文字列をそのまま数の変数に格納できない。parseInt("123", 10)→123- あるいは
Number("123")→123
などを使って、文字列を数値に変換しなければならない。
parseIntをmapに直接渡すと、mapの第 2 引数（インデックス）がそのままparseIntの第 2 引数（基数）として渡されてしまい、予期せぬ結果になることがある。// NG: "10", "20", "30" を受け取ったとき、parseInt は第2引数にインデックスを受け取ってしまう["10", "20", "30"].map(parseInt); // [parseInt("10", 0), parseInt("20", 1), parseInt("30", 2)] という動きになってしまう// 正しくは、以下のようにラップする["10", "20", "30"].map((s) => parseInt(s, 10)); // [10, 20, 30]- したがって、
linesのように書くのが安全かつ可読性が高い。.split(" ").map((s) => parseInt(s, 10))
インデックスのずれ（オフバイワン）に気を付ける
- 問題文では L1,L2,…,LNと書かれているが、TypeScript の配列
L: number[]では 0-index なので、中身が
L[0] = L_1 (問題文),Lとなる。 = L_2, ... L[N-1] = L_N - ループで 1 回目（配列インデックス 0）に跳ねる長さが
L[0]と対応していることを必ず意識しよう。 - 例えば「i=0 のとき
pos += L[i]→ これは問題文の D2=D1+L1 に相当」など、頭の中で対応を合わせるコツも覚えておきたい。
ループを途中で抜ける（break）条件
- この問題では、座標が
Xを超えた瞬間、以降の跳ねはすべてカウントされなくなる。 - だから、「pos が
Xを超えたらbreakしている」 という書き方ができる。 if (pos > X) { break; } else { count++; }
のように書くことで、余計なループを回さずに済むし、何よりロジックが読みやすくなる。- もちろん、あえて最後までループして
if (pos <= X) count++;と書いても合計回数だけは数えられるが、途中で明確に「もう条件を満たさない」ことがわかっていれば、breakを使うのが処理効率的にも読みやすさ的にも優れている。
変数名と型注釈
let count: number = 1;のように、TypeScript の型注釈を積極的に書く と初学者でも安心。- 変数名は、
N: 跳ねる回数で使う入力変数X: 最大座標の閾値L: number[]: 跳ねる長さの配列pos: number: 現在の跳ね位置（累積）count: number: カウント数
のように、意味がわかる名前 がベター（アルファベット 1 文字でも意味を連想しやすいものを優先）。
