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

hamayanhamayan's blog

Japan Tech News #014 2020/04/05

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

Hottest

競技プログラミング

セキュリティ / CTF

  • CTF.Live
    • 何やら爆誕してた
    • 最初の問題からさっぱりわからん。初手がいまだにわからん問題多いな。

☕ 技術 / 雑多

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

[emoji:190] 流し見

NetCorp [VolgaCTF 2020 Web]

https://ctftime.org/task/10853

本当はVolgaCTF全解説する予定だったけれど、気力切れたから、これだけ。

Lunlun Number [AtCoder Beginner Contest 161 D]

https://atcoder.jp/contests/abc161/tasks/abc161_d

解説

https://atcoder.jp/contests/abc161/submissions/11550250

サンプルを見ると105の場合が紹介されている。
あまり桁数が増えていないので、普通にインクリメント作業をしても間に合いそうだ。
x++のような関数を作ろう。
increment(from) := ルンルン数上でfrom+1を返す
基本的には普通のインクリメントと同様で一番下の桁を+1する。
した結果ルンルン数でなくなる場合は、その次の桁を+1する。
繰り上がりのような感じで考えればいい。
例えば、
434からのインクリメントは、末尾の4を+1すると、ルンルン数でなくなるので、次の桁の3をインクリメントする。
44_となるが、そこより下の桁はなるべく小さい数を置くので、4から-1した443となる。
これが、44__であれば、4から-1して、そこからさらに次の桁では-1するので、4432となる。
こういったことを頑張ってやる。

int K;
//---------------------------------------------------------------------------------------------------
string increment(string from) {
    int N = from.size();

    rrep(i, N - 1, 1) {
        int cu = from[i] - '0';
        int nxt = from[i - 1] - '0';

        if (cu < 9 && abs(cu + 1 - nxt) <= 1) {
            from[i]++;
            rep(j, i + 1, N) from[j] = max('0', (char)(from[j - 1] - 1));
            return from;
        }
    }

    int top = from[0] - '0';
    
    if (top < 9) {
        from[0]++;
        rep(j, 1, N) from[j] = max('0', (char)(from[j - 1] - 1));
        return from;
    }

    string res = "1";
    rep(i, 0, N) res += "0";
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> K;

    string ans = "1";
    rep(k, 0, K - 1) ans = increment(ans);
    cout << ans << endl;
}

Yutori [AtCoder Beginner Contest 161 E]

https://atcoder.jp/contests/abc161/tasks/abc161_e

前提知識

  • DPの復元

解説

https://atcoder.jp/contests/abc161/submissions/11549308

※ 本解説は、DPの復元が理解できてないとちょっと厳しいかもしれない

色々な方針が見える。
ある日で必ず働くということを考えるのは、少し難しいように思う。
もう少し見通しがよさそうな方向で考えると、ある日が働けないときにK日以上働けるかを判定する。
K日以上働けないなら、その日は必ずはたらかないと行けない。

ここまではいいのだが、ここから少し飛躍がある。
DPで最大で何日間働けるかを計算してみよう。

dp[i] := i日目を終えたときの最大の働いた日数
dp[i+1] <= dp[i]
dp[i+1+C] <= dp[i] + 1

このDPを計算すると、dp[N]が最大の働ける日数となる。
これが既にKよりも大きかった場合は、ある1日働かなくてもK日以上働けるので、答えはない。
dp[N]=Kの時の最適なパスを考えてみる。
つまり、dp[0]からdp[N]までの遷移の中で、dp[N]=Kとなる遷移のパスのことである。
このパスは一般にはDPから「復元」をする場合に使われる。
自分の実装では、dpの遷移元を記録しておくことで対応している。

今回の問題に置き換えて考えてみると、ある頂点を取り除くと、最適なパスが1つもなくなると
その頂点(=その日)は絶対働く必要がある。

f:id:hamayanhamayan:20200404230515p:plain

これを何とか見つけ出す必要があるが、dpテーブルを見ると、各頂点に対して最適に動いたときに
何日目の労働日になるかが書いてあるような感じになる。
(正確には労働した遷移の遷移先がそれにあたる)
最適パスの労働について見たときに、ある最適労働日が1つの頂点だけだった場合は、
それを削除すると、その労働日の労働がなくなるので、条件を満たさなくなる。
よって、最適労働日を集計して、1日だけならその日は必ず働く日となる。

