きままにものづくり

日々の気付いたことなんかを書いてます。

2015-02-01から1ヶ月間の記事一覧

ARC022 C問題

問題 C: ロミオとジュリエット - AtCoder Regular Contest 022 | AtCoder C: ロミオとジュリエット - AtCoder Regular Contest 022 | AtCoder 解法 DFSをしながら、最大の距離とその頂点を記録しておく。 計算量 コード

ARC023 C問題

問題 C: タコヤ木 - AtCoder Regular Contest 023 | AtCoder C: タコヤ木 - AtCoder Regular Contest 023 | AtCoder 解法 −1の連続する区間を取り出す。例として2 -1 -1 9を取り上げる。この時の組み合わせは、3回の足し算で2を9にするための組み合わせとな…

arc024 C問題

問題 C: だれじゃ - AtCoder Regular Contest 024 | AtCoder C: だれじゃ - AtCoder Regular Contest 024 | AtCoder 解法 文字の出現回数を数える。数えた結果を集合に保存しておく。重なる箇所があるとアナグラムとならないので、そこはqueueを使う。 計算量…

ARC025 C問題

問題 C: ウサギとカメ - AtCoder Regular Contest 025 | AtCoder C: ウサギとカメ - AtCoder Regular Contest 025 | AtCoder 解法 目的地を固定し、ダイクストラで最短経路を計算する。カメの距離、ウサギの距離がとなる点の数を二分探索で計算する。 計算量…

ARC026 C問題

問題 C: 蛍光灯 - AtCoder Regular Contest 026 | AtCoder C: 蛍光灯 - AtCoder Regular Contest 026 | AtCoder 解法 愚直なdpを考える。テーブルは dp[廊下の位置]:=最小コスト とする。これだととなりTLEする。 区間lとrの中で最小の値を見つけるのにの時…

ARC027 C問題

問題 C: 最高のトッピングにしような - AtCoder Regular Contest 027 | AtCoder C: 最高のトッピングにしような - AtCoder Regular Contest 027 | AtCoder 解法 dp[カードの枚数][スペシャルカードの枚数]で動的計画法を行う。 計算量 コード

ARC028 C問題

問題 C: 高橋王国の分割統治 - AtCoder Regular Contest 028 | AtCoder C: 高橋王国の分割統治 - AtCoder Regular Contest 028 | AtCoder 解法 ツリー構造になっているので、子となる頂点をルートとした際のサブツリーの要素数をDFSで求めていく。バランス値…

ARC029 B問題

問題 B: 高橋君と禁断の書 - AtCoder Regular Contest 029 | AtCoder B: 高橋君と禁断の書 - AtCoder Regular Contest 029 | AtCoder 解法 角度に対して二分探索を行う。二分探索では0度の時(縦横が同じ状態)を見逃してしまうので、その点に注意する。 計算…

ARC030 C問題

問題 C: 有向グラフ - AtCoder Regular Contest 030 | AtCoder C: 有向グラフ - AtCoder Regular Contest 030 | AtCoder 解法 強連結成分を取り除けば、有向非巡回グラフ(DAG)になる。得られたDAGをトポロジカルソートすることで、dp[頂点番号][文字番号]で…

SRM637Div1Medium

問題 高さ2、幅Wのボードが与えられる。各マスは黒か白である。ひとつの白いマスを選択し、それを黒に変える。ただし、左側から右側に白いマスだけで行けるルートは残さないといけない。この操作を2人で交互に行う。操作ができなくなった方を負けとする時、…

SRM636Div1Medium

問題 高さH、幅Wのボードが与えられる。各要素は、'.'、'#'のどちらかである。r個のうさぎが与えられ、一様ランダムに'.'となっている要素にうさぎを配置する。 うさぎを頂点とし、Xとf(X)をエッジでつなぐ。Xはうさぎの番号を示し、f(X)はXから最も近いうさ…

ARC033 C問題

問題 C: 仕事計画 - AtCoder Regular Contest 032 | AtCoder C: 仕事計画 - AtCoder Regular Contest 032 | AtCoder 解法 辞書順の制限が無いの場合は、終了時間が早い順に選んでいく貪欲法で解くことができる。 辞書順の制限がある場合は動的計画法を用いる…

SRM441Div1Medium

問題 N個の頂点と、そろぞれの頂点同士の接続関係が与えられる。全ての頂点がつながっている状態にするのに必要な操作の最小回数を求めよ。できない場合は-1を返す。 許される操作は以下である。 4つの頂点A,B,C,Dを選ぶ。AとB、CとDは接続されてる。 AとBの…

SRM643Div1Easy

問題 大きな整数Nが与えられる。これを素因数分解した時の昇順にならんだ因数の数列を求めたい。ヒントとして答えとなる数列の偶数番目の要素(初めのインデックスは0)を取り出した数列が与えられる。 解法 愚直に素因数分解をするととなるため、計算量を削る…

ARC033 C問題

問題 C: データ構造 - AtCoder Regular Contest 033 | AtCoder C: データ構造 - AtCoder Regular Contest 033 | AtCoder 解法 BITと二分探索で解ける。 計算量 削除: 全体: コード

SRM642Div1Easy

問題 要素数Nのtime、probの2つの数列と整数sが与えられる。バス停を考える。バスiが選択される確率はであり、戻ってくるのにの時間がかかる。一つのバスが出発しそのバスが戻ってきたら、バスを選択しまた出発する。バス停を離れているバスは1つだけとする…