不定期プログラミング覚え書き

青コーダーと黄コーダーの間を彷徨う社会人プロコン勢が余力のあるときに復習した内容をまとめるブログ

yukicoder #361: 門松ゲーム2

すごい今更ですけど門松シリーズの解説に於いて門松列の定義は省略してます許してください。

問題

No.361 門松ゲーム2 - yukicoder
kado君とmatsu君が交互に竹を \max(A_0,A_1,A_2)-\min(A_0,A_1,A_2)<=Dを満たす門松に分割していくゲームを行う。これ以上竹を分割できなかったほうが負である。
初期状態の竹の長さLとDが与えられた時に両者が最適にプレイしたらどちらが勝つか答えよ

考えたこと

どう考えてもgrundy数です。
grundy数について復習すると、長さLの竹を(a,b,c)に分割した時、(a,b,c)の状態のgrundy数はgrundy[a]^grundy[b]^grundy[c]である。
grundy[L]は、分割できるすべての状態に対するgrundy数の集合 {grundy[a]^grundy[b]^grundy[c] (a+b+c=L, max(a,b,c)-min(a,b,c)<=b, a,b,cは門松列) }に含まれない最小の0以上整数。

コード

pythonで500^3くらいの実装したら(そもそも実装おかしかったんだけど)TLE返してきたのでC++にチェンジ。

int main(){
   int L,D;
   cin >> L >> D;
   vector<int> grundy(L+1,0);
   for( int i = 6; i <=L; i++ ){
      set<int> grundies;
      for( int x=1; x<=L; x++ ){
         for( int y=x+1; y<=L; y++ ){
            int z = i-x-y;
            if( z <= y ) continue;
            if( z-x >D ) continue;
            //cout << i<<"->"<<x<<","<<y<<","<<z<<endl;
            grundies.insert(grundy[x]^grundy[y]^grundy[z]);
         }
      }
      for( int g = 0 ; g < 500; g++ ){
         if( grundies.find(g)==grundies.end() ){
            grundy[i]=g;
            break;
         }
      }
      
   }
   if( grundy[L] == 0){
      cout << "matsu"<<endl;
   }
   else{
      cout <<"kado"<<endl;
   }
   return 0;        
}

後で試してみたところ、頑張ればpythonでも通りました。
pythonで通すためには、
分割範囲の上限・下限をちゃんと求める(ループ内でif文判定をしない)ことと、
分割後のgrundy数の集合の取り方を工夫する必要がある(少なくともsetとか重複付きリストとかじゃ最大ケースでTLEだった)。
既存のpython3で提出していたrpy3cppさんのコード#87862 No.361 門松ゲーム2 - yukicoderを確認にしたところ、grundy数の上限値は高々Lであるので、
長さLのbool行列Bを作っておいて、分割後のgrundy数に対応する場所をTrue埋めしてenumerate(B)を回すのが賢い方法。
言われてみれば確かにsetとか使う必要無いなあ。

L,D=map(int,raw_input().split())

ans=[0 for i in range(L+1)]
for i in range(6,L+1):
    grundies=[False for j in range(L)]
    for j in range(max((i-2*D)/3,1),(i+2)/3+1):
        for k in range(max(j+1,i-2*j-D),(i-j+1)/2):
            l=i-j-k
            num=ans[j]^ans[k]^ans[l]
            grundies[num]=True
    for a,used in enumerate(grundies):
        if not used:
            ans[i]=a
            break
if ans[L]==0:
    print "matsu"
else:
    print "kado"

yukicoder #360: 増加門松列

問題

No.360 増加門松列 - yukicoder
任意の連続する3数が門松列であり、右側の方が大きい時それを増加門松列という。
7つの数字が与えられるので、並べ替えて増加門松列が作れるか答えよ、という問題

考えたこと

7要素程度なら全部の順列についてチェックすれば良い。
難易度更新されたけれど、359よりもこっちの問題が断然簡単だと思った。

コード

pythonでnext_permutation的なものあるかな?と調べつつ実装。
冷静に考えて前にも調べたことある気がする。

import itertools
def isKadomatsu(A):
    if A[0]==A[1] or A[1]==A[2] or A[0]==A[2]:
        return False
    elif A[0]<A[1] and A[1]>A[2]:
        return True
    elif A[0]>A[1] and A[1]<A[2]:
        return True
    return False
X=map(int,raw_input().split())
for line in itertools.permutations(X):
    ok=True
    for i in range(5):
        B=[line[i],line[i+1],line[i+2]]
        if( isKadomatsu(B) and B[0]<B[2] ):
            continue
        else:
            ok=False
            break
    if ok:
        print "YES"
        exit()
print "NO"

yukicoder #359: 門松行列

