Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2011年05月03日20時02分から.
[summary]

Assignment

300-500-1000の変則セット.

EASY

長方形の領域が,縦にX-1個,横にY-1個,平行に切れている.(X*Y個の小さい長方形のマスがある)
小さな長方形のうち,面積を知ってる長方形が与えられる.
尋ねると,指定した小さい長方形の面積が教えてもらえる.
大きな長方形の面積を求めるためには最小で何回尋ねれば良いかを求める問題.
XとYは50以下.

サンプルより,ある長方形の4隅に当たる部分のうち,3箇所分かったらもう1箇所もわかることが書いてある.
てか,これはシンプルすぎる特徴で,わかる場合ってこれだけじゃないの?
頭の中でイメージする.
これより複雑なのはこれから生成できるでしょう….
ってことで良さそう.
で,分かる場所は,適当に分かるって指定って,これ以上分かる場所がなければ,わからない場所を適当に1個尋ねれば良い.
頭の中のイメージでは,この伝播は可逆というか,ばばばばーと伝わっていくので,どこを調べても良い.
(結果的に,union findっぽい感じらしかったし)
ってことで,300点とは言ってるけど,瞬殺できそう!
愚直に書く.サブミット.
さて,これ実行時間大丈夫かいな?
最悪ケースがよくわからないけど,とりあえず,最大サイズの全部わかってない場合を入れてみる.
TLE.orz
えっと,えっと…,どうしよう.
少しサイズ減らせば間に合うな…,定数倍最適化をする.
駄目だ.じゃあ,こういう定数倍最適化で….
間に合った.いくらか試すけどTLEはなさそう.
再提出.

MEDIUM

整数からなる集合Sを[A,B]と[C,D]の和集合とする.
XをSの部分集合で,Sの任意の要素xに対して,その倍数が少なくても1つはXに含まれていなければならない.
最小のXの要素数を求める問題.
A,B,C,Dは1以上10^10以下.

えっと….
ある要素の2倍が含まれてたら,ある要素を削除,3倍,4倍,とやっていけば良い.
で,sqrt(10^10)倍ぐらいまでやればいいのか.(違う! てかなんでこんな勘違いしたの…)
愚直に駄目な感じで書く….
あれ,なんか,これ計算時間大丈夫かな…心配.
….
なんか,実装面倒だなぁ….
ちょっと整理してかんがえろよ,もっと簡単に,計算量も問題ない書き方があるだろ?
全部消す.
 [A/2, B/2], [A/3, B/3], …, [C/2, D/2], [C/3, D/3], …
みたいなのを全部生成して,区間の端をソートして左からなぞるだけでいけるじゃないか.
書きなおす.
サンプルあった.提出.

HARD

各要素の絶対値が10^9以下の配列Aが与えられる.Aの要素数は50以下.
1回の操作で,Aのある要素を選び,1だけ増やすか減らすかできる.
最小で何回の操作で,数列の和と積を一致させることができるかを求める問題.

場合分けゲー?
なんか,あんまり和と積を一致させる方法がない気がする.
1つを0にして,残りの和を0にするのは例外処理で求めておく.
後は,基本的には絶対値が1のをたくさん並べて,残りの例外的なのは少ない.
てか,積があまり大きくなると実現不可能. ( {1, 1, -1, -1, でっかい} のパターンを忘れている )
積は,100を大きく越えると無理だよね….
ん? 50を超えても無理かなぁ? (そんなことはない)
全探索で行けるんじゃ?
書いてみる.
TLE.
書き方が悪かった.
でもTLE.
積が70以下にしてみる.
ぎりぎり間に合う….なんて微妙な….
70以下でいいからとりあえず提出してみる.

Challenge

何もせず.
あ,HARD落とされた.

System tests

EASY通る.MEDIUM落ちる.
惨敗.というか,負けるだけならいいのだけど,今回のはちょっと頭悪すぎて凹んだ….

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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