びったんびったん

ユーザビリティ・プログラミングについて。

Topcoder Marathon StainedGlass

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17394&pm=15264

Example Tests

It's good that I ran several times only seed 2

1, 188798.4375, 120831.0, 5/20
2, 2.0110236926112E7, 1.8450842E7, 44/1000
3, 2.585656663217272E7, 2.4089131E7, 20/555
4, 7493222.916638096, 6457431.0, 40/518
5, 4.1234232157296196E7, 3.9425575E7, 22/970
6, 8907273.54193523, 8194529.0, 31/728
7, 9728903.343749998, 8059686.0, 15/152
8, 2.7994073349021245E7, 2.5841511E7, 12/294
9, 6883570.201690821, 5904721.0, 44/552
10, 2.3159190600224324E7, 2.1495614E7, 18/474

1, 188798.4375, 120831.0, 5/20 f:id:hakomof:20190115103509p:plain

2, 2.0110236926112E7, 1.8450842E7, 44/1000 f:id:hakomof:20190115103600p:plain

3, 2.585656663217272E7, 2.4089131E7, 20/555 f:id:hakomof:20190115103646p:plain

4, 7493222.916638096, 6457431.0, 40/518 f:id:hakomof:20190115103715p:plain

5, 4.1234232157296196E7, 3.9425575E7, 22/970 f:id:hakomof:20190115103808p:plain

6, 8907273.54193523, 8194529.0, 31/728 f:id:hakomof:20190115103831p:plain

7, 9728903.343749998, 8059686.0, 15/152 f:id:hakomof:20190115103857p:plain

8, 2.7994073349021245E7, 2.5841511E7, 12/294 f:id:hakomof:20190115103946p:plain

9, 6883570.201690821, 5904721.0, 44/552 f:id:hakomof:20190115104009p:plain

10, 2.3159190600224324E7, 2.1495614E7, 18/474 f:id:hakomof:20190115103500p:plain

方針

序中終盤ともに 1 母点を周囲 8 マスに動かす焼きなまし(輪郭追跡 + BFS で差分計算)

試行回数は 125 万くらい

  • 初期状態はランダム
  • 序盤 4 秒
    • 画像を辺の長さが 1/8 になるよう縮小
    • N 色
    • 定期的に減色を空撃ちして、隣接領域との色差が小さい母点らや、同色で至近にある母点の片方らすべてを一度に、色差が大きそうなとこに飛ばす
  • 中盤 12 秒
    • 画像は原寸大
    • N 色
  • 中盤と終盤の間
    • 色数を黄金分割探索、 kmeans++ で減色
  • 終盤 4 秒
    • 画像は原寸大
    • N の 2%-10% 色

考察の流れ

だいたい時系列

焼けそうなので焼く。

状態は

  • 母点の座標
  • 母点のグループ
  • グループの色

からなる。 このうち母点の座標・母点のグループが決まれば最適なグループの色は求まる。 差の絶対値和の最小なので中央値。 なので、母点の座標と母点のグループを焼きなましてグループの色は差分更新で最適値に追従させる。 関連記事

具体的には、色素値ごとの面積の BIT と色素値和の BIT を持つと追加・削除・最適色でのスコアなどが O(log(256)) になり差分更新できる。

近傍

母点の自由な移動はうまく差分計算できても O(領域面積 * log(256)) で遅い。 もっと速くしたい。 近傍を小さくしよう。 母点を周囲 8 マスに動かせば領域の境界しか変わらない。

動かす母点の輪郭を 輪郭追跡 で求めて queue に入れる。 px の所属する母点が変わったか調べて、変わっていたら周囲 8 マスを queue に入れる。 queue が空になるまで BFS する。 これでほぼ厳密に差分計算ができた1

近傍が小さすぎない?

この問題のように要素同士に区別がない(母点を入れ替えてもスコアが変わらない)とき近傍は大きくなくてよい。 なぜなら、遠くに動かす近傍は、母点を玉突きのように少しずつ押し出しても代替できるので。

HACK TO THE FUTURE 2018予選 山型足し算 も同様の理由で近傍が小さい。

近傍が小さすぎない? 2

近傍は大きくなくてよいけど、小さいほどよいわけではない。 画像最大 800px に対して 1px の移動は小さすぎる気がする。 でも近傍を大きくすると遅くなってしまう。 じゃあ画像を縮小しよう。 800px に対する 1px の移動よりも 400px に対する 1px の移動は相対的に大きい。 画像を縮小すると速くなるので一石二鳥。

