HACK TO THE FUTURE 2018本戦参加記

概要

まぐれで予選突破してしまい、こんな機会滅多にないと思うので、参加してきました。

future-contest-2018-final.contest.atcoder.jp

普段、会場の情報とかつぶやいてくれる人とかありがたいと思っていたので、今回はできるだけつぶやくようにしてみました。(鬱陶しくツイートしててごめんなさい)

起床～移動

• 前日yukicoderちょっとだけ出るつもりがガッツリでてしまい、寝たのがAM2時過ぎ
• ちょっと緊張してたかAM8時の目覚ましで起床AC
• たまたま入場がagwさんと一緒になった

準備

• 会場がどんな雰囲気でやるのかわからなかったけど、大きめテーブルに2人ぐらいずつ座れる感じでゆったり
• agwさんとmachyさんの後ろ側の席に陣取る

agwさんとmachyさんの後ろに陣取った（＾ω＾） pic.twitter.com/pylDOPZKu7

— phyllo (@phyllo) 2018年3月3日

コンテスト開始

• 問題読む
  • 50x50マスにいくつかの操作を行える
  • 操作は、植物を植える、収穫する、更地にする、道路を設置する、など7種類あり、それぞれ見合ったお金または労働力が必要となる
  • 植物は植えると、すでに植えられたマスには植物数が+1し、さらに勝手に隣接の更地マスに広がっていくが、マス内の植物数が100になると岩になってしまう
  • 植物の収穫数最大となるような1000ターンの操作列を出力せよ
• 問題かなり複雑じゃないですかね・・・8時間コンテスト・・・？
• 実際のビジュアライザとかの動き見ながら40分ぐらいかけて理解(遅い)

最初の考察フェーズ

• 雰囲気的に、普通の畑みたいに区画に分けたいお気持ちになる
• ということで大雑把には「サイズXの区画を増やす、区画内の収穫をする、他の操作、についてビームサーチする」を目指したい
• 区画は、正方形とかだと移動コストが微妙にかかってしまうので、できれば1*Nか2*Nぐらいの長方形がよさそう？
• 区画内を一気に収穫する想定だけど、収穫後にもう一度植える必要があるのは1手無駄してると思う
• 道路を引くかワープ設置するかとか、道の設置のうまい方法とか考えつつ、お昼

お弁当3種類あった。いただきます。 #HTTF pic.twitter.com/O3EVcit4AS

— phyllo (@phyllo) 2018年3月3日

• お弁当用意していただいていた

「貧乏フェーズ」

• 問題の制約をよく見ると、お金の初期値が100しかない
• これは結構ギリギリな金額で、区画を作りたいと考えていたけど、結構厳しい
• 「貧乏フェーズ」と名付けておく
• 逆に、貧乏を脱出したら打てる手が増えるので、別戦略が必要そう
• 「小金持ちフェーズ」と名付けておく
• 状態の評価値はここら辺分けておきたい

折り返し地点

• とりあえず、ビームサーチしたいと思ったけど、いざ実装しようと思ったら実装がだいぶ重い
• この時点で実装の大変さが原因で途中まで書いてたコード捨てるの結構厳しい・・・
• 0点で終わるよりはと思って、厳密さよりも動くコードを優先することに

貧乏フェーズの実装

• できるだけワープ近くで、かつ、お金がかからないように1マス区画を作るのが最初にやることかなと思い、考える

..R..
.RxR.
RxWxR
.RxR.
..R..

R: 道か岩
x: 栽培区画
W: ワープゲート

• ↑みたいな感じで、ワープ横に栽培区画を作ってそこで99まで栽培を行えば、100ターンぐらいで400植物ぐらいが手に入る
  • もちろん途中収穫などうまくできるとよさそうだけど、ここでは99まで栽培を考えてた
• 市松模様的にもうちょっと広げて上げると多少スコアも上がるので、それを書く
• 収穫とかと区画の作成とかを同時にタイミングを気にしながら手順を作る実装が地味に難しい
• 貧乏フェーズの手法のまま最後まで行った場合のコード、ちょっと変形して別な場所にワープゲートを設置してそちらでも同じことやるコードを書く
  • 最終提出のコードはこれ

小金持ちフェーズの実装

• 貧乏フェーズでは1マスごとにやってしまっているので、1回あたりの収穫量が少ない
• 単純に拡張するとマスのサイズを広げてあげたい
• この時点で、残り時間が3時間もない
• standingみるとかなりやばい点数が出ている
• 貧乏フェーズのコードは手元の見積もりで170万ぐらいだけど、1ページ目にも入れていない・・・
• 「小金持ちフェーズ」だけでなく「大金持ちフェーズ」ぐらいが必要そう・・・

standing凍結(残り1時間)

• とりあえず0点は避けたいので、↑の貧乏フェーズの手法の実装を投げて177万点
• あとはどこまで実装しきれるか・・・
• うおおおおおお
• とにかく動けばいいやと書きなぐっていたら実装がバグりまくる
• デバッグが「出力→ビジュアライザ」しかなくて効率がだいぶ悪い
• 結局実装しきれず終了

むずすぎ！＼(^o^)／ #HTTF

— phyllo (@phyllo) 2018年3月3日

• さすがに8時間ぶっ続けでやった後の疲労感がすごいのと、不完全燃焼感がすごい

会社紹介

• Futureの会社紹介と脆弱性検知ツール「Vuls」の開発者の方の技術紹介とか

https://thinkit.co.jp/article/10092

• ミャンマー？から帰国したばっかりらしい
• 他の社員の方で技術書出されている方とかもいらっしゃるよう

懇親会

• やっぱり決勝は予選と違って「最上位(1～10位)の順位決定」をする必要があるので、問題が難しいとのこと
  • TCO finalなイメージ、らしい
  • それでもオープンも含めかなり高いスコアをたたき出している人が結構いて強い
• あとは、参加者のプロな方やFutureの方などいろんな方とお話しできてよかった
  • 普段はstanding上位やツイッター上でしか見れない方ばかりで恐れ多い(((((((;´д｀)))))))

結果発表！！！ #HTTF pic.twitter.com/BE6I2CF2cW

— phyllo (@phyllo) 2018年3月3日

• 順位発表
• 3位以上はビジュアライザ見ながら発表
• やっぱり上位は盤面全部を使い切ってる感じですごい
  • それにアプローチが上位でも多様で良い問題感ある
• 最後、なんと副賞や参加賞も追加で用意していただいていた(！)
• 集合写真とって解散

反省

お疲れ様でしたー！結果はアレでしたが楽しかった ( ^ω^ ) #HTTF

— phyllo (@phyllo) 2018年3月3日

• 出来は散々だったけど、楽しかった！
• やっぱりこういうイベントに参加できるとだいぶ競プロモチベは上がるなぁと思った
  • イベント開催ありがとうございました
  • アルゴリズムもマラソンもへぼいので、もっといろんな問題解いて強くなりたい
