競技プログラミング/ARC

ABC075 D: Axis-Parallel Rectangle

D - Axis-Parallel Rectangle 解き方 長方形の頂点のx座標、y座標はいずれかの点のx座標、y座標と等しいと考えて問題ないので全探索 ハマったところ 全体でO(N^5)だったのでいけるか不安だったが、TLEはしなかった。 github.com

ABC075 C: Bridges

C - Bridge 解き方 DFSして橋を数える ハマったところ bridgeを見つけるアルゴリズムを忘れていたので、一から書いてたらデバッグに時間かかった github.com

ABC075 B: Minesweeper

B - Minesweeper github.com

ABC075 A: One out of Three

A - One out of Three github.com

DDCC2017 Qual C: 収納

ddcc2017-qual.contest.atcoder.jp 解き方 最長の鉛筆をまず箱に入れて、もし入るなら最短の鉛筆も入れる。これを繰り返して個数を求める ハマったところ 最長の鉛筆と入れられる最長の鉛筆を入れるようにしたら、TLEした 後者を求める時に、配列の要素削除…

DDCC2017 Qual B: 鉛筆

ddcc2017-qual.contest.atcoder.jp github.com

DDCC2017 Qual A: DDCC型文字列

ddcc2017-qual.contest.atcoder.jp github.com

Tenka1 Programmer Contest 2017 C: 4/N

tenka1-2017.contest.atcoder.jp 解き方 h,nを1から3500の範囲で全探索する。h, nが決まればwは求まる github.com

CODE FESTIVAL 2017 qual A C: Palindromic Matrix

code-festival-2017-quala.contest.atcoder.jp 解き方 回文を作るのに必要な同じ文字の数を計算 各アルファベットの出現回数を計算 必要な文字数が多い場所から順に、条件を満たす最小のアルファベットを入れる貪欲 ここが嘘解法っぽさがある github.com

CODE FESTIVAL 2017 qual A B: fLIP

code-festival-2017-quala.contest.atcoder.jp 解き方 行、列を入れ替える順番は無視して良いので、何列、何行入れ替えるかで全探索 ハマったところ +=の副作用を見逃してた github.com

CODE FESTIVAL 2017 qual A A: Snuke's favorite YAKINIKU

code-festival-2017-quala.contest.atcoder.jp github.com

ARC083 E: Bichrome Tree

E - Bichrome Tree 解き方 ある頂点iの部分木について、黒白それぞれの重みの和を、b_i, w_iとして、それを更新していく 黒白は入れ替えても問題ないので、違う色か同じ色かだけ考えれば良い 頂点iがleafの場合、色はどちらでもよく、重みはx_iになる 頂点i…

ARC083 D: Restoring Road Network

D - Restoring Road Network 解き方 これまでに追加した辺のコストの合計と、その辺による各都市間の最短距離(d[i][j])を保持、更新する 距離が小さい方から順に考えていく。 町i, j間の最短距離がcの時、 もし、d[i][j] == cならば、もう辺を追加する必要は…

ARC083 C: Sugar Water

C - Sugar Water 解き方 A, B, C, Dそれぞれの操作を何回するか、全探索 A, Bについては、100A <= F <= 30 * 100より、たかだか30回 C, Dについては、最大でF/2g溶ける(E=100の時)ので、たかだか1500回 合計で[tex:O(109)]なので、ダメでは?という気もす…

ARC082 F: Sandglass

F - Sandglass 解き方 ある時刻におけるAの砂の量は、max(E1+C, min(E2+C, a+C))の形で表せる(aは最初にAに入っている砂の量) 各r_iについて、E1, E2, Cを前計算しておき、クエリに対しては二分探索→最後だけ計算 r_{i-1}のときの関数が求まれば、そこから…

ABC073 D: joisino's travel

D - joisino's travel 解き方 すべての町の間の最短経路の距離を事前にWarshall Floyd等で前計算 町の回り方をR!通りすべて試す(R<=8なので間に合う) github.com

ABC073 C: Write and Erase

C - Write and Erase 解き方 unordered_setを使えば良い github.com

ABC073 B: Theater

B - Theater やるだけ github.com

ABC073 A: September 9

A - September 9 数字として扱ったが、文字列のほうが簡単だった。 github.com

ARC082 D: Derangement

D - Derangement 解き方 となるiの個数を数える ただし、上記のようなiが連続している場合、その2つを入れ替えれば良いので差し引く ハマったところ 特になし https://github.com/HiroakiMikami/procon-workspace/blob/master/src/atcoder/arc082/d.ccgithub…

ARC082 C: Together

C - Together 解き方 差が2以下であれば、同じ数字にできる 差が2以下となる数字の個数の最大値を求める ソートして、尺取り法すれば良い ハマったところ 特になし https://github.com/HiroakiMikami/procon-workspace/blob/master/src/atcoder/arc082/c.ccg…

AGC019 B: Reverse and Compare

agc019.contest.atcoder.jp 解き方 A[i] == A[j]を満たすA[i..j]を反転させる時、A[i+1..j-1]を反転させた時と同じになるので、それを引く ハマったところ 最初回文を除かないといけないと考え、実装はしたもののO(N^2)から落ちなかった 回文を除く方針は、…

AGC019 A: Ice Tea Store

agc019.contest.atcoder.jp 解き方 ただの貪欲 ハマったところ なんか貪欲法の実装に手間取ってしまった記憶がある https://github.com/HiroakiMikami/procon-workspace/blob/master/src/atcoder/agc019/a.ccgithub.com

ARC081 E: Don't Be a Subsequence

E - Don't Be a Subsequence 解き方 部分列でない最小の文字列の、先頭の文字を決める→2文字目以降の文字列について考える、を繰り返すDP DPする時には、後ろから決めていかないといけない どの文字を先頭にするか決めるために、どの文字がどこに現れるかに…

ARC081 D: Coloring Dominos

D - Coloring Dominoes 解き方 左から順々に見ていく。直前のタイルの貼り方と、次のタイルの貼り方は2*2の4パターンなので、それぞれ場合分けしながら計算する ハマったところ 上下に見ようとしたり、DFSしようとしたり、迷走していた 高さ2と小さいのだか…

ARC081 C: Make a Rectangle

C - Make a Rectangle 解き方 2個以上存在する数字を大きい方から2つ選んで長方形を作る ハマったところ 正方形のケース(同じ数字が2回登場する)を忘れていた github.com

ABC070 D: Transit Tree Path

D - Transit Tree Path 解き方 aからKへの距離とKからbへの距離の和を出力する Kから各頂点への最短距離は、木なので、DFSすればO(n)で求まる。 ハマったところ 0-indexと1-index混ぜてた 読み込み時に変えておくべきという話はありそう 最初全頂点から全頂…

ABC070 C: Multiple Clocks

C - Multiple Clocks 解き方 最小公倍数を求めるだけ。場合によってはオーバーフローに気をつけないといけないのかな。 github.com

ABC070 B: Two Switches

B - Two Switches 解き方 区間[A:B]と[C:D]の重複区間を求める。[max(A, C):min(B, D)]。 github.com

ABC070 A: Palindromic Number

A - Palindromic Number 解き方 先頭から確認するだけ github.com