AtCoder ABC236D"Dance"をrubyで解く
久しぶりにログインしてみたら、なんか色変記事のいいねが増えてました！ ……すみません、こんな実力の奴がああもイキリ散らかしてほんとすみません。
問題
思考回路
まず制約を見ます。(重要)
Nが最大で8という事は参加者数は最大16人。多少は無理ができますが、16!通りを素でゴリ押しするのは無理です。
つまり「重複なく全探索」が問題のキモではないかと読みました。
次の疑問は、N=1のときは1通り、N=2のときは3通りだけどN=3のときは何通りなのよ？ です。
(1,2)(3,4)(5,6)
(1,2)(3,5)(4,6)
(1,2)(3,6)(4,5)
(1,3)(2,4)(5,6)
(1,3)(2,5)(4,6)
(1,3)(2,6)(4,5)
(1,4)(2,3)(5,6)
(1,4)(2,5)(3,6)
(1,4)(2,6)(3,5)
(1,5)(2,3)(4,6)
(1,5)(2,4)(3,6)
(1,5)(2,6)(3,4)
(1,6)(2,3)(4,5)
(1,6)(2,4)(3,5)
(1,6)(2,5)(3,4)
コピー用紙とボールペンの原始人スタイルで書き出した結果が以上の15通りです。
で、ですよ。この作業中に気づいた事がありました。
「1ペア目の一人目は必ず1だな？」
「んで残り五人は1ペア目の二人目としてループしてるな？」
「1ペア目に選ばれなかった四人のうち、一番小さいのが2ペア目の一人目だな？」
「残り三人が2ペア目の二人目としてループしてるな？」
「残った二人が最終ペアだな?」
そして何より
「このアルゴリズム、再帰で書けるな？」
日本語プログラミング
1.「残りの参加者」が1~2N、「現スコア」0点の状態を再帰関数に渡す。
2.「残りの参加者」が二人の場合はその二人のスコアと「現スコア」の排他的論理和が最終スコア。それをintegerで早期リターンする。
3.「残りの参加者」が四人以上場合、そのうち先頭の人はペア一人目に確定。「残りの参加者」から外す。
4.ペア二人目は「残りの参加者」全員を一人ずつループ。
5.ペアが二人とも確定したので、スコア表を見て「現スコア」との排他的論理和を取って「現スコア」を更新。
6.「残りの参加者」からペア二人目を外し、「残りの参加者」と「現スコア」を再帰関数に渡す。2に戻る。
7.4のループで誰を二人目に選んだかでそれぞれ最終スコアが帰ってくるが、最終スコア候補の中での最大値をintegerで返す。
2~7を関数に閉じ込め、それを6で再帰的に呼び出します。
(コンテスト中は気づいていませんでしたが)これの挙動はDFSと同じです。つまり私は過去に「勉強したくないでござる！ 絶対に勉強したくないでござる！」と言った再帰DFSを意図せずに実装してしまった事になります。
解答
NをPAIR_COUNTとして受け取っているのが23行目。
24~30行目でグチャグチャやってるのは、一人目を行、二人目を列にした場合にスコアが返ってくるようスコアボードの二次元配列をnilで埋めているだけです。なんでスコアボードの変数名がpair_scoresなんだよ。
32行目で全参加者の配列を作り、34行目でスコアボードや初期スコアの0と一緒に関数に渡しています。(日本語プログラミングの1)
5行目の早期リターンが日本語プログラミングの2。
日本語プログラミングの3が7行目。
9行目から13行目のmap.with_indexが日本語プログラミングの456。ループで一人ずつ選び、その一人を外した「残り参加者」と、スコアボードと、選んだペアのスコアとの排他的論理和を取った「現スコア」を再帰関数に渡しています。
mapなので「誰を二人目に選んだかのスコア」が配列になって返ってきます。その中での最大値を返しているのが14行目。日本語プログラミングの7。
六度目の茶落ちがないよう頑張ります！
Discussion