• 実装難易度や実装の仕方、書き方とか気を付けるようにしたい

AGC021 B. Holes

問題

平面上にN個穴があいている。
今、原点を中心とした半径Rの円に無作為にすぬけさんを置く。すぬけさんはユークリッド距離で最も近い穴に落ちる。
すべての穴について、すぬけさんが落ちる確率を求めよ。

制約

• 2 <= N <= 100
• 穴の座標はすべて整数、すべて異なる、|x_i|,|y_i|<=10^6
• R = 10^10^10^10

解法

穴がある位置は、円の中心付近で、円全体からして十分に小さいので細かい部分は無視できる。
どちらかというと、穴の集まる原点付近よりもはなれたの部分に置かれる割合が大きく、そのようなケースだけを考えればよい。

O(NlogN)解

十分離れたところにすぬけさんを置いた場合、すぬけさんが落ちる穴は、穴の集まりの中でも外側にある穴のどれかになる。
穴の集まりの中で、内側の方の穴に落ちるには「凸包内、かつ、他の穴より近い位置」じゃないといけないため、落ちる確率は円の大きさ的に無視できるほど小さくなる。
したがって、穴の凸包を求めて、凸包をなす穴についてだけ考える。

凸包のある穴pと両方に隣り合う穴q,rについて考える。
穴pに落ちるには、両隣の穴q,rとの二等分線を円の外側に向かって伸ばした線より穴p側に設置されていれば穴pに落ちる。(正確には、穴の近くでは他の穴の方が近くてそっちに落ちる可能性があるが、すぬけさんがそこに設置される確率はかなり小さいので無視してよい。(たとえば下の図の二等分線始まり付近に設置されたら内側の穴に落ちる))
凸包の点すべてについて、どの角度で両隣の穴との二等分線が外側に向かって伸びているかがわかれば、角度の割合から落ちる確率が求められる。

凸包を求めるのにO(NlogN)程度なので、答えもO(NlogN)。

O(N^2 logN)解

凸包を使わなくてもよい。

ある穴pに注目する。
穴pから他のすべての穴への角度を求め、ソートしておく。穴pを中心として穴qの角度はatan2(q_y - p_y,q_x - p_x)で求められる。
ソートした角度において、両隣との角度の差がθで、その最大となる角度がmaxθであるとする。(ソート後の最初と最後の角度の差を求めるときは処理が少し変わるので注意)

もし、maxθがPI(180度)よりも小さい場合は、他の穴に囲まれているため、凸包の内部の点で、答えは「0.0」になる。
もし、maxθがPI(180度)よりも大きい場合は、穴pに落ちる角度は赤い二等分線がなす角度なので、答えはmaxθから両側90度分を引いた「maxθ-PI」になる。

各点について、他の点との角度のソートが必要なのでO(N*NlogN)=O(N^2 logN)。

O(NK)解

求められる精度が少し荒いようなため、穴をすべて内包する十分大きな円の周上を等間隔でK点用意し、各点から落ちる穴を見つける、という方法でも通せるらしい。
ただ、Kや円の大きさなどのパラメータでの答えの精度の見積もりが難しい。

反省

普通に忘れてた、、、

負値の切り捨て

億劫がって、小数で保存してた変数から整数の変換時に微小な変化無視するために「+0.5とかしてからintキャスト」とかしてしまってハマった。
負値の場合は、

• intキャストは、0に近づく
• floor()は、小さい整数に近づく

なので、負値で+0.5してintキャストすると1ずれてしまう。
もう使わない。

偏角

theta = atan2(y,x)で-PI <= theta <= PI。

天下一プログラマーコンテスト2016予選B C. 天下一プログラマーコンテスト1999

問題

参加者はN人の総当たり戦の記録をアンドウくんとハシモトくんの2人が行う。
記録はN*Nの表に記録する。(1選あたり2つの記録をする)
アンドウくんは間違えずに記録するが、ハシモトくんは確率Pで正しい記録、確率(1-P)で間違った記録をしてしまう。
各記録は独立事象とし、勝ち数が多い順(同勝ち数の場合は表の並び順)から順位をつける。
アンドウくんの記録が与えられるので、アンドウくんとハシモトくんのそれぞれの記録からの順位付けが一致する確率を求めよ。

制約

• 2 <= N <= 30
• Pは「p/q」形式で与えられ、0 <= p <= q, 1 <= q <= 10

解法

順位を決める要素は勝ち数なので、まず「勝ち数」を考える。
ハシモトくんの記録での各参加者の勝ち数は確率的に変化するが、「ハシモトくんの記録でt勝になる確率」は「アンドウくんの方での記録(s勝)」「確率P」から考えることができる。

dp[s][t] := アンドウくんの記録でs勝だった人が、ハシモトくんの記録でt勝になる確率

これはハシモトくんが正しくつけた記録の数uで場合分けが必要で、

• 試合数(N-1)中、「s勝」「(N-1-s)敗」
• s勝のうち、u個正しくつけた
  • u個が勝ち->勝ち、(s-u)個が勝ち->負け、(t-u)個が負け->勝ち、(N-1-(t-u))個が負け->負け
• m個の記録のうち、n個正しくつけた場合の確率は、「mCn * P^n * (1-P)^(m-n)」で求められるのでこれをdp2[m][n]とする

と、

dp[s][t] =  Σ_{u=0}^{s} dp2[s][u] * dp2[N-1-s][(N-1-s)-(t-u)]

となる。

次に、ハシモトくん記録での順位変動を考える。
ある参加者について、記録間違いで勝ち数が変動しても順位が変動しない場合、というのはイメージできる。
順位が変動しない勝ち数の範囲は、他の参加者の勝ち数状況に依存しており、すべての各参加者の勝ち数を全探索することは計算量的に難しい。
そこで、動的計画法的に端から決めていく方法を考える。

順位が低い方から考える。
今、p位の人Xを考えると、p位の人Xの勝ち数がm、(p+1)位の人Yの勝ち数がnとすると、

• 表でXよりYが下の場合、m>=n
• それ以外の場合、m>n

となっていれば順位が変動しない。
この条件を踏まえて、「p位の人が勝ち数q以下で、順位変動しない確率f(p,q)」を考える。最終的な答えはf(1,N-1)。

p==Nの場合、最下位の人を考える場合で、「k=0勝～q勝でのdp[最下位の人の勝ち数][k]の和」になる。
p

• 同じ勝ち点が許されるならr=k
• 同じ勝ち点が許されないならr=k-1

として求める。

反省

実際の考えの流れは「勝ち数が重要」→「一致する確率は勝ち数に基づくdpで求められそう」→「dpの計算で必要となるハシモトくん記録で勝ち数tとなる確率、を求める方法を考える」という流れかも。

