feature image

2022年5月2日 | ブログ記事

CPCTF22 PPC 作問陣Writeup

こんにちは!アルゴリズム班の@ebi @tatyam @tqk @0214sh7 @aya_se @season1618 です。

この記事は2022年5月1日に行われたCPCTF22 のPPC部門の作問陣writeupです。

参加者の1人でtraPの部員の@oribeさんがPPCの面白い設定の問題のイラストを書いてくれました。かわいいですね。

おそらく上段左からAddition Construct、Garbage Bags Optimization、Mogumogu Pakupaku、下段左からRTA in Honey traP、Shout Sucuのことだと思います。

目次

Newbie

Easy

Medium

Hard

おわりに

Newbie

Addition Construct

作問者:@tqk

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
54 0 0 12

問題

tqk さんと tenay さんは traぶ という部員 人のサークルに所属しています。ドーナツを 個買いました。 人ともドーナツを 個以上は食べたいと思っていて、 個までなら食べることができます。条件に合うように、ドーナツを分ける方法を一つ提案してください。

すなわち、以下の条件を満たす整数の組 を一つ求めてください。

制約

解法

作者感想

Nkuth's Plus Notation

作問者:@tqk

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
30 0 1 13

問題

ヌクースさんは次のような演算子たちを定義しました。

例えば、 や、 などが成り立ちます。

を求めてください。

制約

解法

作者感想

State of the clock

作問者:@aya_se

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
30 0 0 10

問題

正常に動作する時計において、 時の角度から右回り方向に長針(分針)が 度、短針(時針)が 度進んでいるという状態は存在するでしょうか?

writeup

時計の針を題材にしたNewbie問でした。個人的にちょっと気に入ってます。

という性質から判定することができます。迷ったら360通りを全探索してもいいですし、条件を整理すると1行でスッキリ書くこともできます。

問題文が短く、コード量も非常に少なく済むので、時間的にコスパいい問題かなと思いましたが、何故かPPCのNewbie問の中では一番AC者数が少ないという結果に。

解答例 (C++)

#include <iostream>
using namespace std;

int main() {
    int A, B;
    cin >> A >> B;
    cout << (A == (B % 30) * 12 ? "Yes" : "No") << endl;
}


Easy

Garbage Bags Optimization

作問者:@ebi

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
31 3 0 0

問題文

一人暮らしを始めたebiくんの家にはゴミ箱が 個ありますが、ゴミ袋がありません。ebiくんは、 日分のゴミ袋を買いにお店に行きました。お店では 以上 以下のすべての整数の容量のゴミ袋が販売されていました。

ebiくんは 以上 以下の整数 を選び、容量 のゴミ袋を 個購入します。その後、 個のゴミ箱それぞれに容量 のゴミ袋を取り付けます。
個のゴミ箱には、 から までの番号がつけられています。

ebiくんは、 日目 () に大きさ のゴミを捨てることがわかっています。ebiくんは、ゴミを以下のようにしてゴミ袋に入れます。

  1. 全てのゴミ箱にゴミ袋が取り付けられていない場合、ebiくんは悲しみ、新しくゴミ袋を買いに行く。
  2. ゴミ袋が取り付けられているゴミ箱のうち最も番号の小さいものを選び、ゴミ箱 とする。
  3. ゴミ箱 に入っているゴミの総量を とする。 であれば、ゴミ箱 に取り付けられているゴミ袋を閉じて捨てる。1. に戻る。
  4. ゴミ箱 に大きさ のゴミを捨てる。

日間の間にebiくんが悲しまないようにするときの、 の最小値を求めてください。

writeup

解法としてはゴミ袋の容量 を二分探索をすることで求めます。二分探索の判定関数は使用するゴミ箱の数が 以下であるかどうかです。
Easyの中でも取っ付きやすい問題を意識して作問しました。後日談ですが、この問題はCPCTF22当日の2日前に「EasyがEasyじゃない!」となって急遽作った問題です。実はMogumogu Pakupakuも2日前から作りました(やべ~~)。

Mogumogu Pakupaku

作問者:@0214sh7

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
25 0 2 0

問題文

スポーツチームの監督であるあなたは、選手たちを怒らせてしまったお詫びに大量のカップケーキをおごることにしました。

カップケーキを食べる選手が 人おり、 番目 () の選手は 秒間隔で 個のカップケーキを 個ずつ食べます。

ある日の正午ちょうどに全員が同時に 個目のカップケーキを食べました。その日の正午の他に全員が同時にカップケーキを食べる瞬間は来るでしょうか?来る場合は Yes を、来ない場合は No を出力して下さい。

