日々drdrする人のメモ

今日もdrdr、明日もdrdr

SRM733 Div1 Medium: BuildingSpanningTreesDiv1

TopCoder SRM 733のMedium "BuildingSpanningTreesDiv1"

解法メモ

続きを読む

CodeChef February Lunchtime 2018 - 問題: COUPLES

CodeChefのコンテスト"February Lunchtime 2018"の問題。

問題: https://www.codechef.com/LTIME57/problems/COUPLES
問題名: "Couples sit next to each other"

N組のカップルがいて、2N人は2N個の椅子に座っている。椅子は円形に並んでおりi番目と(i+1)番目、2N番目と1番目の椅子は隣接しており、i番目の椅子には {A_i}番目のカップルの人が座っている。
ここから、隣接する人同士を入れ替えることで、最終的に各カップルが隣接するようにしたい。この状態を作るのに必要な最小交換回数は何回か、を答える問題。

コンテスト中、うまく解法が降ってきて解けた。そのメモ。

続きを読む

ARC052 - C問題: 高橋くんと不思議な道

問題: C - 高橋くんと不思議な道

N個の頂点と2つのタイプを含むM個の辺が存在する。タイプAは1のコスト、タイプBは(今まで通過したタイプBの辺数)+1のコストがかかる時、頂点0から各頂点に到達するための最小コストはいくらかを答える問題。

コンテスト中にも解けなかった問題。久しぶりにやっても解けず、想定解法(+α)で通したメモ。

続きを読む

ARC065 - E問題: へんなコンパス / Manhattan Compass

問題: E - へんなコンパス / Manhattan Compass

 {xy}平面上のN個の穴について(a, b)の穴のペアから始めて、マンハッタン距離が同じ穴のペアを辿ること(ペア(p, q)とペア(p, r)の距離が等しければ、一方からもう一方を辿ることができる)で辿れるペア数を求める問題。

続きを読む

ARC062 - E問題: AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer

問題: E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer

4頂点に色 {C_{i,j}}を持つN個のタイルを組み合わせ、全ての接するタイルの頂点の色を同じにしながら構成できる立方体は何通り存在するか、を計算する問題。

とりあえず自分の解法。ほぼ想定解法。

続きを読む

ARC057 - C問題: 2乗根

想定解法メモ。

問題は、入力として {a_1a_2 \ldots a_k}が与えられ、
 {\sqrt{N}}の上 {k}桁が {a_1a_2 \ldots a_k}となるような {N}を求める問題。

問題: C - 2乗根

続きを読む

ARC047 - C問題: N!÷K番目の単語

自分のための解法メモ (公式の解法スライド読んでピンとこなかったので)

問題: C - N!÷K番目の単語

続きを読む