昔いろいろ考えたけど、書き忘れた問題
問題: E - MUL
ARC087 - E問題: Prefix-free Game
解いたので解法メモ
URL: E - Prefix-free Game
AGC023 - C問題: Painting Machines
横一列に並んだ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から各頂点に到達するための最小コストはいくらかを答える問題。
コンテスト中にも解けなかった問題。久しぶりにやっても解けず、想定解法(+α)で通したメモ。
続きを読む