スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Codeforces Unknown Language Round #3

2011/07/30 15:00~18:00 (JST)
Codeforces Unknown Language Round #78 の参加記録

今回の言語は Pike.
3 時間で 10 問。

Tags : プログラミング Codeforces

結果

A. WA, AC (01:33)
B. WA, AC (02:59)
C. AC (01:38)
D. -
E. -
F. -
G. -
H. -
I. -
J. -

Standing : 134/805


問題

問題セットの原文はここを参照。

A. Carpeting the Room
n1 × n1 のカーペットを k 枚使って n × n の部屋を覆えるか?
カーペットは辺に平行な向きにだけおくことができる。カーペット同士が重なってもいい。

B. Friendly Numbers
n 個の整数が与えられる。
「 この中からどの 2 つを選んでも、少なくとも一方がもう一方で割り切れる 」 かどうか判定せよ。

1 ≦ n ≦ 1000

C. A+B
整数 a, b が与えられる。
a + b を計算せよ。

1 ≦ a, b < 10500

D. World of Mouth
整数 n と 2 つの文字列 s, t が与えられる。

次の操作を n 回おこなうことで s == t とすることができるか?

[ 操作 ]
・ s の末尾から 1 文字削除する
・ s の末尾に好きな 1 文字を追加する
の高々一方を行う。

E. Lamps in a Line
n 個のランプがあって、それぞれ 1, 2, ..., n という番号がつけられている。
最初のランプの点灯状態は与えられる。

n 個のスイッチがあり、それらを k 回押す。
スイッチ i を押すと、i の倍数番号のランプの点灯状態が反転する。

最終的なランプの点灯状態を出力せよ。

F. Polynom
(x + a1) (x + a2) … (x + an)
という式を展開して、指定された形式で出力せよ。

1 ≦ n ≦ 9
-10 ≦ ai ≦ 10

G. Name the album
過去に n 枚のアルバムが発行されている。
各アルバムのタイトルと発行年が与えられる。

今、m 個のタイトル候補があり、新しいアルバムのタイトルをこの中から選びたい。
・ 過去に発行されていないタイトルがあればそれを選ぶ。
・ そのようなものがなければ、発行年が一番古いものを選ぶ。
・ 上の条件に当てはまるものが複数あるときは、タイトルが辞書式で最大のものを選ぶ。

0 ≦ n ≦ 105
1 ≦ m ≦ 104

H. Battleship
Battleship というゲームの盤面が与えられる。
盤面サイズは 10 × 10.

盤面が以下の条件をみたすかどうかを判定せよ。

[ 条件 ]
・ 4 × 1 の船が 1 つ
・ 3 × 1 の船が 2 つ
・ 2 × 1 の船が 3 つ
・ 1 × 1 の船が 4 つ
あり、どの 2 つも (8 近傍で考えて) 接していない

I. Rotation
二次元平面上の 1 点が与えられる。
この点を、原点中心に k °反時計回りに回転させた点の座標を求めよ。

J. Interval Coloring
n 個の区間が与えられる。
各区間は、開区間,閉区間,半開区間のいずれもありうる。

任意の 2 つの区間 A, B に対して、A \ B ≠ φ であることが保障されている。

各区間に色を塗ることを考える。
このとき、次の条件がみたされるようにしたい。
最小で何色必要か?

[ 条件 ]
任意の 3 つの区間 A, B, C は、次の 4 つを同時にみたすことはない。
(1) A, B, C は同じ色で塗られている
(2) A ∩ B ≠ φ
(3) B ∩ C ≠ φ
(4) A ∩ C = φ

解答

ないよりはましなので、C/C++ 流のハイライトをしている。
競技中に書いたコードそのものではなく、いろんな人のコードを参考にして、短く書き直したものを掲載している。

A.
int main(){
int n,k,n1;
sscanf(Stdio.stdin->gets(),"%d%d%d",n,k,n1);

write(pow((n+n1-1)/n1,2)<=k?"YES\n":"NO\n");

return 0;
}

構文は C/C++ に似ている。
scanf がないので、gets で 1 行まるまる読み込んだあとに sscanf で parse した。

一辺を敷き詰めるには ceiling(n/n1) 個のカーペットが必要。
それの 2 乗個あれば全体を敷き詰められる。

B.
#define rep(i,n) for(int i=0;i<(n);i++)

int main(){
int n=(int)Stdio.stdin->gets();

array a=(array(int))(Stdio.stdin->gets()/",");

bool ok=true;
rep(i,n) rep(j,i) if(a[i]%a[j]!=0 && a[j]%a[i]!=0) ok=false;

write((ok?"":"NOT ")+"FRIENDS\n");

return 0;
}

C 言語と同じ感覚で define が使える。