制約

解法

最初に食べ終わる人が出るタイミングは で、 のLCMが 以下かどうかを判定する問題です。うまくオーバーフローを回避しましょう。

作者感想

開催2日前にテレビを見ていたらフードファイター5人が同時に食べるシーンがあったので、その時、ふと閃いた!このアイディアは、CPCTFの作問に活かせるかもしれない!となって問題ができました。easyが足りてなかったので丁度よかったね
当日レポートによるとWAが出まくったようです。オーバーフローを回避するステップが2回あったのでまあ当然かなと思います。

この問題のフラグがno more royal bitter juiceであるように、それとなーくウマ娘要素を盛り込んでいます。大会の後に気づいたのですが、モグモグパクパクという競走馬がいたみたいです。
tatyam「もぐもぐですわ」
0214sh7「ですわなんてどこにも書いてない」

当初ヒントにLCM(最大公約数)と書いてレビューしてくれたtatyamを困惑させました ごめん!

ebiがRange LthKth Queryのコミットを誤ってMogumogu Pakupakuにpushするという事件がありました。
ebi「force pushして消すか!」
0214sh7「やめろ!!!」

RTA in Honey traP

作問者:@aya_se

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
16 0 0 0

問題

あやせくんは、小悪魔ヒロインたちが登場するライトノベルゲーム『Honey traP』を、できるだけ短時間で完全攻略する遊び、いわゆる「RTA」に夢中です。

『Honey traP』には 個のシナリオがあり、 つのシナリオをプレイしてからクリアするまでにそれぞれ 時間ずつかかります (※既にそのシナリオを 度以上クリアしている場合も同様) 。

個のシナリオは 本の一方通行のルート (辺) によって 有向木 のグラフ構造で結ばれており、 番目 () のルートはシナリオ からシナリオ に入ります。また、葉 (出次数が ) のノードに相当するシナリオは各ヒロインの ED シナリオ となっており、これらの ED シナリオを全てクリアすることが最終目標です。

ゲームはシナリオ からスタートし、あるシナリオ () をクリアした後は、続けて以下のようにプレイします。

(A) シナリオ が ED シナリオではない場合
(B) シナリオ が ED シナリオの場合

あやせくんが最適にプレイした場合に、ゲームの完全攻略に必要な最短のプレイ時間を求めてください。

writeup

ライトノベルゲームって、大抵いくつかのルートがありますよね。1周目に色々なところでセーブしておいて、EDまで終わったら、ルート分岐イベント直前のセーブデータをロードして周回する、というのがお決まりのパターン。そんなノベルゲーあるあるをほぼそのまま競プロの問題にしてみました。

問題文には長々と書いてありますが、要するに

というのが本質になります。

シナリオ をセーブポイントに設定した場合に最大限短縮できる時間の和

(シナリオ の深さ) (シナリオ の子に含まれる ED シナリオ数)

で表せるので、 が最大となるようなシナリオ をセーブポイントに設定すれば、最小のプレイ時間

と求まり、これを出力すればよいです。

の計算には、各シナリオ ① 深さ および ② 子 ED シナリオ数 の計算が必要ですが、① 深さ 回の DFS (もしくは BFS) 、② 子 ED シナリオ数 回の DFS により求まるので、この問題は で解くことができます。

基本的にDFSのみで解ける問題でしたが、考察要素がやや多めだったからか、AC者数はPPCのEasy問の中で最も少ないという結果に。問題文がかなり長めだったのが、敬遠される一因になった可能性もありますね。当初は難易度Medium想定で作問し、writer陣との議論の結果Easyに下方修正した、という経緯もあったので、Easy問の中で最難関(?)なのは一応想定通りなのかな、という気もします。

AtCode Beginner ContestだとD問題で緑diffぐらいで出るノリかな、という想定なので、緑〜水コーダーあたりを目指す方にも是非解いていただきたいですね!

Shout Sucu

作問者:@0214sh7

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
22 1 0 0

問題文

シャウトすく君は、人間とは思えないほどの高音ボイスとそこから繰り出す強烈なシャウトで有名な歌手です。

待ちに待ったライブ当日、なんとシャウトすく君は喉を傷めてしまいました!これでは得意の高音ボイスを披露することができません!そこで苦肉の策として、シャウトすく君はときどき口パクを挟むことで誤魔化すことにしました。

