文学徒が競プロをするブログ

競技プログラミングの精進を記録していきます

ZONeコン 反省

失敗をギリギリ逃れたという感触。もうちょっと行けただろというのはそうですね。

A問題

100点問題にループがくるのは珍しい気がしました。正規表現とかでえいっとやるのが楽かも？

B問題

軽い幾何。しかし数弱文系が咄嗟に二直線の交点の式を出せる道理もなく、いさぎよくICPCの時に整備した幾何ライブラリをペタリ。ありがとうICPC。

C問題

解けそうで解けずもどかしいままコンテスト終了......。水diffが本番で解けないとつらいですね。

試行錯誤しつつまあ二分探索だよねというところまでは良かったんですが、微妙に単調性がなくて困ってしまいました。

例えば、単純に「総合力がXになるか？」という問いを考えると、「5はNo, 4はYes, 3はNo」みたいな状況になってしまうことがあります。

こういう時は「総合力がX以上になるか？」という問いを考えれば良いです。これを覚えられたのは収穫ですね。

こう考えると状態も圧縮できて、判定問題も高速に解くことができ、ACすることができます。知らない考え方ですが決して難しくはないので、解きたかったなあという感覚ですね。

D問題

dequeueを知っていますか？私は知っています。

E問題

なにこれ枠。愚直が250msで通るんですが......？

とはいえ考え方自体は勉強になったのでまあよしです。愚直書いておけばそれだけで青パフォだったのは悔しいですが、それでレート稼いでもねえという感じ。Cを解けていればなあ。

F問題

よく知りません。構築らしいですね。

ABC199 感想

456位の1887パフォで1年ぶりに過去最高パフォを更新！しかも今回はまぐれではなく、解くべき問題を詰まらずに解けた結果だったので、非常にうれしい成果でした！
これからこういった成功を増やしていきたいですわね。

ところで、bitDPを扱う問題のパフォが妙に高く出ている気がします。ナップサック以外の典型DPは得意でない人が多いのかもしれませんね。EDPCを埋め直すとABCでお得に立ち回れるかもしれませんから、要検討です。

A問題

問題文を見て過去のPanasonicコンのトラウマがよみがえりましたが、今回は普通に式をべた書きするだけで良くて、I got a kotonaki.

B問題

xについて全部試せばよい。

C問題

普通に実装難しかったと思うんですが、23分時点で3完緑パフォで死ぬほどびっくりしました。やっぱり私は実装が苦手みたいですね。もっと下埋めして、茶、緑パフォの問題を詰まらずに実装しきる力をつければ安定しそうです。

ところで、これってポインタをswapすれば2のクエリも O(1)で処理できたりしませんかね -> できました

更にいうと、C++のstringは参照型なので、普通にswapしても O(1)らしいです。diffが妙に低い要因の一つはこれかも？

D問題

Eの方ができそうな見た目をしていたので、後回しにしたまま解けませんでした。

連結成分ごとにやると、最初の頂点以外は高々2回程度しか探索しないため解ける。なるほど良い問題だなあという感じです。ただ同じ頂点を通らないようにDFSしながら探索するのはかなり面倒でした。解説にある通り、連結成分の頂点を過不足なく列挙してから探索していくと実装が楽だったと思います。

E問題

これが青diffなの、ありがたいです。この前のBFSとbitDPを合わせる問題もそうでしたが、妙に皆さん解けていない気がしますね。bitDPは遷移がワンパターンだし、制約で察することができるのでかなり楽に方針が立つタイプの典型だと思います。式変形なども必要ありませんし。

順列の状態をまとめるのは明らかにbitDPの使いどころで、巡回セールスマンしかり非常に有名な状態の持ち方だと思います。一度WAを出しはしましたが、かなりスムーズに解くことができました。

F問題

期待値ゲーはコンテスト中に解けると思っていません。別記事でまとめます。

まとめ

とにもかくにも、いい結果が出せて良かった......。何とか青に辿り着けるよう、努力を続けます

ABC135 F Strings of Eternity

やる

問題文