本番で1時間くらい頑張って書いたけど力尽きた。
解説読んで「あーなるほど!」と思ったけど一発で通せなかった。なかなかに悔しい問題。

問題

No.359 門松行列 - yukicoder
2つ歯抜けになっている3*3のマス目がある。
タテ・ヨコ・ナナメがすべて門松列になるように長さLの末を2分割して配置したい。分割方法の数を答えよ

考えたこと (コンテスト時。筋の悪い思考)

ひとまず歯抜けのマス目以外で門松列とならない部分があれば問答無用で解は0である。
以下3通りを考える。
(1) 歯抜けのマスが真ん中だった時
 歯抜けのマスに入るべき数値は「両端のマスの最大値より大きい or 両端のマスの最小値より小さい」
(2) 歯抜けのマスが端であり、真ん中のマスの値>逆端のマスの値の時
 歯抜けのマスに入るべき数値は「逆端のマス以外 and 真ん中のマスより小さい」
(3) 歯抜けのマスが端であり、真ん中のマスの値<逆端のマスの値の時
 歯抜けのマスに入るべき数値は「逆端のマス以外 and 真ん中のマスより大きい」
この条件のもとにそれぞれのマスに入りうる長さの区間を更新すれば良い。
区間更新方法は
「(1)ある区間[l,r:を禁止する」「((2),(3)の前半)ある値pを禁止する 」「((2)後半)ある値pより小さい 」「((3)後半)ある値pより大きい」で、
これらに加えて「 x\in [l,r] \leftrightarrow L-x \in [p,q]となる区間p,qの計算」と、区間のマージを実装すれば良い。

……まで、一通り実装し、example 1が正しい答えを返す所まで来て、
この考え方だと2つ歯抜けとなってる列の処理で大変なことになることに気付いた(ここで心が折れた)。

解説を読んで

yukicoder
なるほど!と思った。
要するに、(1),(2),(3)をみるとうっすら見えるように、マス目に入るべき数値の境界線は既存のますの数値±1に(ほぼ)限られる
この考えのもとに歯抜けのマスの数値として検証すべき区間を算出し、各区間それぞれが題意を満たすかをシミュレートすればよい。

……ただし、これだけ実装して提出すると、以下の時にWAを出す。
L=28, A= \begin{matrix}47& 24& 40\\33&0&0\\37&49&43\end{matrix}
要するに、2つ歯抜けとなっている列の処理が必要ということである。

改めて条件を書いてみると
(4)両端が歯抜けの場合
「歯抜けの値2つはそれぞれ異なり、共に中央の値より大きい or 小さい」
(5)真ん中と端が歯抜けの場合
 (5-a) 真ん中の歯抜け>端の歯抜けの場合:「端の歯抜け!=逆端の値 and 真ん中の歯抜け>逆端の値」
(5-b) 真ん中の歯抜け<端の歯抜けの場合:「端の歯抜け!=逆端の値 and 真ん中の歯抜け<逆端の値」
と言えるが、(4),(5)どちらとも、2つの歯抜けの大小関係が異なるポイント(L/2)が境界条件として必要であることがわかる。

コード
def rangesplit(L,p):
    ret=[]
    for l,r in L:
        if r<p:
            ret.append((l,r))
        elif p<l:
            ret.append((l,r))
        else:
            if l<=p-1 :
                ret.append((l,p-1))
            if p+1<=r :
                ret.append((p+1,r))
            ret.append((p,p))
    return ret
def isKadomatsu(A):
    if A[0]==A[1] or A[1]==A[2] or A[0]==A[2]:
        return False
    elif A[0]<A[1] and A[1]>A[2]:
        return True
    elif A[0]>A[1] and A[1]<A[2]:
        return True
    return False


T=int(raw_input())
for ti in range(T):
    L=int(raw_input())
    A=[map(int,raw_input().split()) for i in range(3)]
    # l is too short
    if L==1:
        print 0
        continue 

    # set where is blankpoint
    blank=[]
    ranges=[(1,L-1)]
    ranges=rangesplit(ranges,L/2)
    for i in range(3):
        for j in range(3):
            if A[i][j]==0:
                blank.append((i,j))
            else:
                if A[i][j]< L:
                    ranges=rangesplit(ranges,A[i][j])
                    ranges=rangesplit(ranges,L-A[i][j])
    checkList=[[(0,0),(0,1),(0,2)],
               [(1,0),(1,1),(1,2)],
               [(2,0),(2,1),(2,2)],
               [(0,0),(1,0),(2,0)],
               [(0,1),(1,1),(2,1)],
               [(0,2),(1,2),(2,2)],
               [(0,0),(1,1),(2,2)],
               [(0,2),(1,1),(2,0)]]
    
    ans=0
    for l,r in ranges:
        Btmp=A
        Btmp[blank[0][0]][blank[0][1]]=l
        Btmp[blank[1][0]][blank[1][1]]=L-l
        ok=True
        for line in checkList:
            for (p,q) in line:
                B=[A[p][q] for (p,q) in line]
                if not isKadomatsu(B):
                    ok=False
                    break
        if ok:
            ans+=r-l+1
    print ans

……日数置いてから「うん?」と思ったけど、これBtmp作った意味が全く無かったというか、
その後でB=[A[p][q]...]と書いてる時点で、本来意図した動きを実現するコードではなかった。

c++vectorの=が要素のコピーだからうっかりこう言う書き方しちゃったけど、pythonでのlistの代入は参照渡しなので、
Btmpの値を書き換える=>Aの値も書き換えられる=> B=[A[p][q]...]と書いても書き換えた値が参照される、という形で動いてしまった様子。
今回のケースは各Btmpの書き換え操作が「歯抜けますに値を代入する」という相互に悪影響のない操作だったためにこれでも通ってしまった、というオチである。
Btmpを全部Aに書き換えたほうがスマートでしたね

yukicoder #358: も~っと!門松列

yukicoderの結果を書こうとしてふと気付いたれど、コンテスト参加ごとにブログ記事をまとめる必要って無いですね(解けない問題の処理とか確かに困ってたし)。
今後は問題ごとに記事をわけて書いていきたいと思う。

考えたこと

 (A_0, A_1, A_2)が与えられた時に  B=(A_0 \% p, A_1 \% p, A_2 \% p) が門松列となるようなpの個数を求める問題。
pが \max(A_0,A_1,A_2)よりも大きくなると任意のpでB=(A_0,A_1,A_2)になるため、これが門松列である場合は解は無限個。
逆に言えばそうでない場合はpが \max(A_0,A_1,A_2)以下であるケースを数え上げれば良い。

コード

プロコンで初めてラムダ式使いました。
門松列判定行列は関数化すれば良かったと書いてから後悔しました。

A=map(int,raw_input().split())
MA= max(A)
if A[0]==A[1] or A[1]==A[2] or A[0]==A[2]:
    print 0
elif A[0]<A[1] and A[1]>A[2]:
    print "INF"
elif A[0]>A[1] and A[1]<A[2]:
    print "INF"
else:
    ans=0
    for i in range(1,MA+1):
        B=map(lambda x:x%i,A)
        if B[0]==B[1] or B[1]==B[2] or B[0]==B[2]:
           continue
        if B[0]<B[1] and B[1]>B[2]:
           ans+=1
        elif B[0]>B[1] and B[1]<B[2]:
           ans+=1
    print ans

AtCoder Regular Contest #051

ω・`)ノ ヤァ

最近TopCoderのレートが低迷気味のため、ちゃんと日記書こうと思いました。

もはや日記の書き方(?)すら忘れてるレベル。

A問題:塗り絵

問題

A: 塗り絵 - AtCoder Regular Contest 051 | AtCoder

考えたこと

円と四角だから完全に重複することないので、以下2つをチェックすれば良い。

円が四角を囲う条件:4隅全部が円の中にある判定すれば良い

四角が円を囲う条件:円の最上点・最下点・最右点・最左点が四角の範囲か判定

コード
int main(){
   int x1,y1,r,x2,y2,x3,y3;
   cin >> x1>>y1>>r>>x2>>y2>>x3>>y3;
   if( x1+r <= x3  && x1-r>=x2 && y1+r <= y3 && y1-r >= y2 ){
      cout << "NO"<<endl;
   }
   else{
      cout << "YES"<<endl;
   }
   int dx[] = {x2-x1,x3-x1};
   int dy[] = {y2-y1,y3-y1};
   bool no=true;
   for( int xi=0;xi<2;xi++ ){
      for( int yi=0; yi<2; yi++ ){
         if( dx[xi]*dx[xi]+dy[yi]*dy[yi] > r*r ){
            no=false;
            break;
         }
      }
   }
   if( no ){
      cout <<"NO"<< endl;
   }
   else{
      cout <<"YES"<<endl;
   }
   
   return 0;
}

B問題:互除法

問題

B: 互除法 - AtCoder Regular Contest 051 | AtCoder

考えたこと

互除法の逆計算を行うだけ。

初期状態がa=0,b=1 (K=0の時) だと逆計算できないので、

a=1,b=2(K=1の状態)からスタートすることにする。

コード
int main(){
   int K;
   cin >> K;
   int b=1;
   int a=2;
   for( int i = 1 ; i < K; i++ ){
      b+=a;
      swap(a,b);
   }
   cout << a << " " << b << endl;
   return 0;
}

C問題:掛け算

考えたこと

とりあえずリストの最大値を超えない範囲でAをかけ続けることを考える。

A=1だと無限ループに陥るが、

そもそもA=1の場合は計算しなくて良いので、例外処理。

リストの最大値を超えない範囲でAを掛け切ったリストをbとし、あとAを掛ける必要がある回数をB_remainとすると、それ以降はAの掛ける順番はbの小さい順である。

よって、すべての要素にAをB_remain/N回掛けて、(ここは大きな値になるのでダブリング処理する)残りのB_remain%N回を小さい順にかけて上げれば良い。

コード

突然のpython

mod 1000000007の計算をするときにlong longとintをちゃんと使い分けるのが面倒くさいな、くらいの軽い気持ちで書いたけど、heapqの使い方など忘れてて時間を食った。

import heapq
N,A,B=map(int,raw_input().split())
a=map(int,raw_input().split())
m=1000000007

def calc(A,ex,m):
    ret = 1
    mul = A
    while ex!= 0:
        if ex%2 == 1:
            ret*=A
            ret%=m
        A*=A
        A%=m
        ex/=2
    return ret

if A==1:
    a.sort()
    for ans in a:
        print ans
    exit()

MA=max(a)
bi=0
for i in range(N):
    curA=a[i]
    while curA*A < MA:
        curA*=A
        bi+=1

if bi>B:
    heapq.heapify(a)
    for bi in xrange(B):
        n=a[0]
        heapq.heappop(a)
        heapq.heappush(a,n*A)
    for i in range(N):
        print a[0]
        heapq.heappop(a)

else:
    for i in range(N):
        while a[i]*A < MA:
            a[i]*=A
            B-=1
    a.sort()
    ex=B/N
    common=calc(A,ex,m)
    r=B%N
    for i in range(N):
        a[i]*=common
        a[i]%=m
    for i in range(r):
        a[i]*=A
        a[i]%=m
    for i in range(r,N):
        print a[i]
    for i in range(r):
        print a[i]
もっと早く出すために

時間かけすぎてしまった反省点メモ。
最大値を超えない範囲でAを掛けきってしまわずに計算終了するケースと、更にその先を計算するケースについて、ほぼ別ロジックで書かれている。

(しかも、Aを掛けきるかどうか?の処理として無駄に似たようなコードが2回書かれている。残念極まりないコードである)

この理由は、前者のケースでドヤってheapqを使おうとしたせいだった。

kmjpさんのコード(Submission #696154 - AtCoder Regular Contest 051 | AtCoder)を見て気付いたけれど、

今回の制約条件ではheapqなんぞ使わずとも毎回sortし直す実装にすれば無駄なケース分けや、heapqの使い方を調べる時間は削減できた。

(Aを掛けきるまでの掛け算回数はたかだか1500回、ソートにかける時間は 50 log 50……余裕ですね)

D:長方形

D: 長方形 - AtCoder Regular Contest 051 | AtCoder

考えたこと

BIT使う系かと思ったけど違うっぽいしDPでも解けそうにない。

つまり、僕には解けない。

復習

りんごさんのニコ生解説が神だった。

AtCoder Regular Contest 051 解説放送 - 2016/04/16 22:30開始 - ニコニコ生放送 48分くらいから。

前処理として、a_w,b_hそれぞれについてi番目の要素まででj個の連続する要素の和の最大値wMax(i,j),hMax(i,j)を計算しておく。

すると、クエリA、Bが来た時に返すべき値は

Z= wMax(A,p)*q+hMax(B,q)*pの最大値である。

qの値を固定して考える。

例えばq=3, hMax(B,q)=4だとする。

すると、この問題は 3wMax(A,p)+4pの最大値を返せば良い。

x=p,y=wMax(A,p)とすると、これはz=3y+4xを最大にする点(p,wMax(A,p))(1<=p<=A)を探す問題になる。

受験数学でお馴染みのy=4x/3-z/3の線を上から被せていって最初にぶつかる頂点を探す問題と同じである。

これはプログラム的には(p,wMax(A,p))の凸包を計算し、二分探索的に求めることが可能である。

まとめると、

Qクエリそれぞれについて、まず(p,wMax(A,p)) (1<=p<=A)の凸包を計算 (O(W))して後、

各 q について (O(H)) 二分探索的にwMax(A,p)*q+hMax(B,q)*pの最大値を計算(O(log W) )し、

最終的な最大値を返す。

これは O(Q* (W+ HlogW) ) だけの計算量となるため、2000*2000*log(2000) = 1.3*10^7

くらいで計算できる。

コード

凸包ライブラリが盛大にバグっていた(外積部分)のでつぎはぎで対処している。

通りはしたけどまだバグってるかも知れないし、ちゃんとメンテしないとな。

long long product( pair<int,int> p1, pair<int,int> p2, pair<int,int> p3 ){
   pair<int,int> v1 = make_pair( p2.first-p1.first, p2.second-p1.second);
   pair<int,int> v2 = make_pair( p3.first-p2.first, p3.second-p2.second);
   return -(v2.first*(long long)v1.second-v2.second*(long long)v1.first);
}
vector< pair<int,int> > convex_hull( vector<pair<int,int> > &V){
   if( V.size() <=2 ) return V;
   int size = V.size();
   sort(V.begin(),V.end());
   vector<pair<int,int> > ret(size*2);
   int retlen=0;
   for( int i = 0 ; i <size; i++ ){
      while( retlen >= 2 && product( ret[retlen-2],ret[retlen-1],V[i] ) <= 0 ) retlen--;
      ret[retlen++]=V[i];
   }
   int underlen=retlen;
   for( int i = size-2 ; i >= 0 ; i-- ){
      while( retlen > underlen && product( ret[retlen-2],ret[retlen-1],V[i] ) <= 0 ) retlen--;
      ret[retlen++]=V[i];
   }
   ret.resize(retlen);
   return ret;
}


int main(){
   int W,H;
   cin >>W >> H;
   int a[W];
   int b[H];
   for( int i = 0 ; i <W; i++ ) cin >> a[i];
   for( int j = 0 ; j <H; j++ ) cin >> b[j];
   for( int i = 0 ; i < 2001; i++ ){
      for( int j =0; j <2001; j++ ){
         wMax[i][j]=hMax[i][j]=-(INT_MAX/2);
      }
   }
   for( int i = 1 ; i <=W; i++ ){
      int cur=0;
      for( int j =0; j<i; j++ ){
         cur+=a[j];
      }
      wMax[i][i]=cur;
      for( int j=i+1; j<=W; j++ ){
         cur -= a[j-1-i];
         cur += a[j-1];
         wMax[j][i] = max(wMax[j-1][i],cur);
      }
   }
   for( int i= 1 ; i <= H ; i++ ){
      int cur = 0;
      for( int j=0; j <i; j++ ) cur+=b[j];
      hMax[i][i]=cur;
      for( int j=i+1; j<=H ; j++ ){
         cur -= b[j-1-i];
         cur += b[j-1];
         hMax[j][i] = max( hMax[j-1][i],cur);
      }
   }

   int Q;
   cin >> Q;
   for( int qi = 0; qi<Q; qi++ ){
      int A,B;
      cin >> A>> B;
      int* w=wMax[A];
      int* h=hMax[B];
      vector<pair<int,int> > ps;
      for( int x=1; x<= A; x++ ){
         ps.push_back( make_pair(x,w[x]));
      }
      vector<pair<int,int> > poly = convex_hull(ps);
      // maximize w[x]*y + h[y]*x
      /*
      for( int i = 0 ; i < (int) poly.size(); i++ ){
         cout << poly[i].first << ", " << poly[i].second<<endl;
      }*/
      long long ans = -2000000;
      for( int y = 1; y <= B ; y++ ){
         int left=0;
         int right=(int)poly.size()-1;
         while( left < right ){
            int mid = (left+right)/2;
            //cout <<left <<"- "<< mid <<"- "<<right << endl;
            long long midValue = poly[mid].first*(long long)h[y]+poly[mid].second*(long long)y;
            long long neighbourValue = poly[mid+1].first*(long long)h[y]+poly[mid+1].second*(long long)y;
            //cout << midValue <<"vs"<<neighbourValue<<endl;
            if( midValue > neighbourValue )right=mid;
            else left=mid+1;
         }
         //cout << y<<": "<< right<<": "<< poly[left].first <<", "<< poly[left].second<<endl;
         ans =max( ans, poly[right].first*(long long)h[y]+poly[right].second*(long long)y);
      }
      cout << ans << endl;

   }
   return 0;
}

TCO2014 R2B

350-500-900とか350諦めて500目指すのワンチャンあるか? とか思っていたら350も激ムズだったし500は問題文の意味が解らなくて0点レート急降下回。
350のチャレンジとかもうチョット頑張れたりしたんだろうか。Failed System Testの人は何人かいたのだけれど。

Level ProblemName Status Point
Easy SwitchingGame Failed System Test(Practiced) 0.0
Medium SumAndProductPuzzle Opened(Practiced) 0.0
Hard --- Unopened 0.0

Easy SwitchingGame

問題

すべてオフになったN個のランプがある。
L番目に満たすべきランプの状態を+(ランプがON),-(ランプがOFF),?(どちらでも良い)からなるstring配列states[]で表現する。
ユーザは以下の操作を繰り返して与えられた条件statesを順番にクリアしていきたい

  1. ONのランプを複数個選択して一気にOFFにする
  2. OFFのランプを複数個選択して一気にONにする
  3. 現在のランプが満たすべき条件を満たすかチェックする

最小の操作数を求めよ

考えたこと

な ん や こ れ!
とりあえず、li個の条件をクリア済みとした時に、
ni番目のランプの満たすべき条件states[li][ni]が +の時や-の時は何やかんやすれば良さそうなので、
states[li][ni]が?である場合を中心に考えることにする。
もっとも、states[li][ni]が?だとしても、将来的にni番目のランプが充たさなければいけない状態と現在のランプの状態が一緒ならば、
そのランプについては常に状態を保存すれば良いので考えなくても良い。
よって、一番厄介なのは states[li-1][ni]が+、states[li][ni]からstates[li+X-1][ni]が?、states[li+X][ni]が-の時(または+-が逆の時)というケース
さらに、この場合でも、他のランプの状態具合に変更 li-1+k個の条件をクリアした段階で+から-へと変更せざるを得ない時は、
便乗してランプの色を変えれば良い。
以上の操作をして、残ったケースについて最適なランプ変更タイミングを考えれば何とかなりそう。
…ケース集合とクリア状況集合の二部グラフとか作って最大フローとか流せばいいんですか?(←間違い)
ゴリッと書いてSummaryチラ見したらみんな早々に提出してて絶望しつつsubmitする
→落ちた\(^o^)/

復習

フローとか流さないで極力状態保存するように粘る貪欲でおkだった…orz
と言うかフローで最適なランプ変更タイミングが出せるかというとそんなことは全然なかった。
あと極力状態保存する貪欲で何か問題が発生することも無かった。

コード(system test通過済み)
   int timeToWin(vector <string> states){
     vector<string> S;
     int L = states.size();
     int N = states[0].size();
     string start(N,'-');
     S.push_back( start );
     for( int i = 0 ; i <(int)states.size(); i++ ) S.push_back( states[i]);
     bool sw[L][2];
     memset( sw, false, sizeof(sw));
     for( int li=0; li < L; li++ ){
      for( int ni=0; ni<N; ni++ ){
        if( S[li][ni] != '?' && S[li+1][ni] != '?' &&  S[li][ni]!=S[li+1][ni] ){
          if( S[li][ni] == '+' ) sw[li][0] = true;
          else sw[li][1] = true;
        }
      }
     }
     int ans = L;
     for( int i = 0 ; i < L ; i++ )
       for( int j = 0 ; j < 2; j++ ){
        if( sw[i][j] ) ans++;
       }

      for( int li=1; li <= L ; li++ ){
      for( int ni = 0 ; ni < N ; ni++ ){
        if( S[li][ni] == '?' && S[li-1][ni]!='?' ){
          char s = S[li-1][ni];
          int curL = li;
          while( curL <= L && S[curL][ni] == '?' ) curL++;
          if( curL > L || s == S[curL][ni] ){
            for( int l = li ; l < curL; l++ ) S[l][ni] = s;
          }
          else{
            int bit = 0;
            if( s == '-' ) bit = 1;
            if( sw[li-1][bit] ){
              S[li][ni] = S[curL][ni];
            }
            else{
              S[li][ni] = s;
              if( li+1 <= L && S[li+1][ni]!='?'&&S[li+1][ni]!=S[li][ni] && !sw[li][bit]){
                ans++;
                sw[li][bit]=true;
              }
            }
          }
        }
      }
      /*
      for( int ni = 0 ; ni < N; ni++ ){
        cout << S[li][ni];
      }
      for( int bit = 0 ; bit < 2; bit++){ cout << sw[li-1][bit]<<" ";}
      cout << endl;*/
     }
     return ans;
  }
  

Medium SumAndProductPuzzle

問題

数学者SusanとPriscillaがいた。
Susanは二つの数x,yの総和x+yを持っており、Priscillaはx*yを持っていた。
Susanが「ふふふ…私の持っている数を特定することはできまい( ・´ー・`)」
とドヤ顔したところ、Priscillaはこの発言によってSusanの数字を特定することができたという。

