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

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

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

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

目次

Newbie

• Addition Construct
• Nkuth's Plus Notation
• State of the clock

Easy

• Garbage Bags Optimization
• Mogumogu Pakupaku
• RTA in Honey traP
• Shout Sucu
• Sum of Max

Medium

• Changed My Mind
• Lower Bound on Divisors
• Next Shift
• Reversible Dictionary
• Weirdo

Hard

• Divisor Array
• Range LthKth Query
• Separate and Attach

おわりに

Newbie

Addition Construct

作問者:@tqk

AC者数

問題

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

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

• $a+b=N$
• $1\le a,b\le 5000$

制約

• $2\le N\le 10000$
• 入力は全て整数

解法

• 仲良く分ける$(a=\left[\frac{N}{2}\right]$ と $b=N-\left[\frac{N}{2}\right])$などの方法があります。

作者感想

• サンプル入出力のように tqk さんが食べるドーナツの数を最大化するには、$a=\min (N-1,5000),b=N-a$ などとすればいいです。

Nkuth's Plus Notation

作問者:@tqk

AC者数

問題

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

• $l{+}^{1}r:=l+r$
• $l{+}^{n+1}r:=\underset{r\mathrm{copies}\mathrm{of}l}{\underbrace{l{+}^n(\cdots (l{+}^n(l{+}^{n}l))\cdots )}}$

例えば、$3{+}^{2}4=3{+}^1(3{+}^1(3{+}^{1}3))=12$ や、$2{+}^{3}3=8$ などが成り立ちます。

$A{+}^{N}B$ を求めてください。

制約

• $1\le N\le 3$
• $1\le A,B\le 9$
• 入力は全て整数

解法

• $N=1$ のとき $A+B$、$N=2$ のとき $AB$、$N=3$ のとき $A^B$ が答えです。

作者感想

• $N$ が大きいとどうするんですか?

State of the clock

作問者:@aya_se

AC者数

問題

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

$0\le A,B<360$

writeup

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

• 短針は0.5°/m (30°/h)、長針は6°/m (360°/h)動く
• 短針の角度が決まると、長針の角度は一意に定まる

という性質から判定することができます。迷ったら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者数

問題文

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

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

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

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

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

$K\le N\le 10^5$

writeup

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

Mogumogu Pakupaku

作問者:@0214sh7

AC者数

問題文

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

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

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

制約

• $1\le N\le 10^5$
• $1\le A_i\le 10^9$ ($1\le i\le N$)
• $1\le B_i\le 10^9$ ($1\le i\le N$)
• 入力は全て整数

解法

最初に食べ終わる人が出るタイミングは $F={\min }_{i\in [1,N]}{A}_i(B_i-1)$ で、 $A$ のLCMが $F$ 以下かどうかを判定する問題です。うまくオーバーフローを回避しましょう。

作者感想

開催2日前にテレビを見ていたらフードファイター５人が同時に食べるシーンがあったので、その時、ふと閃いた！このアイディアは、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者数

問題

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

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

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

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

(A) シナリオ $i$ が ED シナリオではない場合

• 全ゲームプレイを通して $1$ 回 のみ、セーブ機能 を使い、シナリオ $i$ を セーブポイント に設定することができる (※以降セーブポイントは変更できない) 。
• シナリオ $i$ とルートで 直接 結ばれているシナリオのうちいずれかに進み、そのシナリオをプレイする。

(B) シナリオ $i$ が ED シナリオの場合

• 全ての ED シナリオをクリアした場合、ゲームのプレイを終了する。
• まだクリアしていない ED シナリオが残っている場合、シナリオ $1$ に戻ってはじめからプレイするか、もしくは セーブポイント に設定したシナリオとルートで 直接 結ばれているシナリオのうちいずれかに進み、そのシナリオをプレイする。

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

$N\le 10^5$

writeup

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

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

• どのシナリオをセーブポイントに選べば、最も時間短縮できるか？

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

シナリオ $i$ をセーブポイントに設定した場合に最大限短縮できる時間の和 ${\text{Save}}_i$ は

${\text{Save}}_i=$(シナリオ $i$ の深さ$+1$) $\times$ (シナリオ $i$ の子に含まれる ED シナリオ数$-1$)

で表せるので、${\text{Save}}_i$ が最大となるようなシナリオ $i_{\max }$ をセーブポイントに設定すれば、最小のプレイ時間 $T_{\min }$ は

