Hatena::Grouptopcoder

Gus@topcoder

topcoderのid:gusmachineの記録です。普段の日記は揺動散逸日記をどうぞ。

2012-10-21scalaをcodeforcesで練習してみる。

Scalaの練習をしてみました。

Programming In Scalaを去年買って、さらにいつだったかの勉強会で物理本も頂いたのにも関わらず

Scalaを全く書いていませんでした。その反省として適当に書いてみます。

まずはScalaが動くCodeforcesで過去問をときます。目標はdiv-2レベルをすぐに書ける程度。

基本

先駆者がいるので参考にします。

まず実行可能ファイルを書く方法から。

object Main1 {
  def main(args: Array[String]) = {
    // impl
  }
}

singleton object (日本語だと特異オブジェクト)を作って、main(args: Array[String])を定義するだけです。

あるいは、上のリンク先のように

object Main2 extends App {
   // impl
}

とするだけです。

その他は次のようにすれば簡単なプログラムは書けます。

  • 読み込みはjava.util.Scannerを使います。
  • 書き込みはprintlnになんでも渡せます。あるいは"%07d".format(n)等。printfも使えます。

Scala文字列メモを参考にしました。

解答例

一番最初の練習問題、A. Theatre Square を解いてみました。一回IntでオーバーフローによるWAを食らったりしましたが完成。

import java.util.Scanner
object A extends App {
  val sc = new Scanner(System.in)

  val m = sc.nextLong
  val n = sc.nextLong
  val a = sc.nextLong
  println(((m + a - 1) / a) * ((n + a - 1) / a))
}

App? Application?

ところで、手元にあるProgramming in Scala 2nd ed. ではAppではなくApplicationを使っています。この差は一体?

scala.Applicationを継承したクラスは、mainメソッドを書かなくても、クラス起動後に処理が実行される。

尚、起動時に渡したパラメータは利用できない。

Scala2.9で導入されるscala.Appでは利用できるという噂あり。

via. scala.Application | Scalaの標準ライブラリを使ってみる | mwSoft

つまりAppは新しいということですね。これかな: scala.App

2012-03-06

Codeforces #107 Div. 2

00:12

2/19にやった問題。

はやくDiv. 1に行ってこんなつまらない問題リストからおさらばしたい気分です。

o o o hacked opened: 17th.

A

cout << min(k * l / (nl * n), min(c * d / n, p / (n * np))) << endl;

B

判定が面倒。

C

与えられた数が素因数分解していくつの素数からなるか調べる。

D

m種のアルファベットからなる長さNの文字列のうち、そのどの長さkの部分文字列も回文になっているものの数を答えよ。ただし答えは10^9 + 7で割ってあまりを出す。

ちょっと調べればわかるが、kが偶数なら同じ文字の連続以外ありえず、kが奇数ならababab..baしかありえない。

ただし、k < N とか k == N に注意。k < N はpretestに入っていて、k == N は忘れてhackされる始末。

つーか k < N とか問題の趣旨に照らし合わせてぎりぎりヤバめの入力だと思う。

E

問題を読み解くと、「数列{x_n}と添字列{(a, b)_i}が与えられるので、a_i ≤ c_i ≤ d_i ≤ b_i なる c_i, d_i のなかで ∑_{c_i ≤ k ≤ d_i} x_k を最大化するものを各iで求めよ」となる。数列のサイズと添字の数が両方 10^5 オーダーになるため、安直に行うとTLEる。

数列{x_n}の区間{x_k}(a ≤ k ≤ b)に対し、その区間内の区間での和の最大、左端を含む区間での和の最大、右端を含む区間での和の最大、それから全体の合計、この四つをO(log |x_n|)で求められる区間木がO(|x_n| log |x_n|)で構成できるのでそれで終了。

ただしこの区間木書いたの初めてで適当に書いたらSIGSEGVった。gdb-many-windowsを動員するもよくわからず。

問題が終わった後にデバッグしてみた。

https://twitter.com/#!/gusmachine/status/171593946970071041

ぎゃーなんだこれはー!!! > if (child[i]) {delete child;}