さらに、画像を縮小して焼いてから原寸大で焼くと試行回数と精度のバランスが取れるが、大きい近傍で焼いてから小さい近傍で焼くことにもなる。 近傍をだんだん小さくするのは良い工夫なので二石四鳥。

減色

疲れたので以降雑

母点のクラスタリングは基本的にうまく焼きなませない。 例えば、空のグラデーションが 5 色のとき 4 色のグラデだとか 6 色のグラデへの移行は全体的にずれるので焼きなましの小さな近傍では対応できない。 なので、母点の座標の焼きなましと母点のクラスタリングは分けて最適化することにする。 やり方は序盤に減色だとか、終盤に減色だとか、徐々に減色していくとか色々考えられ一概に判断できなかったので全部試した。 結果、序中盤は N 色で、1 回だけ減色するが良かった。 結果から考察すると、一度減色してしまうと同じ色同士の母点が結びついて動きづらくなるのでギリギリまで減色しないのが良いようだ。

クラスタリングは kmeans++ 。 といっても厳密スコアによる山登りに等しい。 代表色のクラスタリングではなく領域の全色集合同士のクラスタリングクラスタ数は黄金分割探索で、凸じゃないけどだいたい凸ってことで気にしない。 黄金分割探索で求まったクラスタ数±1に kmeans++ を数百回多スタート。 これ大事。 さっき書いた通り近傍探索(焼きなましとか kmeans++)がうまくいかないので多スタートで誤魔化している。 というか多スタートする必要があったから母点の座標の焼きなましと母点のクラスタリングを分けた。

母点のワープ

f:id:hakomof:20190115170813p:plain

黒背景には最小限の母点しかない。 元々黒背景にもたくさんの母点があったのだが、隣接領域がすべて同色の母点は除いてもスコアが変わらず、有意義なとこに差し込めばスコアが良くなることに気づいた。

これを拡張すると、隣接領域との色差が少ない母点は除けそうである。

同様に無駄な母点が無いか考えてみたところ、同色の母点がすぐ近くにあるとき 1 つを残して除けそうなことにも気づいた。

序盤の間等間隔に 9 回減色を空撃ちして、同色で至近にある母点の片方らと隣接領域との色差が小さいほうから 2.5% の母点らすべてを一度に、領域境界に周囲 9 マスの色差の和の二乗を重みとしてランダムワープ。

なんで焼きなましのサブ近傍にしなかったの?遅いのと、ワープ先になじんでからじゃないと良い悪いの判断ができない気がしたから。

なぜ序盤だけ?ワープ後になじませるのに大きい近傍が必要だから。


  1. 領域の角度がとてもきついときに離散化で領域が連結でなくなることがある。このとき輪郭追跡が漏れる。が、実験したところ数ケースに 1px 程度しか誤らないので許容範囲。

ビームサーチは DP

この記事は Competitive Programming (1) Advent Calendar 2018 - Adventar の 6 日目です。
5 日目の記事は armeria_betrue さんの 解説記事のはなし - ARMERIA です。
7 日目の記事は xuzijian629 さんの Implicit Treap - 競プロ練習記録 です。

ビームサーチとは

ビームサーチとはグラフのヒューリスティック探索アルゴリズムです。 初期ノード群から BFS 順に探索していき、深さ(初期ノードからの遷移回数)ごとに良さそう順のノードの上位 N コ以外を枝刈りすることで時間 / 空間計算量を改善します。

58-72p でくわしく説明されているので引用します。

本記事の趣旨

ビームサーチといったら上述のような説明が定番?です。 その説明は正しいのですが、私はビームサーチを上述を含んだより広汎なアルゴリズムだと思っています。なので、私の現在の解釈である「ビームサーチは DP の拡張」という観点で説明してみます。 色々な視点から同じものの説明がなされるのも一般に良いことですし。

ビームサーチは DP

DP の説明は省略します。

f:id:hakomof:20181205200921p:plain

例えば、木を探索するとして、どんな経路を通ったかによらず以降の最適な経路が同じ状態を同一とみなすと、木は DAG になり合流部以降の重複探索をなくすと DP になります。 つまり、どういう状態群を同一とみなすかは DP の一端です。

同様に今度は深さが同じ状態群を同一とみなして DP で解いてみましょう。

f:id:hakomof:20181205200949p:plain

単純な形ですが DAG は DAG です。 この DAG を DP するコードを起こすとこんなかんじでしょうか。