「確率の式を正しく出す」「勝ち数のdpの適用を思いつける」「場合分けをミスらない」「誤差死がでないか判断できる」など必要。

問題が解けない原因を考えたい

背景

競技プログラミングの能力を鍛えたい。
ただ、何ができなくて解けなかったのか？や、問題の難しい部分はどこなのか？など簡単な抽象的・体系的でとらえたいお気持ち。
なんとなく思ったことがあるので、それを書き出して整理してみる。

「問題を解く」とは？

「問題を解くこと」＝「アルゴリズムを考えること」＋「アルゴリズムを実装すること」と考えてみる。

「アルゴリズムを考えること」

「アルゴリズムを考えること」＝「"問題"と"アルゴリズム"を辺でつなぐこと」

"問題"が与えられたとき、"問題"を"分解または言い換え"て、アルゴリズムの"使い方や制約"を踏まえて"アルゴリズム"を適用する。
ただし、"問題"以外のノードは与えられないため、自分で利用可能なノードを増やす必要がある。

また、SRM形式は辺を1本つなげればよいが、Marathon形式は重み付きグラフになってその最大化を行う。

問題が解けない＝辺をつなぐのを失敗すること

"問題"から"アルゴリズム"までの辺を貼ることに失敗すると問題を解くことができない。

「分解・言い換え」のノードが足りない

"問題"を「グラフにして考えてみたり」、「複数の問題に分解したり」することに失敗。

ここの部分のノードの作り方が難しい問題は、「難しい」問題の印象。

「使い方・制約」のノードが足りない

アルゴリズム自体は知っていても、その"使い方や制約"をきちんと理解できておらず、適用できない。

例えば、動的計画法というアルゴリズムは知っていても、その使い方で「状態設計」「遷移」「高速化」などがちゃんと考えられないと、ノードが作れず、辺を貼るのに失敗する。

「アルゴリズム」のノードが足りない

そもそもアルゴリズムを知らないとお話にならない。

辺が張れていない、間違って張ってしまった

ノードは用意できてもノードとノードの関連性をちゃんと理解できていないと張れると気付かなかったりして失敗。
また、張れると思って張ったら実は嘘解法で張れない辺を張ってしまって失敗。

勉強すべきこと

問題が解けない時、「ノードが足りていない」のか、「辺が張れなかった・間違って張った」のか考えたい。

ある程度、頻出パターン(頻出ノード、頻出エッジ)があるようで、効率的に勉強するには頻出パターンから攻めたほうがよく、「"使い方・制約"と"アルゴリズム"」の部分は体系的にまとめられている。
他には、グラフ系・文字列処理系・幾何系など特定分野に絞って勉強するのもよいのかも。

”分解・言い換え”ノードを増やす

あんまり体系的にまとまっていない気がするし、問題に合わせて考える考察力・発想力が問われる気がする。

"問題"側から"分解・言い換え"側を考える場合は、いろんな問題を解いていろんな言い換えや分解方法を憶えておくか、それらの発想の基となる既存の理論・学問を勉強したりとかが必要なのかも。。。

"使い方・制約"側から"分解・言い換え"側を考えることもできるかもしれなくて、ある程度関係ありそうなノードを考えて辺が張れるか考えてみたり。
また、小さいパターンで実験してみて問題に含まれるパターンを見つけたりというテクニックとかも有効かも。

典型とかもあって、「絶対値を見たら45度回転」とか「Nが小さければbitで2^N全探索できないか」とか、こう来たらこう考える、みたいなのもあるっぽい。

"使い方・制約"ノード、"アルゴリズム"ノードを増やす

アルゴリズムの教科書とか。
"アルゴリズム"の方だけ覚えておけばという感じになると、"使い方・制約"ノードが作れない場合もあるので、できるだけいろんなパターンを覚えておきたい。
使い方・制約を1種類だけしか覚えなかったり、公開されているライブラリからだけで勉強したりと、問題を考えたときに"使い方・制約"ノードが足りず、辺を貼るのに失敗しそうなので、気をつけたい。

その他

• 典型
  • 頻出パターン(頻出ノード、頻出エッジ)
• 枝狩り
  • 無駄なノードやエッジを作らない
• 嘘解法
  • 本当は張れないエッジを張る
• 「アルゴリズムを実装すること」
  • プログラミング言語の理解、ライブラリの準備、見やすい/間違えにくい書き方、・・・

Weathernews Programming Competition

概要

圧縮やRangeCoderの勉強のつもりで参加。

最終順位は26927.87点で20位。
といっても、一つ前との差分値をRangeCoderで圧縮しただけのコード。

問題

5分おき4観測分の衛星データが波長(16チャネル)ごとに64枚ある。このデータすべてを可能なかぎり圧縮・回答するプログラムを作成せよ。
スコアは、bz2の-9オプションでのサイズbase_comp_sizeに対して、「max(0.0, (1.0 - 圧縮サイズ/base_comp_size) * 10^6)」で計算される。

最終的に提出したアプローチ

• 各画像ごとに、2byte単位で読み込み、直前の2byteとの差分を作成し、それをRangeCoderで圧縮

振り返り、というか勉強

ロスレスな(動)画像圧縮、ファイル圧縮あたりが関係しそうということで、そこらへんの勉強のために参加。
いくつかメモ。

画像形式

画像形式でパッとでてきたのがPNG形式で、wikipedia見てみると結構いろいろ載っていて勉強になった。

Portable Network Graphics - Wikipedia

やっていることは「フィルタ処理→圧縮」。
フィルタ処理では「左との差」「上との差」「左と上の平均値との差」「左と上と左上の値を使ったPaethアルゴリズムでの予測値との差」、圧縮はLZ77とハフマン符号の組み合わせ。

この記事を読んで「どっかの値を使う(位置を保存)」とか「ある位置との差分を使う(差分を保存)」を考えてた。
けど、ちょっと複雑な「いろんな情報からそのピクセル値の予測をしてその差分を保存」のようなアイデアは保存する情報が増えて圧縮あんまりできなそうと思ってしまっていたので、全然考えてなかった。

Lossless JPEG - Wikipedia

Lossless JPEGなど損失なしの画像フォーマットがいくつもあるようだったので、それをちゃんと調べられていなかったのは調査不足だった。

1byte単位か2byte単位か

最初、hexdumpコマンドとかで眺めてて、偶数byteと奇数byteで分けて考えてみてもよいかなと思い、それを考えた。
片方はほとんど種類数がないので結構つぶせそうで、もう片方のbyte列をどう圧縮するか？が重要かと考えていた。

しかし、「上位byte列＋下位byte列」で扱うと、それぞれ別に圧縮しても、まとめて圧縮しても、あまり圧縮効果が変わらず、正の点数が取れてなかった。
他にも、差分を取って圧縮するときに「正か負か」と「差分値」を保存するよう別々に分けようとすると同様に圧縮効果があまり得られず。
結局、twitterでも見かけていた「2byte単位」でまとめて扱って～というのが必要だった。

