全国高等学校パソコンコンクール
プログラミング部門 本選問題解説

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

1

問題セット

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

2

問題セット
難易度# タイトル

分野

得点

1 穴あきワッフル

基礎

2

☆

☆

2 サバを読む

基礎

3

★

☆

3 村を整える

整列・シミュレーション

4

★☆

★

4 ロールケーキ

貪欲法

5

★★

★☆

5 ９つの数字組み合わせ（全探索）

6

★★

★★☆

6 PCK君のひそかな楽しみ

数え上げ

6

★★★

★★☆

7 順位の予測シミュレーション

9

★★★

★★★

8 条坊制都市

探索

9

★★★

★★★

9 連環迷路

計算幾何＆グラフ

10

★★★

★★★☆

10 投網

データ構造

10

★★★☆

★★★☆

11 串だんご

数え上げ（動的計画法）

10

★★★☆

★★★

12 星座をさがして

計算幾何・文字列アルゴリズム

13

★★★★

★★★★☆

13 点の削除

探索

13

★★★★☆

★★★★

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

思考

実装

3

問題１ 穴あきワッフル （２点）
正答数:

30チーム

最初の正解:

5分45秒

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説4

問題１ 穴あきワッフル
概要• 穴あきワッフルは、生地が格子状になっている。生地の線が縦に 本、横に 本あるワッフルを、レベル の穴あきワッフルと呼ぶ。
• 線の太さは１ｃｍであり、同方向の線は１ｃｍ間隔で並んでいる。
• 入力として穴あきワッフルのレベルが与えられる。
• ｃｍ× ｃｍの領域を 文字とし、生地には「 」、穴には「 」を使い、レベル の穴あきワッフルを出力する。

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

5

問題１ 穴あきワッフル
解法

解答例（C++）• レベル の穴あきワッフルの線の⾧さは、である。

int N;• 上から 番目、左から 番目の文字は、 と の両方が奇数の場合は’.’（白色）である。それ以外の場合は’#’（黒色）である。

for (int i = 1; i <= M; i++) {cin >> N;
int M = (2*N)+1;
for (int j = 1; j <= M; j++) {if ((i%2 == 1) && (j%2 == 1)) {cout << '.';
} else {cout << '#';}}
cout << endl;}

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説6

問題２ サバを読む （３点）
正答数:

29チーム

最初の正解:

10分31秒

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説7

問題２ サバを読む
概要• 数値

が10進数で与えられる．

• 数値 を10進表記で読み取ったときの値 ＞ 数値 を 進表記で読み取ったときの値であればYes，そうでなければNoを出力．
10進数値を𝑘進数で読み取るときの値

テストケース

30029
8264

11/12/2023

No
Yes

4
2
1
7
6
2
1
*
*
*
*
*
*
*
6
5
4
3
2
1
k
k
k
k
k
k
k0
||
||
||
||
||
||
||
6
5
4
3
2
1
4k +2k + k + 7k + 6k + 2k + k0

パソコン甲子園2023 プログラミング部門 本選問題解説8

問題２ サバを読む
解法• 10進数の値を 進数で読み取るとき、 をいくつにすべきか•であれば、2桁以上のとき読み取る値が大きくなる．
•
であれば、2桁以上のとき読み取る値が小さくなる．
• 1桁の数値は値が変わらない．

の 進数に変換できるか？

•• 10進数の値を示す数字に「9」が含まれていなければ、9進数として読み取ることができる．

読み取った数値が2桁以上で、9が含まれていなければYes.
11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

9

問題２ サバを読む
解答例#include <stdio.h>#include <string.h>
int main(void){char str[10];scanf("%s",str);
printf("%s¥n", (strlen(str)==1 || strchr(str,(int)'9')) ? "No" : "Yes");return 0;
⾧さ
文字にマッチすると}そのアドレスが返るtrue
マッチしなければNULLfalse

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説10

問題３ 村を整える （４点）
正答数:

29チーム

最初の正解:

17分52秒

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説11

問題３ 村を整える
概要•

区画の畑がある． 番目の畑に植えるべき作物の数が与えられる．この数だけ植えると，村が整うと言う．
• すべての畑に適当な数の作物を植えてしまった． 番目の畑に本の作物を植えてしまったので， 本にして村を整えたい．
• 畑の作物の数を変更するときは以下のやり方にしたがわなければならない．
畑 の作物の数を変更したいとする．畑 の作物の数（ 本）よりも作物の数が多い畑 を選ぶ．畑 の作物の数が 本のとき，畑 に本の作物を加えて畑 の作物の数を 本にする．

• このやり方を何度か行って村が整うようにできるならその最小回数を，できないなら を出力する．
11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説12

