Unknown Language Round #3
http://www.codeforces.ru/contest/100/standings
久しぶりの開催を楽しみにしてました。
とりあえず、言語公開。
7z解凍。
インストール。
動かし方がよくわからないので、cygwinのホームディレクトリにpike用のフォルダを作り実行ファイルをコピーして、shellから呼び出せるようにして書き始めました。
meadowだと最初から、pike用のモードみたいなのが入ってるみたいで有り難かったです。
A
- 読む。
- 辺を埋めるのに必要な枚数を求めてそれを二乗して足りるか足りないかを見ました。
- 簡単な入力の取り方を覚えました。
- ただ、最初はずっとin queue状態だったので、無事に終わるのか心配になりました。
17分
int main(){ string s=Stdio.stdin->gets(); int n,k,n1; sscanf(s,"%d %d %d",n,k,n1); int n2=(n-1)/n1+1; if(n2*n2<=k)write("YES"); else write("NO"); }
C
- Aの次に多く解かれていたので、解く。
- ただの足し算だけれど多倍長っぽい。
- ためしに普通に書いてみる。
- 自動的に多倍長になった。
26分
int main(){ int a=(int)Stdio.stdin->gets(); int b=(int)Stdio.stdin->gets(); write(sprintf("%d",a+b)); }
B
- 取り敢えず、入力の取り方がさっぱり分からないので、ググったり、ライブラリを検索したりしまくる。
- foreachで取れそう。
- とれた。
- サンプルが通ったので提出。WA on 5
- 個数が1のときはnotかも。
- WA on 3
- しばらく考えて、0が含まれていたり、負の数が含まれていたりするんじゃないかと思ったのでその処理を加える。
- AC
44分
int main(){ int n; sscanf(Stdio.stdin->gets(),"%d",n); array(int) in=({}); foreach(Stdio.stdin->gets()/",",string pp){ in=Array.push(in,(int)pp); if((int)pp==0){ write("NOT FRIENDS"); return 0; } } for(int i=0;i<n;++i){ for(int j=0;j<i;++j){ if(in[i]%in[j]!=0 && in[j]%in[i]!=0){ write("NOT FRIENDS"); return 0; } } } write("FRIENDS"); }
D
- 文字列の編集距離を答えるというような問題。
- 二つの文字列の後ろの部分の違う文字の個数分変えられるかを考えればいい。
50分
int main(){ int n; sscanf(Stdio.stdin->gets(),"%d",n); string a=Stdio.stdin->gets(); string b=Stdio.stdin->gets(); int as=sizeof(a); int bs=sizeof(b); int ml=as; if(ml>bs)ml=bs; int i=0; for(;i<ml;++i){ if(a[i]!=b[i])break; } if(as-i+bs-i<=n)write("Yes"); else write("No"); }
I
- 座標の回転。
- cosとかsinとかで検索するとMath.Angle.sinとかがヒットして、「えっ？えっ？」みたいになる。
- 普通にsin,cosあった。
- 書く。
- 何となく型を二重にしてみた。
58分
int main(){ float|int k; int x,y; sscanf(Stdio.stdin->gets(),"%d",k); sscanf(Stdio.stdin->gets(),"%d %d",x,y); k=(float)k*Math.pi/180.0; write(sprintf("%.10f %.10f\n",x*cos(k)-y*sin(k),x*sin(k)+y*cos(k))); }
E
-
- 頑張って愚直シミュレーションを書く。
- TLE。
- 1ばっかり出現しているとやばいと思い、出現した個数で元に戻るものは無視するように。
- やっぱりTLE。
- 高速な入力方法とか無いのかとかおもいましたが、面倒くさいので仕方なく、一旦あきらめて他の問題へ。
F
- Eがさっぱり分からないので、次に解いている人の多いFへ。
- 面倒くさい場合分けゲーだと思いながら書く。
- サンプルを必死になって合わす。
- 多少のWAを覚悟したけれど、なんとか一発AC
1時間46分
int main(){ int n; sscanf(Stdio.stdin->gets(),"%d",n); array(int)in=({1}); for(int i=0;i<n;++i){ int k; sscanf(Stdio.stdin->gets(),"%d",k); array(int) tin=copy_value(Array.push(in,0)); for(int i=1;i<sizeof(tin);++i)tin[i]+=k*in[i-1]; in=copy_value(tin); } int pr=0; for(int j=0;j<=n;++j){ if(in[j]==0)continue; if(j==n){ if(in[j]>0 && pr==1)write("+"); write(sprintf("%d",in[j])); }else if(j==n-1){ if(in[j]>0 && pr==1)write("+"); if(in[j]!=1 && in[j]!=-1)write(sprintf("%d*X",in[j])); else if(in[j]==1)write("X"); else write("-X"); }else{ if(in[j]>0 && pr==1)write("+"); if(in[j]!=1 && in[j]!=-1)write(sprintf("%d*X^%d",in[j],n-j)); else if(in[j]==1)write(sprintf("X^%d",n-j)); else write(sprintf("-X^%d",n-j)); } pr=1; } if(pr==0)write("0"); write("\n"); }
G
- 与えられたルールで最もふさわしいものを出力。
- これも頑張って場合分けする。
- 文字列の辞書順比較はC++と同じ感じでできました。
- 他の人の解答を見ると、もっとすっきり書けるっぽくてちょっと残念。
2時間0分
int main(){ int n,k; sscanf(Stdio.stdin->gets(),"%d",n); mapping(string:int)app=([]); for(int i=0;i<n;++i){ string s; int y; sscanf(Stdio.stdin->gets(),"%s %d",s,y); app[s]=y; } sscanf(Stdio.stdin->gets(),"%d",k); string ans=""; int ye=2013; for(int i=0;i<k;++i){ string s; sscanf(Stdio.stdin->gets(),"%s",s); if(ans==""){ ans=s; if(has_index(app,s)==1)ye=app[s]; else ye=1800; }else{ if(has_index(app,s)==1){ if(app[s]==ye){ if(s>ans)ans=s; }else{ if(app[s]<ye){ ans=s; ye=app[s]; } } }else{ if(ye==1800){ if(s>ans)ans=s; }else{ ans=s; ye=1800; } } } } write(ans); }
E
- 再びEに。
- なぜこんなにも遅いのかと思いテストケースを自分で作って手元で実行してみる。
- 1万くらいの入力だと４秒くらいで終わる。
- 10万だと全然間に合わない。
- もっと詳しく測ってみるとArray.push()が異様に遅いことが分かったので、なんとか配列を事前生成する方法を探す。
- allocateを見つける。
- 使う。すぐに答えでた。
2時間27分
int main(){ int n,k; sscanf(Stdio.stdin->gets(),"%d",n); array(string)in=Stdio.stdin->gets()/" "; array(int)app=allocate(n); //for(int i=0;i<n;++i)app=Array.push(app,0); sscanf(Stdio.stdin->gets(),"%d",k); foreach(Stdio.stdin->gets()/" ",string pp){ int t=(int)pp; app[t-1]=1-app[t-1]; } for(int i=1;i<=n;++i){ if(app[i-1]==0)continue; for(int j=i;j<=n;j+=i){ if(in[j-1][1]=='f')in[j-1][1]='n'; else in[j-1][1]='f'; } } for(int i=0;i<n;++i){ if(in[i][1]=='n')write("on "); else write("off "); } }
H
- 前にPKUで見て面倒くさそうだと思って解くのをしなかった問題にすごく似ているとか思いながら、仕方ないから書くことに。
- ゴリゴリと書いて、上下左右のマスを見るのを埋め込みでやったあとに、サンプルの2つ目が合わないので、よく見ると斜めにも触れてはいけないようだったので、6方向を配列で見るコードに書き換えて提出。AC
2時間47分
array(string) in=allocate(10); int check(){ array(int) app=allocate(4); for(int i=0;i<10;++i){ for(int j=0;j<10;++j){ if(in[i][j]=='0')continue; if(j==9 || in[i][j+1]=='0'){ int sz=0; for(;i+sz<10;++sz){ if(sz>4)return 0; if(in[i+sz][j]=='0')break; in[i+sz][j]='0'; array(int) dx=({-1,0,1,-1,0,1}); array(int) dy=({-1,-1,-1,1,1,1}); for(int k=0;k<6;++k){ int nx=i+sz+dx[k]; int ny=j+dy[k]; if(0<=nx && nx<10 && 0<=ny && ny<10 && in[nx][ny]=='*')return 0; } } app[sz-1]++; }else if(i==9 || in[i+1][j]=='0'){ int sz=0; for(;j+sz<10;++sz){ if(sz>4)return 0; if(in[i][j+sz]=='0')break; array(int) dx=({-1,0,1,-1,0,1}); array(int) dy=({-1,-1,-1,1,1,1}); for(int k=0;k<6;++k){ int nx=i+dy[k]; int ny=j+sz+dx[k]; if(0<=nx && nx<10 && 0<=ny && ny<10 && in[nx][ny]=='*')return 0; } in[i][j+sz]='0'; } app[sz-1]++; } } } for(int i=3;i>=0;--i){ if(app[i]!=4-i)return 0; } return 1; } int main(){ int n; sscanf(Stdio.stdin->gets(),"%d",n); for(int i=0;i<n;++i){ for(int j=0;j<10;++j){ in[j]=Stdio.stdin->gets(); } Stdio.stdin->gets(); if(check()==1)write("YES\n"); else write("NO\n"); } }
Hを提出した時点で10位だったので、何とかこのまま留まれないかと思ったのですがJの問題を頑張って理解しようとしているあいだにuwiさんが10問解いてしまい、11位になってそのまま終わりました。
自分にしては相当いい成績になれたので、満足しています。
言語がCにかなり近かったのでそれも有利に働いたのではないかと思います。
また、前回ほど言語の使い方を調べるのに苦労しなくて、退屈しない3時間を過ごせました。
