【2026年度】電気通信大学「情報」第2問の解説|累積和と2次元いもす法を図で理解

【2026年度】電気通信大学「情報」第2問の解説|累積和と2次元いもす法を図で理解 過去問解説

この記事では、2026年度の電気通信大学・前期「情報」の第2問(40点)を解説します。全体の傾向と答えの一覧は【2026年度】電気通信大学「情報」前期の解答解説にまとめています。

第2問は、花が咲く範囲を数えるプログラムを、発展させていく流れの問題です。問1で単純な方法を作り、問2で「累積和」を準備し、問3で累積和を2次元に使います。問3がこの大問の山場ですが、問1・問2をきちんと理解していれば、ちゃんとたどり着けるように作られています。

設問答え
問1 (1)0, 1, 2, 2, 1, 0
問1 (2)18回
問1 (3)ア ③ イ ⑦ ウ ⑧ エ ⑩ オ ⑪
問2 (1)0, 1, 2, 2, 2, 1, 0, 0
問2 (2)0, 0, 0, 1, 0, 1, 0, −2
問2 (3)カ ⑧ キ ④ ク・ケ ①②(順不同)
問3 (1)0, 1, 0, 0, 0, −1
問3 (2)コ ④ サ −1 シ ② ス −1 セ ⑧ ソ 1
問3 (3)タ・チ ⑦⑨ ツ・テ ⑧⑩ ト・ナ ③⑤ ニ・ヌ ④⑤(各組、順不同)

まずは問題の設定をつかもう

調査地域はマス目に区切られていて、花が咲く範囲(開花域)は長方形です。各マスの「開花数」は、そのマスを含む開花域がいくつあるか、という数です。

開花域は (p, q, r, s) の4つの数で表します。p と q が上端と下端の行、r と s が左端と右端の列です。行が先、列が後に並んでいるので、(x, y) 座標の感覚で読むと間違えます。ここは意識しておきましょう。

図の例では、青とオレンジの開花域が重なる4マスだけが 2 になっています。

問1:単純に「全部のマスに1を足す」

問1の方法(a)は、開花域ごとに、その中のマスを全部 1 ずつ増やすという、いちばん単純なやり方です。

(1) 答え:0, 1, 2, 2, 1, 0

設問で問われているのは行2です。開花域 (2, 4, 1, 3) は行2の列 1〜3 を、(1, 3, 2, 4) は行2の列 2〜4 を含みます。両方に含まれる列 2・3 が 2 になります。

列012345
(2, 4, 1, 3)111
(1, 3, 2, 4)111
開花数012210

(2) 答え:18回

1を足す回数は、開花域のマスの数の合計です。長方形のマスの数は「行数 × 列数」で求められます。

(1, 2, 0, 2) は行 1〜2 の2行と列 0〜2 の3列なので、2 × 3 = 6 マスです。(2, 4, 1, 4) は行 2〜4 の3行と列 1〜4 の4列なので、3 × 4 = 12 マスです。合計で 18 回です。

「1〜2 は 2 − 1 = 1 行」と引き算してしまうミスが多いです。両端を含むので、個数は「大きい方 − 小さい方 + 1」です。

(3) 答え:ア ③ イ ⑦ ウ ⑧ エ ⑩ オ ⑪

プログラムは三重の繰り返しです。一番外側で開花域を一つずつ取り出し、内側の二重ループでその開花域の全マスを回ります。

k を 0 から n - 1 まで(ア)
  i を P[k] から Q[k] まで(イ・ウ)
    j を R[k] から S[k] まで(エ・オ)
      A[i, j] = A[i, j] + 1

アは「開花域は n 個で、番号は 0 から始まる」ので n − 1 です。ここで n を選ぶと、存在しない開花域 n まで数えてしまいます。

イ〜オは、i が行番号、j が列番号であることが分かれば決まります。行の範囲が P[k]〜Q[k]、列の範囲が R[k]〜S[k] です。

問2:累積和を使いこなす

累積和は、先頭からその位置までの合計を並べた列です。実際に計算するときは、「1つ前の累積和に、今の値を足す」を左から順に繰り返せば十分です。

(1) 答え:0, 1, 2, 2, 2, 1, 0, 0

0, 1, 1, 0, 0, −1, −1, 0 を左から足していきます。0 → 0+1=1 → 1+1=2 → 2+0=2 → 2+0=2 → 2−1=1 → 1−1=0 → 0+0=0 です。

(2) 答え:0, 0, 0, 1, 0, 1, 0, −2

今度は逆で、累積和の列から元の列を求めます。累積和は「足したもの」なので、逆に「1つ前との差」をとれば元に戻ります。先頭だけはそのままです。

位置01234567
累積和00011220
1つ前との差0001010−2

答えが出たら、その列の累積和をもう一度計算してみると検算できます。元の累積和に戻れば正解です。この「差を取る」という発想が、問3への伏線になっています。

(3) 答え:カ ⑧ キ ④ ク・ケ ①②

問題文の図4と同じように、配列Bをその場で書き換えていきます。

i を 1 から m - 1 まで(カ・キ)
  B[i] = B[i - 1] + B[i](ク・ケ)

カが 0 ではなく 1 なのがポイントです。先頭 B[0] はそのままでよく、i = 0 で始めると B[−1] という存在しない要素を使ってしまいます。キは、要素数 m で番号が 0 から始まるので、最後が m − 1 です。

