問題リンク Distance Between Two Cities 解法 バリバリ数学問題です。 まず、2つの都市間の最短距離は、円の中心と2つの都市を通るようにスパッと球を切断したときの円弧の長さとなります。 切断面の半径Rは球の半径と同じなので、2つの都市それぞれの座標(…

問題リンク Lupin The 4th 解法 経路復元+メモ化再帰で解きました。 dp[蔵を訪れた状態][現在いる蔵]に、その状態から全ての蔵を回るまでにかかる最短時間を格納しておきます。 さらに、next[i][j][2]に、状態 i 現在地 j のとき、次にどの状態に遷移すれば…

問題リンク Building a Space Station 概要 N個の球状のスペースステーションの3次元座標(x,y,z)と半径rが与えられる。 あるスペースステーションから全てのスペースステーションに移動できるように橋を架けるとき、架ける橋の長さの合計を最小にせよ。 スペ…

問題リンク The Secret Number 概要 W*Hのボードに、数字もしくはアルファベットが書いてある。あるマスの数字はその下、もしくは右にある数字と繋げて読むことができる。このとき、ボードの中で最も数が大きくなる数字の列を答えよ。 W+H 解法 DPです。マス…

問題リンク Get Many Persimmon Trees 概要 W*Hの大きさの土地にN個の木がある。S*Tの大きさの長方形で囲むことができる最大の木の本数を答えよ。 1 1 1 解法 問題のサイズが小さいので全探索できます。 ソース

問題リンク When Can We Meet? 概要 N人のメンバーがいる。N人は会議に出席できる日にちを申告している。 会議はQ人以上いないと成立しない。Q人以上出席し、最も人数の集まる日を答えよ。そのような日が複数ある場合は日が近いものを答えよ。Q人以上集まれ…

問題リンク What is the Number in my Mind ? 概要 L桁のヒットアンドブローゲームを行う。H個のヒントが与えられるので、正解の数列を求めよ。そのような数列が無かったり、2つ以上存在する場合は"NO"とせよ。 H個のヒントにはL桁の数列tryとそれに対するhi…

問題リンク Kanglish:Analysis on Artificial Language 概要 Kanglishという言語は26個のアルファベットに加え、さらに2文字で1文字を表す語12個を加えた38文字からなるものである。 今文章が与えられる。38個の文字それぞれについて、右隣にきている語の中…

問題リンク Pile Up! 概要 1〜Nの番号が書かれたブロックがある。最初は全て床に転がっている。 2つの整数の命令リストが与えられ、ロボットはそれに従ってブロックを動かす。最終的にできたブロックの塔全ての高さを昇順に答えよ。 命令はX, Yの整数で構成…

問題リンク Exploring Caves 概要 最初(0, 0)の点にいる。移動量のリストが与えられる。これらの移動の中でスタート地点からの距離が最も遠かった点の位置を答えよ。そのような点が複数ある場合はx座標のより大きいものを答えよ。 解法 入力で与えられた通り…

問題リンク Jigsaw Puzzles for Computers 概要 9個のジグソーパズルのピースが与えられる。これらを使って3*3のパズルを完成できるような置き方は何通りあるかを答えよ。 ピースにはW,R,G,Bとこれら小文字の計8文字のうち4つが書かれている。ピースを並べた…

問題リンク Multi-column List 概要 文章がいくつか与えられるので、それをmulti-column listとして出力せよ。 このリストは1ページにつき、高さplen、横幅widthのカラムがcnum個続いている。カラムの間にはcspace個の空白が入る。文章が1行に入り切らない場…

問題リンク Get a Rectangular Field 概要 5*5のマスに0か1が書かれている。1のみを含む長方形を作るとき、できる最大面積を答えよ。 解法 問題のサイズが非常に小さいので、(i, j)を左上のマスとして幅w, 高さhの長方形が作れるかというのを全て試すことが…

問題リンク Cyber Guardian 概要 N個のパケットフィルタとM個のパケットが与えられる。M個のパケットの中で送信が許されるものを答えよ。 パケットは送信元アドレスと送信先アドレスと本文からなる。アドレスは'0'〜'9'と'?'の文字からなる8文字の文字列で表…

問題リンク Patience 概要 Patienceというゲームをする。1〜5が書かれたカードが各4枚あり、それを5*4に並べる。あるカードに注目し、その隣接8マスのカードの中に同じものがあればその2枚を取り除くことができる。取り除けるペアが複数あっても1度に取り除…