このような会話が成立するSusanの持つ数字Sで、A以上B以下であるものの総和を返せ。

考えたこと

SusanとPriscillaの会話をどう解釈したらいいのかわけわからんのだが詰んだ

復習

TLを眺めていたところ、どうやらこう言う意味だったらしい。

これらの発言を読んだ上でもまだ解法とか色々解っていなかったんですが、少なくとも以上2ツイートのお陰で問題の会話の意図が以下だと理解しました。
Susanが持っていた数Sを分解したとき、a(S-a)は常に合成数であるため、SusanはPriscillaが自分の値を特定不可能と考えた。
しかし、Priscillaが持っていた数字をMとすると、M=x*yを満たしx+yが上の条件を満たすx,yの組合せはひとつしか存在しなかった。
数学っぽく書くと、このような会話が成立するSusanの手持ちSとは、
 Q(S)\wedge( \exists M ( (\exists x, R(M,x)) \wedge (\forall x \forall x2, (R(M,x)\wedge R(M,x2))\to x=x2) \wedge (\forall x, R(M,x) \to x+M/x=S) ))
 Q(S)=\forall a, S-a\geq a \to a(S-a)は合成数
 R(M,x)= (M \% x = 0)\wedge (M/x\geq x) \wedge Q(x+M/x)
