TopCoder Open 2018 MarathonMatch Poland Lightning Round メモ

問題

 H \times Wの盤面が与えられる.それぞれのマスは領域に分かれている(領域には飛地もある).また,どのマスも5色以下の色で塗られている. このとき,領域に以下の制約を満たすように領域に色を塗る.

制約

  • 領域同士が辺で接している場合,それらの領域は違う色であること.
  • ただしなるべく少ない色を使うこと.
  • また,できるだけ元の色を保持できること.

1日目

問題を確認したつもりになる.色数を減らせばいい問題だと認識したが,まったく解法が思いつかない.
その日はほかに用事があったのでコードは全く書いていない.

2日目

とりあえずランダムに色を塗るプログラムを書く.
ただこれはめちゃくちゃ性能が悪くて,1時間回しても10色とかそこらへんの解しか出ない. 投げてみると100位付近….

3日目

「graph coloring local search」とか「graph coloring simulated annealing」とかで検索してみる.
お手軽そうな焼きなまし法のPDFを見つけたので実装.内容を簡単に下にまとめておく.正直これで本当に制約を満たす解が見つけるのか疑問だったが,動かしてみると普通に見つかって感動した. https://arxiv.org/abs/1712.00709

PDF に載ってる焼きなましの概要

  • 初めに使う色数を決めておく.( 大体どの問題も6,7色で落ち着いたので余裕をみて8色から試していった)
  • 頂点にランダムに色を割り振る(この時点ではColoringの制約に違反している).
  • 近傍解: 適当な頂点の色の変更で作る
  • 目的関数: 両端の頂点の色が同じ辺の数 (最小化)
  • 目的関数が0になればColoringできたことになる.

まず愚直に実装して投げてみると90位くらいだった.そのあとパラメータを見直して,6色で塗れる数が多くなると75位くらいにはなった.
この時点ではまだ,oldColorsとの差は考えていなかった.
彩色が終わったグラフに頂点の色を変える山登り(もちろんColoringの制約が壊れないように)で塗り替え数を少なくなるようにしたらまた順位が上がって70位付近.
そのあと塗り替え部分も焼きなましにしたり,高速化したりでprevが56位だった.

最終的な解法とExample

8色で塗れるか焼きなましを試す.塗れたら7,6色と試していく. もし焼きなましが時間内で終わりそうになかったら,残り時間は塗り替え数を少なくするための焼きなましに使う. ちなみにシード1から400では73%が6色で,他23%は7色で塗ることができた.
Example scores:
0) 700351.0
1) 730551.0
2) 608070.0
3) 721516.0
4) 602872.0
5) 604814.0
6) 612986.0
7) 611629.0
8) 604774.0
9) 606147.0

コンテスト終了後

Twitter見てて自分がスコアリングを全く理解していないことに気づいた.
rawスコアは100000*色数 + 塗り替えた色数で計算されて,自分はこれが最終スコアかと思っていた.
が,実際にはほかの人の解のうち最も色数 C_{min}が少ないものと塗り直し数 P_{min}が少ないものと自分の解で計算される \frac{C_{min}}{C_{your}} \times \frac{P_{min}}{P_{your}}がスコアとして使われる.
問題はしっかり読もう.ちなみに色数の焼きなましを5秒で打ち切って,残り5秒を塗り替え数を減らすようにした場合は下みたいな感じになりました. 6)は色が7色に増えてしまっていますが,塗り直し数が減ってるのでこっちのほうがいい解です. 時間を増やしても劇的に変化していないので,自分の実装した焼きなましだとあまり塗り直しは減らせてないみたいでした.
Example Scores:
0) 700351
1) 727464
2) 608070
3) 720114
4) 602663
5) 604814
6) 710964
7) 611585
8) 604747
9) 606147

TopCoder Marathon Match 100 - SameColorPairs メモ

問題

 H \times W (10 \leq H, W \leq 100)の盤面のそれぞれのセルに C (1 \leq C \leq 6)色のうちの一色のタイルが置かれている. 同じ色のタイルを2枚選んでその2枚のタイルの作る矩形の中に違う色のタイルがないときに2枚のタイルを除去できる. なるべく多くのタイルを除去せよ.
上位3名に賞金,50位以上だとTシャツがもらえる.

結果

prev: 32位
システス: 33位
無事にTシャツをゲットしました!!

思考過程と方針

選択肢が多すぎる & 盤面の評価どうする? → ビームサーチは難しそう.それなら焼きなましか → 操作の順番が重要なので簡単に近傍が作れなさそう.最適解はたくさんありそうなのでランダムでもある程度行けるのでは??という感じでランダムで行くことにしました.
適当にタイルを選んで消せるか試し,消せるタイルがなくなるまで試していく感じです.まず単純にこれを実装して投げるとまあまあいい感じでした.そこから定数倍高速化したりしました.
最後にもうこれ以上高速化できなさそうだったので,苦肉の策として数回に一回,そこまでのベストな解の後ろを少し戻して最後のほうだけランダムに探索するようにしました.これのおかげで0.3%くらいローカルで改善しました.
ちなみに上位の方たちは盤面を分割して焼きなまししていたみたいです.まだどういう感じだったのか完全に理解しきれていないので,コードが見られるようになったら見てみたいと思います.
5月にはTCOもあるので楽しみですね.

第2回 RCO日本橋ハーフマラソン 予選

第2回 RCO日本橋ハーフマラソン 予選に参加しました. 結果は168位とよくありませんでした. 問題はコンテストページに譲って解法だけ書きます.

A - ゲーム実況者Xの挑戦

コマンドをランダムに生成,そのコマンドで全部のステージを操作して最終的に一番コインを稼げたステージ上位8個を選ぶ.