最初、シャウトすく君は音階が 以下の音をノーダメージで発することができますが、音階が を超える音を出すと、音は発せるものの喉にダメージを受け、ノーダメージで発することができる音階が 以下から 以下に減少します。同様に、ダメージを 回受けた状態で音階が を超える音を出すと、 を超える音をノーダメージで発することができなくなります。また、ダメージを 回受けるとシャウトすく君は音を発することができなくなります。すなわち、以降は口パクしかできなくなります。

シャウトすく君が今日のライブで歌う曲は 個の音からなり、 番目の音では音階 の音を出します。シャウトすく君のマネージャーであるあなたは、シャウトすく君が今日のライブで最低でも何回口パクをすることになるのかを教えてください。

制約

解法

(選び方を 音目まで決めたときにダメージを 回受けた場合の口パクの回数の最小値) というDPで解くことができます。

作者感想

にしてNewbieで出すかこのままeasyで出すか迷いましたが、easyで出すことにしました。
実はこの問題はストーリーが先にできました。ebi「頭イカれてるだろ」
あるtraP部員の参加者にスーパーアホ設定って言われました。ぼくもそう思います。笑
Hzの音を出せるシャウトすく君、一体何者…?

Sum of Max

作問者:@tqk

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
25 0 0 0

問題

長さ の整数列 が与えられます。 から 個の整数を取り出す方法は 通りありますが、 個の取り出し方それぞれについて取り出した整数の最大値を求め、その総和を で割った余りを出力してください。(取り出した 個の整数が同じでも、取り出した位置が一つでも違えば、別の組として数えます。)

すなわち、

を出力してください。

制約

解法

をソートしても答えは変わらないので、します。
の場合でも、 の方が大きいものとして考えると、各 について が最大値になる取り出し方は、 から 個 と を選ぶような取り出し方なので、 通り存在します。

したがって、 が答えになります。

実装方法がわからない? 「1000000007 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜 を参考にすると良いでしょう。

解説文: @tqk, @tatyam

作者感想

数えるものを工夫するやつすき

Medium

Changed My Mind

作問者:@season1618

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
12 0 0 0

問題文

頂点 辺の単純連結無向グラフが与えられます。このグラフの頂点には から の番号が、辺には から の番号がつけられています。辺 は長さが で、頂点 と頂点 を双方向に結んでいます。

西行君がこのグラフ上を旅します。西行君は最初頂点 から移動を始め、頂点 に向かっていましたが、頂点 に着いたとき気が変わって頂点 に向かうことにしました。このとき、 としてあり得るものを全て求めてください。ただし西行君は合理的なので、常に目的地までの最短経路 (の一つ) を通るものとします。



解法

最初の目的地がX(≠B)のとき、経路にAが含まれる条件はS−A−XがS−Xの最短経路の一つとなること、つまりdist(S,A)+dist(A,X)=dist(S,X)となることです。よってS,Aを始点としてダイクストラ法を2回行うことでO(MlogN)で求めることができます。

余談

大岡山キャンパスを歩いてたら思い付きました(食堂行こうとしたけど面倒くさくて直帰を選択した)。この題材は8割以上の確率で既にある気がします。登場人物の名前は適当でも良かったんだけど、日本各地を旅した偉人として知られる西行にしました。

Lower Bound on Divisors

作問者:@tqk

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
8 0 0 0

問題

整数列 が与えられます。
整数 に対して関数

( の約数のうち 以上で最小のもの)

と定義するとき、 を求めてください。

制約


()

解法

実装例

#include "bits/stdc++.h"
using namespace std;

int main(){
	const int M = 1e6+10; // >= max A_i
	int N; cin >> N;
	vector<int> A(N), c(M, 1<<30);
	for(int i = 0; i<N; ++i)cin >> A[i];

	long long ans = 0;
	for(int m = M-1; m>0; --m){ // O(M log M)
		for(int i = m; i<M; i += m){
			c[i] = m; // c[m], c[2*m], c[3*m], ... (約数に m がある全ての i について c[i])を m に更新します。
		}
		if(m<=N)ans += c[A[m-1]]; // f(A[m], m) = c[A[m]] を答えに加算します。
	}
	cout << ans << endl;
	return 0;
}

作者感想

Next Shift

作問者:@tqk

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
9 0 0 0

問題

新学期が始まって 日が経ちました。 日間毎日、日直に選ばれる生徒は先生のその日の気分で決められていました。しかし、不満が出たので、 日目から下で示す新しいルールに従って日直が選ばれるようになりました。

新しいルール

人の生徒がいて、各生徒には出席番号 から がつけられています。 日目の日直の出席番号は でした。各 について、 日目の日直の生徒の出席番号 を求めてください。

制約

解法