string から int に直接キャストできる。

array(string) operator / (string A,string B) は、B を区切り文字として A を分割してくれる。
分割した文字列の配列が返される。

array(string) から array(int) へも直接キャストできる。
なんだこれ。

問題の解法について。
ソートしたあとに、隣接する要素同士だけ割り切れるかどうかをチェックすれば十分だと思って WA になった。
よく考えたら、負の数がありえるのでそれだとだめだった。
結局 O(n2) 個チェックした。

絶対値の大小でソートすれば O(n) でも解ける気がする。

C.
int main(){
int a=(int)Stdio.stdin->gets();
int b=(int)Stdio.stdin->gets();

Stdio.stdout->printf("%d\n",a+b);

return 0;
}

こういう問題を出すということは多倍長演算に対応しているだろうということで調べたら、思ったとおりだった。
ただの int が勝手に多倍長になるらしい。

D. (時間外)
int main(){
int a=(int)Stdio.stdin->gets();
string s=Stdio.stdin->gets();
string t=Stdio.stdin->gets();

int m=strlen(s),n=strlen(t),i;
for(i=0;i<min(m,n);i++) if(s[i]!=t[i]) break;

write((max(m,n)-i)+(min(m,n)-i)<=a?"Yes\n":"No\n");

return 0;
}

s と t の共通する prefix は変えなくてよい。
あとは、全部入れ替えないといけない。

E. (時間外)
int main(){
int n=(int)Stdio.stdin->gets();
array stat=Stdio.stdin->gets()/" ";

Stdio.stdin->gets();
array step=(array(int))(Stdio.stdin->gets()/" ");

multiset S=(<>);
foreach(step,int a) S[a]=!S[a];

foreach((array)S,int a){
for(int i=a-1;i<n;i+=a){
stat[i]=(stat[i]=="on"?"off":"on");
}
}

write(stat*" "+"\n");

return 0;
}

素直にシミュレーションすると、最悪 O(k n) 回程度のループになるので TLE.

・ スイッチを押す順番は結果に関係しないこと
・ スイッチを偶数回押すことは押さないことと同じ
の 2 点に気付けば、同じスイッチは高々 1 回しか押さなくてよくなるので O(k √n) のオーダー(?)になって間に合う。

multiset の使い方がわからずかなりはまった。
ちゃんと初期化しないとだめ。
multiset S に要素 a を
・ 追加するときは S[a]=true
・ 削除するときは S[a]=false
とする。

F. (時間外)
#define rep(i,n) for(int i=0;i<(n);i++)

int main(){
int n=(int)Stdio.stdin->gets();
array a=allocate(n);
rep(i,n) a[i]=(int)Stdio.stdin->gets();

array b=allocate(n+1);
rep(S,1<<n){
int prod=1,pop=0;
rep(i,n) if(S&(1<<i)) {
prod*=a[i];
pop++;
}
b[n-pop]+=prod;
}

if(n==1) write("X");
else write("X^"+n);
for(int i=n-1;i>0;i--){
string x;
if(i==1) x="X";
else x="X^"+i;

if (b[i]== 1) write("+"+x);
else if(b[i]==-1) write("-"+x);
else if(b[i] > 0) write("+"+b[i]+"*"+x);
else if(b[i] < 0) write( b[i]+"*"+x);
}
if (b[0]>0) write("+"+b[0]);
else if(b[0]<0) write("" +b[0]);
write("\n");

return 0;
}

n が小さいので、係数の計算は全探索でやった。
多分、多項式時間でもできる。

あとは間違えないように実装するだけ。
注意深く書いたつもりでも WA になって萎えるタイプの問題

G. (時間外)
#define rep(i,n) for(int i=0;i<(n);i++)

int main(){
int n=(int)Stdio.stdin->gets();
mapping f=([]);
rep(i,n){
array tmp=Stdio.stdin->gets()/" ";
f[tmp[0]]=(int)tmp[1];
}

string ans;
int m=(int)Stdio.stdin->gets(),year=7777;
rep(i,m){
string album=Stdio.stdin->gets();

int y=f[album];
if(y<year || (y==year && album>ans)){
ans=album;
year=y;
}
}

write(ans+"\n");

return 0;
}

mapping という名前の連想配列が使える。
これもちゃんと初期化しないとエラーになるので注意。

C++ の std::map と違うのは、
mapping f に a がキーとして登録されていないとき、f[a] としても a が登録されないこと。
このとき f[a] が 0 を返すのは C++ と同じ。

H. (時間外)
#define rep(i,n) for(int i=0;i<(n);i++)

