Entries

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

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

カラオケログ (この記事を編集する[管理者用])

2009.12.28 15:06--2009.12.28 19:57 (DAM+持ち込み)+JOY
人数: 8人~9人 (2部屋)

2009.12.29 00:09--2009.12.29 06:00頃 DAM+持ち込み
人数: 5人

曲持ち込みカラオケ本番.
今回は首謀者の人がちゃんと映像も設置されているディスプレイに映してくれた.

続きを読む

カラオケログ (この記事を編集する[管理者用])

2009.12.25 13:23--2009.12.25 14:19 Joy+持ち込み
人数: 1人

続きを読む

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

2009年12月23日11時から.

Assignment

250, 450, 1050の変則セット.
珍しくrngさんがレジストしてない….

EASY

将棋の銀の駒が,ある場所からある場所に移動する最小手数を求める問題.

将棋だと!?
…さて,解き方は…,うーん?
greedyで良いのでは?
良さそう.
書いた.サブミット.

MEDIUM行く前に確認.サンプルに58とかないか…?
ある!

MEDIUM

いろんな長さの棒が幾つかあって,棒を一定回数以下切って,大きい方からK番目の長さを最長にしたい.
長さはいくら?

サンプルがやっぱり58.
それはさておき,2分探索じゃね?
書いた.サンプルは通る.こんなので良いのか?
まぁ,サブミット.

HARD

問題文中の式を満たす,整数から整数に移す関数のうち,Σ|f(x[i])-y[i]|を最小にするのは何?

関数って線形じゃないとダメなんじゃ?
でも,それじゃ,Cが偶数のとき解がない….
適当にローカルな関係式を満たせば良いのでは…,本当か?
わからん.

Challenge

EASYで場合分けしててミスってる人発見.落とす.
MEDIUM見て,あれ,自分って,マイナス1回カットするようにカウントしてね?
してる.終わた.

System tests

MEDIUMは順当に落ちる.EASYは通る.
やっぱり,自分は,朝方のSRMではrateが落ちるのは避けられないみたいだ.

M-1グランプリ 2009 (この記事を編集する[管理者用])

パンクブーブーおめでとう.
確かに,今回が決勝初めてなのが不思議だよなぁ.
少なくても,去年の敗者復活は電気カミソリのクレームのネタで面白い奴だったと思うし.
今年の決勝のネタは,1個目は隣人騒音クレーム,2つ目は陶芸家の弟子で,両方ともある程度は知ってるやつだったんだけど,面白くなってた.

New TopCoder eXchange (この記事を編集する[管理者用])

僕は現状(でも),実力より遥か上のratingが付いている思うので,僕を買うと損すると思うんだ…

カラオケログ (この記事を編集する[管理者用])

2009.12.20 13:30--2009.12.20 14:27 UGA+持ち込み
人数: 1人

続きを読む

A Bangladeshi Contest (この記事を編集する[管理者用])

2009年12月19日17時から5時間,9問.
[ Link ]

徹夜明けにちょっとだけ仮眠取って寝起きで参加ってことで酷いことに….
一応問題数だけならTopタイの7問解いた.
そのうち問題別に記事作るけど,簡単に解いた問題解説.
nodchip先生の記事がわかりやすいので,そっちを見る方が良い.

