スポンサーサイト

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

Croc Champ 2012 - Round 2

2012/04/21
Croc Champ 2012 - Round 2

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

問題

問題セットの原文はここを参照。

A. Trading Business

n 個の店があり、それぞれ m 種類の品物を売っている。
各店、各品物について、売値、買値、在庫数がわかっている。
また、自分が持てる品物の個数にも上限 k がある。
ある一つの店で品物をいくつか買い、他のある一つの店でそれらを売るとき、自分の儲けを最大化せよ。

2 ≦ n ≦ 10
1 ≦ m, k ≦ 100

B. Word Cut

長さが等しい二つの文字列 s, t が与えられる。
s に操作
・ 好きな番号 i を選び、s を prefix s[1..i] と suffix s[i+1..|s|] に分割し、s = s[i+1..|s|]+s[1..i] と置き換える
をちょうど k 回施して t に一致させたい。
そのような操作列は何通りあるか? mod 10^9+7 で。

2 ≦ |s| = |t| ≦ 10^3
0 ≦ k ≦ 10^5

C. Playing with Superglue

n × m の盤を使って二人でゲームをする。
盤の 2 箇所にコマが置いてある。
先手は、コマを一つ選び、4 近傍の好きなマスに移動させる。
後手は、コマがないマスを一つ選び、そのマスに糊をしかける。
糊のあるマスに踏み込んだコマは、以降、動かせない。
最初、どのマスにも糊はない。
二つのコマが同じマスに入ったら先手の勝ち、最後までそうできなければ後手の勝ち。

先手必勝か後手必勝か判定せよ。

1 ≦ n, m ≦ 100

解答

A.
どの店で買うか、どの店で売るかを全通り試す。
買値と売値の差額が大きいものから優先的に買っていけばいい。
http://www.codeforces.com/contest/176/submission/1586948

B.
prefix と suffix を swap する操作は、ようするに rotate しているのと同じ!! ( すぐには気付かなかった )
好きな文字数分だけ rotate できるので、何文字分 rotate したかは重要ではなく、今 s == t となっているかだけに注目すればいい。
なので、i 回目の操作が終わった段階で s == t となっている操作列の個数 ( ソースコード中の good ) と s != t となっている操作列の個数 ( bad ) の二つの変数を用いた DP で計算できる。
変数を使いまわしているので、メモリ量 O(1) になってる。

rotate で s == t となるのが何箇所あるかの前計算に O(|s|^2)、本処理に O(k) かかっている。
http://www.codeforces.com/contest/176/submission/1588136

C.
ひたすら手で例を試して、結果を埋め込んだ。
詰めが甘くて一回 Hack されたけど、それで AC できたのはよかった。

二つのコマの初期座標を (x1, y1), (x2, y2) とすると、|x1-x2| > 4 or |y1-y2| > 4 のときに後手必勝なのは実験すればわりとすぐに見えるので、そうでないときを全探索するというのが想定解だった。
http://www.codeforces.com/contest/176/submission/1590083
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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