int N, K, C; string S;
int dp[201010];
vector<int> pre[201010];
bool vis[201010];
vector<int> dpt[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K >> C >> S;

    rep(i, 0, N + 1) dp[i] = -inf;
    dp[0] = 0;
    rep(i, 0, N) {
        if (chmax(dp[i + 1], dp[i])) pre[i + 1].clear();
        if (dp[i + 1] == dp[i]) pre[i + 1].push_back(i);

        if (S[i] == 'o') {
            if (chmax(dp[min(N, i + 1 + C)], dp[i] + 1)) pre[min(N, i + 1 + C)].clear();
            if (dp[min(N, i + 1 + C)] == dp[i] + 1) pre[min(N, i + 1 + C)].push_back(i);
        }
    }
    
    if (K < dp[N]) return;

    queue<int> que;

    vis[N] = true;
    que.push(N);

    while (!que.empty()) {
        int cu = que.front(); que.pop();
        fore(to, pre[cu]) {
            if (!vis[to]) {
                vis[to] = true;
                que.push(to);
            }

            if (dp[cu] == dp[to] + 1) {
                dpt[dp[to]].push_back(to + 1);
            }
        }
    }

    vector<int> ans;
    rep(i, 0, K) if (dpt[i].size() == 1) ans.push_back(dpt[i][0]);
    sort(all(ans));
    fore(a, ans) printf("%d\n", a);
}

Division or Substraction [AtCoder Beginner Contest 161 F]

https://atcoder.jp/contests/abc161/tasks/abc161_f

前提知識

解説

https://atcoder.jp/contests/abc161/submissions/11544845

余談であるが、1012という制約はとても特徴的であり、平方根をとると106となって、まだやれる計算量となる。 なので、O(sqrt(N))を疑ってもいいだろう。

Kを固定して、操作を逆に考えてみよう。
操作を見てみると、1から初めて+Kをするか、×Kをするかという操作になっている。

f:id:hamayanhamayan:20200404224310p:plain

逆操作の×Kはいつでもできる。
これは遷移先は必ずKの倍数となるので、÷Kが選択されるためである。
だが、+Kはいつでもはできない。
+Kした結果がKの倍数であれば/Kされてしまうためである。
これは元々がKの倍数であれば+KしたときにKの倍数となってしまう。
よって、1からスタートするが、×Kを1回でも行った場合はそれ以降は×Kをするしかなくなる。
まとめると、操作は、「(1)+Kを任意回する (2)×Kを任意回する」に限定される。
この遷移先の中にNが含まれていれば、Kは条件を満たすKとなる。

f:id:hamayanhamayan:20200404224321p:plain

こうして見てみると、1,K+1,2K+1,3K+1がNであるようなKというのは、N-1の約数になっている。
K-1の約数を全列挙して2よりも大きいものが答えのKとなる。

後は、K倍されているものが考慮すべきものとして残るが、このKはNの約数が候補として上がる。
よって、KをNの約数として固定して、そのKで割れるだけ割ったときの残りが、nK+1の形になっていればいい。
これも残り-1をしてKの倍数かを判定すればいい。

自分は両方のパターンで出したKをsetに入れて、重複チェックを念のためしているが、
たぶん被らないと思う。

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    set<ll> ans;

    auto ed1 = enumdiv(N);
    fore(d, ed1) if (2 <= d) {
        ll K = d;
        ll n = N;
        while (n % K == 0) n /= K;
        if ((n - 1) % K == 0) ans.insert(K);
    }

    auto ed2 = enumdiv(N - 1);
    fore(d, ed2) if (2 <= d) ans.insert(d);

    cout << ans.size() << endl;
}

Reiwa Sequence [yukicoder 1017]

https://yukicoder.me/problems/no/1017

解説

https://yukicoder.me/submissions/458766

