Hatena::Grouptopcoder

eagletmtの日記

2011-07-30

Codeforces Unknown Language Round #3

23:28

http://codeforces.com/contest/100

開始15分くらい前に二度寝から覚め,慌てて登録して参加した.


今回は Pike という言語を使うらしい.http://pike.ida.liu.se/

https://aur.archlinux.org/packages.php?ID=11649 を見付けたが,orphan だしビルドできるか不安だなーと思いつつ,依存関係を微妙に修正して makepkg.

なんか configure が長いのでそのうちにリファレンスを見て,基本的な構文と sscanf の存在を確認した.

で,案の定ビルドに失敗していた.

make -j1 でリトライしてみたけどダメ.そんな構造体のメンバなんてないよ的なコンパイルエラーを見て諦めることにした.

どうやら Debian 向けのバイナリパッケージがあるっぽかったので,VirtualBox 内の Debian 環境で実行することにした.

Debian 内にコーディング環境は作ってなかったので,sshfs でマウントしてローカルの Vim で編集するというスタイルでいった.

コンテストの案内(?)には「Emacs ユーザはよかったね,Pike のシンタックスハイライトがあるよ」的なことが書いてあったけど Vim にもありました!!! (なので,はてなでもシンタックスハイライトできます)


ここまでで30分くらい経ってる.

A

割って判定するだけか.

% も普通にあるだろうと思いながら書いて提出.

int solve(int n, int k, int n1)
{
  int x = n / n1;
  if (n % n1 != 0)
  {
    x++;
  }
  return x*x <= k;
}

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

  if (solve(n, k, n1))
  {
    write("YES\n");
  }
  else
  {
    write("NO\n");
  }
  return 0;
}

B

N^2 回試すだけか.

Statements のところで for 文を確認し,Working with Strings のところで / で split できることを知った.

array(string) を array(int) にするにはどうすればいいんだろう.まぁ毎回 sscanf してもいいか…

int solve(array(string) xs)
{
  for (int i = 0; i < sizeof(xs); i++)
  {
    int x;
    sscanf(xs[i], "%d", x);
    for (int j = i+1; j < sizeof(xs); j++)
    {
      int y;
      sscanf(xs[j], "%d", y);
      if (x % y != 0 && y % x != 0)
      {
        return 0;
      }
    }
  }
  return 1;
}

int main()
{
  Stdio.stdin->gets();
  string s = Stdio.stdin->gets();
  array(string) xs = s / ",";
  if (solve(xs))
  {
    write("FRIENDS\n");
  }
  else
  {
    write("NOT FRIENDS\n");
  }
  return 0;
}

C

入力が最大で 10^500 と多倍長がいるっぽい.

既に解いてる人多いし pike のパッケージが GMP に依存していたし,きっと普通に多倍長演算できるんでは.

int main()
{
  string s = Stdio.stdin->gets();
  int a;
  sscanf(s, "%d", a);
  s = Stdio.stdin->gets();
  int b;
  sscanf(s, "%d", b);
  write("%d\n", a+b);
  return 0;
}

D

探索か DP になるのかな,と思って飛ばした.

E

うーん,普通にシミュレーションで通るんかなと思って提出してみたけど TLE

パス.


このへんで解いている人が多い簡単そうなものから解いていこうとした.

I

回転行列かけるだけか.

sin とか cos とか書いてみたら普通にあったのでそのまま提出.

int main()
{
  float pi = acos(-1.0);
  string s = Stdio.stdin->gets();
  float theta;
  sscanf(s, "%f", theta);
  theta = pi * theta / 180.0;
  s = Stdio.stdin->gets();
  float x, y;
  sscanf(s, "%f %f", x, y);

  float a = x*cos(theta) - y*sin(theta);
  float b = x*sin(theta) + y*cos(theta);
  write("%f %f\n", a, b);
  return 0;
}

D

D に戻ってきた.

後ろを削るか足すかしかしないから,先頭の一致している部分は無視して,残りの長さの和が n 以下ならいいんじゃ.

ここで n 以下なのか n 未満なのか不安になってよく読んでみて,n 未満だ!!と理解して提出したら WA

えー,じゃあ n 以下なの,と変えて提出したら AC.(ひどい…)

int main()
{
  string s = Stdio.stdin->gets();
  int n;
  sscanf(s, "%d", n);
  string s1 = Stdio.stdin->gets();
  int len1 = sizeof(s1);
  string s2 = Stdio.stdin->gets();
  int len2 = sizeof(s2);

  int len = min(len1, len2);
  int i = 0;
  for (; i < len; i++)
  {
    if (s1[i] != s2[i])
    {
      break;
    }
  }
  if ((len1 - i) + (len2 - i) <= n)
  {
    write("Yes\n");
  }
  else
  {
    write("No\n");
  }
  return 0;
}