Aはこの前TopCoderのMember SRMのbeta 2回目?か何かで出題されたのとほとんど同じ.
見ている枝のコストが空港の建設コストより小さい間クラスカルする.
空港の数を最小化だと思っててWAもらった.
Bはやるだけ.文字列操作.
Cは個人的には難しかった.というか今も想定解法理解していない.
負けるパターンはwikipedia: Wythoff's_gameの通りなんだけど,テストケースが多いのでそれを愚直に調べてTLE.
テストケースを最初に全部読み込んで,ソートして,Fenwick Tree使って数え上げるという荒業でAcceptもらった.
後で,nodchip先生の記事をちゃんと読む.
Dは書くだけ.
Eは問題文を読むのに手間取った.書くだけ.最初から縦横が同じ長さの個体がいると0,縦横別々に同じのが存在すると1,あたりがコーナーケースで気をつけるべき点か.
Gは2分探索 + rolling hashでO(N log N)で解ける.N=文字列の長さ.でもNは高々1000ということでN^2でも良いらしい.
最初に使えない文字を,1字1字別の文字に変換していくと,それは1回しか登場しなくて,使えないことになるので,実装が楽.
なぜか,答えは2以上じゃないといけないと思い込んでWAもらいまくった.
Iは行列べき乗.障害物がある場所まで行列べき乗して,障害物がある場所は別の行列をかける.そして,次の障害物までまた行列べき乗をかける.

カラオケログ (この記事を編集する[管理者用])

2009.12.18 21:40頃--2009.12.19 05:40頃 UGA
人数: 6人 (平均滞在人数5.8人ぐらい)

続きを読む

SRM455 DIV2 MEDIUM - EasySequence (この記事を編集する[管理者用])

Source

TopCoder SRM455 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

0~9が要素となる無限に長い数列AをA[0], A[1], ... , A[N-1]は与えられて,それ以降は
 A[k] = (A[k-1] + A[k-2] + … + A[k-N]) mod 10
で定義する.
長さ50以下の数列Bが与えられたとき,Aの連続部分列として,Bが登場する最初の位置を求める問題.
登場しないならそれを指摘する.
Nは7以下.

解法

まず,Aはそのうち周期的になる.(連続するN項から,その次の項も前の項も一意に決まるので,循環して戻ってくることも言える)
なぜなら,連続するN項が一致したら,その後は同じものが続くから.
ってことで,最大周期は高々10^N.
愚直にやれば,O(最大周期 * Bの長さ)ぐらいで解けるわけだけど,ちょっと不安な感じ.
よくよく考えれば,Bの長さがN以上ならば,Bの最初のN項から数列を作って行って,Bに一致しないならBは登場しない.
そうでなければ,最初のN個が一致した時点で,そこからBが登場することが分かる.
後は,N項まとめて1個の整数として扱ってやれば,O(最大周期)で解ける.
が,実はそんなことしなくても,最大周期は高々2万ぐらいらしく,愚直に書けば通るらしい.(この辺は後で要勉強)

コードはそのうち….

C++によるスパゲッティなソースコード (2009-12-18 05:37追記)
// includeは略
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int visited[10000000], pw[8];

int getNext(int *sum,int N,int now){
  now  = now*10 + *sum;
  *sum = ((*sum)*2 + 10 - now/pw[N])%10;
  return now%pw[N];
}