今までの経験からして、これ系で行けそうというものはあるが、制約がちょっと厳しいのと、構築する必要がある。
なにも思いつかんけど、難易度がREDじゃないというときは、何か性質を見抜くべきと考えよう。
つまり、自明な所から考えてみる。

まず同じ数が1ペアでもあれば、それを+と-にして他を全部0にすれば答えが作れる。
よって、考えるべきは、すべて異なる数が与えられた場合である。
この場合、割と作れそうな感じがするが、ここからの思考が難しい。
んー、分からん!

(解説読み中…)

どんなパターンでも22種類くらいあれば構築可能とのこと。
N=22という基準は鳩ノ巣原理で端的に言える。なるほど。明白だ。
そういう問題どっかで見たな。
ではなく、端的に換言すると、こういうのを早く思い出せ(反省)。

まあ、結論としては配列Aの先頭22個を取り出してN≦22の問題として改めて解くことを考える。
こちらの問題もまあまあ実装に困るのだが、半分全列挙を知っていればO(3N/2)がアルゴリズムとしては一番わかりやすい。

とりあえず、O(N2N)の解法を紹介しておく。
O(N2N)ですべての部分集合について総和を計算する。
それで以下の配列を構築する。
msks[tot] := 総和がtotとなる部分集合mskの集合
説明がちょっとわかりにくいが、コードを見て補完してほしい。
この時、「totが最も小さくて、個数が2個以上のmsks[tot]の1番目の集合と2番目の集合は必ず共通項を持たない」。
これはなぜかというと、共通項をもし持つのであれば、それをどちらの集合からも削除して、totがより小さいものにできるためである。
なので、totが最小のmsks[tot]の1番目と2番目を取ってくれば、それが+にする集合と-にする集合となるので、
それを+,-にして他を0で答えると答え。

int N, A[151010];
vector<int> msks[4010101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    int M = min(22, N);
    rep(msk, 0, 1 << M) {
        int sm = 0;
        rep(i, 0, M) if (msk & (1 << i)) sm += A[i];
        msks[sm].push_back(msk);
    }

    rep(tot, 1, 4010101) if (1 < msks[tot].size()) {
        int plus = msks[tot][0];
        int minus = msks[tot][1];

        printf("Yes\n");
        rep(i, 0, M) {
            if (i) printf(" ");

            if (plus & (1 << i)) printf("%d", A[i]);
            else if (minus & (1 << i)) printf("-%d", A[i]);
            else printf("0");
        }
        rep(i, M, N) printf(" 0");
        printf("\n");

        return;
    }

    printf("No\n");
}

三目並べ [yukicoder 1016]

https://yukicoder.me/problems/no/1016

解説

https://yukicoder.me/submissions/458599

貪欲法で解けそう。
まずは自明な所から考えてみる。

既にoooがあるなら勝っているし、どこか1マスにoを入れれば勝てるなら勝ち。
複数手で勝てる手を考える。

3手詰めは?
-o--
この状況であれば3手詰めができる。
実はまだある。
o---o
これを思いつくのがきついが、詰めるためには毎回王手をかける必要がある。
それはoo-を作るか、o-oを作るしかないので、その辺から考えていく。

5手詰めは?
o-----o

7手詰めは?
o-------o

他にもあるかもしれないが、それっぽい規則性も見えたところで、出してみる。
以上の詰めパターンがあるならOが答え。
無ければX

int N; string S;
//---------------------------------------------------------------------------------------------------
#define ok "O"
#define ng "X"
string solve() {
    cin >> N >> S;

    vector<string> wins = {"ooo", "-oo", "oo-", "-o--", "--o-"};
    fore(win, wins) rep(i, 0, N) if (S.substr(i, win.size()) == win) return ok;

    vector<int> winvec;
    rep(i, 0, N) if (S[i] == 'o') winvec.push_back(i);

    int n = winvec.size();
    rep(i, 0, n - 1) {
        int st = winvec[i];
        int en = winvec[i + 1];
        int lose = 0, blank = 0;
        rep(j, st + 1, en) {
            if (S[j] == 'x') lose++;
            else blank++;
        }
        if (lose == 0 && blank % 2 == 1) return ok;
    }

    return ng;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) cout << solve() << endl;
}