$$T_{\min }=\sum _{v\in EDシナリオ}(vの深さ+1)-{\text{Save}}_{i_{\max }}$$

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

${\text{Save}}_i,T_{\min }$ の計算には、各シナリオ $i$ の ① 深さ および ② 子 ED シナリオ数 の計算が必要ですが、① 深さ は $1$ 回の DFS (もしくは BFS) 、② 子 ED シナリオ数 は $1$ 回の DFS により求まるので、この問題は $O(N)$ で解くことができます。

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

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

Shout Sucu

作問者:@0214sh7

AC者数

問題文

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

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

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

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

制約

• $1\le N\le 10^4$
• $0\le K\le 100$
• $0\le A_i\le 10^9$
• $10^9\ge X_0>X_1>\cdots >X_{K-1}\ge 0$
• 入力は全て整数

解法

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

作者感想

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

Sum of Max

作問者:@tqk

AC者数

問題

長さ $N$ の整数列 $A=(A_1,A_2,\dots ,A_N)$ が与えられます。$A$ から $K$ 個の整数を取り出す方法は $\left(\genfrac{}{}{0ex}{}{N}{K}\right)$ 通りありますが、$\left(\genfrac{}{}{0ex}{}{N}{K}\right)$ 個の取り出し方それぞれについて取り出した整数の最大値を求め、その総和を $998244353$ で割った余りを出力してください。(取り出した $K$ 個の整数が同じでも、取り出した位置が一つでも違えば、別の組として数えます。)

すなわち、

$$\left(\sum _{1\le i_1<i_2<\cdots <i_K\le N}\max \{A_{i_1},A_{i_2},\dots ,A_{i_K}\}\right)\mathrm{mod}998244353$$

を出力してください。

制約

• $1\le N\le 2\times 10^5$
• $1\le K\le N$
• $1\le A_i\le 10^9$ ($1\le i\le N$)
• 入力は全て整数

解法

$A$ をソートしても答えは変わらないので、します。
$A_i=A_{i+1}$ の場合でも、$A_{i+1}$ の方が大きいものとして考えると、各 $i=1,\dots ,N$ について $A_i$ が最大値になる取り出し方は、$A_1,A_2,\dots ,A_{i-1}$ から $K-1$ 個 と $A_i$ を選ぶような取り出し方なので、$\left(\genfrac{}{}{0ex}{}{i-1}{K-1}\right)$ 通り存在します。

したがって、$\left(\sum _{i=K}^N\left(\genfrac{}{}{0ex}{}{i-1}{K-1}\right)\times A_i\right)\mathrm{mod}998244353$ が答えになります。

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

解説文: @tqk, @tatyam

作者感想

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

Medium

Changed My Mind

作問者:@season1618

AC者数

問題文

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

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

$N\le 10^5$
$M\le 10^5$
$S\ne A\ne B$

解法

最初の目的地が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者数

問題

整数列 $A=(A_1,A_2,\dots ,A_N)$ が与えられます。
整数 $n,m(n\ge m>0)$ に対して関数 $f(n,m)$ を

$f(n,m):=$ ( $n$ の約数のうち $m$ 以上で最小のもの)

と定義するとき、$\sum _{i=1}^{N}f(A_i,i)$ を求めてください。

制約

$N\le 10^6$
$i\le A_i\le 10^6$ ($1\le i\le N$)

解法

• $M:=\underset{i}{\max }{A}_i$ とします。
• $i$ の約数のうち $m$ 以上で最小のものを表す数列 $c_i$ を作り( $1\le m<M$ )、$m$ を降順に動かしながら $c$ の値を更新し、($m\le N$ の場合は) $f(A_m,m)=c_{A_m}$ を答えに加算します。
• $\sum _{i=1}^M\frac{1}{i}\in O(\log M)$ より、計算量は $O(M\log M)$ です。(参考 : 調和級数 - Wikipedia)

実装例

#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;
}

作者感想

• pypy 使ってください
• 愚直解(計算量に ​ がつく、約数全列挙など)を落とそうと頑張っていたら、ジャッジが手元より遅くて(↑sol_tqk が最大 0.8s くらい)、 ​ がつかない解法まで定数倍で落ちたりしたらしいです。ごめんなさい
• ちなみに頑張ると ​ がつく解法でも通せます。ごめんなさい 2 (これは知ってて出したけど)
  • tatyam の愚直解、ぼくの想定解より速いんだけどなんで? 笑 って一生言ってた