()日目の日直は です。 () 日目は、 人の生徒が周期的に選ばれます。その周期がどのようになるかを求めることができれば、 () 日目の日直は 周期の番目が答えとなります。

数列 に含まれる値の種類数を とします。周期の前から 個は に含まれない値を小さい順に並べたものになります。それ以降は の各値に対して最後に表れるインデックスをキーとしてソートした順に並べたものになります。

前半 個について、 に含まれていない 以下の値を適切に管理することができれば高速に求めることができます。 に含まれていない 以下の値を区間として ([,] に含まれる整数は に含まれない) として管理します。それに加えて各区間の右端の値 以下の に含まれていない整数の個数を管理します。これによって二分探索を用いることにより、 周期における () 番目の出席番号を で求めることができます。

後半 個については前計算としてソートをすることで で求めることができます。

以上よりクエリ で答えを求めることができるので、全体の計算量は となります。

解説文: @ebi, @tqk

作者感想

Reversible Dictionary

作問者:@season1618

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
4 0 0 0

問題文

個の英小文字からなる文字列 が与えられます。以下の条件を満たすように文字列の列 を作るときの、 の最大値を求めてください。

条件

文字列 に対して、 を左右反転させた文字列を と定義する。

制約

解法

文字列の性質は特に関係ありません。一方の順序についてソートして他方の順序についてLISを求めれば良いです。

余談

LISって二つの順序について整合するような最大列なのかーという気付きを得たのでこういう問題を考えてみました(自分はそういう見方をしたことがなかった)。正答者は4人で、結構少ないと感じました。問題の配置の関係なのかな。

Weirdo

作問者:@tqk

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
6 0 0 0

問題

世界には 種類の人間がいます。正直者嘘つき、そして変質者です。

種類が不明な 人の人間がおり、 から までの番号がつけられています。それぞれの人間は、 人の人間のうちから 人を選び、その人が正直者嘘つきであるかの発言をしました。人 () は以下のように発言しました。

各種類の人間はそれぞれ以下のような発言をすることが分かっています。

人間の種類の性質を満たすように各人間の種類を決めたときの、正直者の人間の数の最大値を求めてください。

制約

解法


実装例

#include "bits/stdc++.h"
using namespace std;

class UnionFind{
public:
	vector<int> par, rank, hon; // hon: 正直者の数 (i がそのグループの root のとき、そのグループの)
	UnionFind(int n){ init(n); }
	void init(int n){
		par.resize(2*n), rank.resize(2*n), hon.resize(2*n);
		for(int i=0; i<2*n; ++i)par[i] = i, hon[i] = i%2; // 正直者 1 人のみのグループが 1
	}
	int root(int x){ return x==par[x]?x:par[x]=root(par[x]); }
	bool same(int x, int y){ return root(x)==root(y); }
	void unite(int x, int y){
		x = root(x), y = root(y);
		if(x==y)return;
		if(rank[x]<rank[y]){
			par[x] = y;
			hon[y] += hon[x];
		} else{
			par[y] = x;
			hon[x] += hon[y];
			if(rank[x]==rank[y])++rank[x];
		}
	}
};

int main(){
	int n, a, b, ans = 0;
	cin >> n;
	UnionFind t(n); // 頂点数 2*n. 頂点 2*i が人 i が嘘つきである場合、2*i+1 が正直者である場合に対応
	for(int i=0; i<n; ++i){
		cin>>a>>b;
		t.unite(2*i+1, 2*a+b); // b==1のとき正と正、b==0のとき正と嘘をつなぐ
		t.unite(2*i, 2*a+1-b); // b==1のとき嘘と嘘、b==0のとき嘘と正をつなぐ
	}
	for(int i=0; i<n; ++i){
		if(!t.same(2*i, 2*i+1)){ // 矛盾が起きていないなら、正直者が多くなるほうを選び答えに足す
			ans += max(t.hon[t.root(2*i)], t.hon[t.root(2*i+1)]);
		}
		t.hon[t.root(2*i)] = t.hon[t.root(2*i+1)] = 0; // 1 回見たらグループの正直者の数を 0 にすればダブルカウントしない
	}
	cout << ans << endl;
}

作者感想

Hard

Divisor Array

作問者:@ebi

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
4 0 0 0

問題文

正整数 が与えられます。 を小さい方から 個の素数の積とします。
以下の条件を満たす長さ の数列 はいくつありますか?答えを で割った余りを出力してください。

条件

制約


writeup

で考え、その結果を用いて の場合を求めるという方針がキーでした。