State dp[Depth];
dp[0] = initialState;
for (int d = 0; d < Depth - 1; ++d) {
    for (State nextState : dp[d].getAllNextStates()) {
        dp[d + 1] = max(dp[d + 1], nextState);
    }
}

お気づきいただけただろうか… この配る DP の振る舞いは幅 1 のビームサーチと完全に一致します(なにやら冗長なただの greedy でもよいです)。 なぜ一致するのかというとビームサーチが DP そのものだからというほかないです。 結局、ビームサーチは深さごとに状態をまとめる、 DAG になる、 DAG のトポロジカル順序である深さの昇順にビームを更新していく、と DP をしているに過ぎなかったのです。

ビームサーチの DP との違い

  • 状態のまとめ方が過剰
  • 評価関数
  • ビーム幅

状態のまとめ方が過剰

効率的な探索をしてなお最適解が現実的な時間で求まらないとき、非最適解でよいから現実的な時間で求めたいという動機があります。 そこで、現実的な実行時間になるまで状態を過剰にまとめるというのが思想の出発点だと思っています。

評価関数

本来異なる状態を同一とみなす以上、最適解に通じる状態が残るとは限りません。 ですが、状態のつぶれた情報をフルに駆使した評価関数で精度の底上げができます。

ビーム幅

例えば、実行時間が 10 秒くらいになるような状態数が 500 万くらいに状態をまとめるといった器用なことはできません。 そのため、実行時間と性能に融通が利きません。 ですが、ビーム幅を導入すると実行時間は約ビーム幅倍になり相応に性能が上がる(ことがある)ので、少し融通が利くようになります。


以上よりビームサーチは状態の過剰なまとめを許容する形に拡張された配る DP だと思っています。

で、何ができるの?

  • ビームは深さ以外でも切れます
  • あるビーム内状態の次状態は直後のビームでなくてよいです
  • 1 次元でなくてよいです
  • ビームサーチ以外の嘘 DP との併用や換装ができます
  • DP の知見が流用できます

例えば以下のような 2 次元の DP をビームサーチ化するとしたら、ビームはタテにもナナメにも切れます(切った後も DAG になっています)。 逆にヨコにはループができるので切れません。1

f:id:hakomof:20181205212430p:plain

f:id:hakomof:20181205212441p:plain

f:id:hakomof:20181205212503p:plain

ビームをどう切るかで性能が大きく変わるのは想像にたやすいでしょう。 肝心のビームをどう切ればよいかですが、 パラメータが違う状態同士の優劣判断が一番難しいパラメータで切るのが良さそうに思います。 なぜなら、各ビームにはそのパラメータが同じ状態しか含まれないので、そのパラメータを評価関数に含めなくてよくなるからです。 例えば、ゲーム AI などで 5 ターン目と 100 ターン目の比較は難しいからビームをターンで切るといったかんじです。

おわりに

近年マラソンをする人が増えうれしい限りで、焼きなまし / ビームサーチを覚えたい / 覚えたといったツイートをよく見かけるようになりました。 しかし、インターネット上の情報は少なく例も単純です。 そこで、実際のビームサーチ(や焼きなまし)が単純な例よりもはるかに柔軟でそれ自体に工夫の余地が多いことを少しでも感じてもらえたらなと思い本記事を書きました。 もちろん、それ以前のどんな方針を立てるかがマラソンで一番おもしろいとは思います。 ですが、ビームを撃つとか焼くとか決めた上でそれ自体を改造するのも十分おもしろいので楽しんで欲しいなと思います。


  1. 切れないことはない

Topcoder Marathon KnightsAndPawns

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17225&pm=14994

焼きなましに飽きた1点をのぞけば、おもしろい問題だったと思います。

f:id:hakomof:20180731200014j:plain

方針

  1. 空のボードにナイトをごく少数ランダムに配置して初期状態とする。
  2. ナイト数を固定してペナルティ最小化の焼きなまし(SA)をする。近傍はナイト1つの移動だけで追加や削除はしない。
  3. ペナが0つまりvalidな状態に到達したら、ベストを更新して、その状態にナイトを1つランダムに追加して2に戻る。

例えば、
ナイト数100のvalidな状態をSAで求める。その状態にナイトを1つ追加して、
ナイト数101のvalidな状態をSAで求める。その状態にナイトを1つ追加して、
ナイト数102のvalidな状態をSAで求める…
これを時間いっぱい繰り返します。

この方針の優位性

