2018-10-04

SRM519 Div1Easy BinaryCards

SRM 練習会

考察

あるカードをドット面にするとき、それ以下のカードは全部ドット面…じゃあ、めくるカードの集合を出せばいけそう。
1~32まで手でシミュレーションをしていると、「AからBまで遷移させる操作の中で、めくるカードはA^Bの最上位bit以下のもの」であることがわかる。あとはそれを全部めくったものが答え。

ex)

A=1001(9)からB=1100(12)の遷移は9:{1001,1011}→10:{1010}→11:{1011,1111,1101}→12:{1100}であり、めくるカード全体は0111。これはA^B=0101の最上位bitから確認できる。

実装

肝心の、最上位bitの良い求め方がわからなかったので調べたら面白いページが出てきた。明日使えないすごいビット演算.いくつか拝借して関数化した。
maxって型違うと比較できないんだ…というか0はint型なんだ。

#include <bits/stdc++.h>
using namespace std;

class BinaryCards {
public:
    // 最上位bit
    unsigned long long MSB(unsigned long long n){
        n=n&0xFFFFFFFF00000000?n&0xFFFFFFFF00000000:n;
        n=n&0xFFFF0000FFFF0000?n&0xFFFF0000FFFF0000:n;
        n=n&0xFF00FF00FF00FF00?n&0xFF00FF00FF00FF00:n;
        n=n&0xF0F0F0F0F0F0F0F0?n&0xF0F0F0F0F0F0F0F0:n;
        n=n&0xCCCCCCCCCCCCCCCC?n&0xCCCCCCCCCCCCCCCC:n;
        n=n&0xAAAAAAAAAAAAAAAA?n&0xAAAAAAAAAAAAAAAA:n;
        return n;
    }
    long long largestNumber( long long A, long long B ){
        long long diff=MSB(A^B);
        return (B|(max(diff-1,0ll)));
    }
};

2018-10-03

SRM518 Div1Easy LargestSubsequence

SRM 練習会

問題URL：LargestSubsequence
最長増加部分列(LIS)が連想されたけどそうでもなかった。
ひさびさに瞬殺できる問題が来てうれしい。

考察

サンプル2:exampleの部分文字列で辞書順最大を考える。
この中で一番大きいのはxだから、まずxが確定。次に取るべきはxより右の文字列ampleの中で最大のもの(左から取ったら明らかに小さくなる)。この中の最大はpだからxpが確定して…とやるとxpleが答え。こんな感じで、前に取った文字よりも右側の文字のうち最大となるものを取るといい。複数あったら一番左。

実装

exampleを後ろから順に大小評価するとxxppleという文字列ができる。これは「自分とそれより右側で最大の文字」を表す。すると後は元の文字列とのdiffを取るだけでよい。 $O(|S|)$

#include <bits/stdc++.h>
using namespace std;

class LargestSubsequence {
public:
    string getLargest( string s ){
        int n=s.size();
        string t=s;
        for(int i=n-2;i>=0;i--){
            t[i]=max(t[i],t[i+1]);
        }
        string ans;
        for(int i=0;i<n;i++){
            if(s[i]==t[i]) ans+=s[i];
        }
        return ans;
    }
};

2018-09-27

SRM517 Div1Easy CompositeSmash

SRM 練習会

問題URL：CompositeSmash
グラフを最初、CSAcademyのGraph Editorで描いていたが、なんかぐわんぐわんして腹立ったのでやめた。手書きは手書きでミスしたときが面倒なことに気付いたので、今度から多分またデジタル。

考察

素因数分解したら法則性が見えるのだと思っていたが、実際は虚無。想定しうる分け方を全部試したい気持ちになったので、下図のようなグラフを描いてみると、これはどうやらDFSで行けそう。~~君、再帰書けるの?~~

f:id:ChiyosBigDragon:20180921194412j:plain — SMAAAASH!!のやりかた

実装

素因数の組み合わせをbitで全列挙し、それぞれについて再帰を行う。再帰が苦手な理由として、「どこでreturnするのかわからない」というのがあるので逐一、値を出力する。すると何回も同じ値が呼び出されていることに気が付き、計算量を見積もっていないことも相まって不安になる。そのためメモ化しているが、今考えるとクリティカルではなさそうだし、むしろmemo[]をクラス内に書いてバグってしまった。こういうところの理解が足湯より浅い。

#include <bits/stdc++.h>
using namespace std;

