はまやんはまやんはまやん

hamayanhamayan's blog

K-colinear Line [ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248） E]

競技プログラミング

https://atcoder.jp/contests/abc248/tasks/abc248_e

解説

https://atcoder.jp/contests/abc248/submissions/31046558

幾何問題。
以下解法、非常に面倒なので、別の解法があるかも…

（解法に移る前に）

以下のケースでちょっとはまったので、WAではまってる人はこれを確認してみるといいかも。

6 3  
1 3  
1 4  
1 5  
6 10  
6 11  
6 12

Infinityのとき

K=1の場合はどのような場合でも無数に解が存在する。
K=1の時は、Infinityと出して終了しよう。

どういった方針を取るか

今回は点を通る直線を題材とした問題であるが、直線は少なくとも2点があれば作成することができる。
逆に3点あると複数の直線ができてしまったり、色々面倒なので、2点を使った直線から解法が導けないか考えてみる。

ここから思考が飛ぶが、試行錯誤がこの間にあったと考えてほしい…

例えば、任意のa番目の点とb番目の点（a＜b）について直線を列挙していったときに、
同一直線状に3点ある直線は3回現れる。点abcを通っていれば、ab,ac,bcの列挙時に出てくる。
同一直線状に4点ある直線は6回現れる。点abcdを通っていれば、ab,ac,ad,bc,bd,cdの列挙時に出てくる。
つまり、同一直線についてはn点あれば、C(n,2)回現れることになる。（関数Cは二項係数）

よって、
cnt[ (ある直線を表す何らかの情報）] := 任意の2頂点を選んだときにある直線が何通りあるか
というのが計算できれば、その個数から直線に何個点があるかを逆算することができる。

『ある直線を表す何らかの情報』

自分はこれに傾きと切片を使った。
入力値が[-109,109]だったので、doubleは落ちそうな気配があり、有理数でどちらも保持する道を選んだ。
傾きをdx/dy, 切片をbup/bdownという風に有理数で定義して、2つの分数について正規化をすれば、
(dx, dy, bup, bdown)の数の組がとある直線を一意に表してくれるようになる。
以下の関数を作って計算している。

getParameter(a,b) := 2頂点a,bを通る直線を表す(dx, dy, bup, bdown)を返す

具体的には
https://blog.hamayanhamayan.com/entry/2018/09/30/203639
っぽいことをやる。

a = (ya - yb) / (xa - xb)
b = (xa * yb - xb * ya) / (xa - xb)

という感じで分数を作って、ソースコードにあるnormalization関数みたいに有理化する感じである。
(xa - xb)が0になるときが注意で、傾きは分子を1にするが、切片は分子をそのままにしている。
縦の直線なので、傾きと切片を定義はできないのだが、便宜上このようにして直線を同一視させている。

pair<ll, ll> normalization(ll up, ll down, bool slope = true) {
    if (down < 0) {
        up *= -1;
        down *= -1;
    }

    if (down == 0) {
        if (slope) up = 1;
    }
    else {
        ll g = gcd(abs(up), down);
        up /= g;
        down /= g;
    }

    return {up, down};
}

int N, K; ll X[301], Y[301];

tuple<ll, ll, ll, ll> getParameter(int a, int b) {
    ll dx = X[a] - X[b];
    ll dy = Y[a] - Y[b];

    tie(dy, dx) = normalization(dy, dx);

    // ya = dy * xa / dx + b
    // b = (ya * dx - dy * xa) / dx

    ll bup = Y[a] * dx - dy * X[a];
    ll bdown = dx;

    tie(bup, bdown) = normalization(bup, bdown, false);
    return { dy, dx, bup, bdown };
}

void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> X[i] >> Y[i];

    if (K == 1) {
        cout << "Infinity" << endl;
        return;
    }

    map<tuple<ll, ll, ll, ll>, int> cnt;

    rep(a, 0, N) rep(b, a + 1, N) cnt[getParameter(a, b)]++;

    map<int, int> rcomb;
    rep(n, K, N + 1) rcomb[n * (n - 1) / 2] = 1;

    int ans = 0;
    fore(p, cnt) ans += rcomb[p.second];
    cout << ans << endl;
}

Range Count Query [ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248） D]

競技プログラミング

https://atcoder.jp/contests/abc248/tasks/abc248_d

