はじめに

こんにちは、19Mのhukuda222です。最近は研究にかまけており、traPではあまり活動していませんでした。そんなある日、部内SNSでCPCTF2021の作問者の募集を見て「そういえば、CPCTFの作問やってみたかったけどやってこなかったな」と思い立ち、問題を提供させていただきました。競プロは多少経験があるもののCTFの方はからっきしなので、提供したのはPPC問が大半です。

この記事ではCPCTF2021で私が作った問題のwriteupを書いていきます。問題以外に関する記事は後日出るそうです。

作問者writeup

以下の10問を作問しました。

Newbie/Hello World
Misc/Shortest Letter
OSINT/Secret Account
OSINT/Where is the Museum?
PPC/Elementary School
PPC/Contrarian Otaku
PPC/Mountain
PPC/Simple Mahjong
PPC/Anime Watching
PPC/Score Calculator

Newbie/Hello World(10点,60AC)

PPCに不慣れな人向けの問題です。Newbie/Call And Responseよりも簡単な気がするんですが、その割に解いた人が少なかったのが不思議でした。ヒント3を開けると提出可能な言語での回答が見られます。

Misc/Shortest Letter(100点,50AC)

Miscは雑多な問題があるジャンルなんですが、その中でもかなりネタ寄りの問題です。問題名をググると、世界一短い手紙のやりとりとして有名なヴィクトル・ユーゴーの逸話を紹介するページが先頭に出てきます。彼は出版社に自著の売り上げを聞く際?と書かれた手紙を送り、出版社は!と返しました。?のasciiコードが問題文である63で、!のasciiコードがFLAGです。

問題文が異常に短かったら面白いよなと思って作った問題です。ヒント3まで見ると0秒でFLAGがわかるので、終了際に点数を伸ばすのに貢献した問題だったかも知れません。

OSINT/Secret Account(100点,48AC)

OSINTの紹介としてよく使われる「ネットストーキング」でも代表的なtwitterの裏アカウントを特定する問題です。@trapyojoの裏アカウントを探します。bioにかかれている本名「あずまのりこ」でユーザー検索し、@trapyojoをフォローしているアカウントが裏アカウントです。

この裏アカウントを鍵垢にしていなかったせいで参加者にフォローされてしまったのは想定外でした。同じような問題を作ろうとしている方がいたら鍵垢にするのをおすすめします。

@trapyojoは僕も開発に関わった思い出深いbotなので、以降に紹介する問題には全て彼女が登場します。現在もっとよいbotに作り直そうとしている最中ですのでご期待ください。

OSINT/Where is the Museum?(200点,31AC)

twitterアカウントのツイートから、彼女が過去に行った博物館を当てる問題です。「デイリーヤマザキが近くに3つある」というツイートや、フォローしているアカウントから横浜市中区に住んでいることを絞りこみ、彼女のlikesから該当する博物館を探す、というのが想定解です。

「デイリーヤマザキが近くに3つある」場所はほとんどないのでそこ付近の博物館の電話番号を片っ端から試す、もしくはlikesの博物館の電話番号を片っ端から試す、でも解くことができます。当日レポートを見た限りでは、総当たりで解いた人が多そうです。

PPC/Elementary School(100点,69AC)

twitterで度々話題になる、掛け算の順序に関する問題です。ヒント3を開けると想定解のコードが見られます。

A, B, C, D = map(int, input().split())
if A == D and B == C:
    print("Yes")
else:
    print("No")

PPC/Contrarian Otaku(200点,10AC)

亜種ライフゲームのルールの元で、条件を満たす初期状態を構築する問題です。AC数を見て、レベル3にすべきだったと反省しました。一方で、実装コストだけなら問題を解くコストよりもジャッジを書くコストの方が高そうな気がします。

$H = 1, W = 1$ の時のみ構築できず、それ以外の場合は構築することができます。 $W > 1$ の時は、1行飛ばしで全員に工作をすれば条件を満たすことができます。また、 $W = 1$ の時は全員に工作すれば条件を満たせます。

#include <iostream>
#include <vector>

const int MOD = 1e9 + 7;

using namespace std;
using ll = long long int;
using vl = vector<ll>;

#define REP(i, n) for (ll i = 0; i < (n); i++)