ということである。これを少しずつ解けそうな雰囲気まで持っていくのが今回の問題。

まず、Q(S)を簡単にする。a>=2の時a(S-a)が合成数なのは自明なので、Q(S)はS-1が合成数であると書き換えても構わない。
これを新たにP(S-1)と表記することにする。

次に、\exists x R(M,x)を満たすMは少なくとも合成数である。
何故ならば、Mが素数であったとすると、Mは1*Mとしか乗算に分解できないが、Q(1+M)は1+M-1素数であることよりR(M,x)の三番目の条件が成立しないからである。
一方、Mが合成数とすると、x=1は1+M-1が合成数であることよりR(M,x)を成立させるとわかる。
このことより、後半の条件は、 (\forall x, x\geq 2 \to not R(M,x)) \wedge M+1=S と書き換える事ができる。
以上のことから、Sの満たすべき条件とは、
 P(S-1) \wedge \exists M,( P(M)\wedge (\forall x, x\geq 2 \to not R(M,x))\wedge M+1=S)
すでにMとSの関係が得られているのでM=S-1を代入して
 P(S-1)\wedge (\forall x, x\geq 2 \to not R(S-1,x))
これを計算すれば良い。
Pの判定はエラトステネスの篩をつかえばよく、
Rの判定は2以上の整数x,yを取り出した時にQ(x+y)=P(x+y-1)が成立する場合はR(x*y,x)がx>=2で成立する(つまりこの場合はx*yはNG)、といった具合に計算する。