読んで

考察

自明に単調性があるので、二分探索で決め打てそうなことがわかります。問題は決め打ったときの判定なので、まずはそこを考察していきます。

ひとまず愚直に考えます。 tを x回連結した文字列 Tを作ります。では sを y回連結した文字列 Sは Tの部分文字列を持ちますか？という問題がめっちゃ速く解けると嬉しいですね。

厄介なのは sを y回連結するというところです。 xの方は二分探索で決め打つので良いのですが、 yはそう上手くいきません。何か上手く考えると一意に定まりそうな気配もしますが、愚直に時間をかけてもアレなんですよね...。ひとまず置いておきます。

二分探索で判定は、愚直にやると筋が悪い気がしてきたので別方面を考えます。

何も思いつかないので解説を見ました。あ～～～～文字の関係をグラフとして解釈するやつ三回は解いたのに忘れてたなあ.....。 Sは tの大体二倍くらいの長さにしてあげれば良くて、あとはロリハなり何なりで辺張って、ループがなければUFして連結成分の最大値取っておしまい。

ループがあったら -1にして、そもそも辺が張られていなければ 0。

うわ～かしこい。言われれば素直に出来るし、解けるべきだったなあと......

ABC197 感想と反省

終了ギリギリで5完。滑り込めたのは嬉しかった。1482パフォってしょっぱいね。まあでも水復帰したからOK。

A問題 Rotate

うし

B問題 Visibility

びーと

C問題 ORXOR

一瞬マジでびっくりしたけど N = 20で安堵。ちょっと実装にもたついたがWAなしで通ったのでよし。

D問題 Opposite

本当にカス。どうすればいいのか全然分からず一旦Eに行った。その後重心から回転させればいいんじゃね？ということに気づき、重心を原点に移して回転させて戻すコードを適当にぴゃぴゃっと書いたら20秒前に通った。嬉しいよりも先に驚きが来た。嬉しいです。

E問題 Traveler

一瞬貪欲に見えて困惑していたけど、無事グラフに読み替えることができた。端だけを見れば良いということをお気持ちで何となく信じて丁寧にダイクストラしてAC。DPでも良いとは思ったが、辺さえしっかり張れればダイクストラ自体は何も考えずに済むのが大きい。

F問題 Construct a Palindrome

自力ACは出来たが、Twitterで結構ヒント見ちゃってたからなあという気持ち。
ただまあ考察していくと正直やれることはあんまりなくて、前と後ろのペアを見て、進めるところを進んでいくダイクストラなりBFSなりで解くしかなさそうだなという気持ちになって、お祈りしながらBFSを回すと通った。

計算量的に考えると確かにそこまで多くなくて、高々[tex: N2]くらいの計算しか回らないからそうだなあ確かにという感じ。

これをもっと速くできれば青も夢じゃないんだが...

ABC195 F Coprime Present

翌日のARCのAでも似たようなの見ましたね。

問題

読んで

解法

自明解として、 {2}^{B-A+1}の計算を回せば答えは出ます。

まあ流石にそれは間に合わないので高速化を考えます。選んだ数の集合すべてのペアが互いに素であるということは、素因数分解した際に素因数が同じであるものがないということを表します。しかし素因数分解をしたくても、最大の数が {10}^{18}だったりするので、素因数分解は難しいでしょう。

B-A \leq 72とかいう変な制約がバチバチに怪しいのでこれを踏まえて考えてみます。

まず互いに素ということは、偶数同士は絶対に同じにできません。0以外の偶数は素因数に2を含むからです。そして偶数は一つ飛ばしで並んでいます。

同様に、3の倍数同士も絶対に同じにできません。3の倍数は二つ飛ばしで並んでいます。

そのようなことを考えていると、 B-A \leq 72なので、たかだか 72までの素因数しか考えなくて良さそうな気持ちになります。

証明してみます。

72よりも大きい素数で、かつ一番小さい数は 73です。ある数の組が互いに素ということは、二つの数を素因数分解した際に、素因数が同じであるものがないということと同義です。