class EasySequence {
public:
int find(vector <int> A, vector <int> B) {
  int i, k, An, As, Bn, Bs, Cn, Cs;

  pw[0]=1; rep(i,A.size()) pw[i+1]=pw[i]*10;
  
  An=As=Bn=Bs=0;
  rep(i,A.size()) An=An*10+A[i], As+=A[i];
  rep(i,min(A.size(),B.size())) Bn=Bn*10+B[i], Bs+=B[i];
  As%=10; Bs%=10;

  if(B.size() > A.size()){
    Cn=Bn; Cs=Bs;
    REP(i,A.size(),B.size()){
      if(B[i]!=Cs) return -1;
      Cn=getNext(&Cs,A.size(),Cn);
    }
    B.erase(B.begin()+A.size(),B.end());
  }

  rep(i,pw[A.size()]) visited[i]=0;
  k=0;
  while(!visited[An]){
    visited[An]=1;
    if(An/pw[A.size()-B.size()]==Bn) return k;
    An=getNext(&As,A.size(),An); k++;
  }
  
  return -1;
}
2009-12-18 14:30 追記

てか,最初に戻ってくることわかってるんだからvisitedとか必要ないよね….

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

2009年12月18日01時から.

Start

作業してたら少し遅れた….
300,550,900の変則セット.

EASY

0と.からなる50*50以下の盤面が与えられる.
3*3以上の0で長方形の枠が作られていると思って,一番深い場所の深さは?
枠は接しているかもしれない.関係ない0が混じっているかもしれない.

さぁ,どうしたものか….
Greedy…でもいけそうな気もするけど,なんかすごい場合分けが必要な気もするぞ.
計算時間が怖いけどDPでいいんじゃないの?
取り敢えず,50^5程度のDPを書いてみる.間に合う.サブミット.

MEDIUM

三角形がN段積み上がってる図形で,凸な六角形の数をカウントする問題.
Nは500000以下.

数学ゲーな気がします.
上端の長さと,高さが決められたら,作れる六角形の数は計算できそう,右に何回行って,左に何回行くとかそういうので.
いや,でも,それは場合分けが必要だ….
それをO(1)で計算したところで,上端と高さ2つ決めないといけないのでO(N^2)で死亡コース.
う~ん…,わからん.

HARD

900だし,こっちのが簡単な気がする.
問題文ややこしいな….

根付木の枝にスイッチがついてて,1回押すとON, OFF切り替わる.
5種類の木が与えられて,それぞれにコストが定まっていて,そのコストを払うと,最初の木にぴったり重なる部分に対する枝のスイッチを全部押せる.
ただし,各種類の木に対して,同じ場所(ルートが同じ)で適応できるのは高々1回.
スイッチを全部切り替えるのに必要なコストの最小値は?
5種類の木のノード数は5以下,最初の木のノード数は23以下,最初の木は子供が6ノード以上あるノードはない.

まず,最初に読んだとき,
 各種類の木に対して,同じ場所(ルートが同じ)で適応できるのは高々1回.
って条件は意味がないと勘違いしてしまった….
そう思い込んじゃったら,ダイクストラじゃんとか思って書き始める.
状態数が2^22で,枝数も多いので間に合わない気がする….
でも,まぁ,取り敢えず書いてみる.
答えが合わない.
ようやく,条件に意味があることを理解する.
時間切れ.

Challenge

部屋内で,MEDIUMは1人しか提出してない.たぶん落ちない.問題的にも提出してる人的にも.
HARDは提出0.
ってことで,EASYを狙うしかない.
2*2で枠と判定したら間違う,TLE狙い,を考えて0を50*50を準備.

…読めない.
中盤でこの人は間違えてる,ってのを見つけたんだけど,何を投げれば落ちるのかわからなかった.
終盤で落とされてた.

System Tests

EASYは通った.
0点多い,ってか,EASYが難しいよね.少し昔ならMEDIUMで出題されてそうな問題.
反面,MEDIUMもHARDも結構皆解けてるんだよなぁ….
Rateは微妙に増加.

カラオケログ (この記事を編集する[管理者用])

2009.12.16 15:12頃--2009.12.16 16:40頃 DAM+持ち込み
人数: 1人

友達から400円割引券1枚もらったので,曲持ち込んで歌う方法確かめるために行ってみた.
PCのディスプレイを見ながら歌うので良ければ,PCのヘッドフォン用出力と,カラオケの(空いている)マイク入力(3.5mmジャック)を繋げるだけ.
DAMだと前面にマイク入力あるけど,Joyだと背面らしいので,DAM推奨らしい.
(そもそも,Joyだと歌いたい曲入ってないことが多いので,個人的にはそもそもDAM一択だが…)
今日試したやつだと,マイクの音量調整は,マイクごとに設定できなかったので,PC側で音量調整する必要がある.
一応,抜き差しするときは,マイクの音量0にしておいて,PCの音量調整のときは,最初小さめにしておいてから調整する.(大きな音を鳴らさないために)

続きを読む

LiveArchive 3278 - Zones (この記事を編集する[管理者用])

Source

World Finals - Shanghai - 2004/2005
LiveArchive 3278

問題概要

20個以下の電波塔を建てる候補地がある.
それぞれの場所の人口が与えられて,また,幾つか複数の電波塔でカバーされている部分の人口が与えられる.
k個の電波塔を立てるとして,カバーできる最大人数を求める問題.
複数の立て方があるなら,辞書順最小のものを求める.

解法

最高でも20 choose 10通りしかないので,全部計算する.

LiveArchive 3277 - Workshops (この記事を編集する[管理者用])

Source

World Finals - Shanghai - 2004/2005
LiveArchive 3277

問題概要

1000個以下の会議と,1000個以下の部屋がある.
会議は参加人数と何分間行うか,部屋は椅子の数と何分間使用可能か,の情報が与えられる.
最適に割り当てて,行うことができない会議の数を最小化する問題.
会議の数が等しいなら,行うことができない会議の出席人数を最小化する.

解法

greedy.
参加人数の多い会議から処理していって,それが開催できる中で,利用可能時間の一番短い部屋を使う.

LiveArchive 3276 - The Great Wall Game (この記事を編集する[管理者用])

Source

World Finals - Shanghai - 2004/2005
LiveArchive 3276

問題概要

n*nの升目の中にn個の石がある.
1回の移動で1個の石を上下左右に1マスだけ移動できる.
最終的に,縦,横,斜め,どれかに一直線上に並べるまでの最小手数を求める問題.
nは15以下.

解法

最終的な形は2n+2通りしかないので,全部試して最小値を求める.
最終的な形が決まっていれば,最小費用流で最小手数は求まる.

LiveArchive 3274 - Crossing Streets (この記事を編集する[管理者用])

Source

World Finals - Shanghai - 2004/2005
LiveArchive 3274

問題概要

2次元平面上に,x軸に平行,または,y軸に平行に幾つかの線分がある.
線分の交わっている場所は通れないとして,ある場所からある場所に移動するのに,跨がなければならない線分の数の最小値を求める問題.
線分の数は500以下,座標は大きい.

解法

縮小座標作って,01-BFS.(コストが0か1なのでdequeueを使った,もしくはqueueを2個使ったBFS)

LiveArchive 3273 - Lots of Sunlight (この記事を編集する[管理者用])

Source

World Finals - Shanghai - 2004/2005
LiveArchive 3273

問題概要

東西一直線上にアパートが幾つか建っている.
部屋の片方の側面全体に日光が当たっているか,部屋の真上に太陽があるか,その時間帯を求める問題.

解法

簡単な2次元幾何.
適当に計算するだけ.
LiveArchiveだとPresentation Errorになるけど,LiveArchiveなので仕方ない.

LiveArchive 3272 - cNteSahruPfefrlefe (この記事を編集する[管理者用])

Source

World Finals - Shanghai - 2004/2005
LiveArchive 3272

問題概要

52枚のカードがあって,半分ずつ分けて,1枚ずつ交互に重ねていく形のシャッフルを10回以下行った.
ただし,毎回シャッフルの過程で,たかだか1か所隣り合う2枚のカードがスワップしている可能性がある.
最初は順番に並んでいたとして,シャッフル後のカードの位置が与えられるので,
 何回シャッフルしたか
 何回目のシャッフルで,どこのカードがスワップしたか
を求める問題.
複数あるなら,スワップ回数最小,それでも複数あるなら,スワップした位置が辞書順最小のものを求める.

解法

枝刈り探索.
1回スワップすることで,カードの場所が変わるのは2枚なので,それを利用して枝を刈る.

LiveArchive 3271 - The Traveling Judges Problem (この記事を編集する[管理者用])

Source

World Finals - Shanghai - 2004/2005
LiveArchive 3271

問題概要

意訳して問題概要を書く.
ノード数20以下の無向グラフが与えられる.
その中でノードのサブセットが1個与えられる.
そのノードのサブセットを含むノードのセットの最小全域木の中で,コスト最小のものを求める問題.
ただし,複数あるなら,ノード数が最小のもの,それでも複数あるなら,使うノードの種類が辞書順最小のものを求める.

解法

ノードを使うかどうか,たかだか2^20程度(実際には2^18まで)なので,全部最小全域木作って調べる.

LiveArchive 3270 - Simplified GSM Network (この記事を編集する[管理者用])

Source

World Finals - Shanghai - 2004/2005
LiveArchive 3270

問題概要

2次元平面上に,携帯の電波塔が50個以下,町が50個以下,それぞれ座標が与えられる.
いくつかの街の間には直線の道路で結ばれている.
携帯電話は一番近い電波塔につながるとして,ある町からある町に移動するとき,電波塔の変更回数の最小値を求める問題.
電波塔の有効範囲の境界上に町があるとか,変なコーナーケースはないことが保証されている.

解法

強実装問題.
電波塔の有効範囲をボロノイ図を書いて調べる.
後は,それぞれの道路が,境界を何回跨ぐかを調べて,それを距離としてワーシャルフロイドか何かする.
サイズは小さいので全て非効率的な方法でも良い.

UVa 11732 - strcmp() Anyone? (この記事を編集する[管理者用])

Source

Alkhawarizmi Programming Contest 2009 (2009-12-05) (blog)
UVa 11732

問題概要

1000文字以下の文字列が4000個以下与えられる.
すべての文字列のペアに対して,strcmpを呼び足した時,比較回数の合計を求める問題.

解法

文字列をソートして,各文字列と何文字目まで一緒の文字列が何個あるかを使って計算する.
O(文字列の数 * (文字列の数+文字列の長さの最大値))ぐらい.

UVa 11731 - Ex-circles (この記事を編集する[管理者用])

Source

Alkhawarizmi Programming Contest 2009 (2009-12-05) (blog)
UVa 11731

問題概要

三角形が与えられるので,その3つの傍心からなる三角形の面積を求める問題.
また,3つの傍接円ともともとの三角形との共通部分の面積を求める問題.

解法

2次元幾何,実装問題.やるだけ.

UVa 11730 - Number Transformation (この記事を編集する[管理者用])

Source

Alkhawarizmi Programming Contest 2009 (2009-12-05) (blog)
UVa 11730

問題概要

1回の操作でAをA+xに変更できる.ただし,xはAの素因数のどれか(ただし,A自身は素因数とみなさない).
SをTに変更するのに必要な最小ステップ数を求める問題.
SとTは1000以下.

解法

DP.各数字からTにするのに必要なステップ数の最小値をメモしておく.

UVa 11729 - Commando War (この記事を編集する[管理者用])

Source

Alkhawarizmi Programming Contest 2009 (2009-12-05) (blog)
UVa 11729

問題概要

N人の人がそれぞれやるべきタスクを1個ずつ持っている.
タスクは,指導に必要な時間と,実行に必要な時間の2つが設定されている.
指導は一度に1人しかすることができなくて,実行は指導が終わったら即座に行える.
全てのタスクが終わるまでに必要な最小時間を求める問題.

解法

greedy.実行の時間が長い人から指導していけばよい.

UVa 11728 - Alternate Task (この記事を編集する[管理者用])

Source

Alkhawarizmi Programming Contest 2009 (2009-12-05) (blog)
UVa 11728

問題概要

1000以下の数字nが与えられるので,約数の和がnとなるような最大の整数を求める問題.

解法

やるだけ.

UVa 11727 - Cost Cutting (この記事を編集する[管理者用])

Source

Alkhawarizmi Programming Contest 2009 (2009-12-05) (blog)
UVa 11727

問題概要

3つの整数が与えられるので,中央値を求める問題.

解法

やるだけ.

UVa 11725 - Colorful Board (この記事を編集する[管理者用])

Source

Alkhawarizmi Programming Contest 2009 (2009-12-05) (blog)
UVa 11725

問題概要

7*7以下の升目があって,幾つかのマスを除いて,各マスに色を塗る.
使える色は4色で,隣り合うマスは違う色でぬらなければいけない.
色の塗り方をmod 1000000007で求める問題.

解法

DP.
今見ている場所から,一列分だけ前の色を覚えておく.

UVa 11724 - Evaluate the Expression (この記事を編集する[管理者用])

Source

Alkhawarizmi Programming Contest 2009 (2009-12-05) (blog)
UVa 11724

問題概要