Next Shift

作問者:@tqk

AC者数

問題

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

新しいルール

• まだ日直に選ばれたことのない生徒がいるとき、そのうち最も出席番号が小さい生徒が選ばれる
• そうでないとき、最後に日直に選ばれた日付が最も古い生徒が選ばれる

$M$ 人の生徒がいて、各生徒には出席番号 $1$ から $M$ がつけられています。$i$ $(1\le i\le N)$ 日目の日直の出席番号は $A_i$ でした。各 $1\le i\le Q$ について、 $B_i$ 日目の日直の生徒の出席番号 $C_i$ を求めてください。

制約

• $1\le N\le 10^5$
• $1\le M\le 10^{18}$
• $1\le A_i\le M$ ($1\le i\le N$)
• $1\le Q\le 10^5$
• $1\le B_i\le 10^{18}$ ($1\le i\le Q$)
• 入力は全て整数

解法

$i$ ($1\le i\le N$)日目の日直は $A_i$ です。$i$ ($>N$) 日目は、 $M$ 人の生徒が周期的に選ばれます。その周期がどのようになるかを求めることができれば、 $i$ ($>N$) 日目の日直は 周期の$(i-N\mathrm{mod}M)$番目が答えとなります。

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

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

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

以上よりクエリ $O(\log N)$ で答えを求めることができるので、全体の計算量は $O(N\log N+Q\log N)$ となります。

解説文: @ebi, @tqk

作者感想

• easy で問題設定から作ってたら意外とだるくなって medium になった
• いい実装問になってよかった
• 最初は log が 2 個つく解法(にぶたん内でにぶたん)だったけど @ebi さんが別解出してくれた

Reversible Dictionary

作問者:@season1618

AC者数

問題文

$N$ 個の英小文字からなる文字列 $S_1,S_2,\dots ,S_N$ が与えられます。以下の条件を満たすように文字列の列 $T=(T_1,T_2,\dots ,T_{|T|})$ を作るときの、$|T|$ の最大値を求めてください。

条件

文字列 $A$ に対して、$A$ を左右反転させた文字列を $\text{rev}(A)$ と定義する。

• $T_i$ は $S_1,S_2,\dots ,S_N$ のいずれか ($1\le i\le |T|$)
• $T_{i+1}$ は $T_i$ より辞書順で真に大きい ($1\le i\le |T|-1$)
• $\text{rev}(T_{i+1})$ は $\text{rev}(T_i)$ より辞書順で真に大きい ($1\le i\le |T|-1$)

制約

• $N$ は整数
• $1\le N\le 10^4$
• $S_i$ は英小文字からなる文字列 ($1\le i\le N$)
• ${\sum }_{i=1}^N|S_i|\le 10^6$ ($|S_i|$ は文字列 $S_i$ の長さを表す)
• $S_i\ne S_j(1\le i<j\le N)$

解法

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

余談

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

Weirdo

作問者:@tqk

AC者数

問題

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

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

• $B_i$ が $0$ のとき :「人間 $A_i$ は嘘つきだ。」
• $B_i$ が $1$ のとき :「人間 $A_i$ は正直者だ。」

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

• 正直者 : 正直者のことを正直者だと、または、嘘つきのことを嘘つきだと発言する。
• 嘘つき : 正直者のことを嘘つきだと、または、嘘つきのことを正直者だと発言する。
• 変質者 : 変質者のことを正直者だと、または、変質者のことを嘘つきだと発言する。

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

制約

• $1\le N\le 2\times 10^5$
• $0\le A_i\le N-1$ ($0\le i\le N-1$)
• $B_i\in \{0,1\}$
• 入力は全て整数

解法

• ある人間の種類を正直者だと仮定すると、その人間の発言から、ある人間の種類が決まることがあります。これを繰り返し行うことを考えます。

• 各人間は、いくつかのグループに分けられて、そのグループ内のある人間の種類を決めると、そのグループ内の全ての人間の種類が決まります。

• また、そのグル＝プは、以下のどちらか一方の性質を満たします。

  • 正直者と嘘つきだけ含まれる。正直者と嘘つきを反転した 2 つの場合のみ性質を満たす。
  • 全員変質者である。