二つの数を素因数分解した際に 73が両方に出てくるということは、両者が 73の倍数であるということです。 73の倍数は72飛ばしで並んでいます。

しかしこの問題では選べる数の範囲が最大でも72個の連番になっています。つまり範囲の最初に 73の倍数があっても、次の 73の倍数は範囲外となってしまいます。

これより、 73より大きい素数で初めて割れる数は、与えられた入力の中では実質的な素数として扱っても差し支えはなさそうです。

よって、たかだか 72までの素数で素因数分解してやればいいということがわかりました。

そして 72までの素数はちょうど 20個であるので、 {2}^{20}は十分間に合います。

あとはbitDPで解けるんですが、このbitDPは思いつかなかったな......。含んでいる素数でbit全探索を考えて壊れました。

その後含んでいる素数でbitDPを考えたんですが回らず、解説を見ると aから bの数を一つ一つ集合に加えていくかでbitDPということがわかって、それはそう～と叫ぶとACできました。うーんこの辺は純粋に経験の差だなあ。もっと詰めていきます。

#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define rep(i,n) for(ll i=0;i<(n);++i)
typedef long long ll;
using namespace std;

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    ll a, b; cin>>a>>b;

    const vector<ll> prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71};

    auto prime_factor = [&](ll x) {
        int m = prime.size();
        ll tmp = 0;
        rep(i,m) {
            if (x%prime[i] == 0) {
                tmp |= (1<<i);
            }
        }
        return tmp;
    };

    ll ans = 0;
    ll n = prime.size()+1;
    vector<ll> dp(1<<n);
    dp[0] = 1;

    for (ll i = a; i <= b; ++i) {
        for (ll bit = 0; bit < (1<<n); ++bit) {
            if (dp[bit] == 0) continue;
            ll t = prime_factor(i);
            bool ok = true;
            rep(j,n) {
                if (bit & (1 << j) && t & (1 << j)) {
                    ok = false;
                }
            }
            if (!ok) continue;
            ll nxt = bit | t;
            dp[nxt] += dp[bit];
        }
    }

    rep(i,(1<<n)) ans += dp[i];
    cout << ans << '\n';

    return 0;
}

ABC195 E Lucky 7 Battle

最近忙しくてこまる。精進する精神的な余裕が.......。 何かDPをするのはわかったんだけど微妙に合わなかった。たすけて

問題概要

読んで

考察

うーん、7で割ったあまりで状態が表せることはわかって、前からDPしたけどダメでしたね。

こういうゲーム系の問題を状態遷移で考える時は、後ろから必勝かどうかを考えていくといいらしい。そういえばgrundy数とかもそんな感じですね。これは典型として絶対覚えておきます。

後ろからやるタイプのDPはよくある「 i番目までみたときに云々」ではなく「 i番目から始めたときに云々」と解釈すると頭がすっきりします。

dp(i, j) := iターン目に7で割ったあまりが jである状態から始めたとき、高橋君の勝ちが確定しているかどうか という関数を考えます。

え、これ初期化どうすんねん。後ろから必勝かどうかを考えたい -> まず一番後ろの判定どうするの という気持ちになって困ってしまいました。しかし上の定義をよく考えると、 Nターン目から始めたときに勝つかどうかなので、 Nターン目に7で割ったあまりが 0のものだけ勝つということが言えます。

そして遷移は

  1. s_iを採用するか 0をつけるかで場合分け
  2. 高橋君のターンか青木君のターンかで場合分け

の二つについて考える必要があります。

まず一つ目の場合分けですが、

s_iを採用した場合 (10 \times j + s_i) mod\ 7が次のあまりになり、

0を採用した場合は (10 \times j) mod\ 7が次のあまりになります。

これを踏まえたうえで二つめの場合分けを考えます。

まずどちらのターンにしろ、後ろから更新していくので dp(i+1, j) ( 0 \leq j \leq 7)の状態は勝つか負けるかが確定しています。