int main() {
  ll H, W;
  cin >> H >> W;

  if (H == 1 && W == 1) {
  	cout << -1 << endl;
    return 0;
  }
  if (W == 1) {
    REP(i, H) cout << "o" << endl;
  } else {
    REP(i, H) {
      if (i % 2 == 0)
        REP(j, W) cout << "o";
      else
        REP(j, W) cout << "x";
      cout << endl;
    }
  }

  return 0;
}

ヒント3で $W = 1$ の場合の処理を書き忘れていました。もしもヒント3まで見たのに解けなかった人がいたら申し訳ないです。初心者が解ける問題を解き終わった後に暇になるのは良くないので、競プロの知識がなくても時間さえあれば解ける枠のつもりで作りました。当日のAC数の遷移を見た限り、実際にそうなっていたかはかなり怪しいです。

PPC/Mountain(300点,10AC)

数列が与えられ、その中から単調増加した後に単調減少する最大長部分列を求める問題です。LIS(最大増加部分列)を両方向から求めて、その中で最大長になるような分岐点 $a_{i}$ ( $a_{i - 1} < a_{i} > a_{i + 1}$ )を全通り調べれば解くことができます。

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>

using namespace std;
using ll = long long int;
using vl = vector<ll>;

const long long int llINF = 9223372036854775807 / 2;

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define AUTO(i, m) for (auto &i : m)

int main() {
  ll N;
  cin >> N;
  vl A(N);
  REP(i, N) { cin >> A[i]; }
  vl B = A;
  reverse(B.begin(), B.end());

  vl DP1(N, llINF);
  vl DP2(N, llINF);

  vl NUM1(N, -1);
  vl NUM2(N, -1);
  vl PATH1(N, -1);
  vl PATH2(N, -1);

  map<ll, ll> M1;
  map<ll, ll> M2;
  REP(i, N) {
    ll index1 = lower_bound(DP1.begin(), DP1.end(), A[i]) - DP1.begin();
    DP1[index1] = A[i];
    if (index1 > 0)
      PATH1[i] = M1[DP1[index1 - 1]];
    M1[A[i]] = i;
    NUM1[i] = index1;

    ll index2 = lower_bound(DP2.begin(), DP2.end(), B[i]) - DP2.begin();
    DP2[index2] = B[i];
    if (index2 > 0)
      PATH2[i] = M2[DP2[index2 - 1]];
    M2[B[i]] = i;
    NUM2[i] = index2;
  }

  ll max = 0;
  ll maxi = 0;

  REP(i, N) {
    if (NUM1[i] + NUM2[N - 1 - i] > max) {
      max = NUM1[i] + NUM2[N - 1 - i];
      maxi = i;
    }
  }

  deque<ll> D;

  D.push_front(A[maxi]);

  ll now = maxi;
  while (PATH1[now] != -1) {
    now = PATH1[now];
    D.push_front(A[now]);
  }

  now = N - 1 - maxi;
  while (PATH2[now] != -1) {
    now = PATH2[now];
    D.push_back(B[now]);
  }
  cout << D.size() << endl;
  AUTO(d, D) { cout << d << " "; }
  cout << endl;

  return 0;
}

これは、Mountainというゲームをやっている時に思いついた問題です。LISを2回やるだけではあるものの実装が割と面倒臭いです。

PPC/Simple Mahjong(300点,20AC)

$1$ ~ $N$ が書かれた $N$ 枚の山札から、 $M$ 人のプレイヤーが3枚ずつカードを引いた場合に、引いたカードがそれぞれ連番になっている通り数を求める問題です。

$1$ つ数字を書くスペースがある小さいカードを $N - (3 \times M)$ 枚と、 $3$ つ数字を書くスペースがある大きいカードを $M$ 枚用意します。
次に、小さいカードを横 $1$ 列に並べ、全ての大きいカードをそれぞれ両端か小さいカードの間の $N - (3 \times M) + 1$ 箇所のどこかに置きます。
この置き方は $_{N - (3 \times M)} H_{M}$ 通りです。
最後に、左端から数字を順番に書いていき、大きいカードをプレイヤーに1枚ずつ配るとプレイヤー全員が勝つ手札を構築できます。配り方は $M!$ 通りです。