RangeCoder

エントロピー符号化で、Huffman Codingは情報理論とかでも知っていたけど、さらに圧縮率の高い算術符号化(≒RangeCoder)があるとのことで、それを実装するのを目的にすることにした。

Algorithms with Python / レンジコーダ (range coder)

RangeCoderの実装や内容は上記のページを参考に、写経。
理解が怪しくて、1byte単位のコードはそのままでいいけど、2byteやそれ以上の単位を扱う場合の処理がうまく書き直すのに苦労してた。というか、提出コード、いろいろ変えたりして定数がおかしいまま提出してた、、、バグってるはずなのに普通に動いているよう・・・

予測符号化・変換符号化

http://www.pcsj-imps.org/archive/2013tutorial.pdf

終了後に調べた限りだけど、上記資料がまとまってた。
「予測符号化」というっぽいが、「次の値を予測し、予測値との差分値を符号化」をどうやるかがアイデアとして重要だったよう。

そもそも「隣接画素が似ている(画素の相関が高い)場合に、隣の画素を予測値として注目画素との差を取ることで、分散(値の種類数)を減らせて(冗長性を減らせて)、効率よく圧縮できる」ので、この考えだと「前の画素の値を予測値にする」の発展として、いろんな情報や予測手法(線形・非線形な手法、用いる予測器を切り替える「適応予測」など)を考える方向へ行けてたよう。

また、データを互いに相関のないデータへ変換する「変換符号化」も。
ブロックに分ける、離散コサイン変換、・・・。

Hokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017参加記

概要

AtCoderで開催されたマラソンマッチに参加してみた。
phyllo-algo.hatenablog.com
1stの方は比較的時間取れて取り組めたけど、2ndの方は時間がほとんど確保できず、だいたい2.5日分ぐらいしかできなかったと思われる。。

最終順位は6,961,040点で73位。

WAが2つ出てて、Timelimitを10秒で計算してるという大ポカ。

問題

重みなし無向グラフGが与えられる。そのグラフの頂点をG_embの連結な部分頂点集合に対応させる。
基礎点として5000点が与えられる。
G_embの方で部分頂点集合同士で隣接していた場合、+100点となる。
G_embの方で、ある部分頂点集合s(v)の頂点数が|s(v)|である場合、-Σ_v (|s(v)|-1)となる。
Gのすべての辺がG_emb側で隣接状態になっていた場合、ボーナスとして+100000点となる。
連結でない頂点集合だったり、不正な場合は0点となる。
最終得点が最大となるよう対応付けを求めよ。

最終的に提出したアプローチ

• 初期配置は、Gの頂点の近傍ができるだけ近くなるようにランダム配置し、それをできるだけランダムに伸ばせるだけ伸ばしたもの
• G_embの頂点を1つランダムに選び、その8近傍どれかにコピーする焼きなまし

時系列での振り返り

今回は考察重視で行きたいと思ってたけど、何が重要なポイントかは手を動かして見つけないとやっぱりダメだった。

初日～8日目(1日分ぐらい)

• HHMM1とだいたい似ていて、焼きなましが有効そうな形をしていたので、HHMM1の反省をしつつ焼きなましをちゃんと書こうと考えた
• 焼きなましについて勉強&&HHMM1の復習
• おそらく、全部焼きなましに任せるとアレなので、HHMM1と同じように「形を固定化して割り当て問題」か、「近傍のうまい定義」をすればひとまずよさそうか、とか考えていた
• 忙しかったり、体調不良であまり手を動かせず

10日目～12日目(1.5日分ぐらい)

• ひとまず、HHMM1復習のコードを流用してHHMM2用に書き直して様子見
• 実装が適当すぎて、スコアが差分計算できていないので、そこがボトルネックで回数稼げてないコードを作成
  • ビジュアライザーは、テキスト出力の簡素なモノしか用意してなかった
• で、どうも、回数稼ぐよりも、初期配置が重要そうな感じだったので、初期配置を中心に考えることにしたが、前半「形の固定化して割り当て問題」を考えていた時のアイデアとか完全に忘れてて、0ベースで考え直し

• 斜めだと、線をまたぐことができるので、平面グラフ的でなくても連結にすることができそうなので、斜めが肝っぽい
• 前半の時の紙を見るに、形状のアイデアとしては、斜め直線型やダイヤモンド型をうまく配置させられれば多くの頂点に絡みそうと考えたらしい
• 直線型よりもうにゃうにゃ絡み合う方が期待できそうな気もするので、ランダムに線を伸ばす感じのコードを作成(最終提出のやつ)
• で、ここで(なぜか)ボーナス点を取りに行っていないことが気になって、上位とはそこが差になっていると考えたため、できるだけちゃんと辺をつなぎに行くような方法を考える方に走った
• グラフが大きくなってもG_emb側で全連結になるよう辺をつなぎに行けるうまい方法が思いつけず、結局時間を無駄にしてしまって終了

13日目

• あきらめて、書いてたコードを提出
• 14日目は時間取れないのがわかっていたのでここで終了

SystemTest後

• TLEが10秒のままという指摘をもらってマジか状態(今回は30秒)
• スコア差分計算してないのは、結構どんな場合でも実装優先度は高そうなので早めに実装したほうがいい、という話をした
• WAが2つ出てるけど、実装が大味すぎてるので、ミスってただろう、という感じ(おそらくスコア計算の部分で0点なのに0点じゃないと返してる気がする)
• 「完全グラフ埋め込み」というのがtwitter流れてるのをみて天才か、と思った
  • 時間取れても至れたか怪しいので、ARC点数でいうとアイデア思いつくのは600点ぐらい、具体的な形状を見つけるのは800点ぐらいだと思う

Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017参加記

概要

AtCoderで開催されたマラソンマッチに参加してみた。終了30分前なので、時系列で振り返ってみる。
システムテスト前のスコア・順位は156,999点で66位/298人。おそらくシステムテスト後は順位下がる・・・

最終順位は720,841点で62位でした。

今回は知り合いと競争してて、知り合い内では3人中3位という感じで効率の悪さと実力不足が明らかになったなぁという感じ。
とはいえ、マラソンマッチはちゃんと参加できたことがなかったのに対し、今回は比較的時間使えていたので、完敗。

問題

重み付き無向グラフGが与えられる。そのグラフの頂点を別のグラフG_embの頂点にマッピングする。
もしG_embにマッピング後、G_embでの頂点で隣接辺だった場合、Gでの辺の重みが適用される。
G_embはKing's Graphというグリッドの斜め方向頂点にも辺をつないだグラフが与えられる。
マッピング後のG_embでの重みの合計が最大になるような頂点のマッピングを求めよ。

