横一列に並んだN個のマスを、N-1台のマシンで塗っていく。i番目のマシンはi番目とi+1番目のマスを黒く塗る。
ある順列Pを与え、その番号の順番でマシンを動かしていき、N個のマスが初めて黒く濡れた時点のPのindex(1-indexed)がスコアとなる。
全ての順列についてこのスコアを求め、その総和を計算する問題。
解けなかった。解法メモ。
続きを読むARC096 - E問題: Everything on It
N種類のトッピングが乗せれるラーメンで、トッピングの組み合わせを異なる通りの組み合わせのラーメンのうち何杯か注文し、N種類のトッピングが、注文したラーメンらのうち2杯以上に乗っている組み合わせ数を計算する問題。
公式や他の提出コードを参考にした解法メモ。
続きを読むCodeChef February Lunchtime 2018: Couples sit next to each other
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番目の椅子には番目のカップルの人が座っている。
ここから、隣接する人同士を入れ替えることで、最終的に各カップルが隣接するようにしたい。この状態を作るのに必要な最小交換回数は何回か、を答える問題。
コンテスト中、うまく解法が降ってきて解けた。そのメモ。
続きを読むARC052 - C問題: 高橋くんと不思議な道
問題: C - 高橋くんと不思議な道
N個の頂点と２つのタイプを含むM個の辺が存在する。タイプAは1のコスト、タイプBは(今まで通過したタイプBの辺数)+1のコストがかかる時、頂点0から各頂点に到達するための最小コストはいくらかを答える問題。
コンテスト中にも解けなかった問題。久しぶりにやっても解けず、想定解法(+α)で通したメモ。
続きを読むARC065 - E問題: へんなコンパス / Manhattan Compass
問題: E - へんなコンパス / Manhattan Compass
平面上のN個の穴について(a, b)の穴のペアから始めて、マンハッタン距離が同じ穴のペアを辿ること(ペア(p, q)とペア(p, r)の距離が等しければ、一方からもう一方を辿ることができる)で辿れるペア数を求める問題。
ARC062 - E問題: AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer
問題: E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer
4頂点に色を持つN個のタイルを組み合わせ、全ての接するタイルの頂点の色を同じにしながら構成できる立方体は何通り存在するか、を計算する問題。
とりあえず自分の解法。ほぼ想定解法。
続きを読む