前提知識

解説

https://atcoder.jp/contests/abc248/submissions/31044881

色々な解法が見える問題。
実際WaveletMatrixというデータ構造を使えば、一瞬で答えが出るのだが、二分探索解法で説明する。

以下、配列の要素については0-indexed（0始まり）で説明している。

手動でクエリを計算してみる

手動で答えてくださいと言われたら、L番目からR番目まで順番にXがあるかを見ていくような感じになると思う。
ここで、Xだけを見ることが出来れば、高速化できそうという気持ちになり、そういった方法を探してみる。

数が同じものをまとめておく

クエリを処理前の段階でとある数について、その数がある添え字（index）をまとめた配列を用意しておくことにする。

indexes[x] := 値がxである数列の要素の添え字の集合

具体的には入力例1 3 1 4 1 5であれば、

indexes[1] = { 1, 3 }
indexes[3] = { 0 }
indexes[4] = { 2 }
indexes[5] = { 4 }

というのをあらかじめ用意しておく。
こうすれば、とある数Xが含まれる場所は前計算で求めたこれを使えば高速に求められることになる。

要求問題が変わる

こうすると、要求される問題が以下のように変化する。

与えられた配列の中にLからRの数は何個あるか

これを計算するには二分探索が使える。
二分探索するためには配列がソートされている必要があるので注意。
自分の作成方法だと、構築すると既にソートされているが、実装によってはそうでないかもしれない。
自分の作成方法はコードを確認してほしい。

さて、二分探索で求めるのは、

  • L以上の数が初めて現れる場所 st
  • Rより大きい数が初めて現れる場所 gl

である。これが求まれば、個数はgl - stとなるので、これを求めればいい。

C++であれば、iteratorというのを理解する必要があるが、

  • ソート済みの配列に対して～以上の数が初めて現れる場所はlower_bound
  • ソート済みの配列に対して～より大きいの数が初めて現れる場所はupper_bound

で二分探索を意識しなくても計算することができる。
二分探索ではO(logN)の計算量なので、全体でO(QlogN)となって間に合う。

int N, A[201010];
int Q;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    cin >> Q;

    map<int, vector<int>> indexes;
    rep(i, 0, N) indexes[A[i]].push_back(i);

    rep(q, 0, Q) {
        int L, R, X;
        cin >> L >> R >> X;
        L--; R--;

        auto st = lower_bound(all(indexes[X]), L);
        auto gl = upper_bound(all(indexes[X]), R);

        int ans = gl - st;
        printf("%d\n", ans);
    }
}

Dice Sum [ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248） C]

競技プログラミング

https://atcoder.jp/contests/abc248/tasks/abc248_c

前提知識

解説

https://atcoder.jp/contests/abc248/submissions/31043632

この問題では動的計画法を用いて、答えを作成していく。
動的計画法の入門の次の一手くらいの問題なので、全く分からないという方は他の入門サイトで学習してくることをすすめる。

何から始めるか

とある数列の構築方法の組数を計算する問題であり、かつ、modで組み合わせ数を計算するような問題である。
このような問題の解法として動的計画法は良く使われており、既視感から動的計画法を使った解法を考え始める人も多いだろう。
実際自分はノータイムでDPを考え始めたので、この部分は経験によって埋まる部分だと思う。

動的計画法

動的計画法と言えば、

dp[i] := 数列のi番目まで確定しているときの組み合わせ

なので、これをベースに考えてみよう。
数列は1～Mの数が選択できるので、M=3であるとすると、2番目までの作り方は以下の9通りである。

1 1  
1 2  
1 3  
2 1  
2 2  
2 3  
3 1  
3 2  
3 3

この時、dp[2] = 9のように計算することができ、dp[3]を計算するためには、3番目を1～Mで選択した場合を考えて遷移を考える。
だが、今回の問題では最終的に数列の総和について条件が課されている。
ということは数列の長さという特徴以外に、総和という特徴も考慮して分類する必要が出てくることになる。
しかも、ここで重要なのが、総和さえ求めておけば、今までどんな数列が選ばれていたかは後の選択には影響しないということである。
つまり、総和が4である「1 3」と「2 2」は数列の3番目以降を選ぶという観点では、条件が全く同じになる。
よって、特徴として総和を選ぶことで最終的な条件判定はできるまま、計算をまとめてしまうことができるようになる。
次のようなDPを考えよう。