 a+b*c*(d+e)
のような,足し算と掛け算のみの式が与えられる.
また,各変数同士の不等式が与えられる.
各変数には正整数を割り当てなければいけず,不等号も満たさないといけない.
式の値の最小値を求める問題.
割り当て方法がない場合はそれを指摘する.

解法

足し算と掛け算しかないので,できるだけ小さい値を割り当てれば良い.
後は,構文解析.

UVa 11723 - Numbering Roads (この記事を編集する[管理者用])

Source

Alkhawarizmi Programming Contest 2009 (2009-12-05) (blog)
UVa 11723

問題概要

R個のものをN種類の数字とD種類のアルファベットのsuffixで一意に定める.
Dはアルファベットなので26以下でなければならない.
suffixをつけないのも許される.
RとNが与えられたとき,Dの最小値を求める問題.不可能ならばそれを指摘する.

解法

RはN*(D+1)以下でなければならないことから,Dの最小値を計算する.
Dが26を超えたら不可能.

TopCoder (この記事を編集する[管理者用])

今日の午前2時からのSRM454は初めて日本人の参加者数が3桁だったっぽい.(otinn.com)
126人.過去の最高記録はSRM452の98人.
chokudai先生の連載の効果かなー?

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

2009年12月06日02時から.

Assignment

超有名な日本人レッドコーダー2人と同じ部屋.怖い.

EASY

Nが1000000以下だし,問題文の定義に沿って実装して愚直にループするだけ?
取り敢えず書いてみた.最大ケースでも間に合うこと確認.
サブミット.

MEDIUM

7-segmentとか実装ミスが怖すぎる.
問題自体はどう見ても典型的DP.
書いてみた.
何か,unused codeが30%以上ある気がするけど,本当にサブミットするかい?って聞かれて怖い.
でも,30%も使ってないコードはないはず.サブミット.

HARD

螺旋で座標定義するのとか嫌だ.というか苦手.
うーん,わからん.O(N)はアウトだしなぁ….
1行とか1列ずつ処理すれば良いんじゃないの?
取り敢えず,Nの数字の座標を求めよう.
考える.
 a*b + (a+1)*(b-1) + (a+2)*(b-2) + …
とか
 a*b + (a+1)*(b+1) + (a+2)*(b+2) + …
とか,こういうの計算できるようになれば,まとめてジャンプして処理できる.
O(sqrt(N))だ!
でも,その計算面倒だよ….
がりがりがり.
バグる.
がりがりがり.
直らない.
がりがりがり.
直った…と思ったらサンプルで2つだけ合わない.
たっぷり時間あったはずなのに,時間切れー.

Challenge

あれ,この人,7-segment文字で2を表示するのミスってるんじゃね?
と思ってチャレンジしたけど失敗.
エンコードの順番勘違いしてただけだったorz
-25pt.

System Tests

システムテストは基本的に平和.自分も両方通った.
てか,自分が普通にシステムテスト通るとか何ヶ月振りだろう….
HARDは結構みんな落としてるなぁ….
前回に引き続き,どちらかといえば簡単めな回でした.(だからといって解けるかどうかは別問題)

Appendix

Recent Articles

ブログ内検索

Ads


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