この記事は 新歓ブログリレー2026 47日目の記事です。
はじめに
どうも、25Bのt-okaと申します。
先日行われたCPCTF2026において、PPCを2題出題しました。作問時に考えたことなどをここに記しておこうと思います。せっかくなので没になった案も抜粋して紹介します。
他の作問者の方のwriteupもいずれ出ると思います。
I Love DAG[Lv.2]
問題文はこちら
コメント
ちょっとした一発ネタの問題です。問題名の"DAG"は"Directed acyclic graph"の略称で、サイクルを持たない有向グラフを指します。
もしサイクルが存在する場合、それを抜き出すと、頂点番号が大きい方から小さい方へ向かう辺と、小さい方から大きい方へ向かう辺の両者が存在します。
したがって全ての辺について、頂点番号が小さい方から大きい方へ有向辺を張っていけば、サイクルができることはありません。これに気づけば、簡単な実装のみでACすることができます。
もしリアクティブ問題ではなかった(最初からグラフが与えられていた)場合、BFSやDFSを用いて、移動した方向に辺の向きを定めるという方法も有効ですね。
結果
かなり多くの正解者が出ました。Lv.2の中では比較的簡単だったかもしれません。
グラフ問題ですが専用の難しいテクニックは必要としないので、今回初めて競技プログラミングを挑戦したという方もこれをきっかけにグラフに馴染んでもらえたら嬉しいです！
All Distance is Square Number[Lv.4]
問題文はこちら
背景
グラフ構築問題です。なんとなくパスの重みの総和に関する構築問題を作りたいと思い立ち、試しにパスの辺の重みの総和が平方数になるようにするにはどうすれば良いか考えていた所、この問題が完成しました。
まず、始点を一つの頂点に限定して考えてみましょう。
このグラフにおいて始点を頂点 に限定したとき、各頂点に移動していくとパスの辺の重みの総和が常に奇数和、つまり平方数となります。
では始点が頂点 でない場合はどうしましょう？はじめに私は以下のように考えました。
とりあえず、終点の頂点番号が始点の頂点番号よりも大きい場合のみを考えます。そうでない場合は逆順のパスを考えれば良いです。
頂点 からスタートしたら、青い辺を辿って頂点 に移動します。ここまでのパスの辺の重みの総和は奇数和です。そして、赤い辺を辿って頂点 に移動することで、奇数和を保ったまま移動することができました。頂点 を始点に青い辺を辿って移動してきた場合と同じ総和になっています。したがって、残りは青い辺を辿って終点まで移動すれば良いです。
いい感じの構成案ができたので、とりあえず問題として整えてみます。
頂点数 を入力で与え、以下の条件を満たすグラフを作らせることにしましょう。
- グラフは単純である
- 任意の頂点間に対して、辺の重みの総和が平方数であるようなパスが存在する
- 頂点数を , 辺の数を とすると
これで完成！！！！！やったね！！！！！
と、言いたいところなのですが、LLMなどでテストプレイを行っていると、以下のような別解が見つかりました。
頂点 と の間に重み の辺を貼り、それ以外は上図のように重み の辺を張ります。このようにすると、確かに各頂点間に対して、辺の重みの総和が平方数となるパスが存在してしまいます（各自確かめてみて下さい）。ちなみにこれ以外のやり方もいくつかあるようです。
...これはいけませんね。この別解自体は綺麗ではありますが、許す解法を多くしすぎてしまうと難易度が下がりますし、解法を模索する楽しみが減ってしまうように感じます。
ではどうしましょう？何か条件を追加して上手いこと調整する必要がありそうです。そういえば最初に考えた構築方法は、実はまだ平方数の性質を利用しておらず、平方数以外でも成立するものでした(正整数を無数に含む集合であれば、上手く部分集合を取って、小さい順に並べて階差を取れば良いです)。せっかく辺の重みが奇数列になっているので、上手くそれを利用して、より多くの条件を満たすグラフにしたいものです。
そこで、以下のようなグラフを考えました。
最初に考えたグラフからは、赤い辺が変化しています。端点の一方が、頂点 から へ変化しています。今までは、青い辺を辿って頂点 に戻り、赤い辺を辿っていましたが、今回は頂点 に戻るので、頂点 と を結ぶ 重み の辺を通りません。そこで、その重みを赤い辺の重みに吸収させて辻褄を合わせてみましょう。
すると、青い辺の重みが奇数列、赤い辺の重みが偶数列となり、全ての辺の重みが相異なるグラフになりました！これなら先ほどの別解も潰せますし、良い感じの難易度になりそうです。
結局、満たすべき条件は以下のようになりました。
- グラフは自己ループを含まない(多重辺はあっても良い)
- 任意の頂点間に対して、辺の重みの総和が平方数であるようなパスが存在する
- 頂点数を , 辺の数を とすると
- 全ての辺の重みは相異なる 以上 以下の整数
グラフの構成に多重辺が必要になったので、単純グラフという条件は撤廃しました。また、別解のリスクを減らすため、辺の重みの上限もギリギリにしておきました。
結果
他のPPC Lv.4と同じくらいの正解者数となりました。自分で作った問題の難易度って分かりにくいので一安心。
解法についてですが、全探索のようなことをして通している提出がいくつかありました。
例えば、条件を満たしている 頂点 辺のグラフに、 頂点と 辺を辺の重みと位置を全探索して追加する、ということを繰り返してグラフを構成しているものがありました。また、あらかじめ手元でそれを行ったもの(もしくは手動で気合いで見つけたもの...？)を埋め込んで提出していたものもありました。
この解法は (と辺の重みの上限)がもっと大きければ防ぐことができた可能性があります。ジャッジの都合上、辺の重みの総和が平方数となるようなパスを出力してもらう必要があり、それに かかるので、制約は としていました。
ですが、インタラクティブ形式にして、適切な回数だけパスを質問すれば、 をより大きくすることが可能です。こうした方が良かったかも知れませんね。
後から思うことは色々ありますが、個人的には良い感じの問題が作れたかなと思うので満足です。面白い別解を見つけたらぜひ教えて下さい。
おまけ
以下の条件を全て満たすグラフを考えて下さい。
- グラフは単純
- 任意の頂点間に対して、辺の重みの総和が平方数であるような単純パスが存在する
- 頂点数を , 辺の数を とすると
- 全ての辺の重みは等しい
- 全ての辺の重みは正整数
Find Fake[Lv.2](没)
ここからは没問題です。
問題概要
インタラクティブ問題です。 枚の金貨のうち 枚だけ偽物です。偽物は僅かに軽いので、天秤を 回まで使用し、偽物を特定して下さい。無理ならそれを報告して下さい。
コメント
有名な論理パズルの拡張です。偽物の枚数を増やすなど、良い感じに設定を複雑にしてLv.4くらいで出せたら良いなと考えていましたが、上手くいきませんでした。
Zookeeper's Crossing the River[Lv.3](没)
問題概要
川渡り問題と呼ばれる問題があります。狼と羊とキャベツを上手いこと川の対岸に運ぶ問題です。これと同じように 種類の動物に対して、捕食-非捕食関係が与えられるので、対岸に運ぶ方法を一つ構成して下さい。無理ならそれを報告して下さい。ただし、ボートはあなたを覗いて、一度に最大 匹の動物を運ぶことができます。このとき、捕食-非捕食関係にある2匹を同時にボートに乗せてはいけません。
コメント
有名な論理パズルの拡張2です。捕食-非捕食関係をグラフに落とし込み、二部グラフの問題で考えることを想定しています。結局没になったので深くは考えていないのですが、想定より難しい(Lv.4になりうる)という説が浮上していました。
最後に
CPCTF2026は無事終了しました。参加して下さった皆様、ありがとうございました。そして、作問陣の他の方々には、問題案に対する意見やアドバイス、問題文の修正案など、数えきれないほどサポートして頂きました。本当に助かりました...。
来年CPCTF作問に携わるかは分かりませんが、やはり作問は面白いですね。今後も思いつき次第問題を作って行きたいと思います。
とりあえずこのブログは終わり！またね！！
明日
明日の投稿者は @Lachite さんと @2251799813685248 さんです。お楽しみに。
