CodeChefのコンテスト"February Lunchtime 2018"の問題。
問題: https://www.codechef.com/LTIME57/problems/COUPLES
問題名: "Couples sit next to each other" (Code: COUPLES)
N組のカップルがいて、2N人は2N個の椅子に座っている。椅子は円形に並んでおりi番目と(i+1)番目、2N番目と1番目の椅子は隣接しており、i番目の椅子には番目のカップルの人が座っている。
ここから、隣接する人同士を入れ替えることで、最終的に各カップルが隣接するようにしたい。この状態を作るのに必要な最小交換回数は何回か、を答える問題。
コンテスト中、うまく解法が降ってきて解けた。そのメモ。
続きを読む問題: C - 高橋くんと不思議な道
N個の頂点と２つのタイプを含むM個の辺が存在する。タイプAは1のコスト、タイプBは(今まで通過したタイプBの辺数)+1のコストがかかる時、頂点0から各頂点に到達するための最小コストはいくらかを答える問題。
コンテスト中にも解けなかった問題。久しぶりにやっても解けず、想定解法(+α)で通したメモ。
続きを読む問題: E - へんなコンパス / Manhattan Compass
平面上のN個の穴について(a, b)の穴のペアから始めて、マンハッタン距離が同じ穴のペアを辿ること(ペア(p, q)とペア(p, r)の距離が等しければ、一方からもう一方を辿ることができる)で辿れるペア数を求める問題。
問題: E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer
4頂点に色を持つN個のタイルを組み合わせ、全ての接するタイルの頂点の色を同じにしながら構成できる立方体は何通り存在するか、を計算する問題。
とりあえず自分の解法。ほぼ想定解法。
続きを読む12/21~12/23に行われたACM-ICPC アジア地区 ナコーンパトム大会の参加記です。
https://www.ict.mahidol.ac.th/acmicpc2017/index.html
チームIQ1(自分、ちゃっく、kuwa氏、コーチのshimomireさん)でタイのナコーンパトムに行きました。