$_{N - 3 M} H_{M} \times M! =_{N - 2 M} C_{M} \times M! = \frac{( N - 2 M ) !}{( N - 3 M ) ! M !} \times M! = \frac{( N - 2 M ) !}{( N - 3 M ) !}$

よって、 $\frac{( N - 2 M ) !}{( N - 3 M ) !}$ が答えです。

#include <iostream>
#include <vector>

const int MOD = 1e9 + 7;

using namespace std;
using ll = long long int;
using vl = vector<ll>;

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)

ll MODPOW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = MODPOW(n, m / 2);
    return (tmp * tmp) % MOD;
  } else {
    return (n * MODPOW(n, m - 1)) % MOD;
  }
}

ll nCr(vl &f, ll n, ll r) {
  if (n < r)
    return 0LL;
  if (r > n / 2LL)
    r = n - r;
  ll res = (f[n] * MODPOW(f[n - r], MOD - 2LL)) % MOD;
  res = (res * MODPOW(f[r], MOD - 2LL)) % MOD;
  return res;
}
ll nHr(vl &f, ll n, ll m) { return nCr(f, n + m - 1, m); }

int main() {
  ll N, M;
  cin >> N >> M;

  vl f(N + 10, 1);
  FOR(i, 1, N + 1) f[i] = (f[i - 1] * i) % MOD;

  cout << (nHr(f, N - (M * 3) + 1, M) * f[M]) % MOD << endl;

  return 0;
}

一時期、雀魂にハマっておりその時に考えた問題です。最初は、麻雀本来のルールを元に問題を作ろうと思っていたのですが、あまりにも複雑になるためシンプルにしました。今回のPPC問の中でも特に算数パチンコ感があって僕は好きです。

PPC/Anime Watching(400点,10AC)

アニメのオマージュ関係を表す有向非巡回グラフと視聴予定のアニメの集合が与えられ、オマージュ元のアニメは先に見るという条件を満たすようなアニメ視聴予定を求める問題です。

まず、アニメの有向非巡回グラフに対してトポロジカルソートを行います。
次に、各アニメ $b_{i}$ を根として深さ優先探索を行い、アニメ $b_{i}$ を視聴するにあたって視聴する必要のあるアニメを列挙します。
最後に、トポロジカルソートの結果から視聴する必要があるアニメのみを抽出したのが答えです。

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long int;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define AUTO(i, m) for (auto &i : m)

void dfs(ll u, vvl &g, vl &ans, vector<bool> &used) {
  if (used[u])
    return;
  used[u] = true;
  AUTO(i, g[u]) dfs(i, g, ans, used);
  ans.push_back(u);
}

vl tsort(vvl &g, ll N) {
  vector<bool> used(N, false);
  vl ans;
  REP(i, N) dfs(i, g, ans, used);
  reverse(ans.begin(), ans.end());
  return ans;
}

void dfs2(ll u, vvl &g, vector<bool> &visited) {
  if (visited[u])
    return;
  visited[u] = true;
  AUTO(i, g[u]) dfs2(i, g, visited);
}

int main() {
  ll N, M;
  cin >> N;
  vvl G(N);
  vvl rev_G(N);
  REP(i, N - 1) {
    ll A;
    cin >> A;
    REP(j, A) {
      ll a;
      cin >> a;
      G[a - 1].push_back(i);
      rev_G[i].push_back(a - 1);
    }
  }

  cin >> M;

  auto ans = tsort(G, N);
  vector<bool> visited(N, false);
  REP(i, M) {
    ll b;
    cin >> b;
    dfs2(b - 1, rev_G, visited);
  }
  ll count = 0;
  REP(i, N) {
    if (visited[ans[i]])
      count++;
  }
  cout << count << endl;

  REP(i, N) {
    if (visited[ans[i]])
      cout << ans[i] + 1 << " ";
  }
  cout << endl;

  return 0;
}

pythonだとTLEの危険がある枠の1つです。テスターのtatyamくんのpythonコードはギリギリACだったものの、僕の書いたpythonコードはTLEでした。僕のpythonコードはpypy3だと通ったので、pythonでTLEだった人は試してみてください。

PPC/Score Calculator(500点,2AC)

盤面の中で特定の順番に並んでいるブロック組の最大数を求める問題です。

