Codeforces Beta Round #64

(SRM 500 と Codeforces #62 も記録はしてあるので、そのうち載せる)

仮眠してから参加。

A Cookies

方針

フラクタルっぽい。これは再帰か、1000はスタック大丈夫かなぁなどと考えているうちに、実は3の冪乗じゃないかと気がつく。

実装

Ruby なら多倍長演算をサポートしているので、ループ回していちいち剰余を取る必要もない。n = 0 の場合わけも忘れずにできた。提出。

B Text Messaging

方針

構文解析きたー、と思ったが、要するに .!? で区切って sentence に分解し、頭から greedy に詰めていくだけ。

実装

これも Ruby で split 使えば楽勝……のはずが、ちょっと手間取る。まず、/[.?!]/ で split すると、これらの記号が抜けてしまうので、あとで補正しないといけない。それから、最初以外の sentence では頭にスペースが入ってくるので、削除しないといけない。

N = gets.to_i
str = gets.chomp

count = 1
current = 0 # 間違い! -1 が正しい

sentences = str.split(/[.?!]/).map{|e| e.gsub(/^ /, '')}

sentences.each {|e|
  
  e += ".";
  if e.size > N
    puts "Impossible"
    exit
  end
  current += e.size + 1

  if current > N 
    count += 1
    current = e.size
  end
}
puts count

でサンプルケース通った。提出。

C Lucky Tickets

方針

Project Euler にありそうな問題。とりあえず、100 くらいまで計算してみるが、(86, 34) みたいな non trivial なケースがあるし、解析解を求めるのは無理そう。

この手の「○○を満たすもののなかで最小」というのは、二分探索と相場が決まっているが、(x, y) と二次元なのが問題。対称性より、x <= y としてもよいのは気づいた。シャクトリ的にできないかとか、x を固定して y を探索できないかと考えたが、いずれにせよ、あるx, y でいくつ Lucky Ticket があるかは数えてみないと分からないので計算量が多すぎる。

分からない。

D Professors task

方針

逐次的 convex hull。普通の convex hull は、やりかたは知っているが書いたことがない。逐次的なやつはやり方も知らないが、一応考えてみる。

明らかに領域の内側になる点(例えば、最初の3点の重心)を固定。そこを中心にして、角度で点列をソートして、二分木に保持していく。凹みが生じてしまうかどうかは、中心点からの距離で判定すれば…… 的な感じ?

仮にこれで合っていたとしても、実装できる気がしない。

A, Bに戻る

A をロックして、n = 0 のケースを場合分けしていない人を探すが、もういない。

B をロックして、コーナーケース(メッセージ冒頭のスペースの処理など)を狙おうと思い、テストケースを作成しているうちに、自分自身のコードが「10 ab ab. ab. abcd abcd.」で落ちることを発見。入力冒頭の扱いがまずかった。再提出。250点くらい下がる。あー、もったいない。

結果

1753→1723。レート低下は意外と大きくないが、順位は大きく後退。

感想

B の再提出が痛かった。自分で気がつけただけでも進歩と考えるほど楽観的にはなれないなぁ。

教訓: 「ループの中で集計するときは、頭と終わりに注意」

C で足りなかった発想は、a / rev(a) = rev(b) / b。これも「分離して次元を落とす」パターンだよなぁ。