Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1979-6a38f13d
この記事にトラックバックする(FC2ブログユーザー)

2011 Qualification Round (参加記録) (この記事を編集する[管理者用])

2010年05月07日08時から24時間,4問.
[ Link ]

今年は25点以上でRound 1に進出.
Smallだけで進出することも可能になった.

A問題 - Bot Trust

2つのロボットと,2組の一直線上に並んだボタンがある.
ボタンは,それぞれ,100個ずつ等間隔に並んでいる.
片方のロボットは片方の直線上を動け,もう片方のロボットはまた別の直線上を動ける.
ロボットは時間1あたりに,今いる場所のボタンを押すか,隣のボタンに移動することができる.
最初,2つのロボットはそれぞれ端のボタンにいる.
順番に押すべきボタンの列が与えられたとき,それを達成するための最小時間を求める問題.
Small: 押すべきボタン数は10個以下
Large: 押すべきボタン数は100個以下

シミュレーションやるだけで問題ないよな.
Largeでも時間は余裕.書く.サブミット.

B問題 - Magicka

{Q, W, E, R, A, S, D, F} を基本文字と言う事にして,それ以外のアルファベットを基本じゃない文字ということにする.
最初リストは空で,リストに順番に1文字ずつ,合計でN文字入れていく.
最終的なリストを求める問題.
ただし,以下2種類の規則が与えられ,それが適応できる状況になったら適応していく.
 規則1: xyz (xとyはベース文字,zはベース文字でない) の形で与えられ,xとyが隣り合ったら,即座にxy (かyz) をzに置き換える
 規則2: xy の形で与えられ,規則1が即座に適応できない状況で,xとyの両方がリストに存在するなら,リストを空にする
Small: 与えられる規則1の数は1個以下,与えられる規則2の数は1個以下,Nは10以下
Large: 与えられる規則1の数は36個以下,与えられる規則2の数は28個以下,Nは100以下

問題文がややこしい.
連鎖とかあるの,同時に2つ以上の条件満たしたらどうなるの?
….
そういうのは無いよう条件が作られているのか!
じゃあ,まぁ,適当にシミュレーションでいい.
書く.Incorrect.あれ?
あ,これ,規則2は全部消えるのか.挟まれた部分だけ消えるんだと思ってた.
修正.SmallはCorrect.Largeもサブミット.

C問題 - Candy Splitting

N個の正整数が与えられる.
その整数を2つのグループにわける.片方が空集合であってはいけない.
その2つのグループの各要素のXOR (排他的論理和) が等しくならなければいけない.
そのようなグループ分けがなければNOと出力し,そうでなければ,片方のグループの要素の和を最大値を出力する問題.
Small: Nは2以上15以下
Large: Nは2以上1000以下

ん,Nは1000?
どうやるんだ….
分けれる条件はXORが0.
って,分けれるならどうわけても分けれるのか.
えっと,全部総取りは駄目なんだっけ,駄目って書いてあるな.
じゃあ,一番少ないのを弟に渡して終わりかな.
書く.サブミット.

D問題 - GoroSort

1~Nがちょうど1回ずつ登場する配列が与えられる.
配列を昇順でソートするのに必要な操作回数の期待値の最小値を求める問題.
1回の操作では,
 配列の要素をいくつか (0以上N以下) 固定して,配列のその他の要素をランダムに並び替える
ことができる.
Small: Nは10以下
Large: Nは1000以下

これ前計算したことあるから結果知ってる.
合ってない場所だけ入れ替えると,大体1個合うから,大体「場所が間違えてる要素の数」ぐらいでソートが終わりそうだけど,実際にそうなる.
でも,まあ,これ,知らなかったら大変だろうなぁ…,普通にやるならDPかな.
知ってるから,それで書く.サブミット.

Result

4問とも通った.少し簡単になったかなぁ.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1979-6a38f13d
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。