// 0=未/1=ok/2=no
int memo[100010];
class CompositeSmash {
public:
    int goal;
    // 素因数分解
    vector<int> prime_factorization(int n){
        vector<int> v;
        if(n==1) v.push_back(1);
        int i=2;
        while(n>1){
            if(n%i==0){
                n/=i;
                v.push_back(i);
            }else{
                i++;
            }
        }
        return v;
    }
    // 探索
    bool dfs(int n,vector<int> v){
        if(memo[n]==1) return true;
        if(memo[n]==2) return false;
        // cout<<n<<endl;
        if(n==goal) {memo[n]=1;return true;}
        // どう割っても無理
        if(n%goal!=0) {memo[n]=2;return false;}
        // 素因数の組み合わせ
        int vv=v.size();
        for(int i=1;i<=vv/2;i++){
            vector<int> p;
            for(int j=0;j<vv-i;j++) p.push_back(0);
            for(int j=0;j<i;j++) p.push_back(1);
            do{
                 vector<int> l,r;
                 int le=1,ri=1;
                 for(int j=0;j<vv;j++){
                     if(p[j]){
                         l.push_back(v[j]);
                         le*=v[j];
                     }else{
                         r.push_back(v[j]);
                         ri*=v[j];
                     }
                 }
                 // cout<<le<<" "<<ri<<endl;
                if(!dfs(le,l)&&!dfs(ri,r)) {memo[n]=2;return false;}
            }while(next_permutation(p.begin(),p.end()));
        }
        memo[n]=1; return true;
    }
    // 判定
    string thePossible( int N, int target ){
        goal=target;
        for(int i=0;i<100010;i++) memo[i]=0;
        if(dfs(N,prime_factorization(N))) return "Yes";
        else return "No";
    }
};

2018-09-26

SRM516 Div1Easy NetworkXOneTimePad

SRM 練習会

問題URL：NetworkXOneTimePad

考察

全てのciphertextが、plaintextsの内どれか1つに戻るようなkeyの数を求める。xorの性質を考えるとこれは、

写像 key: ciphertexts → plaintexts が単射であるような、keyの数を求める

と言い換えられる(ﾎﾝﾄ?)

そんなことは割とどうでもよくて、結局やることはciphertexts[0]をplaintexts[i]に戻せるようなkeyが他のciphertextも戻せるかの確認。

実装

$50^{4}$ が間に合うのか確認するのがだるかった(≒ $O(N^{4})$ を嫌った)ので、stringをlong longに変換。これで前計算 $2\times 50^{2}$ 、実行 $50^{3}$ で確実に間に合う。ここまでやっといて^(xor)の計算量が $O(1)$ じゃなかったら笑う。

#include <bits/stdc++.h>
using namespace std;

class NetworkXOneTimePad {
public:
    int crack( vector <string> plaintexts, vector <string> ciphertexts ){
        vector<long long> p,c;
        for(auto i:plaintexts){
            string s=i; reverse(s.begin(),s.end());
            long long a=1,sum=0;
            for(auto j:i){
                sum+=a*(j-'0');
                a<<=1;
            }
            p.push_back(sum);
        }
        for(auto i:ciphertexts){
            string s=i; reverse(s.begin(),s.end());
            long long a=1,sum=0;
            for(auto j:i){
                sum+=a*(j-'0');
                a<<=1;
            }
            c.push_back(sum);
        }
        int ret=0;
        for(auto i:p){
            long long key=c[0]^i;
            bool flg1=1;
            for(auto j:c){
                bool flg2=0;
                for(auto k:p){
                    if((j^key)==k) flg2=1;
                }
                if(!flg2) flg1=0;
            }
            if(flg1) ret++;
        }
        return ret;
    }
};

2018-09-23

今日の反省会場

AtCoder 反省して♡

AtCoder Beginner Contest 110
unratedだったとして喜んでいいのか

どうして2完なの?

C

S→Tが全射と決め打ってWA。心折られる。というか全単射の証明難しくないか。

D

前日のコドフェスCの想定解がDPだったことから、数え上げ→DPのイメージが出来上がる。はじめ非DP解で重複組み合わせまで行くも、前日の考察経路に重複組み合わせがあったためDP解に切り替える。遷移式まで出すも計算量がまずい。そうこうしてたら終わり。

DのDP解は結局どうなりましたか?¹

dp[ $i$ ][ $j$ ]:=左から $i$ 番目まで見て、積が $j$

とやるのは $O(NM)$ で流石に無理なので…。 $j$ について考えると、結果に影響するのは $j$ が $M$ の約数のとき。（数列に $M$ の約数しか出てこないしね）これを考慮すると座圧チックなことができて、

dp[ $i$ ][ $j$ ]:=左から $i$ 番目まで見て、積が $M$ の約数の小さいほうから $j$ 番目

に直せる。このとき $O(N\times (Mの約数の個数)^{2})$ の実装は思いつくのでざっと計算してみる。約数の個数が大きそうな数でパッと思い浮かぶのが、 $892371480=2^{3}\times3\times5\times7\times11\times13\times17\times19\times23$ で $1024$ 個。 $10^{3}$ オーダーは間違いなさそうなので大体 $10^{11}$ 回…~~ICPCなら間に合うんじゃね~~

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

int prime_factorization(int n){
    int ret=1;
    int i=2,cnt=1;
    while(n>1){
        if(n%i==0){
            n/=i;
            cnt++;
        }else{
            ret*=cnt;
            cnt=1;
            i++;
        }
    }
    ret*=cnt;
    return ret;
}

int dp[100000][2500];

