Codeforces Round #26 (Codeforces format)

Codeforces

惨敗回。未だにこんな程度の実力しかついてないのかとショックが大きい。
結構問題解いてるつもりなのに。やっぱりどうしようもなく才能が不足しているんだろうねえ。

Result

492点 492 / (-2) / - / - / -

392位
1717->1572（青化）


今回はCodeforces formatという形式らしい。
確かTwitterでchallengeっぽいものがあるとかどうのとか見かけたような……
という訳でルールを読んでみる。

  • 5問2時間セットなのはいつものラウンドと共通
  • ただし問題には配点が500,1000,……という配点がついている
  • 開始直後に提出した場合満点だが、1分ごとに点数が減っていく
  • ロック（後述）しない限り何度でもリサブミットができるが、リサブミットには一定の減点がある


ふむふむ。

  • 解答提出後、すぐにSystem Testは行われず、代わりに簡易テストが行われる
  • 簡易テストに通過した場合、解答をロックするかしないかを選べる
  • 解答をロックすると二度と再提出は出来ない
  • その代わりに他者のその問題の解答を見て、hackを試みることができる


ほー。そろそろ読むのつらくなってきた。

  • hackはTopCoderでいうchallenge.入力ケースを直接与えるほか、入力ケースを生成するプログラムを投げることができる
  • hack成功は100点、失敗は-50点


おｋ理解。

A. Almost Prime

問題

ある数を素因数分解したときに現れる素因数がちょうど２つであるとき、その数を"Almost Prime"であるという。
1以上与えられた数n以下でAlmost Primeな整数の数を求めよ。

n≦3000.

試行錯誤

愚直にやって間に合う。書いてサブミット。
CE2回ほど出した...orz

B. Regular Bracket Sequence

問題

'('および')'からなる文字列が"regular"であるとは、
+の演算子と数字1を挿入して正しい数式にできることを言う。


与えられた文字列の部分文字列（必ずしも連続しない）で、regularな文字列のうち最長のものの長さを求めよ。
与えられる文字列の長さは10^6を超えない。

試行錯誤

えー……Bからむずかしくない？？
ってあれ、これcodeforcesで昔出なかった？


確か同じ深さで昔出た位置を覚えておくんだった。
見て書いてみる。サンプル合った。提出WA.
えっ？配列の大きさか何か間違えたかな……大きくして再度提出。


WA.
……問題文読み直す。あ、連続しなくてもいいのか。
えーと？？O(n^2)なら出来るんだけど、入力サイズは10^6で時間制限が5秒だからO(nlogn)の解法があるんだろう。


類題どういうのやったっけ？

  • '(',')','[',']'からなる文字列のregularな最大部分文字列
  • '(',')'からなる文字列のregularな連続する最大部分文字列

んで、O(nlogn)ってのは最長増加部分列のDPだよなあ。


'(',')'のDPも何か単調部分列的なものがあればO(nlogn)に落とせそうなんだけど。
うーん。色々書いてみる。結局テーブル全部更新しなくちゃいけないなあ。
O(nlogn)で最長増加部分列を作るアルゴリズムは、

  • 配列のi番目に長さiの最長増加部分列の最後の項をもっておいて、
  • a[i]で一個ずつ更新していく

という方針だった。何でこれが上手くいくかというと、
部分列の最後っていうのは単調列になってて、なおかつテーブルを更新するとき更新箇所が一ヶ所で済むから。


うーん。うーん。
眠くなってきた。つーかみんななんでこんなに提出してんの……
鬱くなってきた。。。


1時間くらい考えて全然わからないのでニコニコをへこみながら見始めた。
終了後に他者の解答だけ見とこ。。。

C以降

みてねえ。

System Test

A通った。392位……し、しんだほうがいい