今更気づいたけど、ZOJ3123って蟻本に載ってる問題じゃん。どや顔でO(nlogn)解法書いたけど、O(n)解法がのってるやん…。

問題 シーザーは兵士を整列させるのが大好きで、n1人の歩兵とn2人の騎兵を所有しています。彼にはこだわりがあって、k1人より多く歩兵が連続して並んでいたり、k2人より多く騎兵が連続して並んでいるのは、美しくない並び方だと思っています。n1,n2,k1,k2が…

問題 自然数nが与えられる。各桁が0と1だけで表される数が、1からnの範囲にいくつあるか答えよ。(n 解法 2進表記を10進数とみなした数を作って比較する。 コード int tob(int n){ int b = 0; stack<int> stk; while(n){ stk.push(n%2); n/=2; } while(!stk.empty(</int>…

問題 バーランド国は新しい硬貨を作ろうと考えた。その硬貨は、それよりも安いすべての硬貨で割り切れるものでなくてはならない。一番高い硬貨の値が与えられるので、なるべく硬貨の数が多くなるように硬貨を構成せよ。 解法 1になるまで、割れる素数で割っ…

問題 n人の男と、m人の女がいる。t人の選び方が何通りあるか求めよ。ただし、t人の中に少なくとも4人の男と1人の女が含まなければならない。(n,m 解法 combinationを使って計算。 コード int main(){ ll comb[50][50]; REP(i,50)comb[i][0] = comb[i][i] = 1…

問題 122344→11221324のような変換をする。(1個の1,2個の2,1個の3,2個の4).。 コード int main(){ int n; cin>>n; while(n--){ string s; cin>>s; s += '#'; int count = 1; FOR(i,1,s.size()){ if(s[i]!=s[i-1]){ printf("%d%c",count,s[i-1]); count = 1; …

ZOJ :: Problems :: Show Problem 問題 n個の文字列が与えられる。ある文字列が、もう一方の文字列のprefixになるような２つの文字列が存在するか判定する。 解法 O(n^2)の全探索だと間に合わない。sortして隣り合う文字列を調べるとo(nlogn)で判定できる。 …

問題 多項式の微分をする。入出力は係数。 解法 やるだけ。 コード int main(){ int T; cin>>T; while(T--){ int n; cin>>n; REP(i,n){ int C; cin>>C; printf("%d",C*(n-i)); putchar((i==n-1)?'\n':' '); } if(!n)cout<<0<<endl; cin>>n; } return 0; }</endl;>

問題 長さNの数列a[0],..,a[N]が与えられる。総和がSを超えるような連続する部分列の、最小の長さを求めよ。 解法 まず部分和sを計算する(s[i+1] = s[i] + a[i], s[0] = 0)。 するとa[i],...,a[j]の総和はs[j+1]-s[i]となるので、始点iを決めると、終点はS+s…