問題３ 村を整える
上段: 𝑟 ～ 𝑟
下段: 𝑐 ～ 𝑐

解法１（シミュレーション）

上段: 𝑟 ～ 𝑟
昇順に 下段: 𝑐 ～𝑐
ソート

と置く．

//

:

を出力して終了を満たす がある):と:// 解法には不要を出力して終了を出力して終了
11/12/2023

を出力
パソコン甲子園2023 プログラミング部門 本選問題解説13

問題３ 村を整える
解法１の正しさ• -1が出力されるとき、村を整えられないことが言えればよい。
• 以下の条件のいずれかが成り立つと村を整えられないことがわかる．
••

を満たす がある．
を満たす がないような がある．

• 解法1で、ある で
1.
2.

のとき，
と

が出力されるのは、以下のいずれかの場合．
を満たす がないとき．

• は昇順にソート済みで，ので，上の２の場合には からを満たす についてが成り立つにも と等しいものがないことがわかる。

以上より、解法1は正しい。
11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説14

問題３ 村を整える
解答例

計算量

𝟐

void solve(vector<pair<int,int>> a) {int num=0;
sort(a.begin(), a.end());
for (int i = 0; i < N; i++ ) {if (a[i].first < a[i].second){ cout << -1 << endl; return; }if (a[i].first != a[i].second) {int j;for (j=i; j<N; j++)if (a[i].first == a[j].second) break;if (j>=N) { cout << -1 << endl; return; }num++;}}
cout << num;}
11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説// 𝑟 < 𝑐// 𝑟 ≠ 𝑐// 𝑟 = 𝑐15

問題３ 村を整える
解法２（条件のチェック）• 「解法1の正しさ」で述べた条件が成り立つと村を整えられない．
• この条件の否定と同値な条件Aは以下のとおり．
すべての について，• 条件Aが成り立つ．

，かつ，を満たす がある．

以下の条件Bがを満たすすべての について，

で成り立つ．

，かつ，とを満たす がある．

• このとき、解法1のforループの各繰り返しで条件Bが成り立ち，その結果，村が整えられることがわかる．
• 以上より，入力が条件Aを満たすかチェックするだけで，村が整えられるかどうかがわかる。
11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

16

問題３ 村を整える
解答例

計算量: バケットを使うと，setを使うとvoid solve(vector<int> r, vector<int> c) {int num=0;vector<bool> b(1000+1);
for (int i = 0; i < N; i++) { b[c[i]]=true; } // バケットを使う
for (int i = 0; i < N; i++) {if (!b[r[i]] || r[i] < c[i]) { // 𝑟 = 𝑐 を満たす𝑘がないか、𝑟 < 𝑐 なら整えられない
cout << -1 << endl; return;}if (r[i] != c[i]) num++;}cout << num;}

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

17

問題４

ロールケーキ （５点）

正答数:

29チーム

最初の正解:

17分58秒

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説18

問題４ ロールケーキ
概要• 文字o, xを含む文字列•が与えられる．

を下記の条件で文字列を切り分けてピースを作り，ピースの数を最大にする• ピースは2文字以上• それぞれのピースは同じ⾧さ• それぞれのピースに含まれるoの数は同じ

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

19

問題４ ロールケーキ
解法• 2文字のピースを考える• 3文字のピースを作った場合、2文字のピースを作ったときと同じかそれ以下の数になる• 4文字以上のときも同様• oの数が０～２のときについて、それぞれ先頭から条件に合う文字列を切り分ける．

ピースの文字数の考察3文字で切り分けたとき
oが３つ
ooo

oが１or2 つ
oox
oxo
xoo

xxo
xox
oxx

oo
ox または xoを取り出せる を取り出せる

oがなし
xxx

xx
を取り出せる• 先頭から切り出すと最良になることは、帰納法で証明できる（スケジューリング問題）．

• oの数が０～２のそれぞれについて切り
分け、ピースが多いものが答え
11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

2文字で切り分けることが最良
20

問題４ ロールケーキ
解答例#include <stdio.h>#define MAX(a, b) ((a) > (b) ? (a) : (b))
int main(void) {char in[100001];
int sum_oo=0, sum_xx=0, sum_ox=0, i;
scanf("%s",in);for(i=0; in[i]!='¥0'; ++i)if(in[i]=='x' && in[i+1]=='x') {++sum_oo; ++i;}
for(i=0; in[i]!='¥0'; ++i)if(in[i]=='o' && in[i+1]=='o') {++sum_xx; ++i;}
for(i=0; in[i]!='¥0' ; ++i)if(in[i]=='o' && in[i+1]=='x'|| in[i]=='x' && in[i+1]=='o') {++sum_ox; ++i;}
printf("%d¥n",MAX(MAX(sum_oo,sum_xx),sum_ox));return 0;}
11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