コード
class SumAndProductPuzzle {
   public:
   long long getSum(int A, int B){
   bool isprime[5000001];
   memset(isprime,true,sizeof(isprime));
   vector<int> prime;
   for( int i = 2 ; i*i < 5000001; i++ ){
    if( isprime[i] ){
      prime.push_back(i);
      for( int j = i+i ; j < 5000001; j+= i ){
        isprime[j]=false;
      }
    }
   }
   bool ok[5000001];
   memset( ok, true, sizeof(ok) );
   for( int i = 2 ; i*i < 5000001; i++ ){
    for( int j = i ; i*j < 5000001; j++ ){
      if( !isprime[i+j-1] ) ok[i*j] = false;
    }
   }
   long long ans =0;
   for( int i = A; i <=B; i++ ){
    if( !isprime[i-1] && ok[i-1] ) ans += i;
   }
   return ans;
  }
感想

I hate math!!!

SRM623

Google Code JamでTシャツ圏外だったりCodeForcesでDiv2に落ちたりTCO Marathon Match全く話にならなかったり最近負け続きである。
少しでも復習とかちゃんとやっていかないと駄目ですねこりゃ。と思っての更新。参加記執筆速度も多分上げたほうが良いんだろうな。
とりあえず有給とってのSRM回位はちゃんと書きましょう。ちなみにレートは微増。有給とってレート下がるとさすがにテンション下がるので少しでも上がってよかった。

Level ProblemName Status Point
Easy UniformBoard Passed System Test 227.30
Medium CatchTheBeat Opened(Practiced) 0.0
Hard AliceAndFriends Unopened 0.0

Easy

問題

正方形のマス目があり、各セル上に林檎とナシが置かれてたり置かれてなかったりする。
プレイヤーはK回(所与の値)以内の果物の移動(果物をあるセルから取り出し、空セルへと移動させる操作)によって、
林檎で敷き詰められた長方形の面積を最大化したい。最大の面積を答えよ。

考えたこと

マス目の長さ最大が20とかだし普通にあり得る長方形領域を愚直な探索させればいいんじゃないか?
ある長方形領域が与えられたときに、その中を林檎で敷き詰めるためには、各セルについて
林檎がある:何もしないでおk
空セル:何処かから林檎をもってくる1ステップ必要(長方形の面積<林檎の個数ならそのような林檎は必ず存在)
ナシがある:ナシをどこかにどける&林檎を持ってくるの2ステップ必要(空セルがどこか一つあれば可能な操作であることに注意)
というステップ数を加算すれば求められる。
領域全列挙が20^4でステップ数の計算が20^2、正味20^6位だけど 20^6=6.4*10^7だからなんとかなるっしょ

コード
   int getBoard(vector <string> board, int K){
     int size = board.size();
     int n_apple=0;
     bool possible = false;
     for( int i = 0 ; i < size; i++ ){
      for( int j = 0 ; j < size; j++ ){
        if( board[i][j] == '.' ) possible = true;
        if( board[i][j] == 'A') n_apple++;
      }
     }
     cout << n_apple << endl;
     int ans = 0;
     for( int height = 1 ; height <= size; height++ ){
      for( int width = 1; width <= size; width++){
        int area = height*width;
        if( area > n_apple ) continue;
        for( int x = 0 ; x+height-1 < size; x++ ){
          for( int y = 0 ;y+width-1 < size; y++ ){
            int curK = 0;
            for( int dx = 0 ; dx < height; dx++ ){
              for( int dy = 0 ; dy < width ; dy++ ){
                int curX = x+dx;
                int curY = y+dy;
                if( board[curX][curY] == 'A' ) continue;
                if( board[curX][curY] == 'P' ){
                  if( possible ){
                    curK += 2;
                  }
                  else{
                    curK += 5000;
                  }
                }
                if( board[curX][curY] == '.' ){
                  curK ++;
                }
              }
            }
            //cout << height << ", "<< width << ", "<< x <<", "<<y<< ", "<< curK << endl;
            if( curK <= K ){
              ans = max(ans,area);
            }
          }
        }
      }
     }
     return ans;
  }

Medium CatchTheBeat

問題

2次元座標においてy=0の直線を1秒距離1の速度で移動するプレイヤーと
x[0]=x0-offset,x[i+1]= ((x[i]+offset)*a+b % mod1)-offset
y[0]=y0, y[i+1]=(y[i]*c+b) % mod2
によって計算可能な果物の初期位置(x[i],y[i])が与えられる。
果物は1秒にy軸と水平に1だけ落ちるとする。
プレイヤーは巧みに移動しながら果物の回収量を最大化したい。

考えたこと

移動可能なところに枝張って最大流とかにする的何か?
いやそんなことないな。っていうかノード数500000ってかなりきつくね。
何とかして NlogNくらいで計算しろってことだとは思うけど…
(x[i],y[i])をとった後に取れる果物の範囲って y-x >=(y[i]-x[i]) かつ y+x >= (y[i]+x[i])の範囲なのだが、
これを活かすことはできるだろうか…十分大きなy座標におけるこの区間の重複を数えたりすればいいのか?
→試しに書いてみたけど全然違うわ。アカンわこれ。

復習

一位だったmsg555さんのコードを読んだ。y-xとy+xを使うという着想は割りと良かったらしい。
ちょっとだけ一般化を意識した書き方をすると、今回の問題は、
各果物iについてパラメタAi(=y-x),Bi(=y+x)という値が計算でき、
Ai<=AjかつBi<=Bjだった時のみ果物i,jは連続取得可能とした時、最大取得果物数を答えるということ。

では肝心の解き方については、まず各果物について(A,B)を計算してソートさせることで、
i番目の果物とj番目の果物はiB_(k+1), dp[k][p-1]<=B_(K+1) )
dp[k+1][p]= dp[k][p] otherwise
となる。
これはvector構造とupperbound関数を使ってlogNのオーダでupdate可能である。
よって、これを繰り返していって最終的なdp[last]のサイズが解となる。