各ブロックの組の候補を頂点とし、同時に数えることができない候補を辺で結びます。そうすると、この問題は最大安定集合問題として考えることができます。一般のグラフの最大安定集合問題は NP 困難ですが、このグラフは 2 部グラフです。 2 部グラフの最大安定集合は、(頂点の数) - (最大マッチング数) で計算することができます。

#include <iostream>
#include <queue>
#include <vector>

using namespace std;
using ll = long long int;
using vl = vector<ll>;

#define REP(i, n) for (ll i = 0; i < (n); i++)

// 二部グラフの最大マッチング
class bipartite_matching {
public:
  ll n;
  vector<vector<ll>> g;
  vector<ll> match;

  bipartite_matching(int n_) : n(n_), g(n_), match(n_), used(n_) {}

  void add_edge(ll u, ll v) {
    g[u].push_back(v);
    g[v].push_back(u);
  }

  ll maximum_matching() {
    ll res = 0;
    fill(begin(match), end(match), -1);
    for (ll v = 0; v < n; ++v) {
      if (match[v] == -1) {
        fill(begin(used), end(used), false);
        if (dfs(v))
          res++;
      }
    }
    return res;
  }

private:
  vl used;
  bool dfs(ll v) {
    used[v] = true;
    for (ll u : g[v]) {
      ll w = match[u];
      if (w == -1 || (!used[w] && dfs(w))) {
        match[v] = u;
        match[u] = v;
        return true;
      }
    }
    return false;
  }
};

int main() {
  ll H, W, X;
  cin >> H >> W >> X;
  vector<string> S(H);
  string T;
  REP(i, H) cin >> S[i];
  cin >> T;
  auto D = vector<vector<vector<ll>>>(H, vector<vector<ll>>(W));

  ll count = 0;
  REP(h, H) REP(w, W - X + 1) {
    bool ok = true;
    REP(x, X) if (S[h][w + x] != T[x]) ok = false;
    if (ok) {
      REP(x, X) D[h][w + x].push_back(count);
      count++;
    }
  }
  REP(w, W) REP(h, H - X + 1) {
    bool ok = true;
    REP(x, X) if (S[h + x][w] != T[x]) ok = false;
    if (ok) {
      REP(x, X) D[h + x][w].push_back(count);
      count++;
    }
  }

  auto BM = bipartite_matching(count);
  REP(h, H) REP(w, W) {
    if (D[h][w].size() == 2) {
      BM.add_edge(D[h][w][0], D[h][w][1]);
    }
  }

  cout << count - BM.maximum_matching() << endl;

  return 0;
}

2 部グラフの最大安定集合を求める問題を僕があんまり見たことがなかったので作った問題です。O(HW)で解く解法も存在します。

最後に

CPCTF2021に参加していただき、ありがとうございました。楽しんでいただけたら幸いです。初めて作問というのをやったのですが、思った以上に楽しかったです。

私の拙い問題をチェックしてくれたtatyamくんとnoshiくん、いろいろ大変そうだったCPCTF2021の開発・運営の方々、ありがとうございました。

CPCTF2021 作問者writeup by hukuda222

はじめに

作問者writeup

Newbie/Hello World(10点,60AC)

Misc/Shortest Letter(100点,50AC)

OSINT/Secret Account(100点,48AC)

OSINT/Where is the Museum?(200点,31AC)

PPC/Elementary School(100点,69AC)

PPC/Contrarian Otaku(200点,10AC)

PPC/Mountain(300点,10AC)

PPC/Simple Mahjong(300点,20AC)

PPC/Anime Watching(400点,10AC)

PPC/Score Calculator(500点,2AC)

最後に

関連する記事

CPCTF2021 作問者writeup by hukuda222

はじめに

作問者writeup

Newbie/Hello World(10点,60AC)

Misc/Shortest Letter(100点,50AC)

OSINT/Secret Account(100点,48AC)

OSINT/Where is the Museum?(200点,31AC)

PPC/Elementary School(100点,69AC)

PPC/Contrarian Otaku(200点,10AC)

PPC/Mountain(300点,10AC)

PPC/Simple Mahjong(300点,20AC)

PPC/Anime Watching(400点,10AC)

PPC/Score Calculator(500点,2AC)

最後に

この記事をシェア

関連する記事