21

問題４ ロールケーキ
解答例
int fsm_oo[3][2]={{1,0},{2,0},{1,0}};
int fsm_xx[3][2]={{0,1},{0,2},{0,1}};
int fsm_ox[4][2]={{1,2},{1,3},{3,2},{1,2}};
int st_oo=0, st_xx=0, st_ox=0;
int cn_oo=0, cn_xx=0, cn_ox=0;char c; int in;oo, xx, ox/xo を受理する有限オートマトンを作る
o
o
x
x
o
x
o
o
x

o
x

ooを受理
11/12/2023

o

x
o

xxを受理

x

x
o
x

o
x
oxとxoを受理

while(1){scanf("%c",&c);if(c=='¥n') break;in = c=='o' ? 1 : 0;
st_oo=fsm_oo[st_oo][in];st_xx=fsm_xx[st_xx][in];st_ox=fsm_ox[st_ox][in];if(st_oo==2) ++cn_oo;
if(st_xx==2) ++cn_xx;
if(st_ox==3) ++cn_ox;}
printf("%d¥n",MAX(MAX(cn_oo,cn_xx),
cn_ox));

パソコン甲子園2023 プログラミング部門 本選問題解説22

問題５ ９つの数字（６点）
正答数:

19チーム

最初の正解:

36分34秒

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説23

問題５ ９つの数字
概要• 家の入口に特殊な電子錠がついている。
• この電子錠には１から９までの数字が、右の図のように縦３行、横３列に配置されている。数字は操作開始前に自由に並び替えることができる。
• この電子錠には数字を指し示すカーソルが１つあり、カーソルは常にどれか１つの数字を指し示している。入力開始時には、カーソルが右下の数字を指している。
• 電子錠を開錠するための暗証番号として、１から９までの数字からなる数字列が設定されている。以下の操作で、暗証番号を左から順番に入力していくことで解錠することができる：• 隣接する上下左右のどれかの数字へカーソルを移動する。
（１回の操作）• カーソルが指し示す数字を入力する。
（１回の操作）• 暗証番号を表す整数
必要な操作回数の最小値を求めよ。

11/12/2023が与えられたとき、暗証番号を入力するためにパソコン甲子園2023 プログラミング部門 本選問題解説24

問題５ ９つの数字
解法• 電子錠において、に配置した数字からに配置した数字へのカーソル移動に要する操作回数は、数字間のマンハッタン距離。
• 例えば、右図の配置方法において、た への移動に要する操作回数は、に配置された からに配置され• ９つの数字の配置方法は全部で通りあり、最小の操作回数を求めるためには、全ての配置方法について操作回数を調べる必要がある。
• 暗証番号は最大で桁なので、左から順番に数字間の距離を足していく素朴な解法では、全ての配置方法について調べると時間制限

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説25