自然言語で説明すると「 i+1番目のターンから始めたときどうなるか」がわかっているので、その情報をもとに「 i番目のターンから始めたらどうなるか」を考えたいです。

  • 高橋君のターンの場合

結論から言うと、

x = (10 \times j + s_i) mod\ 7

y = (10 \times j) mod\ 7 とおいて、

dp(i, j) = dp(i+1, x) \lor dp(i+1, y)

です。

自然言語で説明すると、「 iターン目から i+1ターン目には s_iか 0のどちらかを選ぶことで遷移出来て、その i+1ターン目のどちらか片方でも勝ちが確定した状態であればそちらに遷移すればいいので、 iターン目から始めても高橋君の勝ちが確定した状態になる」

ということになります。

  • 青木君のターンの場合

やはり結論から言うと

dp(i, j) = dp(i+1, x) \land dp(i+1, y)

です。 xや yは高橋君のターンと同じ値を表しています。

自然言語で説明すると、「 iターン目から i+1ターン目には s_iか 0のどちらかを選ぶことで遷移出来て、その i+1ターン目が両方とも勝ち確定状態だった場合のみ、青木君は逃げ場がないので iターン目から始めても高橋君の勝ちが確定した状態になる」

ということです。

これを実装するとACします。以下コード。やっぱメモ化再帰はラムダ式が楽だなあ。

#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,n) for(ll i=0;i<(n);++i)
#define REPR(i,n) for(ll i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}


int main(int argc, char const *argv[]) {
    int n;
    cin>>n;
    string s,t; cin>>s>>t;

    vector<vector<bool>> memo(n+1, vector<bool>(7, false));
    vector<vector<bool>> vi(n+1, vector<bool>(7, false));
    
    auto dp = [&](auto &&f, int i, int j) -> bool {
        if (i == n) return (j == 0);
        if (vi[i][j]) return memo[i][j];
        vi[i][j] = true;

        int d = s[i]-'0';
        int x = (10*j+d)%7;
        int y = (10*j)%7;

        bool ret = false;
        if (t[i] == 'A') {
            ret |= (f(f, i+1, x) && f(f, i+1, y));
        }
        else {
            ret |= (f(f, i+1, x) || f(f, i+1, y));
        }

        return memo[i][j] = ret;
    };

    if (dp(dp, 0, 0)) cout << "Takahashi" << '\n';
    else cout << "Aoki" << '\n';

    return 0;
}

ABC194 反省

もう何もかもがダメ。嫌な気持ちになりすぎて昨日精進する気がおきませんでした。

最近調子が上向いていたので、悲しいです。

A問題 I Scream

よく読んでif文を書けという問題。地味に誤読しました。サンプルありがとう。

B問題 Job Assignment

N \leq 1000 なので二重ループを回せばおしまいです。

C問題 Squared Error

灰色diffってマジ？？？？？？？？？？

あー A_i \leq 200 であることを利用するのか。まったく思いつきませんでした。確かにね。

式変形してホイだけど、地味に実装バグらせて悲しかった。

D問題

問題の問題。いやこれ緑diffってマジです？？何も信じられません。下位層のレベル上がりすぎ。

とりあえず期待値は期待値DPだと思ってうんうん唸ったものの、まあ解けず。

反省として、なにやら上手い式をひねり出すのに固執していたことが悪かったですね。僕の実力でそんなにうまいこと行くわけないのです。

そもそも実質的には全ての頂点を選ぶまでの期待値なので、「サイコロ 全ての目が出る 期待値」とか検索すればよかったです。
これは見えるべきでした。というか見えていたのに、シンプルな問題に換言できませんでした。

取り組んでいる複雑な問題を、明らかに単純そうな問題、或いは明らかに既出な問題に落とし込むのは競プロの基本なので、これが出来なかったのは大反省ですね。

何をすればいいかわからず、視野狭窄な状態になっていたのが最大の敗因でしょう。これは「何をすればいいか分からなくなったときの定石」みたいなものを持っておく必要がありますね。

今までは「単純な問題に切り分けて考えてみる」しか選択肢を持っていなかったのですが、「元の問題の言い換えを考える」ことも意識していきたいです。

