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

11/06/2022

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

1

問題セット

11/06/2022

1 卓球

7 素数日の並び

2 ベコレンジャーカード

8 ゲームブック

3 直方体ボート

9 縄張りの大きさ

4 演算ユニットの接続

10 数列の復元

5 どろだんご

11 N数列6 一筆書き12 三角形パズル
パソコン甲子園2022 プログラミング部門 本選問題解説

2

問題セット
難易度

正解数
（凍結前）

# タイトル

分野

得点

1 卓球

基礎

2

☆

☆

34

2 ベコレンジャーカード

基礎

3

★

☆

32

3 直方体ボート

探索

4

★

★

33

4 演算ユニットの接続

組み合わせ（貪欲法）

6

★☆

★★

25

5 どろだんご組み合わせ（全探索）

7

★★

★★

19

6 一筆書きグラフとデータ構造

9

★★☆

★★★

16

7 素数の日の並び

シミュレーション

10

★★

★★★★

1

8 ゲームブック組み合わせ（動的計画法）

11

★★★☆

★★

10

9 縄張りの大きさ

文字列検索

11

★★★☆

★★★

6

10 数列の復元

組み合わせ（数学）

11

★★★★

★★☆

14

11 N数列

データ構造

12

★★★★

★★★★

4

12 三角形パズル

計算幾何学

14

★★★★☆

★★★★☆

2

11/06/2022

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

実装

3

問題１ 卓球

（２点）

正答数:

34チーム

最初の正解:

松本秀峰中等教育学校
P22 逆転コードマン
1分57秒 (13:16:57)

11/06/2022

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

4

問題１

卓球

概要
• 卓球の試合では，両者の点数の和が６の倍数になっているときだけ，試合中にタオルを使ってよい．
• 与えられた２つの整数𝑝と𝑞について， 𝑝 + 𝑞が６の倍数であるかを判定せよ．

11/06/2022

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

5

問題１

卓球

解法
• 与えられた２つの整数𝑝と𝑞について，𝑝 + 𝑞が６で割り切れるかを判定する．
解答例１
int main(){int p, q;
cin >> p >> q;cout << (((p+q)%6==0)? 1 : 0 ) << endl;
return 0;}

11/06/2022

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

問題２ ベコレンジャーカード （３点）
正答数:

32チーム

最初の正解:

静岡県立浜松工業高等学校
P26 味のしない輪ゴム
7分49秒 (13:22:49)

11/06/2022

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

7

問題２

ベコレンジャーカード

概要• ４枚のカードに書かれたキャラクターを表す整数 𝑐𝑖 (1 ≤ 𝑐𝑖 ≤ 4) が与えられる．
• このうち１枚のカードを紛失した．どのカードを紛失したかは分からない．
• 残ったカードで同じキャラクターのペア１組を作れるか判定せよ．
1. どのカードを紛失しても必ずペアが作れる場合
2. ペアが作れる可能性がない場合
3. ペアを作れる可能性はあるが必ずではない場合

11/06/2022

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

8

問題２

ベコレンジャーカード

解法• 与えられた４枚のカードの状態について，場合分けを行う
1. どのカードを紛失しても必ずペアが作れる場合• 同じキャラクターが３つ以上含まれる[1, 1, 1, 4], [4, 4, 4, 4], etc.
• 同じキャラクターのペアが２つ含まれる[1, 1, 2, 2], etc.
2. ペアが作れる可能性がない場合• 全てのキャラクターが異なる[1, 2, 3, 4], etc.
3. ペアを作れる可能性はあるが必ずではない場合• 上記の場合以外[1, 1, 2, 3], etc.

11/06/2022

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

9

問題２

ベコレンジャーカード