のときは、 (先頭から 項まで決めた際に、総和が であるような数列の個数)という dp を考えることで求めることができます。この dp は遷移に imos 法を用いることで となります。

のときは、素因数分解した結果から約数の個数を求める計算に注目するとDirichlet積になります。繰り返し 乗法を用いることで計算量は となります。


Hardということもあって難しい問題だと思います。思っているより解いてくれてとても嬉しいです、ありがとうございます。
yukicoderに移植したのでぜひ!

Range LthKth Query

作問者:@tatyam

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
1 0 0 0

問題文

要素の整数列 と、整数 が与えられます。

以下の形式のクエリが 個与えられるので、それぞれについて答えを求めてください。


解説

元問題の L 番目の K 番目の数 の解法は答えで二分探索でした。しかし、 が大きいのでこれは使えません。 とかなり小さいことに注目すると、全ての区間に対して「 番目の数」を求められそうです。これを使って全ての区間に対して「 番目の 番目の数」を求めてみましょう。

次元平面に「 番目の数」を 個ずつ永続 次元 BIT に追加して二分探索で答える、などいろいろな解法で になりますが、

ことに注目すると にすることができます。

感想

作問テク : 既存の問題をアレンジする を使ったら難しい問題ができて解けてしまいました。
の時点で橙 Diff くらいあって、参加者層的に solved 1 も納得です。
東工大 OB の rian さんに で解かれてしまいました…
Python で通せるように調整していたので仕方ないかな〜

yukicoder に移植したので解いてね〜〜

Separate and Attach

作問者:@0214sh7

AC者数

ヒントなし ヒント1 ヒント2 ヒント3
2 0 0 1

問題文

の順列 が与えられます。
あなたは順列 に以下の操作をすることができます。

操作

あなたはこの操作を何回か繰り返すことで に一致させたいです。
最低で何回操作を行う必要がありますか?なお、この操作を有限回行うことで に一致させることができることが証明できます。

制約

解法

におけるのような、連続かつ増加するような列のうち極大であるものの個数を とおくと、答えは になります。

作者感想

同じ難易度内ではアルファベット順に並ぶという仕様の影響で最後に配置されましたが、おそらくHard最易問題だと思います。というのも、「よくわからんけどこんな感じで通るやろ」が通ることが想定されていたためです。最初に配置されてたらもうちょっと解かれてたかな…?

実はこの問題、16問の中で一番最初に完成した問題でした(最後はMogumogu Pakupaku)。なのでARCとかでしれっと爆破されないかヒヤヒヤしていました。我ながらいい問題ができたと思います。

これもyukicoder に移植しました。

おわりに

ジャッジのトラブルでJavaの提出が上手くいかないことがありました。各言語でのジャッジチェックは正直怠ったなと思います。これは次回に活かします。

位置が影響してか、Reversible DictionaryとSeparate and Attachは想定より正答数が少ない結果になりました。問題の並び順はもう少しなんとかしたかったですね。次回は問題IDを振ろうと思います。

来年もCPCTFでお会いしましょう。

目次に戻る

ebi icon
この記事を書いた人
ebi

競技プログラミングが好きです。

tatyam icon
この記事を書いた人
tatyam

競技プログラミングと音ゲーをしています。 AtCoder銀冠 ICPC 2020/21 Yokohama 3 位, WF 15 位 (good_yamikin) ICPC 2021/22 Yokohama 3 位 (tonosama) ICPC 2022/23 Yokohama 1 位 (tonosama)

tqk icon
この記事を書いた人
tqk

あ...あ...

0214sh7 icon
この記事を書いた人
0214sh7

きいろこーだー アルゴリズム班の元班長さんです

aya_se icon
この記事を書いた人
aya_se

サウンドや競プロをやっています。

season1618 icon
この記事を書いた人
season1618

数学と物理と情報工学

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2021年8月12日
CPCTFを支えたWebshell
mazrean icon mazrean
2021年5月19日
CPCTF2021を実現させたスコアサーバー
xxpoxx icon xxpoxx
2023年9月26日
traP コンペ 2023 夏 sponsored by ピクシブ株式会社 運営後記
abap34 icon abap34
2023年7月13日
アルゴリズム班はやとき王選手権「競(けい)プロ」を開催しました!
abap34 icon abap34
2022年10月11日
アルゴリズム班にKaggle部を設立し、初心者向けデータ分析体験会を開催しました!
abap34 icon abap34
2021年5月16日
CPCTFを支えたインフラ
mazrean icon mazrean
記事一覧 タグ一覧 Google アナリティクスについて 特定商取引法に基づく表記