最終的に提出したアプローチ

• まずは山登り
• その後、グラフが密な場合はちょくだいさんサーチっぽいの、疎な場合は焼きなましのハイブリッド
• 頂点のマッピングは、G_embの中心から渦巻き状に広げていく形で決め打ちし、何番目にどの頂点を割り当てるかを考えた
• ちょくだいさんサーチっぽいのは、重複排除がうまくできなかったので、各番目で上位数件で切り捨てる感じで多様性を確保する感じ
• 焼きなましの方は、2-optっぽく、適当に2点選んで交換するので近傍探索。悪化した場合での採択率を山登り時点でのスコアとかで微妙に変えてる
• 評価値は生のスコア

時系列での振り返り

初日

• 問題理解自体は簡単そうな雰囲気だけど、どこらへんが難しいポイントかわからないので、数日は適当に実装しながら考えた
• 初日は「ビームサーチ」か「n手先読み」を考えてた
• 実装は適当に1点を決めてそこから8近傍に頂点を増やしていく感じで、先読みを1ターンだけするものを書いた

2日目

• 状態数が多すぎて試せる分量が少なすぎるので、8近傍に頂点を広げていくビームサーチを実装しようと書いてみた
• この時点では適当な調整をして148kぐらいだったけど、サイズが大きい場合に探索量が多くTLEしてしまったりスコアに大きな差がでてしまう問題があった
• というか、ビームサーチの時間のコントロールが難しいというのが身をもってわかった

3日目

• ビームサーチではなく、他の方法もありそうか考えてた
  • 決定的な手法とか、マッチングとか
  • 焼きなましとか試してみたけど、うまくいかず、ちょくだいさんサーチっぽい感じで何回も最初から最後までを繰り返す感じの探索でやってみたら悪くなさそうだったので、この方向で書きはじめ
• ここで、ビジュアライザーを作ってないことが気になったので、C#で最終状態を出力する雑なものを作成

4日目～5日目

• ビジュアライザー見ると、形がひどいときがあることに気づいた(上みたいなの)
• ある程度中央付近に固まっていた方が都合がよさそうだろうと思って、距離が離れるほど評価値が下がるように書いた
• けど、うまくいかなくて、ここで、「どこに何を」割りあてるかだと状態数が多くなりすぎるので、形を決め打ちして「何を」割りあてるかだけにすればよさそうと気づいた
• 形はいろいろ考えられそうな気がするけど、とりあえず中心からグルグル渦巻き状に増やすようなものを考えることにした

• 形の最適解の考察としては探索結果を見る感じだと平行四辺形っぽい形が多いので、辺の数的にもそういう形だろうと考えてた
• けど、最後そこまで調整たどりつけなかった

6日目～7日目

• メモリの制約からpriority_queueで保持する状態数に限りがありそうなので、適当に状態を削って探索
• ただ、サイズが大きい場合は、十分な探索ができてなくて、イマイチスコアがでない
• 他のアルゴリズムに浮気しつつ手を動かしてたけど、ダメだった

8日目～11日目

• ここらは、ちょっと細かい考察と実験をしながら、提出の方はパラメータとかちょこちょこ変更して提出する感じで進めてた
• 多様性確保のための状態の間引き方でうまい方法が思いつかず、ネットで情報調べたり勉強したり、いろいろ試してた
  • いろいろ取り入れようとすると探索量が減ってスコアが下がることを繰り返しててて、つらぽよ
  • あと、n手先読みとかペアを作ってからそれをくっつけてく方法とか別アプローチを試したりしてたけど、どれもイマイチで、つらぽよ
• この時点での提出の最高点は154kぐらい

12日目

• いろいろ出力して観察していたところ、どうも焼きなましっぽい動きをしてそうに見えたので、焼きなましでいけないか検討始めた
• すると、調整が雑でもスコアが結構伸びた(！)
• しかし、スコアが大きい場合、ちょくだいさんサーチっぽい方がスコアがよかったので、焼きなましとハイブリッドで実装
• この時点での提出最高点は156kぐらい

13日目～最終日

• 高速化を試していないことに気付いたので、時間計測とかintをshortにとかを置き換え
  • あと、cinをscanfにしたりしたらなぜかスコア下がったりして最終提出は変えなかった、、、
• 500点ぐらい増えて最高スコアの156,999
  • ただ、何回か提出してみると、上振れスコアのようで、再提出すると数百点平気で下がってしまう運任せコード

• 受理率が悪すぎて効率の悪い探索ばかりしていそうだったので、近傍の定義を効率化しようとして、ランダムに任意地点の2点をswapするのではなく、隣同士の2点を交換し続ける感じで書いてみたけどスコア悪化

• あとは冷却スケジュールと評価関数が何もできていないので、そこを最後に詰めようと実験
• 冷却スケジュールの方は、診断人さんまとめの焼きなましページを参考に、ちゃんと調整してローカルだと+600点ぐらいになったので、喜々として提出したら下がって絶望
• 評価関数はいい形悪い形とかで加点減点を追加したらスコアが下がってしまって絶望
  • 頂点の辺の合計とか、何番目に大きい辺を使ってるかとか
• 最終日で調整する時間がないのに、ローカルとオンラインのスコアの相関がなくなってて、絶望しながらオンラインの提出調整するしかなかった
• 絶望
• 絶望
• 結局点数上がらないので、上の提出最高得点のコードを最終提出して、絶望のうちに終了

最終提出後～寝るまで

• 振り返ってみてみると、焼きなましの受理率がものすごく悪いし、無駄なスワップとか繰り返しまくっているのでだいぶ改善の余地がある
• 探索量とかは結構稼げてるから「焼きなまし＋評価関数工夫＋ヒューリスティックルール」が正解だったかなぁとか思う

• あと、問題の切り分けとして、グラフの密度が「密」「疎」「スコアが大きい」あたりで分けて考えたけど、「疎」と「スコアが大きい」時が重要なのに全然詰められていなかった・・・

• ビジュアライザーは、最終結果を見るものしか作れてなかったけど、「やりながら見る」や「やってる途中経過(探索しているもの)を確認できる」ようなものを用意しないと厳しいなと思った

• 他にも試したけどここに書いていないものは、みんなの解答出てから反省時に振り返りたい

ARC085 D. ABS

問題

N枚の山札が与えられる。上からi番目のカードの数字はa_i。
XさんとYさんが、この山札を使ってゲームをする。最初にXさんはZが書かれたカード、YさんはWが書かれたカードを持っている。
2人は交互に「山札の上から1枚以上のカードを取り除く。最後にひいたカード以外は捨てる」という行動を繰り返す。
山札がなくなるとゲーム終了で、最後のスコアは両者のカードの数値の差の絶対値となる。

Xさんは最終スコアが最大化するように、Yさんは最終スコアが最小化するように行動する場合、最終スコアはどうなるか？