dp[i][sum] := 数列のi番目まで確定していて、これまでの総和がsumである組み合わせ

上の例でいうと、

dp[2][2] = 1
dp[2][3] = 2
dp[2][4] = 3
dp[2][5] = 2
dp[2][6] = 1

となる。

dp[i][sum]からの遷移としては、1～Mのいずれかnxtを選ぶような遷移になり、
dp[i + 1][sum + nxt] += dp[i][sum]
という感じでやっていくと良い。ソースコードを見てもらう方が分かりやすいかもしれない
。
このように状態が2つ以上になるDPも頻繁に出てくるので、DPの雰囲気をつかんだら、このような問題にも取り組んでみてほしい。

int N, M, K;
mint dp[51][3010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;

    dp[0][0] = 1;
    rep(i, 0, N) rep(sum, 0, K + 1) rep(nxt, 1, M + 1) dp[i + 1][sum + nxt] += dp[i][sum];

    mint ans = 0;
    rep(sum, N, K + 1) ans += dp[N][sum];
    cout << ans << endl;
}

Bishop 2 [AtCoder Beginner Contest 246 E]

競技プログラミング

https://atcoder.jp/contests/abc246/tasks/abc246_e

前提知識

解説

https://atcoder.jp/contests/abc246/submissions/30681205

問題文とはxとyの解釈を逆にして説明している。
好みの問題ではあるのだが、つまり、チェス盤の上からy行目、左からx列目としてx,yを扱う。

今回の問題は最短経路問題であるため、最短経路問題と解くために使用されるダイクストラやBFSを
ベースに解法を作成していく。
これをベースに解法を考えていくと答えが導けたみたいな流れとなる。

拡張ダイクストラ

通常のダイクストラでは、頂点、つまり、場所だけを状態として考えて最短経路問題を行うが、
拡張ダイクストラでは、場所以外の何らかの情報（ないし状態）も合わせて状態を考えて最短経路問題を解くことを指す。
なので、状態の持ち方が変わるだけなので「拡張」という言葉をつける必要もないのだが、なんとなくついている。
（ググるときに便利なワードではあるが、誤用というか不適切では？と言われることも多いので注意）

さて、状態としてどのマスにいるかということ以外にコストに関わってきそうなことを考えてみよう。
ビショップはポーンが無ければコストを増やすことなくずっと進んでいくので、ダイクストラのような1手ずつ
進んでいくことを前提に考えると、直前に（最後に）どの方向に移動したかという情報があれば、
コストがかかるかどうかを判別できそうである。
なので、ダイクストラを行う場合に以下のような配列（グラフ的には頂点か）を考えて更新していく。

opt[y][x][dir] := マス(x,y)にいて、直前に進んだ方向がdirである場合の、最小手数

後は、ダイクストラをしていくだけなので、それほど難しくない。
自分のコードは以下。
https://atcoder.jp/contests/abc246/submissions/30679961

int N;
int Ax, Ay, Bx, By;
string S[1510];

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int dx[4] = { 1, 1, -1, -1 };
int dy[4] = { 1, -1, 1, -1 };
int opt[1510][1510][5];
bool vis[1510][1510][5];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    //cin >> Ax >> Ay >> Bx >> By;
    cin >> Ay >> Ax >> By >> Bx;
    Ax--; Ay--; Bx--; By--;
    rep(y, 0, N) cin >> S[y];

    min_priority_queue<pair<int, tuple<int, int, int>>> que;
    rep(x, 0, N) rep(y, 0, N) rep(dir, 0, 5) opt[y][x][dir] = inf;
    rep(x, 0, N) rep(y, 0, N) rep(dir, 0, 5) vis[y][x][dir] = false;

    opt[Ay][Ax][4] = 0;
    que.push({ 0, { Ax, Ay, 4 } });

    while (!que.empty()) {
        int x, y, dir;
        tie(x, y, dir) = que.top().second;
        que.pop();

        if (vis[y][x][dir]) continue;
        vis[y][x][dir] = true;

        if (x == Bx && y == By) {
            cout << opt[y][x][dir] << endl;
            return;
        }

        rep(d, 0, 4) {
            int xx = x + dx[d];
            int yy = y + dy[d];
            if (0 <= xx && xx < N && 0 <= yy && yy < N) {
                if (S[yy][xx] == '#') continue;
                if (chmin(opt[yy][xx][d], opt[y][x][dir] + (dir != d))) {
                    que.push({ opt[yy][xx][d], { xx, yy, d } });
                }
            }
        }
    }

    cout << -1 << endl;
}