方針に悩んだので、とりあえずナイト数とvalidが存在するかどうかの関係性を洗いました。雑なSAで調べました。それによると、あるX以下のナイト数はすべてvalidをつくれて、Xより大きいナイト数はすべてvalidをつくれないという綺麗な感じに分かれました。また、Xのvalidな最適解はわりと高速に求まったので、これは最適解を拾えるケースはきっちり拾えないと死にそうという印象になりました。(最終方針だとケースの半分強で最適解と思われるものが安定して出る)

これらを元に前述の方針を立てました。

メリット

  • ナイト数を1つずつ増やしながらvalid解を求めていくので、時間に余裕があれば安定して最適解が出る
  • SAのスコアが単なるペナなのでペナ方向のランダムウォークは理想的に行われる

デメリット

  • ナイト数を1つずつ増やしながらvalid解を求めていくので、収束が遅い。ですが、valid解にナイトを1つ追加した解つまりペナがとても少ない解からSAをはじめることでこのデメリットはかなり軽減される。
  • ナイト数を固定しているので、ナイト数方向のランダムウォークは皆無

他にもいくつか考えましたが、この方針が強そうだったので採用しました。

方針の続き

前述の方針そのままにさらに工夫を足します。

近傍を絞る

近傍はナイトを1つ動かす。ですが、ランダムなナイトをランダムな空きマスに動かすのではなく、

  • invalidなナイトをランダムな空きマスに動かす。
  • 攻撃されすぎなナイトを攻撃しているナイトを、ランダムな空きマスに動かす。
  • 攻撃されなさすぎなナイトを攻撃できる空きマスに、ランダムなナイトを動かす。

の3種類に絞ります。いずれもあるナイトのinvalidを解消する近傍です(たいていは別のマスにinvalidが移るだけですが)。SAはこのようなたとえスコアが下がっても部分的に改善する近傍だけが必要かつ十分なようで、それ以外の近傍を削ることが重要かつ頻出です。状態内のinvalidなナイトはとても少ないのでものすごい削られます。

毎試行必ず遷移するSA

普通のSAは近傍をランダムに選んで受理されたら遷移するので、試行回数×受理確率=遷移回数がパフォーマンスの目安になります。もし受理確率を100%にできたらもともとの受理確率が1%だとしたら100倍の高速化になります。今回の問題はこれができます(別途処理を追加するので10倍くらいの高速化(うろ覚え

このテク、過去のKnightsAttacksというコンテストで使ったのでそのときのツイートを流用します。(別にKnightがらみでなくてもこのテクは使ええます)

今回は黒赤青すべてのマスが変化するので41種類

今回は-16から+16の31通り

過去のコンテストのツイートバリバリ流用できるのほんと草生える

多スタート

局所にはまることはあるのでボードが小さいときは2回スタート

Example scores

Example scores:
0) 15.0
1) 1293.0
2) 3391.0
3) 1444.0
4) 1869.0
5) 173.0
6) 1415.0
7) 261.0
8) 230.0
9) 1499.0

f:id:hakomof:20180731195934j:plain f:id:hakomof:20180731200014j:plain f:id:hakomof:20180731200135j:plain f:id:hakomof:20180731200110j:plain f:id:hakomof:20180731200120j:plain f:id:hakomof:20180731200347j:plain f:id:hakomof:20180731200427j:plain f:id:hakomof:20180731200443j:plain

Topcoder Marathon Match 100 SameColorPairs

問題文

方針

私は焼きなまし厨なのでとりあえず焼きなましを考えます。

この問題の要求する解は消すペアとその順番です。その解そのものを(順番を含めて)直接焼きなますというのは難しそうです。なぜならあるペアを消すと新たにペアが消せるようになる、といった順序関係が強そうなので、順番を安易に変えると状態が壊れそうだからです。

そこで消すペアと順番を分けて考えてみます。消すペアの集合(消せる消せないにかかわらずすべてのマスをペアにしたもの)を固定したときの順番はどうなるでしょうか。これは以下のような簡単な貪欲で最適な順番、最適なスコアが求まります。

  1. 消せるペアを消す
  2. 新たに消せるペアが増えるのでそれも消す
  3. 1つも消せなくなるまで消す

なので、

  • 消すペアの集合を焼きなましの状態とする
  • 状態を少し変えたら、先の貪欲でスコア(差)を求めて遷移判定をする

とすれば焼きなましに帰着できました!

近傍

