問題リンク Surf Smelt Fishing Contest II 解法 最初はPriorityQueueでゴリオシできると思ったのですが無情のTLE。 なのでセグメント木っぽいの作って解きました。 木のノードには、その区間の最大匹数とそのidを持たせておき、クエリが来るたびに更新しま…

問題リンク Maximum Sum Sequence II 解法 よくある総和の問題です。 (1, 1)-(i, j)の部分行列の総和S[i][j]を前計算しておくと、 (y, x)-(i, j)は S[i][j] - S[y-1][j] - S[i][x-1] + S[y-1][x-1] で求められます。 ソース

問題リンク Sum of Integers II 解法 DPです。 dp[N][X][S]: X以下の数字から異なるN個を選んで、和がSになる組み合わせ数 という表を埋めれば解けます。 解法2 DPですが、 dp[N]: 2個の数字を使って和がNになる組み合わせ という表を用意して dp[i] * dp[N-…

問題リンク Sum of 4 Integers II 解法 よくあるタイプの数え上げ問題です。 (a, b)と(c, d)の組に分け、(a, b)で和sを作る組み合わせ数、(c, d)で和n-sを作る組み合わせ数を掛け合わせていけば解けます。 ソース

問題リンク Surf Smelt Fishing Contest 解法 1人ずつ記録を見ていって、定義通りに優勝者を探します ソース

問題リンク Calculation of Area 解法 割るだけです ソース

問題リンク Blur 解法 DFS+枝刈りで解きました。 f(i, j, k, drop): 既にk滴使っている状態でマス(i, j)に大きさdropの滴を落とす という関数を作っておいて、左上から右下のマスへこの関数を再帰させます。 問題が与えている座標系は(x, y)座標ですが、自分…

問題リンク Path on a Grid 解法 与えられる壁の情報が厄介で扱いづらいので扱いやすい形に変えます。 座標を左上から順に0〜24と番号付けし、e[i][j]の2次元配列で座標i, jの間に壁があることを示すようにします。 次に移動ベクトルを作るのですが、上、右…

問題リンク Overlaps of Seals 解法 最良優先探索の方針で解きました。 空間を4分割していき、最もシールが重なっていそうなところから探索をかけます。 クラスRは探索空間を表し ・X座標の左端と右端 minx, maxx ・Y座標の上端と下端 miny, maxy ・空間の4…

問題リンク The Shortest Path on A Rhombic Path 解法 DPです。その地点に到達するときの最大値を格納します。 数字の配置がひし形で変則的なので、ひし形の半分で区切ってDPを埋めるといいと思います。 ソース

問題リンク The Code A Doctor Loved 解法 Mapで対応表を作って頑張りました。 かったるかったですが、表さえできてしまえばあとはやるだけです。 ソース

問題リンク Strange Mathematical Expression 解法 逆ポーランド記法の式を評価できれば勝ちです。Stackを使います。 ソース

問題リンク Patrol 解法 道を一筆書きできるかを判定する問題です。 頂点の次数を調べていき、次数が奇数の頂点が0もしくは2個ならば一筆書き可能です。 0個の場合にオイラーグラフと呼び、2個の場合に準オイラーグラフと呼びます。 前者は閉路を持ち、後者…

問題リンク Joseph's Potato 解法 ヨセフの問題です。 残り1人になるまでシミュレートしてもO(nm)なので間に合います。 ソース

問題リンク Search Engine 解法 "," "." " "の3文字は同じ区切り文字という意味で混在させておくと面倒です。 文字列中の",""."はreplace()を使って" "に置き換え、" "でsplit()します。 あとはsplitして得られた各文字列sの長さが3以上6以下かどうかを調べ…

問題リンク Era Name Transformation 解法 年月日を表すクラスEを作り、比較メソッドcompareToを作りました。 pre-meiji, meiji, taisho, showaについて、各年号の最終日をクラスEの配列eとしてで作っておきます。 入力された年月日fをpre-meijiから順に比べ…

問題リンク Flying Jenny 解法 乗り物の並びは4,1,4,1,2,1,2,1で固定です。先頭の乗り物を0〜7番の乗り場にしたときに何人残るかを全部試します。 乗り物を文字列で表現("41412121"など)すれば、辞書式で一番小さいものが答えになります。 ソース

問題リンク A Symmetric Point 解法 直線P1P2と直線QRの交点Pをもとめて、QPを倍伸ばしたところがRだと思ってやってみたがWAをくらい、じゃあもういいよ！って手計算で点Rを計算しました。 QRの中点はP1P2上にある QRとP1P2は直交する の２つの条件から連立…

問題リンク Leap Year 解法 0 ソース

問題リンク Square Searching 解法 右下の座標が(i,j)で1辺がwの正方形が作れるかは下準備をすればO(1)で判定できます。 sum[i][j]という2次元配列を用意します。これは(0,0)〜(i,j)の長方形に含まれる空きマスの数を表します。 このsumを使うとマップ上の任…

問題リンク Third Root 解法 3乗根を求めるための漸化式が載っているのでそれを実装します。 終了判定は q * 10^-5 未満ですが、ソースではq*10^-6になってるのは自分でもよくわかりません。 ソース

問題リンク Area of Polygon 解法 問題文にヘロンの公式が載っていますがスルーしました。 多角形の面積は外積を使って求めることができます。 ググればすぐに引っ掛かります。 ソース

問題リンク Magic Square 解法 魔方陣の作り方が問題文に載ってるのでそれを頑張って実装すれば勝ちです。 ソース

問題リンク Run Length 解法 文字列を先頭から見ていき、'@'以外ならそのまま。'@'なら復元処理をします。 ちょっとした工夫の話をします。 文字列を作るときに String ans = ""; としておいて、+文字列連結演算子で復元文字列を作っても勿論いいですが、Str…

問題リンク Treasure Hunt II 解法 点(x, y)から次の地点に進むまでの大きさ(dx, dy)を求めれば勝ちです。 原点を中心に(x, y)を反時計回りに90度回転させて(X, Y)とします。 X = x*cos90 - y*sin90 = -y Y = x*sin90 + x*cos90 = x です。この(X, Y)ベクト…

問題リンク BMI 解法 BMIを調べて25以上の学生の番号をリストに突っ込んでいきます。 全学生を調べた後リストが空なら"該当なし"、そうでないなら番号を出力します。 ソース

問題リンク Videotape 解法 時分秒のままだとやりにくいので、入力されたカウンタ値を秒単位に変換し、x[s]とします。 標準録画の場合は7200(=2時間)からxを引いたものが残りのテープです。 3倍録画の場合は7200*3(=6時間)から3*xを引いたものが残ります。 …

問題リンク Surface Area of Quadrangular Pyramid 解法 底面の面積はx*xです。 側面の２等辺三角形の１つの面積sは s = x * sqrt(x*x+h*h) / 2 です。 よって四角すいの表面積Sは S = x*x + s*4 = x*x + 2*x*sqrt(x*x+h*h) で求まります ソース

問題リンク Carden Lantern 解法 最小全域木が使える問題です。 辺のコストは配置する灯篭の数です。 ※UnionFindのソースはチームwakaba様の公開ライブラリから拝借させていただきました ソース

問題リンク Bombs Chain 解法 爆発する爆弾の上下左右３マスを探索し、爆弾を見つけたら再帰的に爆弾を爆発させればおｋです。 ソース