2-variable Function [AtCoder Beginner Contest 246 D]

競技プログラミング

https://atcoder.jp/contests/abc246/tasks/abc246_d

前提知識

解説

https://atcoder.jp/contests/abc246/submissions/30680524

なかなか難しいというか、競プロ的なアプローチを含んだ問題。
二分探索が分かっていない場合はそちらを先に学習してきてほしい。

何から始めるのか

サンプルを自力でうまく解くような方法が無いかを探してみる。
入力1に対して答えを見つけようとした場合、Xの候補である9, 10, 11, ...が条件を満たすかどうかを
判定して、満たす最小のものを答える方法が考えられる。
しかし、とあるXに対して、そのXが条件を満たすかどうかを判定するのはやや難しく、
別のアプローチが無いかを考えてみることにする。

候補が全列挙できるのでは？

ここから競技プログラミングで良く出てくる候補の全列挙をベースに考えてみる。
とあるXが条件を満たすかを判定するのは難しいので、生成の元となっているa,bの列挙から攻めてみる。
3乗が含まれるので、a,bはそれぞれ106が上限であることが分かる。
aは非負整数、かつ、少なくとも a3 ≦ 1018 なので、 a ≦ 106 である必要があるということ。

これでa,bの全列挙が出来れば、条件を満たすXをすべて生成できるので、ここからX以上の最小値を求めればいい。
だが、このままやるとTLE

片方を効率化する

aは[0, 106]の範囲で全探索するとして、bをもっと賢く探索できないかを考えてみる。
条件となっている多項式の計算をf(a,b)と置いて考えてみる。
とあるaについて、
f(a,0), f(a,1), f(a, 2), ...
というのを考えてみると、とある部分を境目としてN以上になっているはずである。
この「とある部分を境目として」という部分から二分探索が使えそうと思い立てば、もう解法は目の前である。

二分探索

bは[0,106]のどこかに最適解が存在するが、N≦f(a,b)を満たすかというのを条件にして境目を見つけよう。
境目が見つかれば、その境界線上のbの大きいほうの値が最適なbになっているはずなのでf(a,b)について
答えの候補として更新していこう。

ll N;

ll f(ll a, ll b) {
    return a * a * a + a * a * b + a * b * b + b * b * b;
}

void _main() {
    cin >> N;

    ll ans = infl;
    rep(a, 0, 1010101) {
        ll ng = -1, ok = 1010101;
        while (ng + 1 != ok) {
            ll md = (ng + ok) / 2;
            if (N <= f(a, md)) ok = md;
            else ng = md;
        }
        chmin(ans, f(a, ok));
    }
    cout << ans << endl;
}

LINE CTF 2022 Web 解説まとめ

Security

CTFtime.org / LINE CTF 2022

自分の復習用に集めた情報をまとめておく。

gotm

SSTI可能。idに{{.}}を与えてやるとJWTの秘密鍵が漏洩するので、それを使ってトークン改ざんしてflagを獲得する。

Memo Drive

バリデーションをbypassしながらLFIして、./flagを読む問題。

bb

環境変数を使ってRCEする方法がこの世に存在するようだ。これを使う。

https://movaxbx.ru/2022/02/22/how-do-i-use-environment-variables-to-inject-and-execute-arbitrary-commands/
（ruドメインの締め出しか知らないが、アクセスできない。VirusTotalとかでIPアドレスを持ってきてhostsに追加する感じで手元で名前解決してやれば見れる。）

online library