同じ色のペアを2つ選んでつなぎかえます。マスAとBを消すペアとマスCとDを消すペアを、ACを消すペアとBDを消すペアに変えるといった感じです。

状態に制限がなく、近傍も小さいのでうまく焼きなませそうです。

ですが、先の貪欲はめちゃくちゃ遅いのでまともにまわりません。なので収束速度の底上げ・高速化をしていきます。

盤面を分割して順に焼きなまします。探索空間が小さくなり収束が速くなることが期待されます。消すペアは近いことが多いので局所的な焼きなましはあまりデメリットになりませんでした。

盤面は1-27分割しますが最後の2ブロックだけ多スタートします。

近傍は、消せないペアか他のペアをたくさん囲っているペアの中から選びます。他のペアをたくさん囲っているペアというのは、囲われているペアが先に消えることを縛っていて、それがたくさんということは大局的に良い状態ではない可能性があります。なので変更の候補です。

近傍のつなぎかえ先は(広義)近いマスほど高確率で選ばれるようにします。

先の貪欲は次のような言い換えができます。消すペアを頂点として、ぺアXを消してからでないとペアYを消せないときXからYに有向辺を張った依存グラフを、閉路の手前までトポロジカルソートすると先の貪欲と同じ結果が得られます。消せるペアを探す手間が省ける分こっちのほうがたぶん速いです。

評価値は、消せるペア数 - 依存グラフの最小閉路の数 / 2.5です。閉路以下のペアはすべて死ぬので閉路の数をペナルティとすると探索空間がなだらかになってよさげです。

依存グラフは差分更新します。更新が必要な辺は、変更する2つのペアに入出する辺だけなので、グラフ全体を毎回つくりなおさなくていいです。

依存グラフを差分更新するにあたり、新しいペアを囲うペアを列挙する必要がありますが、愚直にすべてのペアを走査すると遅いので、バイナリ空間分割という衝突している物体の列挙を高速にするアルゴリズムを使います。囲われていることと衝突していることは同じことなので転用できます。

Yandex Algorithm 2018 Optimization track. Round 2 News freshness

問題文

暫定3位でした。険しい。問題自体はとてもおもしろかった。

greedy

巡回するサイトを1つずつ順番に決めていってパスをgreedyにつくります。パスがつくり途中だと2週目以降にいつどのサイトを訪れるかが定まらずスコアに加味できないので困ります。そこでパスの周期(timeToIndexの和)を決め打ちします。あらかじめ決めた周期(それ以外認めない)になるようにパスをつくることで、つくり途中でも2週目以降のスコアを計算できるようになります。

実装としては、最初は自由にパスを伸ばします。そして周期-150を切ったら、パスの後尾からランダムに伸ばして周期ジャストでパスの先頭に戻れるものの中からgreedyに1つ選ぶなどすると、だいたい成功します。

評価関数は、testerスコアの期待値 / すべてのパスのtimeToIndexの和としました。すべてのパスのtimeToIndexの和でわることで、timeToIndexあたりのスコアが高い効率のよいサイトが選ばれていきます。

あとはテキトーな周期で何回かgreedyしてmaxをとれば8600点以上が出ました。

周期

周期についていろいろ。

timeToIndexあたりのスコアがよいサイトばかりを選ぶとtimeToIndexが小さいので周期が短くなります。しかし周期が長いと週回数が少なくなり、1つのクローリングが影響する箇所が少なくなるのでよいスコアを得やすいです。短いことにも長いことにもメリットがあるので周期には短すぎず長すぎないベターな長さが存在します(実験によって確認)。

ベターな周期はすべてのサイトのtimeToIndexの和の45%-70%(5000-20000)ぐらいになるようです。またパス長は周期を長くするためにNギリギリであることが理想的ですがgreedyによって得られるパス長はNの65%-100%くらいになります。

ほどよい周期のパスをgreedyで得るために評価関数をtesterスコアの期待値 / pow(すべてのパスのtimeToIndexの和, timeCoef)に変えます。timeCoefが1に近いほど周期が短く、0に近いほど長くなります。timeCoefのよさげな値は3分探索で求めることができますがgreedy1回がとても重いのでやめました。timeCoefのよさげな値をローカルで時間をかけて求めて、testcaseパラメータと最小二乗法でえいっしたらこんな式に、

timeCoef = sqrt(S / (double)numberOfEdges) * -7.836528104606689 + 0.7974926014955707;