F

係数の計算は n <= 9 だしどうやってもよさそう.

出力部分で何かしらミスりそう.

そういえば n 要素の配列ってどうやってつくるんだ.array + array で append らしいのでまぁそれで伸ばせばいっか…


3WA の後に AC.-X^n とか -X とかにハマってた.

ちなみに n 要素の配列は allocate(n) で作れた…

int main()
{
  string s = Stdio.stdin->gets();
  int n;
  sscanf(s, "%d", n);
  array(int) as = ({});
  array(int) xs = ({0});
  for (int i = 0; i < n; i++)
  {
    s = Stdio.stdin->gets();
    int a;
    sscanf(s, "%d", a);
    as += ({a});
    xs += ({0});
  }

  for (int s = 0; s < (1<<n); s++)
  {
    int d = 0, c = 1;
    for (int i = 0; i < n; i++)
    {
      if (s & (1<<i))
      {
        ++d;
      }
      else
      {
        c *= as[i];
      }
    }
    xs[d] += c;
  }

  int first = 1;
  for (int i = n; i >= 0; i--)
  {
    if (xs[i] != 0)
    {
      if (!first && xs[i] > 0)
      {
        write("+");
      }

      if (i == 0)
      {
        write("%d", xs[i]);
      }
      else if (i == 1)
      {
        if (xs[i] == 1)
        {
          write("X");
        }
        else if (xs[i] == -1)
        {
          write("-X");
        }
        else
        {
          write("%d*X", xs[i]);
        }
      }
      else if (xs[i] == 1)
      {
        write("X^%d", i);
      }
      else if (xs[i] == -1)
      {
        write("-X^%d", i);
      }
      else
      {
        write("%d*X^%d", xs[i], i);
      }
      first = 0;
    }
  }
  write("\n");
  return 0;
}

G

mapping という型が用意されているのは知っていたが,これの作り方がわからない.

リファレンスを読んで mapping(string : int) dict = ([]) で宣言+初期化して,dict[key] = val で追加できることを知った.

実際に動かしてみると,存在しない key に対しては dict[key] は 0 を返している??みたい.

で,書いて提出したけど WA

ミスを発見して修正して提出したけど WA

存在しない key に対する dict[key] の値の仮定が間違ってるんじゃないかとか,そっちばかり調べながら WA

全然原因がわからず,ラスト10分くらいは諦めてた.


コンテストが終わって上位の人の G を開いてみて,問題文の「alphabetically latest」を「アルファベット順で最初」という意味にとっていたが,それが間違っていたことに気付いた.

英語……

int main()
{
  string s = Stdio.stdin->gets();
  int n;
  sscanf(s, "%d", n);
  mapping(string:int) dict = ([]);
  for (int i = 0; i < n; i++)
  {
    s = Stdio.stdin->gets();
    string name;
    int year;
    sscanf(s, "%s %d", name, year);
    dict[name] = year;
  }
  s = Stdio.stdin->gets();
  int m;
  sscanf(s, "%d", m);
  string ans = "";
  int year = 3000;
  for (int i = 0; i < m; i++)
  {
    s = Stdio.stdin->gets();
    int y = dict[s];
    if (y < year)
    {
      year = y;
      ans = s;
    }
    else if (y == year)
    {
      ans = max(ans, s);
    }
  }
  write(ans + "\n");
  return 0;
}

E はちょっと工夫して,偶数回のスイッチを無視して奇数回のスイッチを1回分にするだけで TLE しなくなるらしい…

int main()
{
  Stdio.stdin->gets();
  string s = Stdio.stdin->gets();
  array(string) lights = s / " ";
  int n = sizeof(lights);
  Stdio.stdin->gets();
  s = Stdio.stdin->gets();
  array(string) keys = s / " ";

  array(int) a = allocate(n);
  for (int i = 0; i < sizeof(keys); i++)
  {
    int k;
    sscanf(keys[i], "%d", k);
    ++a[k-1];
  }
  for (int i = 0; i < n; i++) {
    if (a[i] % 2 == 1) {
      for (int j = i+1; j <= n; j += i+1)
      {
        if (lights[j-1] == "on")
        {
          lights[j-1] = "off";
        }
        else
        {
          lights[j-1] = "on";
        }
      }
    }
  }
  write((lights * " ") + "\n");
  return 0;
}

環境作りに手間取ったけれども Unknown Language 楽しかった.

どーでもいいが,前回のコンテストがノーコンテストで今回は Unknown Language なので,まだレートがついていない.