問題 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…