timeCoefは決まりましたが、そのtimeCoefに対応する周期は事前にわかりません。周期が長すぎるとパス長制限で構築に失敗しますし、短いほどスコアが悪くなります。なので2分探索で構築に失敗しない最大の周期を求めます。

ここまででよさげな周期を求めることができました。これで8700点ぐらい

周期には他にも着眼点があって、周期がtopicのfreqの倍数のときスコアがよくなります。というのも、そうであるときニュースの生成周期とクローリングの周期がそろうので、1週目で高スコアをとれれば、すべての周回で高スコア(同スコア)をとれるためです 。周期がずれてるとすべての周回で高スコアをとるのは難しくなります。

なのでいずれかのtopicのfreqの倍数であるような周期の中から2分探索すると8740点ぐらい

山登り

この問題はぱっと見山登り/焼きなましできない系に見えますができます。

timeToIndexの和が110程度の部分パスをランダムに選びます。そしてtimeToIndexの和が同じであるようにランダムに生成した部分パスと置換します。こういう近傍だと変更域以外の時間がずれないので山登り/焼きなましが有効ななだらかに近い探索空間になります。

greedyの結果を山登りして8790点ぐらい

入力バイナリから画像を作成するプログラムを公開しました

圧縮する入力バイナリは2次元のradianceのデータなようです。 このデータの画像はnetCDFデータのビューアから見ることができるようで、見るためにはnetCDFデータをビューアで開く、Rad行をダブルクリック、Create a 2D plotを選択します。

f:id:hakomof:20171216003749p:plain

とりあえず入力バイナリがどんなものか理解するために、入力バイナリから同じ画像を作成するプログラムを書きました。動作にはPython3、ライブラリPillowが必要です。(ソースコードはブログ最下部)

py script.py bin_4obs/OR_ABI-L1b-RadC-M3C01_G16_s20172101802185_e20172101804558_c20172101805000.bin

f:id:hakomof:20171216003715p:plain

これで画像が作成されます。色がぜんぜん違いますが、グラデーション色が違うだけでradianceはビューアと一致しています。

入力バイナリは、2次元を1次元につぶした2バイトのunsigned short?のradianceの基本値?が連続しているようです。この基本値にバンドごとに固有の定数(これはビューアからコピペしたので ミスってるかも)をかけて足すと、ビューアのradianceと一致しました。

というわけで適当にお役立てください。また、私はまったく詳しくない人なので間違っているかもしれないです(間違っていたら教えてください、そしてごめんなさい)。

from math import *
import os.path
import struct
import sys
from PIL import Image

def rgb(minimum, maximum, value):
    minimum, maximum = float(minimum), float(maximum)
    ratio = 2 * (value - minimum) / (maximum - minimum)
    b = int(max(0, 255 * (1 - ratio)))
    r = int(max(0, 255 * (ratio - 1)))
    g = 255 - b - r
    return r, g, b

all_scale_factor_and_add_offset = [
    (0.8121064, -25.936647),
    (0.15859237, -20.289911),
    (0.37691253, -12.037643),
    (0.07073108, -4.5223684),
    (0.09580004, -3.0596137),
    (0.030088475, -0.9609507),
    (0.001564351, -0.0376),
    (0.007104763, -0.5586),
    (0.022539102, -0.8236),
    (0.02004128, -0.9561),
    (0.03335779, -1.3022),
    (0.05443998, -1.5394),
    (0.04572892, -1.6443),
    (0.049492206, -1.7187),
    (0.05277411, -1.7558),
    (0.17605852, -5.2392),
]

file = sys.argv[1]
band = int(os.path.basename(file)[19:21])
scale_factor = all_scale_factor_and_add_offset[band - 1][0]
add_offset = all_scale_factor_and_add_offset[band - 1][1]
scale = int(sqrt(os.path.getsize(file) / 7500000))
width = 2500 * scale
height = 1500 * scale
radiances = [[0 for _ in range(width)] for _ in range(height)]
min_radiance = 1e9
max_radiance = -1e9
with open(file, 'rb') as f:
    for i in range(width * height):
        x = i % width
        y = i // width
        p = struct.unpack('H', f.read(2))[0]
        radiance = p * scale_factor + add_offset
        radiances[y][x] = radiance
        min_radiance = min(min_radiance, radiance)
        max_radiance = max(max_radiance, radiance)
image = Image.new('RGB', (width, height))
data = image.load()
for y, rs in enumerate(radiances):
    for x, r in enumerate(rs):
        data[x, y] = rgb(min_radiance, max_radiance, r)
image.save(file[:-3] + 'png')