Codeforces Beta Round #17

Codeforces

サーバー落ちで流れて以来のCodeforces。
最近コンテスト続きなので気合十分で挑んでみたのですが…。

  • -

A. Noldbach problem

問題：2以上n以下の素数のうち，隣接する2つの素数の和+1で表せるものの数がk個以上かを判定する

  • nもkも1000以下と小さいので，何も考えずに判定を書いてAccept。

B. Hierarchy

問題：「社員Aが社員BをコストCで部下にする」という関係がいっぱい与えられて，全社員から成る木構造を作るための最小コストを求める問題。

  • 「最小コストで木構造」とだけ見て最小全域木のコードを書いてた。
    • ちなみに，書き終わってサンプルを試した段階でやっと違うと気付いた。
    • 何をやってるんだマジで…。
    • (追記)Codeforces上にKruskalで通したって言ってる人が何人かいる。いけるのか…。
  • 問題では追加情報として各社員の能力値Qiが与えられる
    • 「AがBを部下にする」という関係があればAの能力値はBの能力値より上
  • なので，能力値が最も高い社員以外を部下になるコストが最も低い人に割り当てるだけ
  • だれにも部下にしてもらえない人がいれば木が構築不可という事で-1を返す。

C. Balance

問題：文字a, b, cからなる文字列sが与えられて，文字1つを隣接するどちらかのものと同じにする操作を何回か加える。s中のa, b, cそれぞれの数の差が高々1になるような文字列は何種類作れる？

  • 文字列長が150だし，制限時間がちょっと長い。
  • メモ化探索でもするのか…？と思いつつ，結局何も閃かず終了。

D. NotePad

問題：b進数で長さnの数字をノートに書き連ねていく。1ページにc個ずつ書く時，最後のページに書かれる数字の個数は？

  • 制限：2≦b<10^10^6、1≦n<10^10^6、1≦c≦10^9
    • ノートに数字を書く人の忍耐とノートの量は無限大
    • この作業、一生かかっても終わらないんじゃないか…
  • 多倍長ゲーか…？と思ってとりあえずjavaでコードを書いてみる。
    • 答えは(b-1)*b^(n-1) mod cなので，これを何とか計算すれば良い。
    • 仕様を調べつつ頑張った結果、3WAを経てTLE＼(^o^)／
  • 冷静に考えると，cがintで収まるのでc++を使っても実装はそんなに大変じゃない。
    • b%cを筆算っぽく計算する
    • nは文字列として扱い，べき乗は ans = (ans^10)*((b%c)^n[i]) を繰り返せば良い
  • かなり終盤に気付いてあわてて書き始めるも間に合わず。
    • 超絶デバッグを経て終了20分後くらいにAccept。
    • 超絶デバッグしてる時点で結局ダメじゃないか…。
  • -

結果：0:05(+0) / 0:24(+0) / -- / --(+3) / -- ，77位
レーティング：1844 -> 1820

迷走っぷりが酷い…。
最近のコンテストは、終わる度にもっと落ち着くべきとか思ってる気がします。
今度のGCJ Round3くらいは晴れやかな気持ちで終われるよう頑張りたいです。