スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Codeforces Round #144 (Div. 1)

げきむず。
三問以上正解が tourist だけ。

Tags : プログラミング Codeforces 未解決

結果

A は disjoint な完全グラフを大きいものから貪欲に置いていけばいいかなと思って、書いてみたら次数が最大で 120 くらいになってしまってだめだった。次に、どのサイズの完全グラフを組み合わせれば最適かを DP で計算してみたけど、貪欲と同じ結果しか出なかった。完全グラフに頂点を 1 個追加して改善したら大体よさそうだったので出した。systest で落ちて、調べてみたら次数が 101 になるケースがあった。
B は素直にアプローチできて、あんまり詰まらずに書くことができた。二項係数の計算で mod を取り忘れて 1WA った。
C は、なんか状態数が少ないかなーと思って map でメモ化するコードを書いていたけど、自前のランダム最大で全然間に合ってなかったから出さなかった。

問題

A. Cycles
頂点数 100 以下の無向グラフで長さ 3 の閉路の個数がちょうど k であるものを一つ求めよ。

1 ≦ k ≦ 10^5

B. Table
n × m のグリッドの各マスに石を置く。
一つのマスには高々一つの石が置ける。
グリッドに含まれるすべてのサイズ n の正方形について、正方形に含まれる石の個数がちょうど k 個であるような石の配置は何通りあるか? mod 10^9+7 で。

1 ≦ n ≦ 100
n ≦ m ≦ 10^18
1 ≦ k ≦ n^2

C. Doe Graphs
0 以上の整数 n に対して、n 次の Doe graph を問題文のように定義する。( 説明略 )
今、n 次の Doe graph がある。二頂点 (a_i, b_i) 間の最短距離を求めるクエリを t 個処理せよ。

1 ≦ n ≦ 10^3
1 ≦ t ≦ 10^5
1 ≦ a_i, b_i ≦ 10^16

D.

E.

解答

A.
上に書いたように自分の方法ではダメだったので、Editorial の方法で解いた。
頂点を一つずつ追加していき、頂点を追加するたびに、すでにある頂点との間に辺を張るかどうかを全部試す。辺を追加しても三角形の個数が k を超えなかったら追加する。
O(n^3) でできる。
シンプルでよい。

http://codeforces.com/contest/232/submission/2354346

B.
一番左の正方形 (0,0)-(n-1,n-1) を一マス右にずらしたときのことを考える。
すると、1 列目と n+1 列目の石の数は等しくないといけないことがわかる。
どんどんずらしていくと、
1 列目の石の数 = n+1 列目の石の数 = 2n+1 列目の石の数 = ...
2 列目の石の数 = n+2 列目の石の数 = 2n+2 列目の石の数 = ...
:
n 列目の石の数 = n+n 列目の石の数 = 2n+n 列目の石の数 = ...
ということがわかる。
つまり、各列に置く石の数は n 列目までで全部決まってしまう。

このことに気付けば、
dp[何列目まで見たか][残り何個石を置けるか] = ( 石の置き方の総数 )
で DP できる。
状態数が O(n^3) で遷移が O(n) なので、全体で O(n^4) で解ける。
DP の最内部で二項係数の累乗を計算しないといけない。この部分を前計算するかメモするかしておかないと O(n^4 log m/n) くらいになって多分 TLE する。

TLE が怖かったので、ちょっとだけ枝を刈った。

http://codeforces.com/contest/232/submission/2344190

C.
Editorial を参考にして解いた。

まず、Doe graph の頂点数は Fibonacci 数列になっていて、a_i, b_i ≦ 10^16 なので実際は n ≦ 90 程度まで考えておけば十分ということに注意しておく。

再帰的に小さい Doe graph の最短経路問題に落としていくのが基本。
今 D(n) を見ているとして、最短距離を求めたい二頂点 a, b の関係は
(1) 共に D(n-1) 側にある
(2) 共に D(n-2) 側にある
(3) 一方が D(n-1) 側に、もう一方が D(n-2) 側にある
の三通りが考えられる。
それぞれ、最短経路として考えられるケースをすべて試す。(1) のときは 5 通り、(2) のときは 1 通り、(3) のときは 3 通りのケースがあり、間違いやすい。
このときの遷移の式を注意深く見てみると、( a < b として )
(i) a == 1
(ii) b == |D(n)|
のどちらかのケースが実際に起こる状態のほとんどを占めていることがわかる。a > 1 かつ b < |D(n)| のケースは (1) のときだけ起こり、これは分岐しないから。
なので、(i) と (ii) のときがメモ化できればよさそう。再び遷移の式をにらむと、実際に起こる状態には規則性があることに気付く。たとえば (i) のとき、b としてありうる値は三通りしかない。この三通りというのは
・元々の a が -|D(n)|, -|D(n-1)|, ... されてきてできた値
・元々の b が -|D(n)|, -|D(n-1)|, ... されてきてできた値
・今の Doe graph の一番番号が大きい頂点
の三つ。同じように (ii) のときも三通りしかなく、三つめは (i) の三つめと同じなので、合計で各 n について、実際に起こる状態は五通りしかない。
これで配列でメモ化できて、一クエリあたり 90 の定数倍くらいの計算量になり間に合う。

時間制限 3 sec のところ、2.7 sec かかった。かなりシビア。
もっと速いコードを書いてる人もたくさんいるけど、何やってるのか不明。

http://codeforces.com/contest/232/submission/2355231
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。