スポンサーサイト

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

Croc Champ 2012 - Round 1

2012/04/06
Croc Champ 2012 - Round 1

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

問題

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

A. Rock-Paper-Scissors

Nikephoros と Polycarpus が n 回じゃんけんをする。
Nikephoros は周期 m のあるパターンに従って手を決める
Polycarpus は周期 k のあるパターンに従って手を決める
それぞれが負けた回数を求めよ。

1 ≦ n ≦ 2・10^9
1 ≦ m, k ≦ 1000

B. Chamber of Secrets

n × m の盤上にいくつかの柱がある。
左上のマスから、右に向かってレーザーを発射する。
レーザーは柱を貫通するが、柱に魔法をかけると、柱の縦横 4 方向にレーザーを拡散させることができる。
盤の右下のマスから右方向にレーザーを通すことで、敵を倒すことができる。
魔法をかけるべき柱の最小本数を求めよ。
どうやっても敵を倒せなければ -1。

2 ≦ n, m ≦ 1000

C. Spiral Maximum

n × m の盤があり、各マスには一つの整数が書かれている。
問題文中の図にあるようなサイズ k ( k は奇数 ) の螺旋を盤上にはみださないように一つだけ乗せる。
螺旋の黒い部分の上にある数の和を最大化せよ。

3 ≦ n, m ≦ 500

解答

A.
二人の手のペアは周期 m・k をもつので、その分を一気に飛ばして計算して、余った n mod m・k 回は素直に計算する。
http://www.codeforces.com/contest/173/submission/1480549

B.
今いる位置と方向のペアを状態として最短経路を求める問題。
Dijkstra 法で解いた。
TLE がかなりきわどいけど、4 方向ではなく 2 方向 ( 縦 or 横 ) だけ保持するようにしたらぎりぎり間に合った。

deque を使って、コスト 0 の遷移は先頭に、コスト 1 の遷移は末尾に追加するようにすると log をかけずに解くことができる。かしこすぎる。
この手法は 0-1 BFS といわれているらしい。この問題で始めて知った。
http://www.codeforces.com/contest/173/submission/1483076

C.
螺旋の形をよく観察すると、サイズ k の螺旋がサイズ k+2 の螺旋にぴったり嵌まることがわかる。
嵌めたあとの形はほぼ長方形 ( 一マスだけ空く ) になる。
この長方形の部分にある数の和は DP で前計算しておけば O(1) で求められる。( 二次元累積和 )
ここまで気付けば、あとは小さい k から順に DP で、螺旋を任意の位置においたときの数の和を求めていくことができる。
DP 配列は k 方向には使いまわさないと MLE するかもしれない。
http://www.codeforces.com/contest/173/submission/1651851
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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