制約

• 入力はすべて整数
• 1 <= N <= 2000
• 1 <= Z,W,a_i <= 10^9

解法1

ゲームの先読み。

Yさんがi番目までカードを引いたとする。
Xさんはi+1番目から何枚かのカードを引くことになるが、このとき、最終スコアがどのようになるかがそれぞれの枚数の時でわかっていれば、それで最適な枚数を引けばよい。(Xさんは最大化したいので、最終スコアが最大になる枚数を引くことになる)

int dp[pos][turn] := turnさんの番で、相手がposまでカードを引いてる場合の最終スコア

として、メモ化再帰すればO(N^2)で求められる。

// ZとWはカードの数値を入れた配列vの最初2つに入れておく
int dp[2005][2];

int dfs(int pos, int turn){
  if(dp[pos][turn] != -1) return dp[pos][turn];

  int ret = (turn==0)?MIN:INF;
  REP(i,pos+1,N){
    int tmp;
    if(i == N-1){
      tmp = abs(v[pos]-v[i]);
    }else{
      tmp = dfs(i,1-turn);
    }

    if(turn == 0){
      ret = max(ret, tmp);
    }else{
      ret = min(ret, tmp);
    }
  }
  return dp[pos][turn] = ret;
}


// dfs(1,0)が答え

解法2

想定解法はO(1)。

最初、Xさんが取れる行動はいくつかあるが、「全部取る」「1枚残す」だけ考えればよい。
全部取る場合、Xさんはa_N、YさんはWになる。最終スコアはabs(a_N - W)。
1枚残す場合、Xさんはa_{N-1}、Yさんはa_Nになる。最終スコアはabs(a_{N-1} - a_N)。

2枚以上残した場合、Yさんは1枚残して最終スコアをabs(a_{N-1} - a_N)にすることができる。
なので、Xさんの最終スコアはabs(a_{N-1} - a_N)より大きくはならない。(そうできる場合はYさんによってabs(a_{N-1} - a_N)にされてしまう)
結局、Xさんは、abs(a_N - W)かabs(a_{N-1} - a_N)かの2つしか選ぶことができないので、どちらか大きい方になるように行動するしかない。

反省

コンテスト中は無駄な状態を考えて、
dp[i][j][turn]:=Xさんが最後に取ったのがi番目でYさんが最後に取ったのがj番目でturnさんの番が回ってきたときの最大スコア
を考えてしまっていた。
けど、「1枚以上取る必要がある」ので、自分の持ってたカードの数字は保持しておいても意味がなく、結局i,jの2つ区別して持つは必要ない。

一応、メモリの持ち方をdp[N][N]にして考えることもできて(turnの部分はiとjを見て決められるので不要)、dp[i][j]として、
dp[i][j]:=Xさんが最後に取ったのがi番目でYさんが最後に取ったのがj番目のときの最大スコア
として考える。
i,jを見てどちらの手番かがわかり、かつ、手番の方のiまたはjの値は依存しないので、i,jで小さい方がiだった場合、0～j-1までのdp[i][j]の値は同じなので、1回だけ計算すればよい。

  for(int i=N-1; i>=0; i--){
    for(int j=N-1; j>=0; j--){
      if(i == j) continue; //あり得ないパターンなので無視
      if(i == N-1 || j == N-1){ //最後のカードを取った場合
        dp[i][j] = abs(v[i]-v[j]);
      }
      else{
        int ret = (i<j)?MIN:INF;
        if(i<j){//Xさんの手番
          if(i == j-1){
            REP(k,j+1,N){
              ret = max(ret, dp[k][j]);
            }
          }else{
            ret = dp[j-1][j]; //前に持っていたカードに依存しないので、すでに計算済みの値をコピー
          }
        }else{//Yさんの手番
          if(j == i-1){
            REP(k,i+1,N){
              ret = min(ret, dp[i][k]);
            }
          }else{
            ret = dp[i][i-1]; //前に持っていたカードに依存しないので、すでに計算済みの値をコピー
          }
        }
        dp[i][j] = ret;
      }
    }
  }

//dp[0][1]が答え

yukicoder No.595 登山

問題

N個の地点が1～Nまで順番に直線上に並んでおり、地点iの標高がH_iで与えられる。
地点1からスタートし、すべての地点に1回以上訪れたい。終了地点はどこでもよい。
移動は2種類あり、「隣接地点に移動する場合、登る方向に移動する場合のみ標高の差」か「ワープによる任意地点への移動にはP」のエネルギーがかかる。
最小エネルギーを求めよ。

制約

2 <= N <= 2*10^5
0 <= P <= 10^9
0 <= H_i <= 10^9

解法

コンテスト時間中は、左から順に、隣が登る場合はワープして降ってくるor登るか、隣が降る場合は隣に降るかその地点にワープする感じで、
dp[i][x] := i地点までの最小エネルギーで、i地点にいる場合x=0、いない場合x=1
というのを更新していく感じで書いていた

しかし、降る場合について、右から登ってくるルートを考慮できておらず、

のような場合、「地点1→地点3→地点2→地点1→地点4→地点5→地点7→地点6→地点5」というルートを考えてしまっていた。
(この場合の最小ルートは「地点1→地点3→地点2→(地点1)→地点7→地点6→地点5→地点4」というルート)

左からも右からも降るか登るかすべてを考える必要がある。左右どちらからくるかを区別すると、
dp[i][x] := i地点に左から訪れている場合x=0、右から訪れている場合x=1の場合の、1～i地点までの最小エネルギー
とすれば、i-1とiの地点でのdpの値を考えて、

  dp[0][0] = 0;
  REP(i,1,N){
    // i-1  i
    // -> & ->
    dp[i][0] = min(dp[i][0], dp[i-1][0] + max(0LL,H[i]-H[i-1]));
    dp[i][0] = min(dp[i][0], dp[i-1][0] + P);

    // -> & <-
    dp[i][1] = min(dp[i][1], dp[i-1][0] + P);

    // <- & ->
    dp[i][0] = min(dp[i][0], dp[i-1][1] + P);

    // <- & <-
    dp[i][1] = min(dp[i][1], dp[i-1][1] + max(0LL,H[i-1]-H[i]));
    dp[i][1] = min(dp[i][1], dp[i-1][1] + P);
  }

のような遷移を考えられる。

答えはdp[N-1][0]かdp[N-1][1]の小さい方。

AGC017 C. Snuke and Spells

問題

N個のボールが一列に並んでおり、各ボールには数字が書かれている。
魔法を使うと、今あるボール個数と同じ数字が書かれたボールを消すことができる。また、魔法は連続的に行うことができる。
例えば、{1,3,3}だった場合、魔法を2回連続で行うと、{1,3,3}->3個あるので3が書かれたものが消える->{1}->1個あるので1が書かれたものが消える->{}となる。

