スポンサーサイト

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

TopCoder SRM 522 Div 2

突然ですけど,TopCoder の SRM に初参加してみました.

わけわからない人もいるかもしれませんが,説明は明日するので今日は結果だけを(・∀・)

問1 250点

int の配列が与えられる.
それらは配列のインデックスと値で座標を表している.
たとえば [0,1,2,3] という配列が与えられたら,それは (0,0),(1,1),(2,2),(3,3) という4つの点を表していることになる.

今この点の集合の中からふたつを選んで,その二つを結ぶ直線を対角線とする四角形描き,その四角形の中に含まれる点を考える.
この四角形の中に含まれる点が最大になるように,ふたつの点を選んだ時,含まれる点の最大値は求めるプログラムを書け.

上記の例で説明すると,(0,0) と (3,3) を選んだ場合が (1,1) と (2,2) の2点が含まれ最大となるので,答えは2となる.
なお直線上にある点は含んでいるとみなさない.



問2 550点

Alice と Bob があるゲームをする.
横一直線に並んだパネルがあり,それぞれのパネルには A または B という文字が書かれている.
自分の手番では,パネルの好きな場所にコインを置く.
1つのパネルには1つのコインしか置くことができない.
一回の手番で,コインを置けるパネルの数には制限はない.
ただし,その手番でコインを置くパネルはすべて隣接していなければならない.
また必ず1枚はパネルを残す必要がある.
最後に残ったパネルに A が書かれていれば Alice の勝ち,B が書かれていれば Bob の勝ちである.
パネルが String として与えられ,最初の手番が Alice として,どちらが勝つか出力するプログラムを書け.
なお両者は最良の手を選択する.

一回の手番でのコインの置き方の例を以下に示す.コインを * で表す.

12345
ABBBA
***

この置き方は良い.

12345
ABBBA
** *

この置き方は 2 と 4 が隣接していないので悪い.



問3 990点

ある正数 a,b,c が与えられる.
これらに対して A * B = C を満たたうえで,
|A - a| + |B - b| + |C - c|
が最小となるような正数 A,B,C を求めるプログラムを書け.



ちなみに今回の成績は

250問題:174.50点
550問題:514.97点
990問題:時間足りず

部屋3位

Rating : No Rate → 1286
スポンサーサイト

コメントの投稿

非公開コメント

お知らせ
相互リンクしてくださる方募集してます!!
Twitter 相互フォロワ―も募集してます!!
コメントも募集してます!!
感想でも質問でも気軽にどうぞ!!

ランキング参加してます!!
クリックお願いします!!

にほんブログ村 高校生日記ブログ 高専生へ
検索フォーム
最新コメント
リンク
admin
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。