競技プログラミング

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

AOJ2170: Marked Ancestor

Marked Ancestor | Aizu Online Judge 解き方 対応するMarked Nodeが同じ頂点が同じ集合に含まれるようなunion findを作る 一旦、最終的なunion findを作って、クエリを後ろから辿りながらunion findを更新する ハマったところ 同じノードに複数回マークつけ…

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

AOJ0525: おせんべい

おせんべい | Aizu Online Judge 蟻本初級の練習問題にあったので解いた。 解き方 どの行をひっくり返すかは、全部で2^R通りなので、これについてはすべて試すことができる。 ひっくり返す行を決めて、ひっくり返した後は、各列で裏と表のうち、多い方の数の…

AOJ0121: 7パズル

7 パズル | Aizu Online Judge 蟻本初級の練習問題にあったので解いた。 解き方 終了時点(綺麗に整列した状態)から幅優先探索を行い、各状態から終了状態までの最小回数を求める 状態の個数はたかだか8!個程度なので、この前計算は十分間に合う 各クエリに…

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

ARC080 E: Young Maids

arc080.contest.atcoder.jp 解き方 辞書順なので、先頭から埋める 最初の数列で、奇数番目が解答の先頭に、偶数番目が解答の2番目にくる 奇数番目の最小の数字が先頭に、それより後ろで最小の偶数番目が2番目にくる 3つの領域に分割されるので、それらについ…

ARC080 D: Grid Coloring

arc080.contest.atcoder.jp 解き方 左端あたりからジグザグに指定個数ずつ埋めていく ハマったところ WをNと書き間違えた github.com

ARC080 C: 4-adjacent

arc080.contest.atcoder.jp 解き方 すべての数字を4で割った余りに変えても同じ 2は全部連続させて良い(分けることでうまく行くパターンが増えることはない) 2の連続、1のとなりには0が来ないといけない(2...2, 0, 1, 0, 1, ...., 1, 0, 1など)ので、そ…

ARC079 F: Namori Grundy

arc079.contest.atcoder.jp 解き方 1つ閉路があり、残りはその閉路にぶらさがっているようなグラフ 閉路とそれ以外にまず分ける 閉路以外の部分は、根を0、その上を…としていくと一意に定まる 閉路については、適当に1頂点にxを割り当てて、うまくいくか計算…

ARC079 E: Decrease (Judge ver.)

arc079.contest.atcoder.jp 解き方 1回の操作で、数列の総和は-1される 操作回数は最低でも 回操作をすると、総和が0になるのでこれが操作回数の上限になる(多分) K回の操作後、条件を満たすかどうかは全体を+Kしたあと、K回どれかの要素を-N-1する操作と…

ARC079 D: Decrease (Contestant ver.)

arc079.contest.atcoder.jp 解き方 Nは50に固定しておき、とりあえずN-1+K/NをN個並べる K%Nとかを使って数字を調整すれば構成できる ハマったところ 素直に構成できたが、自信を持てず時間を無駄にしたみたいなところがある github.com

ARC079 C: Cat Snuke and a Voyage

arc079.contest.atcoder.jp 解き方 1から1回で行けるところ、Nに1回で行けるところを列挙し、重複があるかどうか調査 ハマったところ 順調に解けた気がする github.com

AGC018 B: Sports Festival

agc018.contest.atcoder.jp 解き方 全競技を実施すると仮定して、そこから参加人数が多いものを消していく貪欲 ハマったところ 実施競技0から増やしていく貪欲がWAになったあと諦めた 逆からの貪欲くらいは試してみるべきだった github.com

AGC018 A: Getting Difference

agc018.contest.atcoder.jp 解き方 すべての数の最大公約数を求めて、その倍数かどうかで判定 ハマったところ gcdの実装再確認に時間をかけた gcdを求めれば良いことに確信を持つまでに時間がかかった。 github.com

ARC078 D: Fennec VS. Snuke

arc078.contest.atcoder.jp 解き方 1から`N`へのパス上をまず塗り、その後残りを塗るのが最適解 1とNからの距離でそのマスが黒か白か決まる 1とNの2箇所から幅優先探索して、黒白それぞれの塗られる数を探索 ハマったところ Nヶ所から幅優先探索する方法を…

ARC078 C: Splitting Pile

arc078.contest.atcoder.jp 解き方 カードに書かれている数字の和を求めるのはO(n) 上から1枚取る場合、2枚取る場合、と順々にxとyを求めるのは、それぞれO(1)でできる 全部計算してminを求める ハマったところ xをi32で宣言していてオーバーフロー 定数項を…

AGC017 B: Moderate Differences

agc017.contest.atcoder.jp 解き方 一つ前のマスより小さくなるマスの数を固定して,その条件のもと達成できるか判定,これをN回繰り返す ハマった所 どれかの値を固定することで高速に判定し,それをn回繰り返す,って発想が出づらい