int main(){
    int n,m; cin>>n>>m;
    // 座圧みたいな
    int nn=prime_factorization(m);
    map<int,int> mp;
    int cnt=0; for(int i=1;i*i<=m;i++)if(m%i==0){mp[cnt]=i,mp[nn-1-cnt]=m/i,cnt++;};
    // dp[i][j]:=i番目まで見て積がmの約数でj番目になる個数
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<nn;j++){
            for(int k=0;k<=j;k++){
                if(mp[j]%mp[k]==0) dp[i][j]+=dp[i-1][k]%MOD;
                dp[i][j]%=MOD;
            }
        }
    }
    cout<<dp[n][nn-1]<<endl;
    return 0;
}

解答漁ってたらdp[10^5][32]の解があるらしい。解読次第追記↩

2018-09-19

SRM515 Div1Easy RotatedClock

SRM 練習会

問題URL：RotatedClock
プロコンほとんど関係ないんですけど、河合塾のひらめく数学チャレンジ2018の第2弾-3問目に今回の類題があるので、時計問題マニアの方にはおすすめです。~~ちなみに第1弾-3問目は完全にAnts~~

考察

0時に対して短針が $30k+n°$ であるとき、長針は $12n°$ であるのが適切な位置関係。0時にあたる基準を0~11の範囲で全探索して、いい感じになればok。

実装

基準を置く代わりに短針と長針を $30°$ ずつずらす。これを12回やる。 $30k+n°$ の $n°$ は基準によらず一定。なので先に求めたけどあんまり意味ない。最後、解答を文字列に直すのが一番だるい。printf("%02d:%02d")使いたい。

#include <bits/stdc++.h>
using namespace std;

class RotatedClock {
public:
    string getEarliest( int hourHand, int minuteHand ){
        int h=hourHand%30*12;
        int ansh=20,ansm=20;
        for(int i=0;i<12;i++){
            hourHand-=30;
            if(hourHand<0) hourHand+=360;
            minuteHand-=30;
            if(minuteHand<0) minuteHand+=360;
            if(minuteHand==h){
                if(hourHand/30<ansh){
                    ansh=hourHand/30;
                    ansm=minuteHand/6;
                }
            }
        }
        string ret;
        if(ansh!=20){
            if(ansh<10) ret+="0";
            ret+=to_string(ansh);
            ret+=":";
            if(ansm<10) ret+="0";
            ret+=to_string(ansm);
        }
        return ret;
    }
};

2018-09-18

SRM514 Div1Easy MagicalGirlLevelOneDivOne

SRM 練習会

問題URL：MagicalGirlLevelOneDivOne
数学で解くことにもう少し抵抗を感じたい。
連立方程式の書き方が調べてもよくわからない。他人のブログのソースを見たら、pタグ内にベタで書いてあった。そのまま真似したらうまくいって、素で声が出た。

<p>
\begin{cases}
    x=-t_1+t_2+(t_3+t_4)n \\
    y=(t_1+t_2)n+t_3-t_4 \\
    n=jumpType
\end{cases}
</p>

考察

どう見ても $O(1)$ 解がありそう。

いまいちピンと来ないので、式を立ててやってみる。移動方向と回数に注目すると、

\begin{cases} x=-t_1+t_2+(t_3+t_4)n \\ y=(t_1+t_2)n+t_3-t_4 \\ n=jumpType \end{cases}

を満たす整数 $t_1t_2t_3t_4$ が存在するか? という問題に変わる。詰み。これで解ける人は教えてください。

実は上の考察中、「 $n$ の値によらず、 $X,Y$ 軸に対して±2ずつ平行移動できる」ことに気付く。これが本質だった。あとは以下の表に則ってやるだけ。

$(n,x,y)$	経由点(例)	$(n,x,y)$	経由点(例)
$(偶,偶,偶)$	$(0,0)$	$(奇,偶,偶)$	$(0,0)$
$(偶,偶,奇)$	$(n,1)$	$(奇,偶,奇)$	むり
$(偶,奇,偶)$	$(1,n)$	$(奇,奇,偶)$	むり
$(偶,奇,奇)$	$(n+1,n+1)$	$(奇,奇,奇)$	$(n,1)$

f:id:ChiyosBigDragon:20180914171146p:plain — ±2ずつ並行移動

実装

$n$ が奇数&& $x+y$ が奇数のときだけ除外するように書く。

#include <bits/stdc++.h>
using namespace std;

class MagicalGirlLevelOneDivOne {
public:
    string isReachable( vector <int> jumpTypes, int x, int y ){
        string ret="NO";
        for(auto i:jumpTypes){
            if(i%2==0){
                ret="YES";
            }else{
                if((x+y)%2==0) ret="YES";
            }
        }
        return ret;
    }
};

考察

ex)

実装

考察

実装

考察

実装

考察

実装

どうして2完なの?

C

D

DのDP解は結局どうなりましたか?1

考察

実装

考察

実装

DのDP解は結局どうなりましたか?¹