解答例１
sort(c, c+4); // キャラクターを昇順に並べておく
if ( c[0] == c[1] && c[1] == c[2] ||// [a, a, a, *]c[1] == c[2] && c[2] == c[3] ||// [*, a, a, a]c[0] == c[1] && c[2] == c[3] ) {// [a, a, b, b]
cout << 1 << endl;} else if ( c[0] != c[1] && c[1] != c[2] && c[2] != c[3] ){ // [a, b, c, d]cout << 2 << endl;} else {cout << 3 << endl;}

11/06/2022

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

10

問題２

ベコレンジャーカード

解答例２:カードの枚数を数える// カードのカウンタ，枚数と答えの対応
vector<int> n(N,0),res={-1,2,3,1,1};

最大の
枚数

カードの
枚数（整列）

1

1, 1, 1, 1

答えは2

2

2, 1, 1 or
2, 2

2番目に大きい枚数を見て答える．
2番目に大きい枚数が2な
らば、最大の枚数は必ず2 ．この時の答えは1，それ以外の時は答えは3．

3

3, 1

答えは1

4

4

答えは1

11/06/2022

int main(){
int i,c;for(i=0;i<N;++i) {cin>>c; n[c-1]++;}
sort(n.begin(),n.end());
cout << res[n[2]==2?3:n[3]] << endl;
return 0;}

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

問題３ 直方体ボート（４点）
正答数:

33チーム

最初の正解:

愛光高等学校P34 <br>

7分44秒 (13:22:44)

11/06/2022

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

12

問題３

直方体ボート概要• 幅が長さの３分の１，高さが幅の２分の１である，
幅
重さ50キログラムのボートを作る．
• このボートに積み荷を載せて水に浮かべる．
ボート• 積み荷を載せたボートが水に浮くのは，ボートと乾舷
積み荷の重さの合計と，ボートによって押しのけ 高さられた水の重さがちょうど釣り合うとき
水3（1,000cm の水の重さは1キログラム）．
• ボートの上面から水面までの距離（乾舷）を30 cm以上にしたい．
• ボートに載せる積み荷の重さ𝑊(1 ≤ 𝑊 ≤ 1,000)が与えられたとき，ボートの長さ，幅，高さがそれぞれ最小何cm（整数値）になるか求めよ．
11/06/2022

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

13

問題３

直方体ボート解法• 高さ𝑥 ，幅2𝑥 ，長さ6𝑥のボートを作る．
• 𝑥 − 30 2𝑥 6𝑥 ≥ 1000 𝑊 + 50 となる最初の𝑥を求める．
• 1 ≤ 𝑊 ≤ 1,000より線形探索を応用できる．

11/06/2022

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

14

問題３

直方体ボート

解答例
int solve(int W){
for (int x = 31; ; x++ ){if ( 12*x*x*x - 360*x*x >= 1000*(W + 50) ) return x;}}
int main(){int W;
cin >> W;
int x = solve(W);cout << 6*x << " " << 2*x << " " << x << endl;
return 0;}
11/06/2022

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

15

問題４ 演算装置の接続（６点）
正答数:

25チーム

最初の正解:

弓削商船高等専門学校
P07 ぬるぽ
8分22秒 (13:23:22)

11/06/2022

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

16

問題４

演算装置の接続概要• 接続ポートの数がそれぞれ𝑎𝑖 である𝑁個の演算装置を以下のように接続することはできるか？
✓ 一つのポートは他の演算装置の一つのポートにだけ接続できる．
✓ 全ての接続ポートを利用する．
✓ 一つの演算装置の複数のポートが同じ演算装置に直接接続していない．
• 1 ≤ 𝑁 ≤ 200000, 1 ≤ 𝑎𝑖 ≤ 200000, 𝑎𝑖 の総和≤ 200000 ．

11/06/2022

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

17

問題４

演算装置の接続概要
入力例１
4
3 3 2 2

出力例１
Yes

入力例２
3
2 3 3

出力例２
No

11/06/2022

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

18

問題４

演算装置の接続2 3 2 4 3
sort

素朴な解法
𝑓𝑜𝑟 𝑖 ← 1 𝑡𝑜 𝑁 − 1[𝑎𝑖 , 𝑎𝑁 ]を降順に整列
𝑖𝑓 𝑖 + 𝑎𝑖 > 𝑁:
𝑝𝑟𝑖𝑛𝑡 No𝑎𝑖+1 , 𝑎𝑖+2 , … , 𝑎𝑖+𝑎𝑖 から1を引く
𝑎𝑖 ← 0
𝑖𝑓 全ての𝑖について𝑎𝑖 = 0 :𝑝𝑟𝑖𝑛𝑡 Yes
𝑒𝑙𝑠𝑒 :
𝑝𝑟𝑖𝑛𝑡 No4 3 3 2 2-1

0 2 2 1 1
sort
0 2 2 1 1

-1
0 0 1 0 1
sort
0 0 1 1 0

-1
0 0 0 0 0
sort

毎回ソートするため𝑂(𝑁 2 log 𝑁 ) 時間制限
11/06/2022

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

0 0 0 0 019

問題４

演算装置の接続解法
優先度付きキュー𝑄 ← 𝑎1 , 𝑎2 , … , 𝑎𝑁
𝑤ℎ𝑖𝑙𝑒 𝑄 𝑖𝑠 𝑛𝑜𝑡 𝑒𝑚𝑝𝑡𝑦:∑𝑎𝑖 = 𝑆とすると𝑂(𝑆 log 𝑁)𝑡 ← 𝑄. 𝑝𝑜𝑝
𝑓𝑜𝑟 𝑖 ← 1 𝑡𝑜 𝑡
𝑖𝑓 𝑄 𝑖𝑠 𝑒𝑚𝑝𝑡𝑦:
𝑝𝑟𝑖𝑛𝑡 No𝑣 ← 𝑄. 𝑝𝑜𝑝
𝑖𝑓 𝑣 − 1 > 0:
𝑡𝑚𝑝. 𝑝𝑢𝑠ℎ(𝑣 − 1)𝑄 ← 𝑡𝑚𝑝

𝑝𝑟𝑖𝑛𝑡 Yes
11/06/2022

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

20

問題４

演算装置の接続

解答例
bool solve(){priority_queue<int> pq;
for ( int i = 0; i < N; i++ ) pq.push(A[i]);while(!pq.empty()){
vector<int> tmp;
int t = pq.top(); pq.pop();for ( int i = 0; i < t; i++ ){if ( pq.empty() ) return false;
int v = pq.top(); pq.pop();if ( v - 1 > 0 ) tmp.emplace_back(v - 1);}
for ( int v : tmp ) pq.push(v);}return true;}
11/06/2022

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

21

問題５ どろだんご（７点）
正答数:

19チーム

最初の正解:

開成高等学校P08 可変引数テンプレート
40分17秒 (13:55:17)

11/06/2022

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

22

問題５

どろだんご

概要
• 様々な粘土𝑣𝑖 を持つ土と様々な純度𝑝𝑖 の水をそれぞれ数種類使ってどろだん
ごを作る．
• 一つのどろだんごを完成させるまで，様々な土と水を選びそれらを順番に塗っていく．同じ種類の土や水を２回以上塗ることはできない．
• どろだんごの品質は，大きさ，柔らかさ，美しさの尺度により決まる．
• 大きさ𝑠，柔らかさℎ，美しさ𝑏 のどろだんごに土か水を塗ると，その大きさ，柔らかさ，美しさは以下のようになる．
• 粘度𝑣の土を塗ると，大きさと美しさがそれぞれ𝑣，ℎ × 𝑣増える．柔らかさは変わらない．
• 純度𝑝の水を塗ると，柔らかさと美しさがそれぞれ𝑝，𝑠 × 𝑝増える．大きさは変わらない．
• どろだんごの美しさのバリエーションはどれくらいあるか？
11/06/2022

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

23

問題５

どろだんご

考察
𝑣𝑖

𝑝𝑗

2

𝑠

ℎ

𝑏

1

1

1

4
3
7

1

3

+4

+ (3 × 4)

5

15

3
10
2
10

• 𝑠の値は𝑣𝑖 の組み合わせで決まる• ℎの値は𝑝𝑖 の組み合わせで決まる+ (5 × 7)+7

10

11/06/2022+ (1 × 2)+23• 𝑏の値は𝑠とℎの値で決まる• 𝑏の値は常に𝑠 × ℎ

5

50

+3

+ (10 × 3)

8

80

+2

+ (10 × 2)

10

100

• 𝑠とℎのそれぞれの全ての組み合
わせについて，𝑠 × ℎとして得られる数を数える

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

24

問題５

どろだんご

解法
• 土の種類の数𝑁 (1 ≤ 𝑁 ≤ 10)，水の種類の数𝑀 (1 ≤ 𝑀 ≤ 10)．
• 2𝑁 × 2𝑀 を全探索する．
• 結果をsetで数えて𝑂(2𝑁+𝑀 log 2𝑁+𝑀 ) ．

11/06/2022

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

25

問題５

どろだんご

解答例
int N, M, V[10+1], P[10+1];
set<ull> cnt;
cin >> N >> M;
for ( int i = 0; i < N; i++ ) cin >> V[i];for ( int i = 0; i < M; i++ ) cin >> P[i];for ( int i = 0; i < (1 << N); i++ ){for ( int j = 0; j < (1 << M); j++ ){ull p = 1, q = 1;
for ( int k = 0; k < N; k++ )if ( (1 << k) & i ) p += V[k];for ( int k = 0; k < M; k++ ){if ( (1 << k) & j ) q += P[k];}cnt.insert(p*q);}}
cout << cnt.size() << endl;
11/06/2022

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

問題６ 一筆書き（６点）
正答数:

16チーム

最初の正解:

渋谷教育学園渋谷高等学校
P06 がんばりやさん
35分30秒 (13:50:30)

11/06/2022

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

27

問題６

一筆書き

概要
• PCK君が以下のように画用紙に絵を描く．
• 一回の動作で，１つの線分を描く．
• 既に描かれている線分に触れる場合は，お互いの端点だけで重なる．
• 連結した線分のグループを１つの図形とする．
• 線分を描く動作の情報が順番に与えられる．動作が終わるごとに，画用紙に含まれる一筆書きが可能な図形の数を報告せよ．
• 線分の数𝑁 (1 ≤ 𝑁 ≤ 200,000) ．
• 線分の始点の座標𝑥1 , 𝑦1 0 ≤ 𝑥1 , 𝑦1 ≤ 109 , 終点の座標𝑥2 , 𝑦2 (0 ≤ 𝑥2 , 𝑦2 ≤ 109 ) ．

11/06/2022

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

28

問題６

一筆書き

入出力例
入力例
8
5 0 8 35 6 2 3
10 5 10 1
2 3 5 05 0 5 68 3 5 68 3 10 1
10 5 8 3

11/06/2022

1

2

3

2

2

2

0

1

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

29

問題６

一筆書き

考察
• 問題の制約から，図形はグラフの連結成分として表すことができる．
• 連結成分ごとに，一筆書きが可能かを判定すればよい．

11/06/2022

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

30

問題６

一筆書き

一筆書きができる条件

グラフの2つの頂点の次数が奇数であり，グラフの全ての頂点の次数が偶数

残りの頂点の次数が偶数
11/06/2022

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

31

問題６

一筆書き

前処理
• 座標圧縮: 点の座標

→ 頂点番号へ変換

int getId(int x, int y){if ( M.count(make_pair(x, y)) == 0 ){M[make_pair(x, y)] = N++;}
return M[make_pair(x, y)];}• 入力を線分のリストへ変換する
for ( int i = 0; i < Q; i++ ){cin >> x1 >> y1 >> x2 >> y2;
u = getId(x1, y1);v = getId(x2, y2);edges.emplace_back(make_pair(u, v));}
11/06/2022

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

32

問題６

一筆書き

素朴な解法
• 線分が追加される度に深さ優先探索（幅優先探索）し，連結成分ごとに奇数の次数をもつ頂点の数を数える．

• 𝑂(𝑁 2 ) → 時間制限

• 更新された連結成分のみ探索し，差分で計算する．
• 𝑂(𝑁 2 )11/06/2022

→

時間制限

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

33

問題６

一筆書き

解法
• 連結成分を「互いに素な集合」で管理する．
• 初期状態で次数が０の頂点の扱いに注意．
• Union-find 木を用いて𝑂(𝑁 log 𝑁)．
• Rank + 経路圧縮

11/06/2022

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

34

問題６

一筆書き

解法：実装例• Union-find 木における各集合ごとに，次数が奇数である頂点の数を保持する• deg 𝑖 頂点𝑖の次数• odd 𝑖 集合𝑖に含まれる頂点のうち，次数が奇数のものの個数• 𝑢, 𝑣: 追加する線分の端点の頂点番号• 𝑆𝑢 , 𝑆𝑣 : 𝑢, 𝑣がそれぞれ属する集合（Union-find木における代表の頂点番号）• 𝑟𝑒𝑠: 現在一筆書きができる集合の数

11/06/2022

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

35

問題６

一筆書き

実装例：同じ連結成分内の頂点を繋ぐ
𝑖𝑓 𝑆𝑢 = 𝑆𝑣 :deg 𝑢 ← deg 𝑢 + 1
𝑖𝑓 deg 𝑢 が偶数:
odd 𝑆𝑢 ← 𝑜𝑑𝑑 𝑆𝑢 − 1𝑒𝑙𝑠𝑒 :
odd 𝑆𝑢 ← 𝑜𝑑𝑑 𝑆𝑢 + 1
deg 𝑣 ← deg 𝑣 + 1
𝑖𝑓 deg 𝑣 が偶数:
odd 𝑆𝑣 ← 𝑜𝑑𝑑 𝑆𝑣 − 1𝑒𝑙𝑠𝑒 :
odd 𝑆𝑣 ← 𝑜𝑑𝑑 𝑆𝑣 + 1
11/06/2022

𝑖𝑓 𝑆𝑢 の一筆書きが不可能→可能に変化:𝑟𝑒𝑠 ← 𝑟𝑒𝑠 + 1
𝑖𝑓 𝑆𝑢 の一筆書きが可能→不可能に変化:𝑟𝑒𝑠 ← 𝑟𝑒𝑠 − 1

𝑆𝑢 = 𝑆𝑣
uv

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

36

問題６

一筆書き

実装例：異なる連結成分内の頂点を繋ぐ
𝑖𝑓 𝑆𝑢 ≠ 𝑆𝑣 :𝑖𝑓 𝑆𝑢 の一筆書きが可能: 𝑟𝑒𝑠 ← 𝑟𝑒𝑠 − 1
𝑖𝑓 𝑆𝑣 の一筆書きが可能: 𝑟𝑒𝑠 ← 𝑟𝑒𝑠 − 1
𝑛𝑒𝑤𝑂𝑑𝑑 ← 𝑜𝑑𝑑 𝑆𝑢 + 𝑜𝑑𝑑 𝑆𝑣
deg 𝑢 ← deg 𝑢 + 1
𝑖𝑓 deg 𝑢 が偶数:
𝑛𝑒𝑤𝑂𝑑𝑑 ← 𝑛𝑒𝑤𝑂𝑑𝑑 − 1𝑒𝑙𝑠𝑒:
𝑛𝑒𝑤𝑂𝑑𝑑 ← 𝑛𝑒𝑤𝑂𝑑𝑑 + 1
𝑖𝑓 deg 𝑣 が偶数:
𝑛𝑒𝑤𝑂𝑑𝑑 ← 𝑛𝑒𝑤𝑂𝑑𝑑 − 1𝑒𝑙𝑠𝑒:
𝑛𝑒𝑤𝑂𝑑𝑑 ← 𝑛𝑒𝑤𝑂𝑑𝑑 + 1
11/06/2022

𝑢, 𝑣 を合併
𝑆𝑤 ← 𝑓𝑖𝑛𝑑𝑆𝑒𝑡(𝑢)𝑜𝑑𝑑 𝑆𝑤 ← 𝑛𝑒𝑤𝑂𝑑𝑑
𝑖𝑓 𝑆𝑤 が一筆書き可能:𝑟𝑒𝑠 ← 𝑟𝑒𝑠 + 1

v

u

𝑆𝑣

𝑆𝑢

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

𝑆𝑤37

問題７ 素数の日の並び（１０点）
正答数:

1チーム

最初の正解:

筑波大学附属駒場高等学校
P04 simasiman
2時間47分35秒 (16:02:35)

11/06/2022

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

38

問題７

素数の日の並び概要• １週を日曜日から始める7日間とする．
• たとえば2022年11月1日が含まれる週から，12月31日が含まれる週までの週の並びを見ると，右の図のようになっている．

2022年11月,12月日 月 火 水 木 金 土
30 31 1 2 3 4 5
6

7

8

9

10 11 1213 14 15 16 17 18 19• このような週の並びで，日曜日から土曜日までの1週間分の日の並びに，最大でいくつの素数の日が入っているか？

20 21 22 23 24 25 26• 𝑦1 ≤ 𝑦2 ≤ 100,000,000.

11 12 13 14 15 16 17

27 28 29 30
4

5

6

1

2

3

7 8

9

10

18 19 20 21 22 23 24
25 26 27 28 29 30 31

11/06/2022

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

39

問題７

素数の日の並び概要• 開始年月と終了年月が与えられたとき，その開始年月の1日が含まれる週から，終了年月の最後の日が含まれる
週までの期間において，一つの週に現れる素数の日の数の最大値と，素数の日の数が最大になる週の数を求める

2022年11月,12月日 月 火 水 木 金 土
30 31 1 2 3 4 5
6

7

8

9

10 11 1213 14 15 16 17 18 19

例えば，右図の場合，各週の素数の日は以下のようになる．

20 21 22 23 24 25 26

⚫
⚫
⚫
⚫
⚫
⚫
⚫
⚫
⚫

27 28 29 30

1週目の素数の日は31，2，3，5の4つ．
2週目の素数の日は7, 11の2つ．
3週目の素数の日は13, 17, 19の3つ．
4週目の素数の日は23だけで1つ．
5週目の素数の日は29, 2, 3の3つ．
6週目の素数の日は5, 7の2つ．
7週目の素数の日は11, 13, 17の3つ．
8週目の素数の日は19, 23の2つ．
9週目の素数の日は29, 31の2つ．
11/06/2022

4

5

6

1

2

3

7 8

9

10

11 12 13 14 15 16 17
素数の日の数の最大値は4
そのような週の数は1

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

18 19 20 21 22 23 24
25 26 27 28 29 30 31

40

問題７

素数の日の並び考察• 素数2だけは，すぐ隣にある素数3と隣接していて，他の偶数は素数ではないから週の日数が7日なら，2を含む場合に4つになるケースが最大であることがわかる．
• さらに，4つ並ぶ場合は(2,3,5,7)か(31,2,3,5)か(29,31,2,3)か(29,2,3,5)
しかないということが言える．

11/06/2022

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

41

問題７

素数の日の並び考察• ある年の初めから，各月初日までの経過日数をmod7で表すと以下のようになる．
閏年でないとき
月
日数
累積
Mod7

１
31
0
+0

２
28
+31
+3

３
31
+59
+3

４
30
+90
+6

５
31
+120
+1

６
30
+151
+4

７
31
+181
+6

８
31
+212
+2

９
30
+243
+5

１０
31
+273
+0

１１
30
+304
+3

１２
31
+334
+5

２
29
+31
+3

３
31
+60
+4

４
30
+91
+0

５
31
+121
+2

６
30
+152
+5

７
31
+182
+0

８
31
+213
+3

９
30
+244
+6

１０
31
+274
+1

１１
30
+305
+4

１２
31
+335
+6

閏年であるとき
月
日数
累積
Mod7

１
31
0
+0

• 累積日数のmod7が，+0から+6まですべてそろうので，どの年にも必ず日付が1 2 3 4 5 6 7となる並びの月が存在する．
11/06/2022

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

42

問題７

素数の日の並び考察• 丸1年分の期間を見れば，１週間に現れる素数の日の数の最大値は必ず４になる．
• 丸1年に満たない期間について，愚直に集計しても高々365日．
• 期間が1年以上なら，年単位で集計することが可能．

11/06/2022

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

43

問題７

素数の日の並び解法• ある年の，素数の日の数が4になる週の数は，1月1日が何曜日なのかと，閏年かどうかで決まる．
• 前処理で，素数の日の数が4になる週の数をカウントしておく ．
Table[閏年/閏年でない][1月1日の累積日数 mod 7]表を用意して埋める．
• 例えばy1 = 2003, m1 = 9, y2 = 2022, m2 = 11なら，2004年から2021年までは，表からO(y2 – y1)で求まる．2003年9月から12月と，2022年1月から11月までは，愚直にカウントする．
• ただし，重複が出る分を除去する必要がある．
• 計算量O(y2 – y1)．

11/06/2022

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

44

問題７

素数の日の並び解法

前処理：
table[2][7]; //[閏年かどうか][1月1日の曜日]
閏年と閏年じゃない年について1/1が月,火,...,日だったときその年に素数日4の週がいくつあるかをカウントしておく表
ただし1月の週は前の年の週，12月の週は次の年の週と重複して数えられる場合があるので重複を除去する
for ( int i=0; i<2; ++i ) //閏年かどうか
for ( int j=0; j<7; ++j ) //j=0 -> 1/1が日曜, j=1 -> 1/1が月曜..

table[i][j] = 素数の日の数が4になる週を数える
11/06/2022

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

45

問題７

素数の日の並び解法//末端処理𝑖𝑓 𝑦1 = 𝑦2 :𝑟𝑒𝑠 ← 𝑦1 年𝑚1 月から𝑦2 年𝑚2 月まで愚直に求める
𝑒𝑙𝑠𝑒 :𝑟𝑒𝑠 ← 𝑦1 年𝑚1 月から𝑦1 年12月まで愚直に求める
𝑟𝑒𝑠 ← 𝑦2 年1月から𝑦2 年𝑚2 まで愚直に求める//年ごとに処理
𝑖𝑓 𝑦2 − 𝑦1 ≥ 2:
𝑤𝑑 ← ( 𝑦1 +1)年1月1日の曜日
𝑓𝑜𝑟 𝑦1 +1 𝑡𝑜 𝑦2 − 1:𝑟𝑒𝑠 ← 𝑡𝑎𝑏𝑙𝑒[閏年かどうか][𝑤𝑑]を加算
𝑤𝑑 ← 閏年かどうかによって+365または+366して，mod7を取る
11/06/2022

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

問題８ ゲームブック（１１点）
正答数:

10チーム

最初の正解:

灘高等学校
P01 KobLa
1時間9分33秒 (14:24:33)

11/06/2022

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

問題８ ゲームブック
概要• 𝑁ページのゲームブックを作成する．
• 各ページにはいくつかのページ番号を書き込む．以下の条件を全て満たす，
ページ番号の書き方が何通りあるか求めよ．
✓各ページには，そのページ番号よりも大きいページ番号を書き込む．
✓1ページ目から，直接またはいくつかのページを経由して，任意のページにたどり着ける．
✓任意のページから，直接またはいくつかのページを経由して，𝑁ページ目にたどり着ける．
• 2 ≤ 𝑁 ≤ 500．
• 答えを998,244,353で割った余りを出力する．

11/06/2022

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

問題８ ゲームブック
テストケース𝑁 = 2のとき1通り

𝑁 = 3のとき2通り

𝑁 = 4のとき10通り

11/06/2022

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

問題８ ゲームブック
解法（概要）• 𝑂(𝑁 3 )の動的計画法．
• 𝑑𝑝 𝑖 𝑗 ∶=頂点𝑖まで計算し，出次数が0の頂点の個数が𝑗である場合の数．
• 𝑑𝑝 𝑁 1 が答えとなる．

11/06/2022

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

問題８ ゲームブック
解法（詳細）

計算済み（部分問題）追加• 「１ページ目から任意のページにたどり着ける」を満たしつつ頂点を追加していく．
➢１本以上の辺が追加する頂点に入る．
• 頂点𝑁以外の任意の頂点の出次数は１以上である．
➢頂点𝑁のみが出次数が0である頂点となる．
11/06/2022

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

問題８ ゲームブック
解法（状態遷移のイメージ）• 出次数が0である頂点の個数を𝑗とする（出次数が0でない頂点の個数は𝑖 − 𝑗）．
𝑖個

出次数 > 0𝑖 − 𝑗個2𝑖−𝑗

出次数 = 0

𝑗個

𝑗 𝐶𝑡

追加

出次数 = 0の頂点からいくつ繋ぐかを決め打ちする
𝑡 = 1, 2, … , 𝑗
11/06/2022

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

問題８ ゲームブック
解法（状態遷移のイメージ）

𝑑𝑝 1 1 = 1
𝑓𝑜𝑟 𝑖 = 1 𝑡𝑜 𝑁 − 1:𝑓𝑜𝑟 𝑗 = 1 𝑡𝑜 𝑖:/* 出次数が０の頂点とt個繋ぐ */𝑓𝑜𝑟 𝑡 = 1 𝑡𝑜 𝑗:
𝑑𝑝 𝑖 + 1 𝑗 − 𝑡 + 1 += 𝑗𝐶𝑡 × 2𝑖−𝑗 × dp 𝑖 𝑗/∗ 出次数が０の頂点と一つも繋がない場合 ∗/𝑑𝑝 𝑖 + 1 𝑗 + 1 += (2𝑖−𝑗 − 1) × dp 𝑖 𝑗
𝑝𝑟𝑖𝑛𝑡 𝑑𝑝 𝑁 1
11/06/2022

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

問題９ 縄張りの大きさ（１１点）
正答数:

6チーム

最初の正解:

大阪公立大学工業高等専門学校
P05 森林（グラフ）
1時間16分37秒 (14:31:37)

11/06/2022

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

54

問題９

縄張りの大きさ概要• 𝐻 × 𝑊個の英小文字からなる２次元のテキスト𝑇と，整数𝑘が与えられる．
• 𝑇に含まれる，𝑘回以上現れる正方形のパタン𝑃のうち，最も大きいものの大きさを求めよ．そのようなパタンが存在しない場合は「-1」と報告する．
• 1 ≤ 𝐻 ≤ 600， 1 ≤ 𝑊 ≤ 600．

11/06/2022

a

b

b

c

d

a

a

b

b

a

a

a

a

b

b

a

a

a

a

a

• 𝑘 = 2 のとき，答えは３

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

55

問題９

縄張りの大きさ

解法：基本方針• 正方形の大きさを決め打ちして，その大きさのパタンのうち最も多く出現するものが𝑘回以上現れるかを判定する．
• 最も大きいものが答え．

• 正方形の大きさをどのように探索するか？
⇒ 二分探索が適用可能．
• ある特定の大きさのパタンをどのように分類して数えるか？
⇒ 解法１：ローリングハッシュ（確率的な解法）
解法２：ダブリング（決定的な解法）• 解法２をKMRアルゴリズムという．
11/06/2022

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

56

問題９

縄張りの大きさ

解法：正方形の大きさの探索• パタンが大きくなるほど，パタンの出現数の最大値は減っていく（増えない）• パタンが小さくなるほど，パタンの出現数の最大値は増えていく（減らない）⇒ 二分探索が適用できる
パタンの
出現数の
最大値

𝑘

パタンの大きさ11/06/2022

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

57

問題９

縄張りの大きさ

解法：特定の大きさのパタンを数える（解法1）• ローリングハッシュで全ての位置における正方形のパタンのハッシュ値を求める．
• １つの正方形のハッシュ値を𝑂(1) で計算．
• 全てのハッシュ値を𝑂(𝐻𝑊)で計算．
• ハッシュ値をmapで数える．
• std::unordered_map 𝑂(1) が期待できる• std::map
𝑂(log 𝐻𝑊)

11/06/2022

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

58

問題９

縄張りの大きさ計算量：（解法１：二分探索＋ローリングハッシュ）• 二分探索，ローリングハッシュ，unordered_mapを使って𝑂(𝐻𝑊 log 𝐻𝑊)

11/06/2022

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

59

問題９

縄張りの大きさ

解法：特定の大きさのパタンを数える（解法２）• ダブリングを使う．
• 前処理として，一辺が2𝑏 （𝑏 = 0,1, … , 𝑁）の正方形のパタンの出現
情報を生成・保存する（ 𝑁 は 2𝑁 ≤ min(𝐻, 𝑊) < 2𝑁+1 を満たす整数）．
• 一辺が2𝑏 の正方形のパタンの出現情報から2𝑏+1 の正方形パタンの出現情報を生成．
𝑏+1
2• 一辺が2𝑏+1 のパタンは，2𝑏 のパタンを４つまとめることで得られる（ダブリング）．

• 一辺が2𝑏+1 の２つのパタンが等しい＝対応する一辺が2𝑏 のパタンがすべて等しい．
2𝑏11/06/2022

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

60

問題９

縄張りの大きさ

解法：特定の大きさのパタンを数える（解法２）• 一辺が𝑠の正方形のパターンの出現情報は，
2𝐵 ≤ 𝑠 < 2𝐵+1 となる2𝐵 のパターンの出現情報から得られる．
• 一辺が2𝐵 の４つのパターンをまとめて，一辺が𝑠のパターンを作る（ダブリング）．
• 下方向と右方向にそれぞれ𝑠 − 2𝐵 だけずらしてパターンを重ねる（ 𝑠 − 2𝐵 + 2𝐵 = 𝑠）．

2𝐵2𝐵

𝑠 − 2𝐵𝑠• 一辺が𝑠のパターンが同じ ＝ 対応する大きさ2𝐵 の４つのパターンが同じ．

11/06/2022

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

61

問題９

縄張りの大きさ

解法：特定の大きさのパタンを数える（解法２）• パタンをIDで管理。同じパタンは同じIDにする．
• 一辺𝑠のパタンのIDは2𝐵 （2𝐵 < 𝑠 ≤ 2𝐵+1 ）の
パタンのIDの列から生成（ダブリング）．

0

1

2

テキスト 0 d a b
1 a b c2 b c aパターンの出現情報
4 1 2
𝑠 = 21 のパタンのIDは，20 のパタンのIDの列から生成． 一辺20 1 2 3
位置
(0,0)
(0,1)
(1,0)
(1,1)
2 3 3
IDの列 (4,1,1,2) (1,2,2,3) (1,2,2,3) (2,3,3,3)
IDの列の辞書式順序でソート
位置
IDの列
新ID
11/06/2022

(0,1)
(1,0)
(1,1)
(0,0)
(1,2,2,3) (1,2,2,3) (2,3,3,3) (4,1,1,2)
1
1
23
パソコン甲子園2022 プログラミング部門 本選問題解説

一辺21

3 1 1 2 - - 62

問題９縄張りの大きさ計算量：（解法２：二分探索＋ダブリング）• 前処理で生成・保存するパタンの出現情報の個数は𝑂(log 𝐻𝑊)• IDは高々𝐻𝑊種類．
• 𝑀種類の要素𝑁個の辞書式順序によるソートの計算量は𝑂(𝑁 + 𝑀)
⇒ 新しいIDの生成の計算量は𝑂(𝐻𝑊)．
• ダブリングのための前処理で𝑂(𝐻𝑊 log 𝐻𝑊)．
• 二分探索，ダブリングで𝑂(𝐻𝑊 log 𝐻𝑊)• 全体として𝑂(𝐻𝑊 log 𝐻𝑊)．

11/06/2022

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

問題１０ 数列の復元（１１点）
正答数:

14チーム

最初の正解:

大阪公立大学工業高等専門学校
P05 森林（グラフ）
44分1秒 (13:59:01)

11/06/2022

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

64

問題１０

数列の復元

概要
• 長さ𝑁の数列𝑇 = (𝑇1 , 𝑇2 , ⋯ , 𝑇𝑁 )と，正整数𝑋,𝑌が与えられる．
• 全ての要素の値が0である長さ𝑁の数列𝐴 = (𝐴1 , 𝐴2 , ⋯ , 𝐴𝑁 )に対して以下の操作
𝑓𝑘 を複数回行うことができる．ただし𝑘 = 1, 2, ⋯ , 𝑁である．
𝑓𝑘 ：数列𝐴の𝑘番目の要素に𝑋を加算し，それ以外の要素から𝑌を減算する．
• 数列𝐴を数列𝑇と等しくするための各操作の回数の列を出力せよ．ただし，そのような各操作の回数の列が複数存在する場合は，操作の回数の総和が最も少ないものの列を出力せよ．
• 1 ≤ 𝑁 ≤ 2 × 105 ，1 ≤ 𝑋, 𝑌 ≤ 108 ， − 109 ≤ 𝑇𝑖 ≤ 109 ．

11/06/2022

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

65

問題１０

数列の復元

入出力例
入力例１
5 4 1
-5 10 0 0 -5

出力例１
0 3 1 1 0

入力例２
5 4 2
-5 10 0 0 -5

出力例２
-1

11/06/2022

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

66

問題１０

数列の復元

解法
• 操作回数を𝐶𝑖 とする．
• 𝑋, 𝑌 > 0，𝐶𝑖 , 𝑇𝑖 ≥ 0，これらは全て整数．
• 次の式を満たす𝐶𝑖 を求める問題．
𝑋𝐶1 − 𝑌𝐶2 − 𝑌𝐶3 − ⋯− 𝑌𝐶𝑁 = 𝑇1
−Y𝐶1 + 𝑋𝐶2 − 𝑌𝐶3 − ⋯− 𝑌𝐶𝑁 = 𝑇2:
−Y𝐶1 − 𝑌𝐶2 ⋯ − 𝑌𝐶𝑖−1 + 𝑋𝐶𝑖 − 𝑌𝐶𝑖+1 ⋯ − 𝑌𝐶𝑁 = 𝑇𝑖:
−Y𝐶1 − 𝑌𝐶2 − 𝑌𝐶3 − ⋯− 𝑌𝐶𝑁+1 + 𝑋𝐶𝑁 = 𝑇𝑁

• 操作𝑖を𝑖本目の式として表す．
11/06/2022

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

67

問題１０

数列の復元

解法
• 𝑖本目の式
𝑋𝐶𝑖 − 𝑌 ∑𝐶𝑘 − 𝐶𝑖 = 𝑇𝑖
𝑇𝑖 − 𝑌 × ∑𝐶𝑘
𝐶𝑖 =
𝑋+𝑌

から𝐶𝑖 を求めることができる．

操作回数の和𝑆𝐶 = ∑𝐶𝑘 が求まればよい．

• 𝐴 = (0, 0, ⋯ , 0)である。
• 一回の操作ごとの∑𝐴𝑖 の変化量をΔ𝑇 = 𝑋 − 𝑌(𝑁 − 1)とする．
11/06/2022

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

68

問題１０

数列の復元

解法
• Δ𝑇 ≠ 0の場合
∑𝑇

操作回数の和𝑆𝐶 = Δ𝑇𝑖
割り切れない場合や，値が負となる場合は不可能と判定．

• Δ𝑇 = 0の場合
すべての操作を１回ずつ行うと，すべての操作が打ち消される．
最小回数の操作方法では，少なくとも１つの操作は一度も行われない．
そのような要素は常に−𝑌されるためmin 𝑇𝑖 に等しくなる．
よって，操作回数の和𝑆𝐶 = −min(𝑇𝑖 )𝑌• Δ𝑇 ≠ 0の場合は解は一意に定まる．Δ𝑇 = 0の場合は総和の最小性を仮定すると一意に定まる．
•

𝑇𝑖 −𝑌×𝑆𝐶が割り切れない場合や負の値になる場合， 𝑆𝐶 ≠ ∑𝐶𝑖 の場合は不可能と判定する．
𝑋+𝑌

11/06/2022

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

69

問題１１ N数列（１２点）
正答数:

4チーム

最初の正解:

大阪公立大学工業高等専門学校
P05 森林（グラフ）
25分49秒 (13:40:49)

11/06/2022

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

70

問題１１

N数列

概要
• 𝑁個の要素からなる𝑁本の数列𝐴1 , 𝐴2 , ⋯ , 𝐴𝑁 があり，数列
𝐴𝑖 の𝑗番目の要素を𝐴𝑖,𝑗 と表す．最初はすべての数列𝐴𝑖 について 𝐴𝑖,1 , 𝐴𝑖,2 , ⋯ , 𝐴𝑖,𝑁 = 𝑎1 , 𝑎2 , ⋯ , 𝑎𝑁 であるとする．
• 数列 𝐴1 , 𝐴2 , ⋯ , 𝐴𝑁 に対して，以下の３種類の操作を行う．
1. 数列𝐴𝑦 を数列𝐴𝑥 で置き換える．
2. 数列𝐴𝑥 の𝑠番目の要素𝐴𝑥,𝑠 の値と，数列𝐴𝑦 の𝑡番目の要素𝐴𝑦,𝑡 の値を入れ替える．
3. 数列𝐴𝑥 に対して，𝑠番目から𝑡番目の要素の総和を
出力する．

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

• 2 ≤ 𝑁 ≤ 105 ，1 ≤ 𝑄 ≤ 105 ，1 ≤ 𝑎𝑖 ≤ 109 ．
11/06/2022

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

71

問題１１

N数列

解法１
• 永続データ構造（セグメントツリー） ．

解法２（こちらを解説）• 操作過程を表すツリーを構築．
• 交換クエリを更新クエリとして扱う．
• 操作ツリーに対してDFSを行いながらセグメント木を更新・ロールバッ
ク・検索する．
➢要素更新と区間和が行えるセグメントツリーがあれば十分．
11/06/2022

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

72

問題１１

N数列

操作過程を表すツリーを構築• 初期状態：頂点0が全ての数列を表している

1

木の頂点が数列の状態を表す11/06/2022

2

3

4

5

各数列が頂点（状態）に属する

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

73

問題１１

N数列

操作過程を表すツリーを構築• クエリ１：数列のコピー

1

3

4

5

数列１を数列２にコピー
2

11/06/2022

新しい頂点が数例２を表すようになるパソコン甲子園2022 プログラミング部門 本選問題解説

74

問題１１

N数列

操作過程を表すツリーを構築• クエリ２：要素の交換

1

2

1

(2, s)と(3, t)の交換

32

11/06/2022

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

3

75

問題１１

N数列

交換クエリから更新クエリへ• 交換クエリ（ 𝑟1 , 𝑐1 , 𝑟2 , 𝑐2 の交換）が行われるとき，
𝑟1 , 𝑐1 → 𝑟2 , 𝑐2 , 𝑟2 , 𝑐2 → 𝑟1 , 𝑐1 のコピーを同時に行うと考えてよい．
• それぞれの 𝑟1 , 𝑐1 , 𝑟2 , 𝑐2 の値を瞬時に求めることはできない．
（すべての値を持つことはできないので）• 𝑟1 , 𝑐1 の値を求めるには，𝑟1 を表す頂点の祖先であって𝑐1 番目が変更された頂点のうち最も近いものが求まればよい．

11/06/2022

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

76

問題１１

N数列

交換クエリから更新クエリへ
1. クエリを先読みして操作ツリーを構築しつつ，以下の値を計算• 𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑 𝑖 𝑗 ≔頂点𝑖において何番目の情報が必要とされているかを表す．
• 𝑐ℎ𝑎𝑛𝑔𝑒 𝑖 ≔ 非負整数𝑘のとき頂点𝑖の𝑘番目が交換クエリによって更新されることを表す．-1のとき更新されないことを表す．

11/06/2022

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

77

問題１１

N数列

交換クエリから更新クエリへ
2. 操作ツリーに対してDFSを行い以下の値を計算• 𝑐𝑙𝑜𝑠𝑒𝑠𝑡 𝑖 𝑗 ≔ 頂点𝑖の祖先であって𝑗番目が変更された頂点のうち最も近いものの頂点番号．
𝑑𝑓𝑠1 𝑢 :𝑖𝑓 𝑐ℎ𝑎𝑛𝑔𝑒 𝑢 ≠ -1:// ノードuのchanged[u]列目が変更されている
𝑡𝑚𝑝 ← 𝑝𝑟𝑒𝑣𝑖𝑜𝑢𝑠[𝑐ℎ𝑎𝑛𝑔𝑒 𝑢]
𝑝𝑟𝑒𝑣𝑖𝑜𝑢𝑠[𝑐ℎ𝑎𝑛𝑔𝑒 𝑢] ← 𝑢// ノードuにおいて，列cが必要とされている場合，// uにおける列cが更新された最も近いノード番号を記録
𝑓𝑜𝑟 𝑐 𝑖𝑛 𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑 𝑢 : 𝑐𝑙𝑜𝑠𝑒𝑠𝑡 𝑢 𝑐 ← 𝑝𝑟𝑒𝑣𝑖𝑜𝑢𝑠[𝑐]𝑓𝑜𝑟 𝑣 𝑖𝑛 𝑎𝑑𝑗 𝑢 : 𝑑𝑓𝑠1(𝑣)𝑖𝑓 𝑐ℎ𝑎𝑛𝑔𝑒 𝑢 ≠ -1 : 𝑝𝑟𝑒𝑣𝑖𝑜𝑢𝑠[𝑐ℎ𝑎𝑛𝑔𝑒 𝑢] ← 𝑡𝑚𝑝
11/06/2022

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

78

問題１１

N数列

交換クエリから更新クエリへ
3. クエリの順番に以下の値を計算• 𝑣𝑎𝑙𝑢𝑒 𝑖 𝑗 ≔頂点𝑖の𝑗番目が更新される値を表す(𝑣𝑎𝑙𝑢𝑒 0 ← 𝑎)
• 𝑣𝑎𝑙𝑢𝑒 𝑎 𝑏 ← 𝑣𝑎𝑙𝑢𝑒 𝑐𝑙𝑜𝑠𝑒𝑠𝑡 𝑐 𝑑 𝑑𝑓𝑜𝑟 𝑞𝑢𝑒𝑟𝑦 𝑖𝑛 𝑖𝑛𝑝𝑢𝑡𝑄𝑢𝑒𝑟𝑖𝑒𝑠:{𝑐𝑜𝑚, 𝑎, 𝑏, 𝑐, 𝑑} ← 𝑞𝑢𝑒𝑟𝑦
𝑖𝑓 𝑐𝑜𝑚 = 2:
𝑣𝑎𝑙𝑢𝑒 𝑎 𝑏 ← 𝑣𝑎𝑙𝑢𝑒[𝑐𝑙𝑜𝑠𝑒𝑠𝑡[𝑐][𝑑]][𝑑];𝑞𝑢𝑒𝑟𝑖𝑒𝑠 𝑎 ← {𝑐𝑜𝑚, 𝑏, 𝑣𝑎𝑙𝑢𝑒 𝑎 𝑏 }𝑒𝑙𝑠𝑒 𝑖𝑓 𝑐𝑜𝑚 = 3:
𝑞𝑢𝑒𝑟𝑖𝑒𝑠[𝑎] ← {𝑐𝑜𝑚, 𝑏, 𝑐, 𝑛𝑟𝑎𝑛𝑔𝑒𝑄 + +}11/06/2022

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

79

問題１１

N数列

操作ツリーに対してDFSを行いながらセグメント木を更新・ロールバック・検索• ここまでで各交換クエリにおいて更新される値が分かっているので，交換クエリを更新クエリとして処理できるよ
うになる．
• あとはDFSしながら区間和クエリと更新クエリを処理すればよい．

𝑑𝑓𝑠2 𝑢 :𝑓𝑜𝑟 𝑞𝑢𝑒𝑟𝑦 𝑖𝑛 𝑞𝑢𝑒𝑟𝑖𝑒𝑠 𝑢 :𝑐𝑜𝑚, 𝑥, 𝑦, 𝑖 ← 𝑞𝑢𝑒𝑟𝑦
𝑖𝑓 𝑐𝑜𝑚 = 3:
𝑟𝑒𝑠 𝑖 ← 𝑓𝑖𝑛𝑑𝑆𝑢𝑚 𝑥, 𝑦𝑒𝑙𝑠𝑒 𝑖𝑓 𝑐𝑜𝑚 = 2:
𝑡𝑚𝑝 ← 𝑥, 𝑥番目の要素の値
𝑢𝑝𝑑𝑎𝑡𝑒 𝑥, 𝑦
𝑓𝑜𝑟 𝑣 𝑖𝑛 𝑎𝑑𝑗 𝑢 :𝑑𝑓𝑠2(𝑣)𝑓𝑜𝑟 𝑒 𝑖𝑛 𝑡𝑚𝑝:
𝑢𝑝𝑑𝑎𝑡𝑒(𝑒. 𝑓𝑖𝑟𝑠𝑡, 𝑒. 𝑠𝑒𝑐𝑜𝑛𝑑)
11/06/2022

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

問題１２ 三角形パズル（１４点）
正答数:

2チーム

最初の正解:

渋谷教育学園幕張高等学校
P03 貪欲なGreedy
1時間35分3秒 (14:50:03)

11/06/2022

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

81

問題１２

三角形パズル

概要• 𝑁個の三角形が以下の条件で与えられる．
✓互いに重なることはない．
✓各三角形は少なくとも他の一つの三角形と辺の一部を共有して連結している．
✓三角形の集合が形成する多角形の内部は，三角形によりすべて埋め尽くされている．
• これらの三角形で形成される多角形のすべての頂点の座標を求めよ．
• 2 ≤ 𝑁 ≤ 105 ， − 109 ≤ 𝑥𝑖 , 𝑦𝑖 ≤ 109 ．

11/06/2022

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

82

問題１２

三角形パズル概要

11/06/2022

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

83

問題１２

三角形パズル

解法：概要
1. 直線に属する点のリストを作成する．
2. 多角形の辺となり得る辺を抽出する．
3. 多角形を生成する．

11/06/2022

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

84

問題１２

三角形パズル

解法：直線に属する点のリストを作成する• 直線をパラメタで表す．
• 𝑦 = 𝑎𝑥 + 𝑏（傾きと切片）• 𝑎𝑥 + 𝑏𝑦 + 𝑐 = 0 （一般形）• 直線が軸に平行な場合に注意．
• 直線をパラメタによって一意に特定できればよい．
• ある点が属する直線をmapで管理できるようになる．
• 各直線上の点は整列しユニークをかけておく．
• 整列する処理に𝑂(𝑁 log 𝑁) ．
11/06/2022

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

85

問題１２

三角形パズル

解法：多角形の辺となり得る辺を抽出する• 各三角形を反時計回りに辿り，各線分を訪問する．
• 三角形の２頂点を始点・終点として該当する直線上の線分を訪問する．
• 始点・終点は二分探索(lower_bound等）で取得できる．
• 全ての線分を辿る処理に𝑂 𝑁• 始点・終点を特定る処理に𝑂(𝑁 log 𝑁)

11/06/2022

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

86

問題１２

三角形パズル

解法：多角形の辺となり得る辺を抽出する• 異なる訪問方向で相殺される線分を排除
し，多角形の辺を抽出する• 各点ごとに隣接する点を保持する• グラフを生成しておく

11/06/2022

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

87

問題１２

三角形パズル

解法：多角形を生成する• 視点と２番目の点を特定して，未訪問の隣接する点を順番に追加していく

11/06/2022

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

88

問題１２

三角形パズル

テストケース 00_sample_XX.in

11/06/2022

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

89

問題１２

三角形パズル

テストケース 01_small_XX.in

11/06/2022

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

90

問題１２

三角形パズル

テストケース 03_general_XX.in

11/06/2022

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

91

問題１２

三角形パズル

テストケース 05_large_XX.in

11/06/2022

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

92

問題１２

三角形パズル

テストケース 06_corner_maximum_XX.in

11/06/2022

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

93

問題１２

三角形パズル

テストケース 06_corner_maximum_XX.in

11/06/2022

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

94

問題１２

三角形パズル

テストケース 09_beautiful_XX.in

11/06/2022

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

95