iroirohasu
@iroirohasu (iro hasu)

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

競技プログラミングの問題理解について

はじめてQiitaを使うため、何かおかしな点やわかりづらい点があったらすみません。
・質問
https://atcoder.jp/contests/aising2019/tasks/aising2019_a
この問題の答えは(n-h+1)*(n-w+1)となるそうです。自分なりに考えたのですが、なぜこの式になるのか理解できません。
なぜこの式になるか教えていただきたいです。

......
・問題文
A 社主催のプログラミングコンテストの開催が決定したので、その告知を会社の掲示板に張り出すことにしました。

掲示板は N 行 N 列のマス目の形をしています。 また、告知は H 行 W 列ぶんの場所を取ります。

告知をちょうど HW 個のマスを完全に覆うように掲示板に張り出すとき、張り出す場所の選び方は何通りありますか。

・制約
1≤H,W≤N≤100
入力値はすべて整数である。
.....

0

1Answer

二次元で考える前に1次元で考えてみましょう

例えば、全体の長さが10, 広告の長さが5. であるとします。

このとき、広告の置き方としては

[1,2,3,4,5], [2,3,4,5,6], [3,4,5,6,7],...,[6,7,8,9,10]

の5つありますよね?

全体の長さが7だと

[1,2,3,4,5],[2,3,4,5,6],[3,4,5,6,7]
の3通りです。

これを一般化すると

全体の長さ-広告の長さ+1と表せますよね。

そしてこれが横と縦の両方で起こるわけです。

なのでそれをかけて答えとなります

1Like

Comments

  1. ごめんなさい、
    [1,2,3,4,5], [2,3,4,5,6], [3,4,5,6,7],...,[6,7,8,9,10]

    の5つありますよね?
    は嘘です。6つです。
  2. @iroirohasu

    Questioner

    わかりやすい説明ありがとうございます!!
    おっしゃる通り1次元で考えてみると理解できました。
    ありがとうございました!!

Your answer might help someone💌