コード
   int maxCatched(int n, int x0, int y0, int a, int b, int c, int d, int mod1, int mod2, int offset){
     long long x[n];
     long long y[n];
     x[0]=x0;
     y[0]=y0;
     for( int i = 1 ; i < n ; i++ ){
      x[i] = (x[i-1]*a+b)%mod1;
      y[i] = (y[i-1]*c+d)%mod2;
     }
     for( int i = 0 ; i < n ; i++ ){
      x[i]-=offset;
     }
     vector<pair<int,int> > vs;
     for( int i = 0 ; i < n ; i++ ){ if( y[i] >= abs(x[i]) )vs.push_back(make_pair(y[i]+x[i],y[i]-x[i])); }
     sort(vs.begin(),vs.end());
     vector<int> V;
     for( int i = 0 ; i < (int)vs.size() ; i++ ){
      vector<int>::iterator it =  upper_bound(V.begin(),V.end(),vs[i].second);
      if( it == V.end() ) V.push_back(vs[i].second);
      else *it = vs[i].second;
     }
     return V.size();

  }
考察

正直これ今後類問が出ても全然解ける気がしないけど…
二つのパラメタが両方優位の時だけ更新、みたいなモデルを考えるのは微妙に汎用性あるのかもしれないので、頭の片隅には入れておきたい気がする。