B - ゲーム実況者Xのデフラグ

スワップ回数が4000回までなので,0から3999までのセクタをきれいに並べる.

どちらも簡単な解法をとりあえず出して,そのあとに考えようとしました.が,簡単な解法をバグらせて結局そこから先には進めませんでした.短時間で正確に実装できる力が欲しいです.

Raspberry Pi 2(Arch Linux)をREGZA(43J10X)のLAN-HDDに設定する

Samba on Arch Linux on Raspberry Pi 2をREGZA 43J10XのLAN-HDDに登録する方法を説明します.
もともと自分は録画はPT3でやっていて,一人暮らしを始めるときにREGZAを買いましたが結局PT3で録画をしています.
録画した動画の再生方法ですが,

  1. PCで録画,PCとREGZAHDMIでつないでPCで再生
  2. PCで録画,USBメモリに動画をコピー,REGZAで再生
  3. NAS上に録画,NAS上の動画をREGZAで再生

の3つがあります.ただ,1は見るだけなのにPCを操作しないといけない(リモコンだけで視聴できるほうが良い),2はコピーが面倒ということで3が一番楽です. あと1だとせっかくのREGZAのフレーム補間がうまくかからないので画質の面でも劣ります.

今自分にはNASを買えるだけの余裕がないので,家に転がっていたRaspberry PiにSambaを入れて簡易NASを構築しました.
Raspberry PiにはArch Linuxが導入済みということで話を進めます.以下の方法ではREGZAから認証無しに,ゲストとして接続できるようにします.

1. Sambaの導入

pacman -S samba

2. Sambaの設定

2-1. Raspiberry Pi起動時に自動で起動

$ systemctl enable smbd nmbd

2-2. 設定ファイルの編集

以下の必要なところを変更し /etc/samba/smb.conf に保存する.

[global] #全体の設定
dos charset = CP932
server string = Raspberry Pi
syslog = yes
log file = /var/log/samba/log.%m
max log size = 1000
unix extensions = no
dns proxy = no

map to guest = Bad User
guest account = user_name #ゲストとしてアクセスしてきたユーザにどのユーザーを割り振るか.自分がいつも使ってるユーザ
ntlm auth = yes #NTLMv1はデフォルトで無効にされてしまっている.NTLMv2にREGZAが対応していないのでv1を有効にする.


[NAS]
comment = Raspi-NAS
path = /var/lib/samba/shared #共有するフォルダ
read only = no
guest ok = yes
browseable = yes
writable = yes

2-3. Sambaユーザーの追加

Samba用にユーザーを追加します.(もしかしたらいらないかも)
パスワードはLinuxのパスワードと一致しなくても構いませんが,ユーザー名は一致させないといけません.

$ pdbedit -a -u user_name

2-4. Sambaの起動

$ systemctl start smbd nmbd

REGZA側で 設定→接続機器設定→LANハードディスクの登録 から登録を行えば完了です. f:id:shamal_ref:20180125015716j:plain

秋ABの反省 & 2018年の目標

秋ABの反省

単位修得

数理アルゴリズムとシミュレーションとオートマトン形式言語はテストの結果が微妙すぎて取れているか微妙でしたが取れてました.
A評価は体育と計算モデル論だけでした.大学院の推薦は春ABの時点であきらめていましたが,今回の結果でもらえないことが確定しました.

普段の生活

ネトゲばっかりやっていました.マラソンマッチがあるときはそっちもやりましたが,ネトゲ中心の生活でした.なんのために大学に来たんだ.

2018年の目標

  • 院試に合格する
  • AtCoderでレート1800以上(青中盤)になる
  • TopCoderマラソンでレート1800(黄色中盤)になる
  • 規則的な生活
  • 適度な運動
  • 英語の勉強

いろいろ高い目標を上げましたが,できる限り達成したいと思います.
あと時間があれば以下も.

HxHMM1st参加記録

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

結果

システス前 15位
システス後 16位
順位表1ページ目(20位以内)に入ることが目標だったので,目標は達成できました.
 最終的な私の解法は「ビームサーチ+ちょっとした山登り」でしたが,ツイッターを見ると上位陣はほとんど辺の入れ替えで焼きなましをしていたみたいです.一度だけ点の入れ替えで焼きなましをしましたが,微妙だったので大して検討もせず「上位陣はもう少しいい感じにビームサーチしてるんだろう」と考えて焼きなましはそこで捨ててしまいました.
 途中でビジュアライザを作りそれを眺めていましたが,特に改善点が浮かばず結局どの問題でも当たり前にやること(重複除去とか高速化)を順当にやっていただけで終わってしまいました.
 文字だけだと味気ないので記事の一番下にランダムシード8の結果を張っておきます.辺は赤ほど重く青に行くほど軽くなります.

最終的な方針

  • 1つ目の頂点を G_{emb}の中央に置いてそこから幅 max(10,  \lfloor 0.2*|V| \rfloor)でビームサーチをする.
  • 評価は問題のスコアをそのまま使った.
  • 時間が余る場合は頂点を見る順番を変えてもう一度ビームサーチ.
  • 最後にビームサーチで1番良かった解を頂点移動,交換の操作で山登り.
  • 方針ではないがコンパイラはclangにした.gccより1.1~1.2倍ほど速かった.

点数の推移

  • 154598 貪欲に置いていく
  • 156796 頂点を見る順番をランダムにして時間いっぱい試すようにした
  • 158065 貪欲でできた解を頂点移動,交換で山登りするようにした
  • 159099 ビームサーチ化
  • 160256 重複除去を入れた
  • 161592 高速化 & パラメータ調整

f:id:shamal_ref:20171130221518p:plain
random seed: 8