問題 問題概要 探索問題。２分探索で値の前後を求める。 解法 まず、storeに店の位置を入れる。この時、少しsample1を使って、考察してみる。本店の位置を0にしてしまうと、宅配先1からの距離は4-0=4で正確に求まるが、宅配先2からの距離は6-0=6で正確なもの…

問題 問題概要 探索問題。単純に全探索してしまうと、TLE。 解法 まず、単純に考える。全てのパターンを考えれば良いので、以下のコードのように単純に4つの矢が刺さるマスを全探索すればいい。 int main(void){ while(1){ int n, m; cin >> n >> m; if(n ==…

問題 問題概要 場合分けが必要な６方向の幅優先探索。イルミネーションが必要なところが色塗りの感覚でわかる。 解法 まず、イルミネーションが必要なのは、外側のみであり、内側の部分は必要ない。よって、その外側の部分(周りが完全に囲まれている中の部分…

問題 問題概要 ２次元にあるビット(0, 1)を任意の縦列、横列を選び任意の回数反転させることができる。最終的に最も0が多くなる時の0の数を求めよ。 解法 この問題には「R の上限 10 は C の上限 10000 に比べて小さいことに注意せよ」と書かれていて、解法…

問題 問題概要 強連結成分分解する問題。 解法 強連結成分を分解するアルゴリズムとして、Kosarajuというものがある。今回はそれを使って、実装した。アルゴリズム自体は下のサイトを見てもらえれば、分かりやすい。 mathtrain.jp ミス アルゴリズム自体の理…

問題 問題概要 共通部分文字列の問題。ただし、連続した文字列でなければならない 解法 単純なdp。文字列s1とs2の両方を何文字目ま見ているかという要素を配列の要素と持つdpを考えればいい。 dp[i][j] = dp[s1のi文字目までで考える][s2のj文字目までで考え…

問題 問題概要 都市0から都市Nへ移動する。都市iから都市i+1にj日目に移動するとき，Di*Cj疲労度がたまる。都市0から都市Nまで移動した時の疲労度の最小を求めよ．ただしM日以内にNに到達しなければならない。 解法 都市iにいて，その時j日目の状態において…

問題 問題概要 服を選んで、|Cx1 - Cx2| + |Cx2 - Cx3| + … + |Cxi-1 - Cxi| の最大値を求める問題。 解法 動的計画法で解ける。i日目までの服の選び方を決めたとき，i + 1日目以降について服を選んで目的の値を最大化する際には，1日目からi - 1日目までの…

問題 問題概要 与えられた図形が、点Pを通るどのような直線で切ったとしても、面積を2等分する点Pが存在するかどうかを求める問題。 解法 点対称のような図形になればいい。なんて言えばいいかわからないけど、角張った円のような。(重心関して点対称であれ…

問題 問題概要 各国は世界平和を目指して、ミサイルを破棄。ただし、各国はミサイルを製造が古い順番に破棄していかなければならず、さらに、各国のミサイルの威力の合計値(軍事力)の最大値と最小値の差がd以下を常に保ちながら破棄していく必要がある。 解…

問題 問題概要 ゲームのステージがN個あり、そのステージすべてをクリアするためのステージの並べ方の場合の数を求め問題。ただし、(k個目のステージの難易度) >= (k-1個目のステージの難易度) - Tでだければならない。 解法 ステージの難易度を昇順にソート…

問題 問題概要 条件に合う最もよいピザを選ぶ 解法 この問題は貪欲法で解ける。なぜなら、トッピングの値段がすべて同じだからである。トッピングの値段が同じであるなら、トッピングのカロリーが高いものから優先的に選んでいけばいい。あとは、何個のトッ…

問題 問題概要 幅優先探索で最短経路を求める問題。ただしスタートとゴールがいくつもある。 解法 よくあるstartからgoalまでの最短経路を求める問題と同じ。ただし、その途中でチーズを小さい順に食べていかなければならない。そのため、（ciをチーズi番目…

問題 問題概要 与えられる文字列(数字)n個の中からk個選んで、つなげることで、できあがる文字列の種類を求める。 解法 next_permutationを使い、すべての順列を作る。その順列すべてに対して、前からk個選んで選んだ順番に文字列としてつなげる。そのように…

問題 問題概要 一列バージョンのぷよぷよみたいな感じ。好きな場所の色を一箇所変えることができ、それを行うことにより最も多くボールを消せる場合を求める問題。 解法 まずすべての玉の色を変えて全探索する。そして色を変えた前後で同じ色の数をカウント…

問題 問題概要 連続したクエリの中に頂点とそれをつなぐ辺の長さのクエリと、2点間の最短距離を求めよというクエリが含まれる。 解法 任意の2点間の距離を求めるにはワーシャルフロイト法で求めることができる。ただし、最短経路を求めよというクエリに対し…

問題 問題概要 数字の連続した長さの最大値を求める問題。ただし与えられたクエリの中に、0があれば好きな数字に変えることができる。 解法 まず、与えられた数字をバケツソートしておく。前から順番に数字を見ていき、連続成分の大きさで最大ものを探す。そ…

unionfind tree構造を用いる問題