B[i] = B[i − 1] + B[i] がうまく動くのは、左から順に書き換えているからです。B[i − 1] は、すでに「そこまでの累積和」に書き換わっています。

問3:四隅に±1を置くだけでよい

問3の方法(b)は、手順2で何かを書き込んだあと、手順3で各列、手順4で各行の累積和を取ります。問題文は「手順4からさかのぼって、手順2で何を書き込めばよいか」を考えさせる流れになっています。競技プログラミングで「いもす法」と呼ばれる、有名な手法です。

まず1次元で考える

いきなり2次元で考えると混乱するので、まずは1列だけで考えます。「2〜4番目だけが1」という列 0, 0, 1, 1, 1, 0, 0, 0 を累積和で作りたいとします。問2(2)と同じように「1つ前との差」を取ると、元の列は 0, 0, +1, 0, 0, −1, 0, 0 になります。

つまり、「始まりに +1、終わりの次に −1」を書いておけば、あとは累積和で範囲全体が 1 になります。範囲が何マスあっても、書き込むのは2か所だけです。

2次元では「四隅」になる

2次元では、この考え方を行の方向と列の方向の2回使います。その結果、書き込む場所は長方形の四隅の4か所になります。図で手順2から手順4までの変化を追ってみましょう。

手順3では、左上の +1 が下に伸び、「左下の1つ下」の −1 で止まります。右側の −1 も同じように下に伸び、+1 で止まります。手順4では、左の +1 が右に伸び、右の −1 で打ち消されます。こうして長方形の中だけが 1 になります。

なお、問題文には「下端の行や右端の列を含む開花域はない」という条件があります。これは、「1つ下」「1つ右」のマスが必ず調査地域の中にあるようにするためです。

(1) 答え:0, 1, 0, 0, 0, −1

行2に書き込まれる値だけを考えます。開花域 (0, 2, 0, 2) の四隅の値は行0と行3に入るので、行2には何も入りません。開花域 (2, 4, 1, 4) は上端が行2なので、左上 (2, 1) に +1、右上の1つ右 (2, 5) に −1 が入ります。

「開花域が行2を含むかどうか」ではなく、「四隅の値が行2に来るかどうか」で考えるのがコツです。

(2) 答え:コ ④ サ −1 シ ② ス −1 セ ⑧ ソ 1

書き込む場所値
上端かつ左端のマス+1
上端かつ右端のマスの、コ 1つ右サ −1
下端かつ左端のマスの、シ 1つ下ス −1
下端かつ右端のマスの、セ 1つ右下ソ +1

右下だけ +1 になる理由は、図の手順3を見ると分かります。右側の列で下に伸びた −1 を、ここで打ち消す必要があるからです。

(3) 答え:タ・チ ⑦⑨ ツ・テ ⑧⑩ ト・ナ ③⑤ ニ・ヌ ④⑤

(2)で求めた4か所を、配列の添字で書きます。

場所添字操作選択肢
左上P[k], R[k]+1⑦
右下の1つ右下Q[k]+1, S[k]+1+1⑨
右上の1つ右P[k], S[k]+1−1⑧
左下の1つ下Q[k]+1, R[k]−1⑩

後半の2つの二重ループは、問2(3)の累積和を列と行に使ったものです。

j を 0 から w - 1 まで
  i を 1 から w - 1 まで
    A[i, j] = A[i - 1, j] + A[i, j](各列を上から:ト・ナ)
i を 0 から w - 1 まで
  j を 1 から w - 1 まで
    A[i, j] = A[i, j - 1] + A[i, j](各行を左から:ニ・ヌ)

列を上から足すときは「1つ上」の A[i − 1, j]、行を左から足すときは「1つ左」の A[i, j − 1] を足します。内側のループが 1 から始まっているのは、問2(3)のカと同じ理由です。

発展:方法(b)はなぜ速いのか

試験では問われていませんが、「なぜわざわざ方法(b)を考えるのか」も知っておくと、この問題の狙いが見えてきます。

方法(a)では、開花域のマスの数だけ足し算をします。大きな開花域がたくさんあると、その分だけ計算が増えます。一方、方法(b)は開花域1つにつき4回書き込むだけです。あとは開花域の数に関係なく、累積和を列と行で全マスに1回ずつ取るだけです。

方法(a)方法(b)
開花域1つあたりその中のマスの数だけ4回
その後の処理なし全マスで累積和を2回
1000行1000列で、全体に近い開花域が1000個約10億回約200万回

問題が大きくなるほど、この差は広がります。「同じ結果を、より少ない計算で求める」というアルゴリズムの考え方は、大学の情報系の授業でも中心になるテーマです。

まとめ

第2問は、問1の二重ループ、問2の累積和、問3の「四隅に±1」と、前の問いが次の問いのヒントになっていました。初めて見る手法でも、小さな表に数字を書いて動かしてみれば、仕組みはちゃんと見えてきます。試験中に迷ったら、まず手を動かして具体例で確かめてみましょう。

次の記事では、第3問のロボットの問題を解説します。

【2026年度】電気通信大学「情報」前期の解答解説 ――試験全体の傾向と答えの一覧

【2026年度】電気通信大学「情報」第1問の解説 ――5つの小問からなる知識問題

【2026年度】電気通信大学「情報」第3問の解説 ――立方体を動くロボット


最新年度の赤本には、直近の過去問と解答・解説がまとめて収録されています。

コメント

タイトルとURLをコピーしました