しかしまだ合わない→Get()の部分にバグ(maxをうまくとってない)を発見。

しかしまだ合わない。wrong answer on test 4. データが読めないので良くわからず。


みつけた。

  int Right(int pos) const {
    if (pos == start_) {
      return right_;
    }
    if (pivot_ <= pos) {
      return child[1]->Right(pos);
    }
    int v1 = child[1]->Right(pivot_);
    int v2 = child[1]->Sum() + child[0]->Left(pos); // bug
    return max(v1, v2);

しかしwrong answer on test 6

厳しいなこれ

ああint overflowだ。答えx100が2^32超えてるじゃん。

全部long long に直す。

wrong answer on test 15.

マジでー。

あれ答えx100が2^50近くなんだけど。doubleでエラーしてる?

しかしrelative errorが大きいのはおかしい。

10^9 * 50 > 2^32だった。よって期待値の部分でオーバーフローしていた。ここもllにする。

まだ解けてない。 wrong answer on test 15.

あっ

int Sum() const {return sum_;}

ブッダ!なんでこれエラー出てないんだ。

s/int/LL/

通った。


その他

気がついたら Div 1.に昇進していました。

2012-01-09

Codeforces Round #101 Div. 2

11:49

o failed o opened opened : 2134 pts. 147th. 前回と同じでした。B落ちたのよりDE提出ができないほうが酷い感じです。

  • A 486 pts
  • C 1648 pts

A

print (if sorted (a + b) == sorted c then "YES" else "NO")

追記の通り焦ったけど7分で終了。

B

やるだけ。

でしたが一箇所 else return -1; を忘れて "2 -1 3" で爆死。

if-elseが多くなりすぎていたので危ないことには気づいていました。が、しかしどうすればよいでしょう。最後30分で入力作ってcoverage testする、のがかろうじて可能でしょうか。

C

やるだけ。と書くとちょっと忘れそうです。

  • 人数の少ない順にソート
  • "N番目の人は前N人の中で背の順何番目?"を全部計算。この段階でN番目なのにN人前に人がいるとか言ったら-1
  • 最後尾から背の順を決めると全部確定する。

O(N^2)で余裕です。O(N log N)でいけるはず?

44分。Bがあったので。

D

端からDPで余裕。と思ったらスキー逆行だと!?

よくわからないので結局飛ばしました。ダイクストラで十分という話を聞きました。

たしか、O(頂点数^2)の辺を張られると死ぬのでひよった記憶があります。そんなケースは存在しないのでしょうか。

E

眠い頭で、

片方の枝だけでMST実践→もう片方の枝で完成させる→足りない方の枝を足して、出来たループから多い方の枝をカット

みたいなことをやるとできそうなことを導きました、が、眠い。

その他

前回から準備したMakefile+テストがうまくいってなくてハマりました。間違いは次の通り。

python try_cf.py --command $< --input $(<:.exe=.in) 2>&1 | tee $@
正       python2.7 ../try_cf.py --command ./$< --input $(<:.exe=.in) 2>&1 | tee $@

.exeまでをMakefileで作って手動でテストすることで回避しました。

それから、うっかりvirtualbox内の共有フォルダじゃない方で組み始めてしまい、Aを提出するときに焦りました。


SRM 527 practice

23:38

opened x opened: 0.00 pts. 自分の実力を認める展開。あるいはpracticeでよかったともいいます。

275

なぜか貪欲でいけると思い込みました。手元で貪欲法を作ってはその反例を作るを繰り返して時間を潰しました。

やっている最中にノートPCが電源トラブル?で電源が落ちました。再起動してから冷静になって次に。

25分くらいかけてました。本番ならもっと早く動いているはずです。心配だし。

Systest後、ブログにあるDPという記述を見てやっと解法に気づく。気づけば簡単でした。

木の端の頂点をひとつ除いたものを考えます。名前が有りそうですが忘れたのでブランチとでもいいましょう。1頂点だけ使ったブランチは、その唯一の頂点の次数は1です。2頂点のブランチは次数はそれぞれ1, 2です。

max_score[頂点数][ブランチ数]に、N頂点使ってブランチをb個作った時のスコアの最大値を保持します。これを下から順に埋めていきます。

これでDPになりました。

450

  • 辞書順なので頭から探索するに違いない。
  • 探索の途中でも条件を満たすかどうか調べたほうがいい。
  • 条件を満たすかどうかは、二部グラフがfull matchするかどうか確認すればよい。

手元に2部グラフのコードが見当たらないのでゴリゴリ書きました。Edmonds-Karpで。サンプル通ったので提出。

しかしなぜかTLE Systest Failed。調べたところ大きなグラフで0と?としかない入力でした。手元では600 ms程度で実行できているのですが。

1050

残り時間が殆ど無かったので眺めるだけでした。後で解きます。

2012-01-03

SRM 526.5 practice

11:27

o x opened: 159.61 pts. 遅い上に500がsystest failした。ひどい。あと頭文字がかぶるとファイル名の補完が効きにくい。得点を名前にするとかにしたほうがいいのかもしれない。

  • 250 24分 159.61 pts
  • 500 34分 265.50 pts - 265.50 pts
  • 1000 opened

出たら265位くらい。 rateが下がるはず。

250

素直に引いていって、残りが3以下になったら最後の飴を決定し、引いていった飴を素直に足してゆく。

足してゆくところが自明じゃないので二分探査した。

O(log N * log N) くらいで終わるはず。

足してゆくところの条件が頭で理解できずにすごく苦労した。250であることを考えると、もっと簡単に書けると思うのだけれど。

Editorialを見た。みんな時間がかかったらしい。あと、恐ろしく簡単な答えがあることを理解した。

500

max(|x|, |y|) = k なる範囲R_k 内では、どの場所でも雪玉の個数の期待値及び美しさの期待値は同じ。両者を保持して、新たな呪文が唱えられるたびにその値を更新してゆく。O(maxRange * numranges) みたいなオーダー。

バグは以下のとおり。

const int w = range * 2 + 1;
const int area = w * w;
const double next_x2 = double(amount * (amount + area - 1)) / (double(area) * area);

最後の分子がint32をオーバーフロー。area * areaの方は最大ケースを入れた時に気づいたのに。

そもそもint使うべきではない。long longにしておくかdoubleに任せるべき。

1000

  • Grundy数を覚えていない。たしかxorするはず。→あってた。
  • 任意の部分集合がGrundy数非ゼロって何?
  • 時間切れ。

二番目の条件は、xor演算で線形空間を考えた時に線形独立、だった。これが思いつかないとは大学を離れて時間が経ちまくっているな。

まだ面積最小値を取る方法がわかっていない。

本番5人提出正解者なしなので解説を読もう。

追記: 読んだ。

本家解説および日本語訳 by ogiekakoさん

理解した。理解したけどすごいなこれ。

2012-01-02

SRM 528 practice

16:52

レンシューしてみた。 o o opened 489.42 pts. 本番だと100位くらい?

  • 250 14分 199.07 pts
  • 500 28分(含おやつ) 290.35 pts
  • 1000 opened

250に時間かかりすぎ。まあ罠臭かったので結果オーライかも。

250

大した行数書いてないのに手間取った。うなぎを切るべき順番に並べて切れるだけ切るだけ。

切るべき順番は以下のとおり。

bool compByModDiv(int lhs, int rhs) {
  const int l_mod = lhs % 10;
  const int r_mod = rhs % 10;
  const int l_div = lhs / 10;
  const int r_div = rhs / 10;
  return l_mod != r_mod ? l_mod < r_mod : l_div < r_div;
}

500

DP。N文字目まで読んだ時、青い部分文字列と赤い部分文字列のうち短いほうが長い方のprefixになっていて、

長い方の残りの文字列が x になる場合の数を t[N][s]で表現。これをN = 1より順に計算。

1000

わかってない。

解ける気があまりしなかったので時間外にまとめを見て解法を把握。解法は自分で書いたらバグりまくった。一度systest errorしたのであまり意味ない。