問題５ ９つの数字
解法• 全探索する前に、与えられた暗証番号を表す数字の列について、数字 から数字(へ移動する回数を二次元配列に記録しておく。
• 例えば、暗証番号が74174747の場合、c[1][7]=1, c[4][1]=1,
c[4][7]=2, c[7][4]=3と記録。
• これら4つ以外の回数は0• その回数に数字間のマンハッタン距離を掛けた積を全ての数字の組み合わせについて計算し、操作回数に加算する。
• カーソルを右下から最初の数字へ移動するための操作回数を別に加算する。
• 暗証番号の桁数分だけ数字の入力操作が必要。
• 数字の種類を11/12/2023、暗証番号の桁数を で表すと、計算量はパソコン甲子園2023 プログラミング部門 本選問題解説26

問題５ ９つの数字
解答例（C++）

string N; cin >> N;
vector<pair<int,int>> p;vector<vector<int>> c(9+1, vector<int>(9+1, 0));for (size_t i = 0; i < N.length()-1; i++)c[N[i]-'0'][N[i+1]-'0']++;for (int i = 0; i < 3; i++)for (int j = 0; j < 3; j++)p.push_back(make_pair(i, j));int ans = 99999999;
do {int ops = N.length();ops += dist(p[N[0]-‘0’-1],
make_pair(3-1, 3-1));
for (int i = 1; i <= 9; i++)for (int j = 1; j <= 9; j++)ops += c[i][j] * dist(p[i-1], p[j-1]);
ans = min(ans, ops);} while (next_permutation(p.begin(), p.end()));
11/12/2023

int dist(pair<int,int> a,pair<int,int> b) {return abs(a.first-b.first)+ abs(a.second-b.second);}

パソコン甲子園2023 プログラミング部門 本選問題解説27

問題６ PCK君のひそかな楽しみ（６点）
正答数:

12チーム

最初の正解:

33分39秒

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説28

問題６ PCK君のひそかな楽しみ
概要• ⾧さが与えられる．

の文字列 とPCK君のラッキーナンバー• の中に現れる，以下の条件を満たす部分文字列の個数を求める．
• P,C,Kがこの順番に 個以上現れる（ただし、P,C,Kは連続していなくても良い）。

テストケース

PCCKA

11/12/2023

PCCKA
PCCKA

パソコン甲子園2023 プログラミング部門 本選問題解説29

問題６ PCK君のひそかな楽しみ
解法（尺取り法）𝑆• 求める部分文字列の個数を𝑆[𝑙 … 𝑟]とする．

• 文字列 の からまでの範囲の文字列
PCKの個数を調べる（
）．
•

𝑟

𝑙

の中の

の中のP,C,K,PC,PCK,CKの個数を変数 , , ,にそれぞれ保存する。

,,• 部分文字列の中のPCKが 個未満なら，部分文字
列の右端を伸ばす（ を増やす）．右端に追加された
文字 に応じて、右の表のように変数を更新する．

𝑥

𝒑

P

+1

C

𝒄

𝒌

𝒑𝒄 𝒑𝒄𝒌 𝒄𝒌

+1

K

+𝑝
+1

+𝑝𝑐 +𝑐

追加された𝑥がCのとき

LPKQPACPH C
𝑙
11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

𝑟30

問題６ PCK君のひそかな楽しみ
解法（続き）

𝑆

𝑆[𝑙 … 𝑟]• 部分文字列の中のPCKが 個以上になったら，にを加え、部分文字列の左端を縮める（ を増やす）．左端から削除された文字 に応じて、右の表のように変数を更新する．

𝒚

𝒑

P

−1

• 左端を削除してもの中のPCKが 個以上なら，にを加え，再び左端を縮める。

K• 左端を削除したとき
たら，右端を伸ばす。

𝑟𝑙の中のPCKが 個未満になっ

C

𝒄

𝒌

𝒑𝒄 𝒑𝒄𝒌 𝒄𝒌−𝑐 −𝑐𝑘−1−𝑘−1

削除されたyがCのとき

C LCKQKACKH
𝑙
11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説𝑟31

問題６ PCK君のひそかな楽しみ
解答例

計算量:

void solve(string S) {long long int num, p, c, k, pc, pck, ck; num = p = c = k = pc = pck = ck = 0;
for (int l = 0, r = 0; l < N; l++) {while (r < N && pck < L) {if (S[r] == ‘P’) { p += 1; }if (S[r] == ‘C’) { c += 1; pc += p; }if (S[r] == ‘K’) { k += 1; ck += c; pck += pc; }r++;}if (pck >= L) { num += N – r + 1; }if (S[l] == ‘P’) { p -= 1; pc -= c; pck -= ck; }if (S[l] == ‘C’) { c -= 1; ck -= k; }if (S[l] == ‘K’) { k -= 1; }}cout << num;
パソコン甲子園2023 プログラミング部門 本選問題解説
11/12/202332}

問題７順位の予測（９点）
正答数:

2チーム

最初の正解:

2時間49分53秒

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説33

問題７ 順位の予測
概要•

チームが参加し、 問出題されるプログラミングコンテストの順位を予測せよ。参加チームは以下の基準で順位付けされる：• 正答した問題の得点の合計が大きい方が良い成績となる• 得点の合計が等しい場合は、その得点の合計に到達した時刻が早い方が良い成績となる• このコンテストでは、特殊なスコアボードを採用しており、以下の情報が開示される。
• 問題 の得点は である• 問題 に正答したチームの数は である• 問題 を 番目に正答したチームは , である• コンテスト終了時点でのスコアボードの情報から、各チームについて、取りうる順位の最小値と最大値を求めよ。

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説34

問題７ 順位の予測
制約•••• 各チームがいずれかの問題を正答した時刻は全て異なる

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説35

問題７ 順位の予測
解法

Rank

Score

1

100

2

90

2

90

2

90

• 前者は変えようがないため、後者を最小化or最大化することを考える。

5

85

6

80

• まず、スコアの順にチームに仮のランクを付与する。
このとき、スコアが唯一のチームとスコアが０である
チームの順位が確定する。

6

80

8

0

8

0

8

0

• チーム の総得点をとする。

• チーム の順位は「を満たすチーム のチーム数」+「
を満たすチーム のうち、チーム よりも早く全ての問題を解いたチーム数」 。

•

11/12/2023

が等しいチームのグループでランクを更新する。

確定

確定

パソコン甲子園2023 プログラミング部門 本選問題解説36

問題７ 順位の予測
最小値（最も良い順位）• チーム が解ける全ての問題を解いた時点でに達していないチームの数を最大化すればよい。
• チーム が解いていない問題を解いたチームと、チーム が解いていた問題でチームよりも遅く解いたチームの和集合のサイズとなる（これを
とする）。
チーム数
には勝てる

に注目

には勝てない11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説37

問題７ 順位の予測
最大値（最も悪い順位）• チーム が解けるすべての問題を解き切る前にできるだけ多くの参加者が解き切る
ケースを考える。
• チーム が 番目の問題を 番目に解いたとき、
とする ）

「(

)の最小値」（これを

チーム数
に注目

後ろに３チーム
後ろに１チーム
チーム𝑖が解いた問題について、後ろに何人いるか？の最小値

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説38

問題７ 順位の予測
実装の方針• スコアが同じチームグループごとに、各チームの最小・最大の順位を決定• 以下のデータを作る• グループに含まれるチームが解いた問題セット• 問題セットの各問題について、グループに含まれるチームが解いた順番（関係のないチームを排除）• グループ内の各チーム について、順位を決定していく

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説39

問題７ 順位の予測
計算量
• O(

11/12/2023)

パソコン甲子園2023 プログラミング部門 本選問題解説40

問題８ 条坊制都市（９点）
正答数:

7チーム

最初の正解:

1時間5分47秒

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

41

問題８ 条坊制都市
概要
●
●
●
●

11/12/2023

行 列の行列 が与えられる。行列の各要素は非負の整数であるから 行目、 列目を抜き出した行列を考える。この行列に出現しない最小の非負整数(Minimum EXcluded value =)を出力する、についてこれを行う

パソコン甲子園2023 プログラミング部門 本選問題解説42

問題８ 条坊制都市
テストケース
1行目1列目を消すと2が残る -> 0
1行目2列目を消すと1が残る -> 0
2行目1列目を消すと1が残る -> 0
2行目2列目を消すと0が残る -> 1

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説43

問題８ 条坊制都市考察「 の」 「1行・1列消した後の」が成り立つ● 明らかに増えることはないが元々のより小さくなる？
● どのような時に消した後の11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

44

問題８ 条坊制都市考察
例えば左の行列だと、 のは33行目3列目を消すと2が全部消えてが2になる

1行目2列目を消すと0が全部消えて

が0になる

の
未満の値 に対して、 から を全て消すような消し方が存在する⇒
そのような消し方をした時のは 以下になる

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説45

問題８ 条坊制都市
解法
観察から、各値 について「 を全部消すような消し方は存在するか？存在するならどのような消し方か？」を考えることにする。
行・列の消し方は通りあり、考慮すべき はO()個あるので、すべての消し方を愚直に調べようとするとΩ()かかってしまう。(時間制限に間に合わせることは困難)
実は、ほとんどの消し方は考慮しなくて良い

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説46

問題８ 条坊制都市
解法の未満の数について、それぞれどの
座標に存在するかをあらかじめ並べておく
0・・・ (1, 1) (2, 2)
1・・・(1, 2) (2, 1)
2・・・ (1, 3) (2, 3) (3, 1) (3, 3)

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説47

問題８ 条坊制都市
解法
0・・・ (1, 1) (2, 2)
1・・・(1, 2) (2, 1)
2・・・ (1, 3) (2, 3) (3, 1) (3, 3)「並べた座標のうち１つ目の座標が消えない消し方においてが存在するすべての座標を消すことはできない」が成り立つ(１
つ目の座標が消えていないため)
１つ目の座標を消すような消し方は11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

通りしか無い48

問題８ 条坊制都市
解法
0・・・ (1, 1) (2, 2)
1・・・(1, 2) (2, 1)
2・・・ (1, 3) (2, 3) (3, 1) (3, 3)
例えば2なら、
1行目を消して列は自由に選んで消す or
3列目を消して行は自由に選んで消す とすると、またこのような消し方に限り、１つ目の座標(1, 3)が消える。これ以外の消し方は考慮しなくて良い

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説49

問題８ 条坊制都市
解法

消し方を個まで絞ることができた。
さらに消し方の候補を絞ることができる。
(1, 3) (2, 3) (3, 1) (3, 3)(1行目を消した時)(1, 3) (2, 3) (3, 1) (3, 3)(3列目を消した時)

実際に行(列)を消してみて、残ったうち一つ目の座標の列(行)を消すような方法が候補となる⇒その消し方ですべて消えるか確かめれば良い
考えるべき消し方は各要素につき高々2通り

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説50

問題８ 条坊制都市
解法• 考慮すべき座標は個• それぞれの値で消し方を高々2回試す
 それぞれの座標は高々2回しか消えない• うまく実装をするとでこの問題を解ける

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説51

問題８ 条坊制都市
解法
実装上の注意が小さい場合1. 元々の•元々のより大きい値の座標を全て除去しても、解はその値では無く、元々の以下2. ある行(列)を消すだけで、ある値の座標を全て除去できる場合•
その行(列)を消すと、列(行)の消し方に関わらずが値以下になる3. 同じ消し方で複数の値の座標が全て除去できる場合•
消せる値の中で最小のみを考慮する

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説52

問題８ 条坊制都市
実装の方針
以下の値を計算する• 行目を削除することで、を• 列目を削除することで、を• 行目 列目を削除することで、以下にできる。
以下にできる。
を以下にできる。

•

が 行 列目を削除したときの11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説53

問題９ 連環迷路 （１０点）
正答数:

2チーム

最初の正解:

2時間39分42秒

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

54

問題９ 連環迷路
概要• 座標平面上に円が個与えられる．

• 各円の中心の 座標と 座標
は整数．

と半径

• スタート地点(原点)を通る円が1つ以上ある.
• 現在たどっている円 と別の円 が共有点を持てば、円 の周上でその共有点まで移動することで円 の周上に移ることができる.
• どの円の周上にも、スタート地点から到達できる.
• 連環迷路のゴール地点は、 個の円の周上のうち、スタート地点からの周上に沿った最短の移動距離が最も大きい点である.
11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説55

問題９ 連環迷路

交点

解法• 交点を列挙する
スタート地点• スタート地点と、すべての交点を節点とした、グラフに変換する

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説56

問題９ 連環迷路
解法• ダイクストラ法などで、スタート地点からすべての節点への最短距離を求める.
• ゴール地点候補は、各円内で隣り合う節点の間にある点のどこか.

𝐶𝐵

ある円周上で隣り合う点𝐴と点𝐵について、以下がわかっている スタート地点から点𝐴までの最短距離𝐷
 スタート地点から点𝐵までの最短距離𝐷
 円周上に沿った点𝐴と点𝐵の間の距離𝐷
点𝐴と点𝐵の間にあるスタート地点から最も遠い点までの距離𝐿は、(𝐷 + 𝐷 +𝐷 )で求まる.

𝐴
点𝐵と点𝐶の間、点𝐶と点𝐴の間についても、同様に計算する.
すべての円について同様に計算し、最も大きい値が答え.
11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説57

問題９ 連環迷路
解法• 計算量• 交点列挙• グラフへ変換• ダイクストラ• ゴール地点列挙

ゴール地点

★

• コーナーケースにも注意する.

円が一つだけの場合スタート地点
11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説58

問題１０ 投網（１０点）
正答数:

3チーム

最初の正解:

1時間58分38秒

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説59

問題１０ 投網概要•

群の魚群が座標平面上にいる• 番目の魚群は座標に存在して、 匹の魚で構成されている• 直線に対角線がかかるかつ、全ての角が格子点に一致するように正方形の網を投げる• (網の周上or内部にいる魚の数 網の周の⾧さ)の値
は最大でいくつになるか？

•••

1 ≤ 𝑁 ≤ 200,000
0 ≤ 𝑥 , 𝑦 ≤ 200,000
1 ≤ 𝑓 ≤ 1,000,000,000

11/12/2023

A
B
C
O

パソコン甲子園2023 プログラミング部門 本選問題解説60

問題１０ 投網
テストケース(3, 3)を左下角、(5, 5)を右上角となるように網を投げると、10 - 8 = 2が利益となる。
利益を3以上にする網の投げ方は存在しない

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説61

問題１０ 投網解法
• 簡単のため、直線の下側にある点についてはについて対称な点へと移して考える。
• 投網の領域
は区間
で表すも
のとする。
 点
に存在する魚が捕まえられるための条件は、区間が 区間に包含されていることと言い換えることができる。
• この変換により、この問題は直線上の区間のクエリに言い換えられる。

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説62

問題１０ 投網解法••

投網 [𝑎, 𝑏] のうち、 𝑏 を昇順に固定して全探索する。
「𝑏 を固定したときの、各 𝑎 を選択したとしたときに得られる(漁獲高− 網のコスト)」の列を管理する。このとき、以下の 3 つのクエリを処
理する。
1.

2.
3.

11/12/2023

区間 𝑥 , 𝑦 が 𝑏 = 𝑦 を満たすような任意の 𝑖 について 0, 𝑥 に𝑝 を加算
 𝑏 が大きくなったことによって、うまい 𝑎 を選択すると地点 𝑖の魚を得ることができるようになった
区間 [0, 𝑏) に −4 を加算する
 𝑏 が (直前と比較して) 1 増えているため、網の枠のコストはそれぞれ 4 増やす操作をしている。
[0, 𝑏) の max を得る
 1, 2 によって 𝑏 を固定したときの各 𝑎 に対する (漁獲高 − 網のコスト)を計算しているため、その最大値が解の候補となる。
パソコン甲子園2023 プログラミング部門 本選問題解説

𝑎 の候補

63

問題１０ 投網解法
• 区間加算と区間最大値を求めるデータ構造⇒ 遅延伝搬付きセグメント木(Lazy Propagation Segment Tree)• 解が -4 となり得ることに注意する。

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説64

問題１１ 串団子（１０点）
正答数:

6チーム

最初の正解:

25分51秒

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説65

問題１１ 串団子
概要
•
•
•
•

数列 が与えられるから 個の要素を選び、自由に並び替えたものを とするありうる 全てについて、「最大要素の添字の和」の和を求める
結果をで割ったあまりを出力する

制約
•
•
•

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説66

問題１１ 串団子
テストケース、としてあり得る列はの4通り・・・最大値は1で、1である添字は1と2 -> 1 + 2 = 3・・・最大値は2で、2である添字は2 -> 2
・・・最大値は2で、2である添字は1 -> 1
・・・最大値は2で、2である添字は1と2 -> 1 + 2 = 3
合計は3 + 2 + 1 + 3 = 9

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説67

問題１１ 串団子
解法（概要）• 「 の最大要素」、「 の最大要素以外の値の列」を固定した時の寄与を考える• 状態をうまくまとめて、動的計画法を適用する• 組み合わせ計算が必要になるので、パスカルの三角形等を利用して前計算しておく

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説68

問題１１ 串団子
解法（詳細）
の最大要素
の残り
•
• この

の個数 を固定する（場合の数を求める）
要素は、必ず
より真に小さい値である必要がある要素の内訳とその並べ方を固定した時の寄与を求める

固定した

要素の列に

•
•
•

11/12/2023、

1を 個まとめて挿入してできる列の32の添字の和を求めたい3
5

パソコン甲子園2023 プログラミング部門 本選問題解説

5

5

69

問題１１ 串団子
解法（詳細）

1

3

2

3
5

番目に
•

5

5

が挿入されるような挿入の仕方の数は？

番目に 1個を挿入して、残りの個は項の中から自由に割り当てて良い• ⇒11/12/2023

通り
パソコン甲子園2023 プログラミング部門 本選問題解説70

問題１１ 串団子
解法（詳細）

1

3

2

3
5

5

5

について同じように考えれば良い

総和
11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説71

問題１１ 串団子
解法（詳細）

1

3

2

3
5

•

5

5

以外の
要素の内訳とその並べ方の数が分かれば「最大要素」と「最大要素の個数」を固定した時の寄与がわかる。

• 動的計画法を用いてこれを求める

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説72

問題１１ 串団子
解法（詳細）
小さい方から 種類目までの値を利用して、⾧さ の数列を作る通り数とする。
が既知の状態で、11/12/2023

番目に小さい値を 個挿入するとパソコン甲子園2023 プログラミング部門 本選問題解説73

問題１１ 串団子
解法（詳細）
個の箱が一列に並んでいる。 個の箱を選んで新しい要素を入れる。残り 個には元々決まっていた列を「順番を変更せず」入れる
元々決まっていた列の数はnew

11/12/2023

通りなので、

new

パソコン甲子園2023 プログラミング部門 本選問題解説

new

74

問題１１ 串団子
解法（詳細）•
が自明であり、ここから遷移を進めていく。
• このDPテーブルはで埋めることができる。
• 次に、「最大要素について小さい方から 種類目の値」と「最大要素の個数について 個」
について解を求め、総和を計算する。

• この計算は、各値の頻出数を考えると、11/12/2023

で計算できる。

パソコン甲子園2023 プログラミング部門 本選問題解説75

問題１２ 星座を探して （１３点）
正答数:

0チーム

最初の正解:-

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説76

問題１２ 星座を探して
概要
• 星座が

個与えられる.

• 各星座は点で構成されている．

個の座標平面上の点• 以下の操作を、任意の回数組み合わせて行うことで一致させることができる
星座は、同じ種類の星座と考える.
• 平行移動• 原点を中心とした回転• 原点を中心として、正の係数を倍率とした拡大・縮小• それぞれの星座について、同じ種類の星座がいくつあり、何番目の星座が同じ種類の星座かを求める.
11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説77

問題１２ 星座を探して
解法• 各星座の座標を 倍して重心を求め、原点へ平行移動する.
• 各星座内で、星座を構成する点を偏角でソートしておく.
• 偏角順で見たときに、次の点との間でなす角を求めた列 を作る.

• 各星座内で、星座を構成する点の原点からの距離の2乗を求めておく.
• 全ての点について、距離の2乗を最大公約数で割り算した列 を作る.

•と の要素をペアにして配置した列• このとき の要素は大きな数(

11/12/2023

を作る.

など)を掛けて、整数に切り上げる.

パソコン甲子園2023 プログラミング部門 本選問題解説78

問題１２ 星座を探して解法• 比較演算子をのように定義する(C++などの標準的なペアの比較演算子).
•の要素をシフトして回転したときに、辞書順最小になるように並べ替える.
• 列 をローリングハッシュでハッシュ値に変換する.
• 星座同士のハッシュ値が一致すれば、それらの星座は同一であるとみなす.

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説79

問題１２ 星座を探して解法• 計算量• 各星座の偏角ソート• 各星座の距離の最小公倍数• 列 の辞書順回転 (BoothのLexicographically Minimal String Rotation algorithm)• ハッシュ値への変換• 以上を 回行う
• ハッシュ値の比較

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説80

問題１２ 星座を探して
入力データ
01_small_01.in
同じ
星座

同じ
星座

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

違う星座
(鏡像)

81

問題１２ 星座を探して
10_beautiful_01.in

11/12/2023

10_beautiful_02.in

パソコン甲子園2023 プログラミング部門 本選問題解説82

問題１２ 星座を探して
10_beautiful_03.in

11/12/2023

10_beautiful_04.in

パソコン甲子園2023 プログラミング部門 本選問題解説83

問題１２ 星座を探して

10_beautiful_05.in

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説84

問題１３ 点の削除
正答数:

1チーム

最初の正解:

3時間30分16秒

11/12/2023（１３点）

パソコン甲子園2023 プログラミング部門 本選問題解説85

問題１３ 点の削除
概要●

座標平面上の 個の点が与えられる●点を 個削除した時の頂点間距離の二乗の最小値を最大化する

●
●

86

問題１３ 点の削除
考察
● 各点をグラフの頂点、二点間の距離を辺重みとしたグラフとして考える

87

問題１３ 点の削除
考察
● ある頂点を削除すると、その頂点を端点とする辺を削除することができる

88

問題１３ 点の削除
解法
● 課題: 辺重みの最小値の最大化● 全ての辺を重みで昇順ソートした後、二分探索する-

判定問題● 重みの小さい方から 個の辺のみを含むグラフに対して、頂点を最大 回削除することによって、全ての辺を削除できるか？

● (大きさが 以下の頂点被覆は存在するか？)● 以下、この判定問題の解法を考える

89

問題１３ 点の削除
𝑲 𝟏 解法(TLE)-

各頂点に対して愚直に削除するか削除しないかを割り当てる-

この解法を高速化する
bool dfs(int i, int k) {if (k < 0) return false;
if (i == n) {return is_vertex_cover();}
status[i] = DELETE;
if (dfs(i + 1, k - 1)) return true;
status[i] = KEEP;
if (dfs(i + 1, k)) return true;
return false;}90問題１３ 点の削除
考察●

ある頂点を削除する場合
 その頂点のみを削除する●

ある頂点を削除しない場合
 隣接する全ての頂点を削除する必要がある

91問題１３ 点の削除
考察
● 次数が 以下の頂点は削除する必要はない-

次数が の場合● 隣接する頂点を削除することによって損しない

92

問題１３ 点の削除
解法

● 各頂点を順番に見ていき、削除する・しないを決めていく-

次数が 以下 -> 削除しない-

次数が 以上 -> 削除する、または削除しない● 次数が 以上の場合のみ分岐する● この場合分けによって計算量が改善する

93

問題１３ 点の削除
考察
● 分岐するときの残り削除回数 の減少量に注目する-

削除する場合-減少する

削除しない場合
 少なくとも 減少する
 (次数が 以上かつ隣接する頂点を全て削除する必要があるため)● 分岐する度に が または 以上減少する

94問題１３ 点の削除
分岐の様子(

11/12/2023)

パソコン甲子園2023 プログラミング部門 本選問題解説95

問題１３ 点の削除
考察
フィボナッチ数列-

全体の分岐回数は高々判定問題を回で解くことができる

96

問題１３ 点の削除
計算量

● 頂点間距離のソート:● 判定問題一回あたり:
● 全体:

97

11/12/2023

パソコン甲子園2023 プログラミング部門 本選問題解説

98