各ボールは単位時間ごとに、ボール1個だけ数字が変化することがわかっており、変化する回数はM回であることもわかっている。
ここで、各単位時間ごとのボールの状態に対して、いくつか数字を書き換えて連続魔法で全消しができるようにする最小書き換え回数を求めたい。

制約

1 <= N,M <= 2*10^5
1 <= ボールの数字 <= N
1 <= 変化するボールの場所 <= N
1 <= 変化した後の数字 <= N

解法

まずは、あるボールの状態に対して、ボールの最小の書き換え回数を求める問題を考える。

魔法を発動するときのボールの位置は無関係なので、あるボールの状態をソートしたものを考える。
例えば、{1,3,3,5,5}のような場合、魔法を連続発動することで、全消しができる。
どういうときに全消しができるか考えると、

i 1 2 3 4 5
x 1 3 3 5 5

インデクスが5から5が2個、3から3が2個、1から1が1個、、、と、NからNがa個、N-aからN-aがb個、、、と続けられればよいことがわかる。
また、例えば、

i 1 2 3 4 5
x 1 3 3 4 4

の場合は、インデクスが5のとき値が4なので、全消しすることができないことがわかる。
たとえば、この4を5に書き換えると、インデクスが5から5が1個、4から4が1個、、、となり全消しができる。

ここで、全消しができる条件を考えると、各インデクスの部分について、ボールの数字で、すべてのインデクスをボールの数字の連続でカバーできるかどうか？になっている。(上だと、各数字のインデクスのところから各数字の連続ですべてのインデクスをカバーできている)

(難しいが)、これを扱うのに、数字aについて、[a-数字aの個数,a]という範囲を考える。
上の全消しができない場合の例{1,3,3,4,4}を考えると、カバーしている範囲の数を各インデクスで考えると、

i 1 2 3 4 5
r 1 1 2 1 0

のようになる。
5のときカバーできていないので、他の2以上になっているところから5のところに数字を書き換えてあげれば全面カバーができることがわかる。

ここで、書き換えてあげる必要がある数字の個数というのは、カバーされていないインデクス==0になっているところの数なので、これを求めてあげればよい。

数字が変化した場合は、各数字の個数から上のカバーしている範囲の数のところが1か所減って1か所増える、という変化を起こすので、各単位時間での変化はO(1)で更新できる。
前の状態で0の個数がわかっていればこの更新時に0になるかどうかみれば、こちらもO(1)で更新できる。

AGC017 B. Moderate Differences

問題

N個のマスの一番左にA、一番右にBが書かれており、それ以外は空白になっている。
いま、空白のマスに、以下の条件を満たすように数字を入れることができる。

• 隣接するどの2マスについてもその差はC以上D以下

このとき、条件を満たすように数字を入れることができるかどうか判定せよ。

制約

3 <= N <= 5*10^5
0 <= A,B <= 10^9
0 <= C <= D <= 10^9
変数はすべて整数

解法

Aの右隣の空白に何を入れられるか考える。
条件から、減らす方向に[A-D,A-C]と増やす方向に[A+C,A+D]の範囲の数字を入れることができる。
続けて、その隣には、ひとつ前の範囲[x,y]に対して、[x-D,y+D]の範囲が該当する。
最終的に、Bのマスまで来たとき、範囲にBが含まれているものが存在すればYESと答えられる。
しかし、この方法では、マスを進めるにつれ、範囲の数が2倍になっていくので、指数関数的に大きくなっていってしまう。

また、各マスで範囲が重なるような部分をマージするような方法をとったとしても、C==Dの時を考えればわかるように、範囲の数が多くなり、計算量が線形ではなくなるのでTLEしてしまう。

ここで気づきたいのは、各マスでは、「減らす方向への範囲更新」と「増やす方向への範囲更新」の2つの変化をさせられるが、これを行う順番はマスの位置に依存せず、それぞれを何回行ったか？だけでBのマスでの範囲が決まる。

増やす方向の回数をX回、減らす方向の回数をY回とすると、Y=N-1-Xとなる。
このとき、Bマスでの範囲は、[A+X*C-Y*D,A+X*D-Y*C]になる。
Xは、0回～N-1回まで考えられるが、それはループを回せばよいので、範囲内にBが入るかどうかを試せば、O(N)で求められる。

反省

変なコード書いてメモリ使い切ってPC再起動とかやらかしてしまっていた。
(さらに強制終了したせいでPC調子悪くなってダメ)
ちゃんと、計算量的使用メモリ的に問題ないアルゴリズムを考えてから書き始めること。

ARC076 E. Connected?

問題

x,y座標の(0,0)から(R,C)までの長方形を考える。
N個の長方形内の点のペアが与えられる。(各点はすべて異なる)
ペアの点同士を曲線で結びたい。ただし、長方形の外に出たり、交わってはいけない。
可能かどうか判定せよ。

制約

1 <= R,C <= 10^8
1 <= N <= 10^5

解説

Editorial - AtCoder Regular Contest 076 | AtCoder

いくつかサンプルを図で書いてみると、「ペアの点がどちらも長方形の周上にある場合、領域を2分割してしまって、それぞれ異なる領域にある点はどうやっても交差してしまう」というのがわかる。
そうでない場合は、曲線をうまく調整することで交差しないように書くことができることがわかる。

周上を1直線として見て、領域がoverlapしていないかを判定すればよい。

これは、「対応のある括弧の整合性判定(「((()()())((()()())))」みたいなの)」ともみなせるので、stackを使って判定すればよい。

反省

領域のoverlapの判定で、普通にミスってしまった。

領域を周上の座標にマッピングしたとき(l,r)とすると、l側でソートしておき、rをstackに入れながら処理していて、
今(l,r)を考えていて、直前のスタックにあるのがprとすると、

• l < prの場合、かつ、pr < rの場合、オーバーラップしている
• l < prの場合、かつ、r < prの場合、領域内にいるので、prとrをスタックに積んで次へ
• pr < lの場合、新しい領域に入っているので、rだけスタックに積んで次へ

というやり方をしてしまった。
これだと処理が一つ抜けていて、例えば(1,5)、(2,3)、(4,6)のような場合、(2,3)の処理をした後、5と3がスタックに積まれているが、(4,6)を処理するとき、prで考えるべきは5と3両方なのに、3だけ確認して処理して、スタックに5と6みたいな処理をしてしまう。
なので、pr < lの時は、スタックからl < prになるまで全部取り出してあげる必要がある。

  stack<ll> st;
  st.push(R+R+C+C);
  int i=0;
  while(i<v.size()){
    ll l = v[i].l;
    ll r = v[i].r;
    ll pr = st.top(); st.pop();
    if(pr < l) continue;
    if(r<pr){
      st.push(pr);
      st.push(r);
    }
    else if(pr<r){
      cout << "NO" << endl;
      return 0;
    }
    i++;
  }
  cout << "YES" << endl;