app.get("/:t/:s/:e", (req: Express.Request, res: Express.Response): void => {の部分で自由にLFIできるので、これと/proc/self/memを使ってメモリが見れる。
express-sessionではセッション情報がメモリに載るので、usernameにXSSコードを入れてsubmitするとメモリにXSSコードが載るので、それをLFIで取ってきて踏ませる。
すごい方法だけれど、わざわざusernameを報告前に送っているし、領域を指定して取得できる仕様もあるので想定解法なのかもしれない。
ログにpayload乗っけてLFIしてXSS発動と同じ雰囲気。

Discordのwebチャンネルではメモリ経由以外の解法もあると発言している人がいた。この人曰く、この解法ならxssの必要もないとのこと。

Haribote Secure Note

このセクション間違ってるかも。注意。

CSPをbypassして、XSSする問題。以上のように三者三葉。

title todo

賢すぎるな。
画像アップロード機能があってキャッシュ機能もあるのだが、キャッシュヒットした場合は特殊なヘッダーが突くことを利用して、初回アクセスか2回目以降アクセスかが分かる。
これをオラクルとして機能させるために、scroll-to-textと画像のloading=lazyをうまく使う。
後はこのオラクルを使ってXSLeakする。

（そういえば去年もXSLeak問ありましたね）

me7-ball

理解できてない。
使ってるライブラリにsecret無しでデータを読みだす方法があって、それを利用すると解けるということだと思う。
多分。

Choose Elements [AtCoder Beginner Contest 245 C]

競技プログラミング

https://atcoder.jp/contests/abc245/tasks/abc245_c

解説

https://atcoder.jp/contests/abc245/submissions/30483611

やや丁寧めに説明ぞ書いていく。

何から始めていけばいい？

問題への取り組み方として、全列挙してみたり、実験してみたり、色々やってみることが大切である。
条件を満たす数列が存在するかの判定方法の一つとして、数列を列挙してみる方法がある。
以下のサンプルでやってみよう。

5 4  
9 8 7 7 2  
1 6 8 9 5

先頭から数列の数を決めていくとすると、AかBかから数を選択すればいいので、最初は

9  
1

の状態がありえる。ここから2番目の数を確定させるには、このありうる状態から8か6をくっつけていけばいい。
だが、前の数から4より大きくは離れることができないので、

98  
96

が状態として残る。次は78をくっつける。

987  
988  
967  
968

次は79をくっつけるのだが、このままくっつけると更に倍になって管理が大変である。
倍倍になっていくのは嫌なので、ここで一旦手を止めて考えてみる。
今回は数列が作れるかを判定すればいいので、判定に利用されない最後の数以外はなんでもいい。
よって、「最後に何の数がある候補が残っているか」を管理することで、状態を「圧縮」することができる。

??7  
??8

このように最後がなんであるかという情報さえあれば数列が存在するかの全列挙が続行できることが分かった。
これならば状態は2以上に増えることはないし、手計算でも何とかなりそうである。

状態の圧縮

このように先頭からシミュレーションのように列挙をしていくのだが、ここまで作ることのできる数列について
「末尾が配列Aのものがあるか」「末尾が配列Bのものがあるか」さえ分かっていれば、そこから数列を伸ばすことができる。
自分の実装では

cur[ab] := ここまでのシミュレーションで数列ab (ab=0ならA, ab=1ならB)が末尾となる数列があるか

を持ちながら

nxt[ab] := 1手後のシミュレーションで数列ab (ab=0ならA, ab=1ならB)が末尾となる数列があるか

を作成している。
このように現在状態を圧縮しながらシミュレーションすることで、最終的に条件を満たす数列が存在するかを判定できる。
配列A,Bを合体して2次元配列としているので実装を読み解くのが難しいかもしれないが、頑張ってほしい。

その先へ

このような状態の圧縮は競技プログラミングでは頻出の考え方である。
とても広く適用できるので、意識していこう。
特に動的計画法では必須な考え方である。
今回のような問題でコツをつかんで、動的計画法に取り組んでもいいかもしれない。
（本質的には変わらないですが、この問題はDPでも解けます）

int N, K, AB[2][201010];
void _main() {
    cin >> N >> K;
    rep(ab, 0, 2) rep(i, 0, N) cin >> AB[ab][i];

    bool cur[2] = { true, true };
    bool nxt[2];
    rep(i, 1, N) {
        nxt[0] = nxt[1] = false;
        rep(from, 0, 2) if (cur[from]) rep(to, 0, 2) {
            if (abs(AB[from][i - 1] - AB[to][i]) <= K) nxt[to] = true;
        }
        cur[0] = nxt[0];
        cur[1] = nxt[1];
    }

    if (cur[0] || cur[1]) cout << "Yes" << endl;
    else cout << "No" << endl;
}