問題リンク 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度に取り除…

問題リンク Confusing Login Names 概要 N人の名前と整数Dが与えられる。N人の中で混乱する名前の対を全て求めよ。 混乱する名前の対(i, j)とは、 任意の1文字を消す 任意の位置に文字を1字入れる 任意の1文字を別の文字にする 隣接している文字同士を1か所…

問題リンク Pathological Paths 概要 N個のファイルの絶対パスが与えられる。このシステムには、絶対パス中に現れるディレクトリ、フォルダ以外のものは何もない。さらにM個の絶対パスの組が与えられる。この組の指すファイルが同一のものかどうかを判定せよ…

問題リンク Leaky Cryptography 概要 整数N1〜N8とチェックサムN9が16進数表記で与えられる。これらは32ビット整数である。 Σ(Ni xor K) = N9 xor K を満たすような32ビット整数Kを16進数表記で求めよ。 解法 Kを0ビット目から31ビット目まで順番に決めてい…

問題リンク Make a Sequence 概要 N*Nの各マスに棒がささったボードでM目並べゲームをする。Pターンの間の2人のプレイヤーのボールを置いたマスのリストが与えられるのでゲームの結果を答えよ。(i, j)の棒にボールを置くとき、ボールは重力に従った動きをす…

問題リンク The Balance 概要 aグラムとbグラムの錘を使ってdグラムを量りたい。使う錘の個数を最小化せよ。そのような個数の組み合わせが複数ある場合は錘の総重量が最も軽いものを答えよ。a, bの錘を使ってdグラムを量れないということは起こらないことが…

問題リンク Telescope 概要 半径1の円周上の点がN個与えられる。これらの点を使ってM角形を作った時の最大面積を答えよ。 3 解法 いくら考えても分からなかったのでプログラムプロムナードを参考にしました。 メモ化再帰で解きます。 始点sを決めている前提…

問題リンク Fermat's Last Theorem 概要 整数zが与えられる。z^3を超えないx^3+y^3を見つけ、z^3-(x^3+y^3)を計算せよ。xとyは0より大きい整数とする。 1 解法 iを1, jをzとします。 i^3+j^3がzを超えたならjを1つ減らし、そうでないならばiを1つ増やします…

問題リンク A Long Ride on a Railway 概要 N個の駅とM個の路線がある。路線には長さがある。路線の最長パスの長さとその経路を答えよ。 経路は辞書順比較で一番小さいものを答えよ。 1 1 解法 グラフにおける最長パスを求めるのは普通は困難ですが、グラフ…

問題リンク Spiral Footrace 概要 座標(0, 0)に北を向いて立っている。N個の点が与えられる。N個の点を順番に辿り、最後の点についた時の総距離を答えよ。 点を辿る順番は、向いている方向とその点のある方向との角度が一番小さいものとする。 1 0 解法 幾何…

問題リンク Factorization of Quadratic Formula 概要 2次方程式の整数係数a, b, cが与えられる。これを因数分解し、(px+q)(rx+s)としたときのp, q, r, sを答えよ。 但し、p, q, r, sは全て整数であること。また、0 解法 まず、2次方程式の解の公式の判別式D…

問題リンク Unable Count 概要 3つの整数N, a, bが与えられる。1〜Nの整数の中で、a*i+b*jの形で表現できるもの(i, jは非負整数)の個数を答えよ。 N, a, b 解法 DPです。整数xはx-a, x-bのいずれかが表現できれば表現できることになります。 ソース

問題リンク Where's Your Robot? 概要 H*Wの大きさのボードがある。ロボットが北を向いて(1, 1)にいる。 コマンドを与えられるので、それを実行した後ロボットのいる座標を答えよ。 コマンド実行中、ボードを超えてしまうようなときは、ロボットはそのボード…

問題リンク Planning Rolling Blackouts 解法 メモ化再帰で解きました。 ある分割で[i, j]*[k, l]の区画が作られたとします(左上の座標が(i, j)、右下の座標を(k, l)とする長方形と思ってください)。この区画における最大分割数と最大予備電力は、この区画を…

問題リンク And Then. How Many Are There? 解法 円盤は最大で24枚あります。なので円盤全体の状態は2^24で表すことができます。円盤N枚の初期状態は(2^N)-1です。 状態Xから円盤i, jの2枚を選んで取り除けるかを探索していきます。 iとjが同じ円盤だったり…

問題リンク Identically Colored Panels Connection 解法 色を変えるやり方を全て試します。6色の変更を5回行うので6^5通りになります。ただ、最後の1色はターゲットの色にしないと意味がないので、実質6^4になります。 あとは深さ優先探索で連結成分のもろ…