ARC075 E. Meaningful Mean

問題

長さNの整数列aに対して、空でない連続する部分列の算術平均がK以上であるものの個数を答えよ。

制限

2 <= N <= 2*10^5
1 <= K <= 10^9, Kは整数
1 <= a[i] <= 10^9

解説

https://atcoder.jp/img/arc075/editorial.pdf
AtCoder Regular Contest 075 / Beginner Contest 063 解説放送 - YouTube

愚直に計算するとO(N^3)や、すぐ思いつく方法ではO(N^2)で、TLE。

ある範囲[l,r)について、条件は「(Σ_{i=l}^{r-1} a[i]) / (r-l) >= K」と書ける。
これを変形すると、

<=> Σ_{i=l}^{r-1} a[i] >= (r-l)*K
<=> Σ_{i=0}^{r-1} a[i] - Σ_{i=0}^{l-1} a[i] >= (r-l)*K
<=> Σ_{i=0}^{r-1} a[i] - r*K >= Σ_{i=0}^{l-1} a[i] -l*K

<=> b[r] >= b[l]
   ただし、b[x] = Σ_{i=0}^{x-1} a[i] - x*K

となる。
この変換によって、配列bの要素の大小関係の問題(転置数)になる。

この問題は、値を座圧っぽく変換して、BITを使って0～i-1まででb[i]以下の個数を求めればO(NlogN)で計算できる。

反省

• 数式で書き出せるものは書いて、変形してみる

yukicoder No.519 アイドルユニット

問題

N人(2の倍数)のアイドルがいる。
全員ペアを組ませて売り出したい。
しかし、ペアには相性度が決まっており、すべてのペアの相性度の合計値が最大になるようにしたい。
相性度の合計の最大値を返せ。

制約

1 <= N <= 24
0 <= 各ペアの相性度 <= 1000

解説

一般的には、グラフの重み付きマッチングの問題らしい。
ここでは、各アイドルがペアを組んでいるかどうかを状態として持つbitDPを考える。

単純に考えると、「各状態でペアを組んでいないアイドル2人を選んで、状態を更新」するように計算する。

int N;
int cost[30][30];

int dp[1<<25];

int main(){
  cin >> N;
  rep(i,N){
    rep(j,N){
      cin >> cost[i][j];
    }
  }

  rep(i,1<<25) dp[i] = -1;
  dp[0] = 0;

  rep(i,1<<N){
    if(dp[i] < 0) continue;
    rep(j,N) if(((i>>j)&1) == 0){
      REP(k,j+1,N) if(((i>>k)&1) == 0){
        int ii = i | (1<<j) | (1<<k);
        dp[ii] = max(dp[ii], cost[j][k] + dp[i]);
      }
    }
  }
  cout << dp[(1<<N)-1] << endl;
  return 0;
}

これだとO(2^N * N^2)でTLEしてしまう。

実は上記のループは無駄なところがある。
状態が「100100」の場合を考える。
(この状態でjとkのループでは、「1**100」「1*01*0」「1*010*」「10*1*0」「10*10*」「1001**」を列挙して状態を更新している。)
ここで、
「100100」から「110110」と遷移して「111111」に至るケースと、
「100100」から「101101」と遷移して「111111」に至るケースでは、
同じペアの組み方なのに、2回計算してしまっている。

ペアの推移的には、
(0,3)->(0,3)(1,4)->(0,3)(1,4)(2,5)
(0,3)->(0,3)(2,5)->(0,3)(1,4)(2,5)
のような感じ。

このような場合、同じペアの組み方をするのは1通りだけ考えればよいので、状態の中でまだペアを組んでいないアイドル(状態が0のところ)を一人選んで、そのアイドルを必ず取る場合を考えて、そのペア候補だけ(kのループ)を考えればよい。

  rep(i,1<<N){
    if(dp[i] < 0) continue;
    rep(j,N) if(((i>>j)&1) == 0){
      REP(k,j+1,N) if(((i>>k)&1) == 0){
        int ii = i | (1<<j) | (1<<k);
        dp[ii] = max(dp[ii], cost[j][k] + dp[i]);
      }
      break; //これを入れるだけ
    }
  }

計算量は、O(2^N * N)になり、間に合う。

ARC047 B. 同一円周上

問題

座標平面上にN個の点がある。
各点の座標は整数で、ある点Pとのマンハッタン距離が同じであることがわかっている。(点Pの座標も整数)
点Pとしてあり得る点を一つ出力せよ。

制約

1 <= N <= 10^5
-10^9 <= x,y <= 10^9

解説

arc047

平面座標で、点Pからのマンハッタン距離が同じ点というのは、点Pを中心とするひし形の線上に乗る。
しかし、ひし形のまま扱うのは大変なので、テクニックとして45度回転させた座標を考える。
(x,y)->(x+y,x-y)という変換を考えると、上記の「ひし形の線上」というのが「正方形の線上」になり、とても考えやすい。

また、平面座標のどこかの候補点を探す場合、かつ、単純な方法では候補点が多くなりすぎる場合は、候補点を絞ることを考える。
(x座標・y座標それぞれで、線分の端点や交点などだけ取り出してその組み合わせを考える、など)

今回の場合、正方形の1辺の長さDが決まれば、点Pの座標は各点から距離Dの点のどこかということになる。(これだけだとまだ候補点が多すぎる)
もし正方形の1辺が決まれば、その辺の端点から距離がD/2の点(辺に対して両側が考えれる)が候補点になる。
そこで、正方形の辺を探す。

変換後の平面座標において、各軸について独立に出現している点の座標を考える。
その座標で最小の点と最大の点を見つける。
このとき、これらの点を端点とする辺が「正方形の1辺」の候補になる。
(例外としてN=1の時は1辺が作れないので別処理する)

これより長い辺を考える必要があるかというと、もう片方の軸の方で同じことをして見つけた辺がより長い場合、そちらが1辺の長さとしてふさわしい。
言い換えると、各軸について辺の長さを求めて、その大きな方が正方形の1辺の長さDとしてふさわしい。
(Dも候補として各軸について求めた2つがあると考えてもよい)

そして、候補点はそれぞれの点からD/2だけずれた点となる。(最大点+D/2,最大点-D/2,最小点+D/2,最小点-D/2の4点 最大点-D/2,最小点+D/2の2つ)
あとは候補点すべてについて実際に成り立つ点Pを確認してあげればよい。
計算量は、候補点の組み合わせで4*4=16個2*2=4個(または、各軸のDの候補を別に考える場合は、8*8=64個 4*4=16個)についてO(N)でチェックすることになるので、間に合う。

反省

• 座標系で絶対値が出てきたら45度回転させてみる
• 候補点が無数に考えられる場合、端点や中点など候補点としてありえる部分に絞って探索する