• よって、各グループのうち、前者のタイプのグループであるもの全てについて、 $\max ($(含まれる正直者の数)$,$(含まれる嘘つきの数)$)$ を求めれば、その和が答えです。

• 頂点数 $2N$ のグラフを考えて、頂点たちに 人間 $i$ が正直者である状態、人間 $i$ が嘘つきである状態を割り当てます。
• $2$ つの状態が同時に起こる場合に、対応する $2$ つの頂点が連結になるようにします。
• ある人間が正直者である状態と嘘つきである状態の頂点が連結の時、仮定が間違っていたとして変質者に対応させます。
• 正直者の数を数えながらグラフを作ることに注意して、実装します。
• グループ分けを実装するのに UnionFind が便利です。

実装例

#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;
}

作者感想

• 問題文を正確に書くのがむずかった
• 他の問題も日本語や論理的なところなど校正してくれて本当にありがとうございました:pray::pray::pray: @tatyam, @ebi

Hard

Divisor Array

作問者:@ebi

AC者数

問題文

正整数 $N,M,K$ が与えられます。$D$ を小さい方から $K$ 個の素数の積とします。
以下の条件を満たす長さ $N+1$ の数列 $A=(A_0,A_1,\dots ,A_N)$ はいくつありますか？答えを $998244353$ で割った余りを出力してください。

条件

• $A_0=D$
• $i=1,\dots ,N$ について、$A_i$ は $\prod _{j=0}^{i-1}{A}_j$ の正の約数である。
• $\prod _{i=1}^N{A}_i$ の正の約数の個数は $M$ 以下である。

制約

• $1\le N\le 10^9$
• $1\le M\le 2000$
• $1\le K\le 10^9$
• 入力に含まれる値は全て整数である

writeup

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

$K=1$ のときは、 $dp[i][j]:=$(先頭から $i$ 項まで決めた際に、総和が $j$ であるような数列の個数)という dp を考えることで求めることができます。この dp は遷移に imos 法を用いることで $O(M^2)$ となります。

$K>1$ のときは、素因数分解した結果から約数の個数を求める計算に注目するとDirichlet積になります。繰り返し $2$ 乗法を用いることで計算量は $O(M\log M\log K)$ となります。

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

Range LthKth Query

作問者:@tatyam

AC者数

問題文

$N$ 要素の整数列 $A=(A_1,A_2,\dots ,A_N)$ と、整数 $K,L$ が与えられます。

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

• 整数 $l,r$ が与えられる。整数列 $B=(A_l,A_{l+1},\dots ,A_r)$ の $L$ 番目の $K$ 番目の数 を求めよ。

$N\le 2\times 10^3$
$Q\le 2\times 10^5$

解説

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

$2$ 次元平面に「$K$ 番目の数」を $1$ 個ずつ永続 $2$ 次元 BIT に追加して二分探索で答える、などいろいろな解法で $O(N^2(\log N{)}^3)$ になりますが、

• 「$K$ 番目の数」は $N$ 種類しかないのでまとめて追加できる
• 「$K$ 番目の数」は区間の長さが長いほど小さい
• 「$L$ 番目の $K$ 番目の数」は区間の長さが長いほど小さい

ことに注目すると $O(N^2\log N)$ や $O(N^2)$ にすることができます。

感想

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

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

Separate and Attach

作問者:@0214sh7

AC者数

問題文

$1,2,\dots ,N$ の順列 $P,Q$ が与えられます。
あなたは順列 $P$ に以下の操作をすることができます。

操作

• $P$ から (連続とは限らない) 部分列を任意に取り出し、$S$ とおく。
• $P$ の要素のうち $S$ に含まれない要素を $P$ の順番で結合したものを $T$ とおく。
• $P$ を $S,T$ をこの順番で結合したもので置き換える。

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

制約

• $1\le N\le 10^5$
• $P,Q$ は長さ $N$ の順列
• 入力は全て整数

解法

$(1,4,6,2,5,3,7)$における$(1,2,3),(4,5),(6,7)$のような、連続かつ増加するような列のうち極大であるものの個数を $M$ とおくと、答えは $\lceil {\log }_{2}M\rceil$ になります。

作者感想

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

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

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

おわりに

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

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

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

目次に戻る