Entries

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

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

天下一プログラマーコンテスト2013予選B E - 天下一最短路コンテスト (テスター担当) (この記事を編集する[管理者用])

Source

天下一プログラマーコンテスト2013予選B
問題文

問題概要

まず,以下の問題を考える.
2次元平面上にN個の点が与えられるので,最初に与えられた点から出発して,全ての点を通るようなできるだけ短い経路を出力せよ.
この問題に対する貪欲なアルゴリズムとして,
・アルゴリズム1
 まだ通ってない最も近い点を選び,その点に行く,を繰り返す
・アルゴリズム2
 まだ通ってない点が3点以上あるなら,2番目に近い点に行く,を繰り返す
 まだ通ってない点が3点未満になったら,最も近い点に行く,を繰り返す
ただし,同じ距離の点が複数ある場合は,与えられた順番に近いとみなす.
この時,アルゴリズム2の方が,短いかアルゴリズム1と同じ長さの経路を返すようなデータセットを1つ求める問題.
Nが大きいほど点数が高く,N=100で満点だが,Nは100を超えてはいけない.

解法

適当にやればなんとでもなる.以下は解答の一例.
アルゴリズム2が良い結果を返す小さい点のパターンを見つけ,うまく繋げる
95点程度をほぼ1箇所に固めて,残りの点をランダムに配置して,条件を満たすまで繰り返す.(以下のコードはこれ)
アルゴリズム1の経路長 - アルゴリズム2の経路長などをスコアとして山登り,焼き鈍すなどの局所探索を行う.
はしご型や,規則正しく点を配置して,アルゴリズム2が勝つパターンを見つける.

Cによるスパゲッティなソースコード

続きを読む

天下一プログラマーコンテスト2013予選B C - 天下一ジグソーパズルふたたび (テスター担当) (この記事を編集する[管理者用])

Source

天下一プログラマーコンテスト2013予選B
問題文

問題概要

縦$N$マス,横$M$マス,全体で$NM$ピースのジグソーパズルを考える.
上下左右に隣り合うピースは,片方が凹で,片方が凸,端の辺は直線.
KLabのマークであるKっぽい,1辺が直線,3辺が凹のピースの数を最大がしたい.
ただし,4辺とも凹のピースを$A$個以上使って,4辺とも凸のピースが最大でも$B$個までしか使えない.
$2 \leq N, M \leq 8$.
部分点もある.(原文を参照)

解法

DPする.
左上から順番にピースを決めて行って,
 今の場所,4辺凹のピースを使った数,4辺凸のピースを使った数,過去1列分の下向きに接する面は凸か凹か?,一つ左のピースの右側の辺は凸か凹か?
を状態として,K型のピースの最大値をメモする.
状態数は多く見積もっても$1.2 \times 10^7$以下程度だが,配列で愚直にメモリ確保するとMLEに引っかかる可能性があるのに注意する.
いろいろ頑張って枝刈りすれば全探索も可能らしい.

C++によるスパゲッティなソースコード

続きを読む

天下一プログラマーコンテスト2013予選B B - 天下一後入れ先出しデータ構造 (テスター担当) (この記事を編集する[管理者用])

Source

天下一プログラマーコンテスト2013予選B
問題文

問題概要

スタックのシミュレーションを行う問題.
ただし,1回の命令で,同じ数字をたくさん入れたり,たくさんPopしたりできる.
また,スタックに入っている数の数や,スタックのトップの要素を答えたりするクエリが混じっている.
また,スタックのサイズが決まっており,サイズを超えたり,空のスタックからPopしたりトップの要素を参照すると途中でエラーを出して止める.
詳細は問題文を参照.

解法

シミュレーションをやるだけ.
たくさん追加するのは,1つずつやるとTLEになるので,まとめて処理して,何が何個入っている,という形で保存する.
スタックのサイズが,符号付き32ビット整数で表せる限界まで来るので,オーバーフローに注意.(素直に64ビット整数使って気にしないのが楽)

C++によるスパゲッティなソースコード

続きを読む

天下一プログラマーコンテスト2013予選B A - 天下一人力比較 (テスター担当) (この記事を編集する[管理者用])

Source

天下一プログラマーコンテスト2013予選B
問題文

問題概要

問題文中の15個の文字列の中で,辞書順で小さい方から7番目のものを求める問題.
文字列は入力として受け取ることもできる.
文字列はアルファベット大文字のみから成る.

解法

ソートして出力するのが一番楽.
最初の要素を0番目と数えるプログラミング言語では,7番目を出力するのにstr[6]などと指定しないといけないことに注意する.

C++によるスパゲッティなソースコード

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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