さて、「望みの出目が来るまでサイコロを振る期待値は、その出目が出る確率の逆数になる」という有名事実があるらしいです。せめてこのあとは自力で行きたいですね。

出来ませんでした。なるほどここでDP的な考え方を使うのか.......いや難しすぎる。純粋な論理の難しさなら明らかに水色diff以上はあると思います。

f(i) := 残りi個の頂点を選ぶときの期待値と置きます。

ここで「まだ選ばれていない i個の頂点から一つ選ばれる」時の期待値は N/(N-i)です。

よって f(i) = f(i-1) + N/(N-i)と表せて、これが答えです。

https://kimiyuki.net/blog/2016/04/28/dice-and-expected-value/

上記サイトを参考にしました。

E問題 Mex Min

地獄みたいに苦しんだんですが、最初に提出したコードのインデックスを正しいものに変えると2WAまで減って、今持っている数列に番兵入れると全部通りました。敗因はインデックスをきちんとあわせなかったことです。ちゃんと図を書いて確認して実装すればこんなことには.....(10WA)

F問題 Digits Paradise in Hexadecimal

んー何かよくある桁DPなんですが、種類というのが面倒そう？

dp[i][j][l] := i桁目まで見て、 jでN未満か以下かをフラグとして持って、 lでその数を含んでいるかどうかを[{2}^{k}]の集合で管理したdpみたいなものをとりあえず考えてみます。

うーん、その数を含んでいるかどうか、というのが {2}^{k}の状態を必要としていて、これをどうにかする必要がありそうです。え、こんなの解けるんですか？という気持ちになるので解説を見ると、解けることが分かります(完)

今まで自分が持っていた桁DPのレパートリーにはない考え方を用いて解く必要がありました。解けなかった原因はそこにあります。

今まで自分が理解していた考え方としては、この神記事で紹介されているような「一文字ずつ各桁を決めていく」やり方でした。

普通はこの考え方でうまくいくんですが、今回の場合一文字ずつ決めていくと集合を持つ必要が出てきて、ダメなんですね。

こういうときは自前で新しい遷移を組むしかないので、考えます。

ひとまず、dp[i][j] := i桁目まで見て、 j種類の数を含んでいる N以下の数と扱います。

定石として、leading zeroやlessフラグが真である状態での遷移を考えてみます。

場合分けして考えます。もし i+1桁目に今までに使われていない数が使われた場合の数は

dp[i+1][j+1] += dp[i][j] * (16 - j)

です。同様に、 i+1桁目に今までに使われた数を持ってくる場合の数は

dp[i+1][j] += dp[i][j] * j

です。

前者の場合の妥当性ですが、まずleading zeroやlessフラグが常に真である状態を考えているため、 i+1桁目には今まで使われていない数であれば何を持ってきても良いです。
そして、dp[i][j]までは既に数えられているので、純粋に末尾に何をくっつけるか？ということのみ考えれば良いです。

よって、dp[i+1][j+1] += dp[i][j] * (16 - j)として状態をまとめられます。

後者の場合も同様です。

さて、これはleading zeroやlessフラグが常に真である状態を考えていたので、次にlessフラグが偽であるときを考えます。

これはまあlessフラグが偽である = Nとまるきり同じである

ということを意味しているので、適当に今まで出てきた数を管理しておけば

dp[i+1][今の種類数 + 1] += A

dp[i+1][今の種類数] += B

となります。ここで

[tex A := ] 今まで使われておらず、 s_iよりも真に小さいものの数

[tex B := ] 今までに使われていて、 s_iよりも真に小さいものの数

となります。leading zeroについては、与えられる文字列にleading zeroはないことから考えなくて良いです。

最後にleading zeroですが、今まで全部ゼロで、 i+1桁目に初めてゼロ以外が出るという話になります。また、今まで全部ゼロなので、自明に N より小さい状態です。

よって dp[i+1][1] += 15 となります。

以上、全ての遷移パターンを網羅できたので、実装するとACになります。