Entries

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

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

コメント

[C16]

コンテストお疲れさまでした&改めておめでとうございます。
天下一ゆるふわ(ryの者ですが、賞品を間違えて持って帰ってしまったみたいです。
なんとかしたいのでメールもらえませんか?
すいません。迷惑をおかけします。
Original Comment: 2009-08-04 01:36

EDIT: 管理人
これからメール送りますー.
  • 2009-08-04 01:53
  • romao
  • URL
  • 編集

[C17]

   
  • 2009-08-04 01:54
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

天下一プログラマーコンテスト2009 (この記事を編集する[管理者用])

こっそり参加していました.
最初に思ってたより参加者の層が厚かったみたいで,それに合わせて問題の難易度も途中で調整されたらしく,結果的に普通に難しいコンテストだったと思います.
探索問題・実装問題が多くて,どのように枝を刈るべきか,どう実装すれば簡潔に実装できるか,など本当の意味でセンスが問われる問題たちだったと思います.
逆にアルゴリズムについての知識などは,あまり問われないので,こういう類のコンテストに慣れていない人にも優しいコンテストであったと思います.
問題はそのうちここあたりにでるんじゃないかなと思う.

予選1回目 (2009年07月05日00時から24時間,3問)

問題1
ある区間の中に日曜日が何回あるかをカウントする問題.
1日ずつインクリメントしながらループ回してもOKだし,適当に中身に含まれる日を数えて7で割ってごにょごにょするとか.

問題2
数字からなる文字列を連続する4文字切りだしてきて3の倍数になるものの数をカウントする問題.
実際に切り出して数えてみる.

問題3
日本の硬貨,紙幣を使用して10000円になる組み合わせの数を求める問題.
典型的DP.なんとループで回しても結構現実的な計算時間で終わるらしい.答えは32bitには収まらない.

予選2回目 (2009年07月15日00時から24時間,3問)

問題1
都道府県の名前でしりとりしたとき,カタカナでの文字の長さ最長のしりとりを求める問題.
DFSで実際に全部列挙してみる.

問題2
20以下の素数を全部使う必要はないが,左から小さいものから用いて,等式を作る作り方をカウントする問題.
各素数は高々1回しか使えない.
括弧と四則演算が使用可能.等号は1つのみ使用可能.
DPで解いた人が多いみたい.たぶん全探索でも可能.
というか,作れる数字の種類が多いのでDPするメリットが計れない気がしたので,メモリの問題もあるし全探索してみた.
そしたら僕はミスった.

問題3
ちくちくばんばんみたいなタイルがあるので,指定の場所を繋げるまでの最低ステップ数を求める問題.
おそらくiterative deepening.

予選3回目 (2009年07月25日00時から24時間,3問)

問題1
n=1000000までの自然数を17進数で表した時,Gの登場回数をカウントする問題.
桁ごとに適当に17^kで割ったり余りを調べればO(log n)で解けるけど,
まぁループで回しながら全部の17進数表現を求めても大丈夫.

問題2
2次元のn*nのグリッド上に文字が書かれている.(n=100)
最長の2次元回文を求める問題.2次元回文は正方形の枠の部分を適当な順番で読めば回文になるもの.最初のマスは2回読む.
全探索でO(n^5)だけど,ランダムに書かれてて回文の判定はほとんど一瞬で回文にならないことが判定されてしまうので実質O(n^4)程度の時間で求まる.
ちょっと枝刈りすれば実質O(n^3)ぐらいで求まる.

問題3
2次元パッキング問題.
30*30のマスに,20種類の適当なサイズの長方形を埋め込む問題.
長方形には埋め込んだ時に得られる利益と,縦横のサイズが与えられている.
同じ長方形は1個まで設置可能.勿論重なってはいけない.90度回転して配置してもOK.
どうやら,最初に埋め込む長方形の種類を列挙して,面積が900以下で利益最大のものから,実際に配置できるかどうか探索してみる,
という風にやるとうまくいくらしい.

天下一勝ち抜け戦 (2009年08月01日13時15分から,1問あたり1時間程度)

問題1
障害物のある8クイーン問題.ただし,升目は16*16.どれだけ多くのクイーンを配置できるかを求める問題.
マップの形をうまく利用して枝刈りしなければ全探索は厳しかったみたい.
具体的には,右の方から縦に見ていくと枝が刈れて良い感じ.
他の方法は,メモリと相談しながら,後半部分だけメモ化してみて高速化を図るとか.
厳密性は保証できないけど,その他に答えを出すには,
 ニューラルネットワークで,各マスのクイーン置いてほしい度を更新していってみる方法
 分子限定法で探索して途中で解が更新されにくくなったらリスタートする方法(分子限定法にランダム要素を入れておく)
 グリーディーに置けば実は最適解が求まる!
とかできるらしい.

問題2
ナンクロを解く問題.
長い単語から決めつけて探索していけば終わる.
勿論一番難しいのは画像から入力を取る部分である.

問題3
素因数分解するとブレインなんちゃらっぽい言語で書かれたコードが得られる.
それの実行結果を求める問題.
書くだけの実装問題.

天下一決勝戦 (2009年08月02日10時15分から,1時間程度)
エレベータースケジュール問題.
乗る人が来るタイミング,来る階,行きたい階が与えられるので,それぞれの人の所要時間(エレベーターを降りる時間-到着時間)の和を最小化する問題.
エレベーターは1回止まると最低10秒は扉を開けておかなければいけない.1階移動するのに1秒かかる.
人の数が少なく,大して枝刈りしなくても答えはすぐに出る.
ということで,実装問題.

コメント

[C16]

コンテストお疲れさまでした&改めておめでとうございます。
天下一ゆるふわ(ryの者ですが、賞品を間違えて持って帰ってしまったみたいです。
なんとかしたいのでメールもらえませんか?
すいません。迷惑をおかけします。
Original Comment: 2009-08-04 01:36

EDIT: 管理人
これからメール送りますー.
  • 2009-08-04 01:53
  • romao
  • URL
  • 編集

[C17]

   
  • 2009-08-04 01:54
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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