AtCoder

AtCoder関連の情報。

プログラミング

入緑しました

ABC321で入緑しました ABC321で入緑したので、入緑記事を書いておきます。 AtCoderのコンテスト実績 AtCoderのコンテスト実績を貼っておきます。 AtCoder Problemsでの精進記録 大事そうなところだけ貼ってお...
プログラミング

ARC164_B – Switching Travel

ARC164_B - Switching Travel 問題 感想 1回目 解法分からず、解説を読んだ。 ある出発点からスタートして元に戻ってくるには、異なる色の頂点を使って移動し、最後の1回だけ同じ色の頂点を結ぶ頂点を使うことになる。 ま...
プログラミング

AGC052_A – Make it Zigzag

AGC052_A - Make it Zigzag 問題 感想 1回目 解法分からず、解説を読んだ。 $P_x$と$P_{x+1}$を1つずつ見ていき、条件に合うように操作をしたらN回以内になるかなー、と思ったらWAになった。 $P_x,P...
IT

ARC137_A – Coprime Pair

ARC137_A - Coprime Pair 問題 感想 提出 なし 1回目 解法分からず、解説を読んだ。 問題の制約条件下では、素数の間隔は1500以下らしい。 これを知っていると、愚直な方法で解ける。 $(y-x)$が大きい方から試し...
プログラミング

ABC254_E – Small d and k

ABC254_E - Small d and k 問題 提出 感想 1回目 解けた。 頂点の次数が3以下で、距離の探索も最大で3以下なので、通る頂点は最大で$1+3+9+27=40$個になる。 クエリの回数これを繰り返せば良いので、dfsす...
プログラミング

ABC128_D – equeue

ABC128_D - equeue 問題 提出 感想 1回目 考えるのに時間はかかったが解けた。 dfsやdpを考えていたが、うまくいきそうになく、全探索をするとうまくいった。 dfsの場合は全通り試すと$4^K$乗になる。$4^{100}...
プログラミング

ABC318感想戦

コンテスト A問題 感想 $k$を任意の正の整数として、i日目に満月が見られる条件は$i=M+k*P$になっていることである。 $(i-M)%P$を計算して、0であればカウントする。 $(i-M)$がマイナスの場合は対象外。 コンテスト中提...
プログラミング

ABC126_E – 1 or 2

ABC126_E - 1 or 2 問題 提出 感想 1回目 解けた。 $A_{X_i}+A_{Y_i}+Z_i$が偶数という条件だが、これは$X_i,Y_i$のどちらかがわかればもう一方もわかると言い換えできる。 $Z_i$が偶数の時、$...
プログラミング

ABC312_D – Count Bracket Sequences

ABC312_D - Count Bracket Sequences 問題 提出 2回目で解けた メモ化再帰で解けた。 まず、再帰で解くことを考える。 i番目までのcnt=左括弧の数-右括弧の数とすると、cnt>=0でなくてはならない。 c...
プログラミング

ABC282_D – Make Bipartite 2

ABC282_D - Make Bipartite 2 問題 提出 3回目くらいで解けた 以下、解法を書く。 $(全ての頂点の組み合わせの数)-(同じ色同士の組み合わせの数)-(存在する辺の数)$を使って解く。 グラフが連結の時を考える。 ...