string solve(){
array G=allocate(10);
rep(i,10) G[i]=Stdio.stdin->gets();

rep(i,9) rep(j,9) {
if(G[ i ][j]=='*' && G[i+1][j+1]=='*'
|| G[i+1][j]=='*' && G[ i ][j+1]=='*') return "NO";
}

array cnt=allocate(5);
rep(i,10) rep(j,10) if(G[i][j]=='*') {
int k;
if(i<9 && G[i+1][j]=='*'){
for(k=i;k<10;k++){
if(G[k][j]=='0') break;
G[k][j]='0';
}
if(k-i>=5) return "NO";
cnt[k-i]++;
}
else if(j<9 && G[i][j+1]=='*'){
for(k=j;k<10;k++){
if(G[i][k]=='0') break;
G[i][k]='0';
}
if(k-j>=5) return "NO";
cnt[k-j]++;
}
else{
G[i][j]='0';
cnt[1]++;
}
}

return (cnt[4]==1 && cnt[3]==2 && cnt[2]==3 && cnt[1]==4)?"YES":"NO";
}

int main(){
int T=(int)Stdio.stdin->gets();
while(T--){
write(solve()+"\n");
Stdio.stdin->gets();
}
return 0;
}

まず、隣接する船がないことをチェックした。

まじめにやると大変だけど、これは、
2 つのパターン
"*?"
"?*"


"?*"
"*?"

が盤面に含まれないことと同じだということに気付いた。 ('?' は任意の 1 文字)

あとは素直にシミュレーション。

I. (時間外)
int main(){
float t=(float)Stdio.stdin->gets()*Math.pi/180;
int x,y; sscanf(Stdio.stdin->gets(),"%d%d",x,y);

Stdio.stdout->printf("%f %f\n",x*cos(t)-y*sin(t),x*sin(t)+y*cos(t));

return 0;
}

回転行列をかけるだけ。

J. (時間外)
#define rep(i,n) for(int i=0;i<(n);i++)

int main(){
int n=(int)Stdio.stdin->gets();
array l=allocate(n),r=allocate(n);
rep(i,n){
int pl,pr;
sscanf(Stdio.stdin->gets(),"%c%f,%f%c",pl,l[i],r[i],pr);
if(pl=='(') l[i]+=0.5;
if(pr==')') r[i]-=0.5;
}

sort(l,r);

int ans=1;
rep(i,n-2) if(r[i]>=l[i+1] && r[i+1]>=l[i+2]) ans=2;

write(ans+"\n");

return 0;
}

区間の包含関係だけを気にしているので、開区間 (a, b) は閉区間 [a+0.5, b-0.5] と読み替えていい。
半開区間についても同様。

任意の 2 つの区間 A, B に対して、A \ B ≠ φ
という強い制限がついているのがポイント。
これは、A ⊂ B となる A, B がない ということ。
また、区間の左端はすべて異なるということも分かる。

問題文の条件
任意の 3 つの区間 A, B, C は、次の 4 つを同時にみたすことはない。
(1) A, B, C は同じ色で塗られている
(2) A ∩ B ≠ φ
(3) B ∩ C ≠ φ
(4) A ∩ C = φ

は、次のように読みかえられる。

A, B, C が次のような位置関係
AAAAA CCCCC
   BBBBB

になっているときは、A, B, C は同じ色になってはいけない。


このような 3 つ組がないときは、1 色あれば十分。
このような 3 つ組があるときは、2 色あれば十分。
残念ながらこれは証明できていない。
いくつか例を試してみたけど、たとえば次の 2 ケースでは問題なかった。
1.
AAAAA CCCCC EEEEE GGGGG
   BBBBB DDDDD FFFFF

2.
AAAAA EEEEE
  BBBBB
   CCCCC
    DDDDD


二部グラフ ⇔ 二彩色可能グラフ
だから、うまくグラフを作れば二部グラフになっているのかもしれない。

Pike の sort 関数は、第 2 引数以降にも配列を指定すると、第 1 引数と同じルールで一緒にソートしてくれる。

感想

資料が極端に少ない。
日本語の資料はほとんど Wikipedia しかないと言っていい。

コーディングは このサイト を見ながらやった。

雰囲気は C/C++ にそっくり。
set (multiset) や map (mapping) も標準で備わっている。

大きく違うと感じた点は、
・ 入出力が不便。
・ 何でもキャストできる。
・ string の操作がやりやすい。この点は Perl などのスクリプト言語に近いと思う。
・ 変数宣言で型を厳密に決めなくていい。array(int) を array と書いても怒られないし、任意の型を表す mixed というのまである。
・ コンテナ (array, mapping, multiset) を引数に取る独特の演算子がたくさんある。
など。

実行時にコードを解釈するインタプリタにしては速いと感じた。

コンテスト中は、処理系の導入に 70 分くらいかかり、残念な結果になってしまった。
情報系の基本スキルがないのがつらい。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。