暫定: 相対スコア 37,484,834,108点、68位。

ソースコード: https://github.com/kusano/ahc017

アルゴリズム

焼きなまし法
遷移は、道路を工事する日を変える
道路 m の工事する日を変えるとき、 m の両端の交差点を u と v として、 u と v それぞれからの各交差点の最短距離の和の工事日の変更による差分を、遷移を決定するときの差分とする
- スコアの差分の真の値を求めるのが遅いため
この差分を計算するときは、 u からの距離が300未満の交差点のみを対象とする

詳細

1回目の土日

何もせず。登録すらしていなかった。

月曜日、火曜日

登録して問題を見てみる。どう見ても焼きなまし。 AtCoderのヒューリスティックコンテストは、単に焼きなましやビームサーチをするだけの問題は出ないイメージがある。面白くないからね。でも、この問題は焼きなましにしか見えないし、問題応じた工夫の余地があるようにも見えない。この問題で焼きなましに頼らずに工事日を決めるのは無理だよね……？　どういうこと？

ところで、この頂点数で全点対間最短距離を求めるのは無理では？　ワーシャルフロイドは O(N³) だが……。ローカルテスターを見たら、各頂点に対してダイクストラ法を使っていた。ああ、辺数が O(N) だから、こっちのほうが速いのか。

水曜日

スコア計算を実装して、工事日を1, 2, 3, ..., K, 1, 2, ... と順番に割り振ってみる。

（絶対スコアで）47,705,877,230点。

焼きなましを実装。イテレーションが100回くらいしか回らない。なるほど、「素直な焼きなましでは全然速度が出ないでしょ？　さあ、どうしますか？」という問題なのか。

39,292,621,530点。

孤立する交差点ができてる。問題設定的に（たぶん）孤立する交差点は消せるようになっているので、孤立する交差点を消さないことには話にならないだろう。

木曜日

全点対間距離の計算は重すぎる。 1個の頂点と他の頂点の距離でもいいだろ。少なくとも、孤立する交差点は検出できる。どれか1個を選べと言われたら中央に近いものだよね。読み捨てていた X と Y を活用。スコアは×Nをして、元のスコアに合わせた。桁くらいは合うはず。焼きなましの遷移確率の計算では、大小関係だけではなく、差分にも意味がある。

イテレーションが数万回くらいは回るようになり、孤立した交差点が消えた。

776,408,368点。

これがスタートラインか。

金曜日

中央の交差点からの距離では、円周方向の道路を通らない。パッと思いつく回避策は、1個ではなく、複数の交差点からの距離を見ること。でもその分計算は重くなる。

ある道路を工事する日付を変えるとき、最も影響が大きいのは、その道路の両端の交差点である。工事する道路から遠く離れた交差点同士の距離は、全く影響を受けないか、遠回りも容易だろう。たぶん。

焼きなましの試行のたびにスコアの近似方法が変わっているわけで、この差分を足し合わせていくとスコアがマイナスになる。こんなんで大丈夫かと思ったけど、真のスコアも下がっているの大丈夫っぽい。

684,397,753点

このアイデアは他でも使えそうだ。スコアを近似するのではなく、差分を近似しても良いと。

この辺で、制限時間の6秒を10分にして動かしてみる。これには2個の意味がある。

1個は、高速化に意味があるのかが分かること。 100倍高速化すればこのスコアが取れるということである。だいぶスコアが小さくなるので、意味はありそう。

もう1個は、最適に近い解がどのような解なのかが分かること。軽い計算でそのような解が作れるようになると嬉しい。結果はこんな感じで、なんか工事する道路がパスのようになる。

なぜ？　工事する道路はばらけていたほうが良いのでは？　これが分からずに終わり。もっとちゃんと考えれば良かった。

解説放送によると、ある道路が工事中のときそこは遠回りをするようになる。その遠回りというのは、工事中の道路の直前で回避するのではなく、もっと大回りをする感じ。なので、周囲の道路も工事して良いと。なるほど。

www.youtube.com

各日に工事する道路の本数は多少偏る。均等に割り振るのが最適なら K の制約は要らないわけで、偏るだろうなとは思っていた。でも、 K まで使いきる感じでもないな。良く分からん。

まずはスコア大きく悪化する孤立した交差点を消すことが重要。孤立した交差点の有無でスコアが大きく変わるので、このときは細かなスコアはどうでも良い。幅優先探索で数頂点が連結しているかどうかを調べるだけなら軽い。数頂点が繋がっていれば、そこに繋がる道路も多いわけで、それらが同時に工事される確率は無視できるのでは？　先にこの軽い版で孤立した交差点を消してみるか → 意外と固まった数頂点の周囲の道路全部工事していることがある。ボツ。

周囲のほうの道路とかどうでも良いよね。重要なのは通る回数が多い中央部分。焼きなましで中央のほうが選択される確率を上げたら良いのでは？ → 別に良くなかった。ボツ。

スコア計算のとき、全ての頂点との距離を調べる必要ある？　近い128頂点くらいで良くない？　→　良かった。

598,947,065点

土曜日

dijkstra(d, p) を d 日目の頂点 p から各頂点への距離を返す関数、 R[m] を道路 m を何日目に工事するかの変数とし、 R[m] を d0 から d1 に変えるときのスコアの差分を今はこのように計算している。

long long diff = 0;
R[m] = d0
diff -= sum(dijkstra(d0, U[m]));
diff -= sum(dijkstra(d0, V[m]));
diff -= sum(dijkstra(d1, U[m]));
diff -= sum(dijkstra(d1, U[m]));
R[m] = d1
diff += sum(dijkstra(d0, U[m]));
diff += sum(dijkstra(d0, V[m]));
diff += sum(dijkstra(d1, U[m]));
diff += sum(dijkstra(d1, U[m]));

ダイクストラが8回でなかなか重い。式変形をすると、これで計算できることが分かる。

long long diff = 0;
R[m] = d0;
DU = dijkstra(d0, U[m]);
DV = dijkstra(d0, V[m]);
for (int i=0; i<N; i++)
    diff -= max(0LL, abs(DU[i]-DV[i])-W[m]);
R[m] = d1;
DU = dijkstra(d1, U[m]);
DV = dijkstra(d1, V[m]);
for (int i=0; i<N; i++)
    diff += max(0LL, abs(DU[i]-DV[i])-W[m]);

さらに、 dijkstra(d0, U[m]) と dijkstra(d0, V[m]) はだいたい同じような更新順序になるので、 DU[p] か DV[p] のどちらかが更新されたら p に繋がっている距離を更新という感じでまとめられた。

また、 d0 から d1 に変えるコストを計算するときに、ついでに d0 から d2 や d0 から d3 も計算すると、 d0 の値が使い回せてお得。全ての日を候補にしたら（イテレーションが回らなくなるから？）返って悪くなったので、最大8日を候補にした。適当。

593,323,301点

スコアがほとんど変わっていないのは、近い128頂点を見るというのを止めて、全ての頂点を見るようにしたから。近い頂点というのは道路の状況によって変わるので、まとめられない。

ここで近いと言っているのは道路を辿って移動する距離。直線距離で対象を決めれば、道路の状況が変わっても対象が変化しないか。絞りすぎると上手くいかなかったので、直線距離が300未満の頂点を対象にした。本当は N や M の値によって変えるべきかもしれない。

549,097,144点

日曜日

焼きなましでは、制限時間に達したときに温度が0になるようにしている。最後の最後まで悪くなる遷移もする可能性がある。これでスコアが悪化することを防ぐために、最後の状態ではなく、これまでの最高スコアのものを出力するようにしている。普通はこれで良いと思うのだけど、遷移の度にスコアの計算方法が違うから、スコアの値がおかしくなっていて良くなさそう。最後0.6秒くらいは温度を0（山登り）をするか。

549,594,670点

ちょっと悪化。でも、このほうが良いと思うんだよな。運が悪いだけでしょ、とそのままにした。本当はローカルで1,000テストケースくらい回して決めたほうが良い。

あと、これまでのベストではなく、最終結果を出すようにしたほうが良いかも……と思ったが、これは結構悪化したので止めた。

ちょっとお出かけ。

終了30分前にくらいに帰宅して、そういえば時間制限を5.5秒にしていたけど、実際の実行時間が5.6秒くらいだったことに気が付いた。もうちょっと攻めても大丈夫だろうと、時間制限を5.8秒に。

549,475,202点

やり残したこと

とにかくダイクストラ法が重い。ダイクストラ法はフィボナッチヒープというのを使うとオーダーが改善するらしい。理論的には速いというものではなく、ちゃんと速くなるらしい。

rsk0315.hatenablog.com

なんか難しそうで諦めた。でも、コンテスト終了後に言及している人がいないので、わりと綺麗な平面グラフである今回の問題では役に立たないのかもしれない。むしろ、ただのFIFOキューのほうが速いとか何とか。

ダイクストラよりSPFAの方が速かった。まぁ平面グラフなのでそんなもんなのかも。 https://t.co/pF1T0ABJbr #AHC017
— not@Optuna本2/21発売 (@not_522) February 5, 2023

2023-01-09

GoProで撮影したタイムラプスのフレームレートをFFmpegで良い感じにする

この前GoPro HERO11 Blackを買った。数時間の何かを記録するとき、普通に動画を録画すると、バッテリーもSDカードの容量もPCのストレージもすぐに尽きてしまう。そういうときにタイムラプスが有用。タイムラプスとは、本来は写真を繋いで動画にしたものらしいけど、普通に動画として撮影しているので、単に10倍速とか20倍速とかの早回しの動画。

1個問題があり、GoProのタイムラプスは25 fpsで撮影される。PCのモニターは一般的には60 fpsなので、これに合わせたフレームレートにしたい。また、なるべく情報が残っていたほうが良いので10倍速で撮影するけれど、Twitterに投稿するときなどにはもっと早くしたい。このとき、中途半端な速度にするのではなく、残るフレームが一定の間隔になってほしい。まあ、25 fpsだったり残るフレームの間隔が一定でなかったりして気になるかというと、そこまで気にならない気はする。自己満足ではある。

動画編集ソフトを使うのではなくFFmpegでお手軽に変換したい。フレームレートの変換とフレームの間引きが混じってややこしいので、メモしておく。

フレームレートの変換の色々は、このページが詳しい。

nico-lab.net

ffmpeg -r 240 -i GX012345.MP4 -f lavfi -i aevalsrc=0 -map 0:0 -map 1:0 -shortest -vf framerate=60 -s 1920x1080 -b:v 100M output.mp4

というコマンドが良いのではないだろうか。 240 の部分は、60の倍数で適切な値にする。240で、元々のフレームレートの 240/25 = 9.6 倍になる。

以降は各オプションの意味。なお、一般的にLinuxのコマンドはオプションの順番に意味は無いが、FFmpegの場合は意味がある。位置によって、そのオプションが入力に対して効くのか、出力に対して効くのかが変わる。

-r 240

変換元の動画が25 fpsのところ、240 fpsという扱いにする。フレームの間引きはされない。動画の長さが 25/240 になる。

-i GX012345.MP4

変換元の動画。ファイル名は動画に合わせて変える。

-f lavfi -i aevalsrc=0

無音の音声を作る。

-map 0:0 -map 1:0

0番目（0始まり）の動画（ -i GX012345.MP4 ）の0番目のトラック（GoProで撮影した動画では映像）と、1番目の動画の0番目のトラック（ -f lavfi -i aevalsrc=0 で作った無音の音声）を組み合わせて、次に流す。

-shortest

音声と映像の短いほうが終わったら、動画全体の映像を終了する。 -f lavfi -i aevalsrc=0 は無音の音声を作り続けるので、これを付けないと終わらない。

この辺のオプションを付けずに音声がそのままだと、映像が短くなるのに音声が元の長さのままで、最後のほうが音声だけになってしまう。GoProで撮影したタイムラプスには無音の音声が付いているので、別途無音の音声を生成したりせず、単に -shortest を付けるだけでも良さそうだが、なぜか上手くいかなかった。このチケットの話と関係がある？　謎。

trac.ffmpeg.org

無音の音声を付ける意味

なぜ無音なのに音声トラックを付けるの？　音声トラックを消してしまっても良いのでは？　という話。上の3個のオプションの代わりに -an を付ければ音声トラック無しの動画になる。問題が無いならそれでも良い。動画を投稿したり編集したりするときに、映像のみの動画だとトラブルことがある。だから、GoProも無音の音声を付けているのだと思う。

-vf framerate=60

フレームの間引きによってフレームレートを60 fpsにする。 -r 240 にした場合は4フレーム中3フレームが消えることになる。

-s 1920x1080

どうせなら高解像度のほうが良いと思って4K（3840x2160）で撮影していたのをFullHD（1920x1080）に変換。撮影するときにFullHDにしていたり、出力も4Kにしたりするなら不要。

-b:v 100M

フレームレート。100 Mbps。適当に大きなビットレートにしている。FullHDの場合は10 Mbps、4Kで20 Mbpsくらいあれば、画質が気になることはないのではなかろうか。ファイルサイズが気になるなら適当に調整。動画の長さは元の動画の 25/240 になる。ビットレートはビットで、ファイルサイズはバイトであり、8倍違うことに注意。

output.mp4

ファイル名。適当に。

コンテナ、コーデック

MP4やMKVなどのコンテナフォーマットは出力ファイル名の拡張子から決められる。

コーデックはデフォルトではH.264（コンテナによって変わる？）。エンコードに時間が掛かるし、対応していないこともあるし、現状ではH.265にしなくても良いのではと思うが……H.265にするなら、 -vcodec libx265 を付ける。

なお、GoPro 11はH.264で録画することはできず、H.265のみになってしまった。（特許の問題で）H.265は全然普及しないと言われ続けていたけれど、世の中はじわじわとH.265に移りつつあるのかもしれない。

2022-11-21

HACK TO THE FUTURE 予選（AtCoder Heuristic Contest 016）参加記

atcoder.jp

github.com

19,937,073,060 点で暫定77位。

追記。

システムテストは、825,977,155,719点で74位。

問題概要

整数 M とエラー率 e が与えられる。自分の作ったプログラムはそれに対して N を決めて、 N 頂点のグラフを M 個返す。ジャッジは0以上 M 未満の整数 x を決めて、対応するグラフを選び、各辺を確率 e で反転させ、頂点をシャッフルして渡してくる。それに対して整数 x を答える。正解率が高いほど、 N が小さいほど高得点。これが絶対スコア。

採点は相対スコア。各ケースごとに、参加者中で最も高いスコアの何%のスコアを得られたかが相対スコアで、これが順位付けに使われる。こんな採点方法もあるのか。 e が大きいと絶対スコアが何桁も下がるので、それの対策だろう。

しかし、普段のAHCだとスコアを徐々に上げていくのが楽しいが、相対スコアだと他の参加者が最高スコアを更新すると自分のスコアが下がるんだよな……。賽の河原で積み上げた石を崩される感。

11月16日（水）

やる💪 #HTTF
HACK TO THE FUTURE 2023 予選（AtCoder Heuristic Contest 016） - AtCoder https://t.co/5zOdnSudrc pic.twitter.com/IPCWG5GyqB
— kusanoさん@がんばらない (@kusano_k) 2022年11月16日

11日（金）からコンテストは行われていたけど、ここから参加。前の土日はSECCON予選に参加していたのでしょうがない。

とりあえず全部0を返すだけのコードを提出。

453,607点。

Gitのコミットメッセージにはスコアを入れている。順位表に出てくる相対スコアは他の参加者の提出によって変わるので、絶対スコアのほうが良い……と思ったけど、絶対スコアは絶対スコアで e が大きいところのスコアが小さすぎて分かりづらい。

提出は30分間隔の制限があるし、ローカルテスターで動かしてスコアを集計するのも面倒。ジャッジ側の実装は簡単なので、VC++でコンパイルしたときには50ケース実行してスコアを出力するようにした。

辺の本数にエンコードする。 0なら辺が0本、1なら1本、…。簡単ですね。問題ページのサンプルプログラムもこれ。ただし、サンプルプログラムは N が固定のところ、 M 未満を表現できる最小の N を使うことにした。

8,040,225点。

辺の本数にエンコードすると、1本でも違ったらエラーになってしまう。辺は最大4,950本もあり、 M は最大10なので、活用しないのはもったいない。 0なら0本、1なら10本、2なら20本、…とすれば多少のエラーには耐えられる。

単純に一番近いものを選べば良いかと思ったけど、これでは上手く行かない。エラーが起こると、辺の本数は、正規分布っぽく、中央値に移動していく感じになる。返ってきたグラフの変数が x 本のときは、 x 本になる確率が最も高いものを選べば良いはず。数式一発で答えが出そうだけど、分からん。無かった辺が増える本数をループで回して $O(N)$ で解いた。素直に掛け算したら浮動小数点数の精度が足りなくて無限大になる。中身は全部掛け算なので、こういうのはlogを取って足し算をすれば良い。

158,501,069点。

間隔は、 w = (N*(N-1)/2-1)/(M-1) として、0本から M 本までを使うようにしている。これ、たぶん、等間隔ではなく、中央辺りは見分けが難しいから広く取るとかしたほうが良いよね。これもなんか数式一発で最適な方法が出てきそうだが……分からないので諦め。

統計検定2級を取ったけど、全て忘れていて何の役にも立たない。ヒューリスティックコンテストで、「この改善は本当に有意な改善なのか？」とか「どのくらいのテストケース数で試せば良い？」とかも分かるだろうし、もう1回勉強し直したほうが良いのかもしれない。

頂点を3個のクラスタ（完全グラフ）に分けて、そのクラスタのサイズに情報を埋め込んでみる。完全グラフなら辺が大量にあるので、エラーで多少辺が消えても、クラスタっぽいところを選べば元通りのはず。 2個のクラスタだと $O(N)$ 種類の情報しか埋め込めなくて足りないが、3個だと [tex:O(N²)] なので充分。クラスタのサイズはなるべく100/3に近くなるようにした。

386,149,705点。

11月17日（木）

全ての頂点をクラスタに含めようとするから3個必要になるのであって、クラスタに含めない孤立した点も許せば、クラスタ2個でいけるんじゃない？

369,856,736点

いけませんでした。クラスタ3個に戻そう。浮いている頂点か、たまたま辺が多めに消えただけの頂点かの判別が難しい。「どのクラスタに属していますか？」のほうが簡単。

N=100 で固定していた。 M や e が小さいときは、100%正解するので、そんなに要らない。 M と e を10等分くらいに区切って、それぞれごとに最適な N を事前計算。 e が大きいときに N が小さくなるのが面白い。どうせ当てずっぽう以上の正解率にならないなら、 N を小さくしたほうがスコアが上がるということか。

819,627,301点

ここからどうするか。この問題は e や M の値によって解き方が全く変わると思う。自分がどこが劣っているのかを知りたい。最高スコアに近いスコアを取っているケースよりも、最高スコアから大きく劣っているケースを改善するほうが簡単なはずである。

相対スコアを利用して知ることができる。特定のケース意外をわざとREにして、そのときの相対スコアと、AC数から期待されるスコアを比べれば良い。

full:  AC=50 19,616,049,784
e<0.1: AC=13  5,364,873,351 / 5,100,172,943 = 105 %
e>0.3: AC=12    658,952,483 / 4,707,851,948 =  14 %
M<30:  AC=11  3,892,215,217 / 4,315,530,952 =  90 %
M>81:  AC=10  4,278,657,239 / 3,923,209,956 = 110 %

e が大きいときが最悪。 e が大きいときがこれだけ低いのに、 e が小さいときが100%ちょっとということは、 e が小さいときもダメ。 M は、まあそんなに偏りは無いか。

まずは、方法は思いついていてやるだけだった e が小さいほうを何とかする。

グラフの同型判定は難しい問題である。でも、6頂点でもグラフは156個もあって、今回の100未満の整数を表現するには充分。 6頂点くらいなら同型判定もできる。

oeis.org

グラフを送って素直に同型判定をするだけの処理を実装。 e=0.0 はこれで良い。 5頂点のグラフが34個、4頂点のグラフが11個なので、 M<=34 ならば e=0.1、 M<=11 ならば e=0.2 でもこれを使うようにした。ちょっとくらい間違えても N が小さいというメリットが勝る……はず。

1,114,762,760点

クラスタ3個のサイズにエンコードするやつ、サイズが1刻みだけど、 M が小さかったら3刻みでも良いよね。 2刻みは間になったときにどちらだったのかが分からないのでNG。

1,296,211,660点

11月18日（金）

e が大きいところをどうするかな……。

16頂点の完全グラフを6個作って、そこに6頂点のグラフを埋め込んだらどうだろうか。

こういうイメージ。 16頂点の完全グラフには辺が120本もあるし、16頂点の完全グラフ2個の間には辺が256本も引ける。これだけあれば e=0.4 程度のエラーへの耐性は充分だろう。

だめだった。完全グラフの間に辺を引きすぎると、くっついてどこが完全グラフか分からなくってしまう。 64本程度でもエラー耐性としては充分かもしれないと思ったが、最大64本ところを0本や64本にするのと、最大256本のところに64本では見分ける難易度が違う。

パラメタを探索したら、 e が大きいときは諦めて N を小さくしていたけど、どうせ諦めるなら N=4 のほうが良い。クラスタのサイズにエンコードするやつは N に下限がある。 M と e の組み合わせ全てに対して、どれが良いのかを調べるか。このときについでに辺の本数にエンコードするやつも含めたら、 M が小さく e が大きいときに出てきた。へー。

黄色がクラスタのサイズ、赤いところがグラフの同型判定、黄緑色が辺の個数、緑が N=4 で固定で0を返す。

ついでにクラスタのサイズにエンコードするときの、 N （上）とサイズの間隔（下）。

時間が掛かるので、こちらは間隔が粗め。クラウドの活用を考えても良いかもしれない。たぶん、手元のPCで1日掛かるくらいの計算なら、数百円＆1時間くらいでできそう。

11月19日（土）

4個のクラスタにエンコードしたら良い感じになりませんか？ → なりませんでした

16頂点の完全グラフを6個作って～というやつ、完全グラフ間の辺を引けるところには全部引いちゃって良いのでは？　今までは16個の頂点間に辺が多いかどうかを見ていたけど、他のどのグラフに辺が伸びているかどうかで区別ができるのでは？　もしそれも同じなら区別する必要が無い。つまり、隣接行列で見たときに似ている行をクラスタとしてまとめれば良い。

クラスタの16頂点は完全グラフにしていたところ、逆に辺を全て無くしたらちょっと正解率が上がった。ああ、自己辺は無いから、似ているところをまとめるときに、都合が良いのか。

この辺で、

 # ## 
# ### 
 #  # 
##   #
### #

こういう隣接行列のグラフを

    ####    ########    
    ####    ########    
    ####    ########    
    ####    ########    
####    ############    
####    ############    
####    ############    
####    ############    
    ####        ####    
    ####        ####    
    ####        ####    
    ####        ####    
########            ####
########            ####
########            ####
########            ####
############    ####    
############    ####    
############    ####    
############    ####

こうしていることになるのだと気が付いた。ビジュアライザをちゃんと使っておけばもっと早く気が付いたかもしれない。もったいない。

この辺でもう1回パラメタごとのスコアを調べてみる。

full:   AC=50 20,588,242,805
e<0.1:  AC=13  6,191,925,460 / 5,352,943,129 = 116 %
e>0.3:  AC=12  1,665,638,029 / 4,941,178,273 =  34 %
e>0.35: AC= 7    172,974,952 / 2,882,353,992 =   6 %

e>0.35 も調べてみたけどボロボロだ。今何とかしようとしている方法なら、エラーにも強いと思うんだよな。

11月20日（日）

最終日。

16頂点のクラスタにまとめる
クラスタ間に辺があるかどうかで6頂点のグラフにする
N=6 のグラフの同型判定

ということをしようとしている。 1番目が上手くいかない。

そもそも N=6 のグラフなんて（使っているのは）100個しかないのだから、100個それぞれに対して、↑の図示の下のほうの隣接行列を用意して、辺を入れ替えてどれだけそれに近づけるかを焼き鈍しすれば良いよね。先にクラスタを作るより楽そう。なんかフローとかを使って何とかならないかな～と考えているときに、 N=100 のグラフの同型判定そのものを解こうとしていることに気が付いた。

最終的に、 e が大きいところでは、4回実行してときどきこの手法のほうが良いと出てくるようにはなった。が、まあ、たまたまだろうし、たまたまでなくても終了1時間前にこれをサブミットするのは怖い。で、土日は結局何の成果も得られずに終わり。

グラフの同型判定の計算量は良く分かっていないけど、難しい問題ではあるので、同型判定で解こうとしてはいけないんですね～と思っていたけど、結局同型判定に戻ってきたので、ちゃんと考えるべきだった……。

2022-08-20

コミックマーケット100（C100）振り返り

第100回目（！）のコミケでCoppersmith法についてのコピー本を頒布した。これについて、誰向けかも分からないような話をつらつらと書いていく。

CTFのCryptoで使うCoppersmith法を解説する本

Coppersmith法とは？

数学とか暗号とかに興味の無い人は、ここは飛ばしてください。興味のある人はここだけでも読んでください。

Coppersmith method - Wikipedia

$F(x)=x^{n}+a_{n-1}x^{n-1}+\dots+a_1 x+a_0$ について、 $F(x)\equiv 0 \mod M$ の $\left|x\right| \leq M^\frac{1}{n}$ を満たすような解を多項式時間で求めるアルゴリズムである。

一瞬、「解の制約からmodの意味が無くなるのでは？」と思うかもしれない。しかし、 $x^{n}$ は $M$ を超えないが、 $a_1 x$ などは超える。

中ではLLL格子基底簡約を使っている。 LLL基底簡約の使い方の一種として、 $a_0 y_0 + a_1 y_1 +\dots + a_n y_n \equiv 0 \mod M$ を満たす小さな $y_0,\ y_1,\ \dots\ y_n$ を求めるというものがある。今度は「 $x^{0}=y_{0},\ x^{1}=y_{1},\ \dots,\ x^{n-1}=y_{n-1}$ と置いて、その使い方をするだけでは？」と思うかもしれない。解の制約がもっと厳しいならこれで解けるが、Coppersmith法の制約は無理である。雑に言うと、 $y_{0},\ y_{1},\ \dots,\ y_{n-1}$ のビット数が $M$ のビット数を超えるので解がいくらでも出てくる。

で、どうするの？　というのが本題。上記のようなLLL基底簡約の良くある使い方をしていなくて面白い。

この話、終わった後に書いていないで、頒布物の紹介ツイートにでも書いておけば、頒布数が違ってきた気もするな。後述のように時間が無かったのでしょうがない。

ちなみに、「Finding a Small Root of a Univariate Modular Equation」という論文に書かれている。ガチ勢には、「で、その本の論文からの差分は何なの？」とか訊かれそうだな。特に無いので、論文を読んでください。

参加サークル数

www.bigsight.jp

コミケの会場の東京ビッグサイトは、元々東展示棟6ホール＋西展示棟4ホールだった。このうち西展示棟の2ホールは企業向けで、サークル向けは残りの8ホール。これで3日開催。

東京オリンピックのために東展示棟が8ホールになり、南展示棟4ホールも新設された。一方、オリンピックのために使えない棟があったりもしたが、今はフルに使える。で、開催期間は2日間。

単純計算でだいたい同じくらいのサークルが入りそうだが、入場券確認＆検温後の待機スペースに割り当てたり、コスプレに割り当てたりで、結局サークル向けに割り当てられるホール数は以前と変わらず。それで日数が少なくなった上に、感染症対策でサークル間の空間を広く取ったりで、サークル数は半分近くに減っている。

時系列

2月頃。前回のC99は来場者もそうとう絞っていて、本を買いに来てくれる人もほとんどおらず、「次は参加しなくて良いかな」と思っていた。でも、第100回は出られるなら出たいなと申込み。上記のように参加できるサークル数が少なく、100回記念で申し込むサークルも多いだろうし、当選することは期待していなかった。期待していなかったので特に準備もしなかった。

6月頃。当落発表。受かっていた。まじか。本を書こうと頑張り始める。当初は別の本を書こうと思っていた。

7月頃。新型コロナ第7波。本は書けないし、感染者数の増加で「これはまた中止になるのでは……」という感もあり、やる気無し。ちなみに、印刷所に製本を頼む場合、基本的には7月末～8月頭くらいが入稿の目安。多少は金で解決できる。数割値段が高い代わりに、締切りが数日伸ばせるという「特急料金」があったりする。これが資本主義か。

いや、でも、もう無理では。「中止になったら原稿を書く必要も無いんだよな……」で「コミケ中止」でTwitter検索をしていた。「お前、新型コロナ下で音楽フェスが開催されていること文句を付けているけど、その名前の『@C100～』は何だよ。コミケも中止しろ」などの揉め事が起こっていたりした。

7月末頃。中止になると思っていたけど、運営のスタンスとしては「お上に中止にしろと言われない限りはやる」で、政府も緊急事態宣言を出すつもりは無さそう。本を出さなかったからと言って誰かに怒られるわけではないけれど、せっかくの100回だし何とかしたいよなぁ。テーマを絞ってページ数を減らしてのコピー本なら何とかなるのでは？　で今に至る。

コピー本

コピー本とは、コンビニのコピー機などで印刷してステープラー（ホチキス）で綴じた本である。少部数なら印刷所に頼むより安いし、前日に作業をしても間に合う。代わりにクオリティは落ちる。

kinko'sかセブンイレブンなどのコンビニのコピー機を使えば良い。どちらも「同人誌が作れるよ」とアピールしている。どちらでも変わらなそうなものだが、できることできないことが微妙に違っていて悩ましい。

www.kinkos.co.jp

kinko's。プリンタにフィニッシャーが付いていてステープラー留めもしてくれる。さらに、表紙を別の紙にすることができる。たとえモノクロ印刷でも表紙が厚紙になっているだけで、だいぶ印象が違う。それならkinko'sで良いのでは？　と思うが、小冊子印刷をする場合は、なぜかUSBメモリから印刷することができない。一旦印刷してコピーする必要がある。画質が落ちるだろ……。有料で店頭のPCを借りるとできるという噂も聞いたので、今度試してみたい。

昔は24時間営業だったが、新型コロナの影響で24時間営業は取り止め。土日祝日が休みの店も多いので注意。今回のコミケは、前日は平日だが、前々日が祝日だった。

www.doujinshi-print.com

セブンイレブン。USBメモリから直接小冊子にできる。しかし、ステープラー留めをしてくれない。 USBメモリで持ち込むのではなく、インターネット経由でデータを送ることもできるが、1枚（両面の場合は1面）10円のところが、20円と倍になる。大量に印刷しようと思うとUSBメモリが必須。

kinko'sで表紙を厚紙に印刷して、セブンイレブンで本文を印刷するという合わせ技にすることにした。

www.doujinshi-print.com

セブンイレブン（kinko'sも？）のプリンターは用紙の縁ギリギリまで印刷することができない。それでは端のほうが切れてしまって困るので、デフォルトでは「ちょっと小さめ」に印刷するようになっている。本文は文章で余白があるからそんな配慮は要らないんだけど……ということで、「原寸印刷」ができるようになっている。が、しかし、小冊子印刷の場合はなぜか原寸印刷ができない。なぜ？　上記のページだと縮小されることを見越してちょっと大きめのサイズで作れと言っている。 Re:VIEWで作るPDFでもめっちゃ頑張ればできるのかもしれないが、やりたくないぞ……。

B5の元データを小冊子のように面付けしたB4両面のデータを作り、小冊子印刷ではなく普通に両面印刷するという手を思いついた。そのデータをどうやって作るのかというと、手元のPCでPDFを開いて小冊子印刷の設定で印刷してPDFにすれば良い。今でこそ各ソフトからPDFで直接保存ができるけれど、元々PDFといえば印刷でプリンタとしてPDFを選ぶものだった（よね？）

手元のPCの印刷のところには「Adobe PDF」と「Microsoft Print to PDF」が出てきた。普通に考えれば、本家本元の「Adobe PDF」のほうがクオリティが高そうなものだけど、なぜか黒が濃いグレーになり、画像の画質がとても落ちてNG。もしかしたら設定で何とかなったのかもしれないが、分からん。「Microsoft Print to PDF」だと色は問題無し。画像の画質は、「Adobe PDF」よりは良いが、やっぱりJPEGにされてちょっと画質が落ちる。画像については、IllustratorからPNGで書きだしていたものをEPSにしたら劣化しなくなった。

PDFをデータそのまま配置だけどうにかしてくれれば良さそうなもので、そういう有料ソフトもあったが、試してはいない。誰か試したら感想を教えてほしい。

www.bookletcreator.com

中綴じ。針の向きを変えられるホチキスが売っていて、とりあえずこれを使えば中綴じができる。

www.max-ltd.co.jp

とりあえずはこれでも何とかなるのだけど、紙がズレないようにするのがなかなか難しい。本気を出すならこれ。

www.max-ltd.co.jp

東急ハンズで「高いなぁ」と思いながら定価（4,400円）で買ったけど、ヨドバシ.comだと半額くらいで買えるな。まあ、こんな数が出なそうな商品を実店舗で安売りはできないか。半分に折ってから綴じようとすると紙がずれがちなので、このホチキスのガイドをきっちりB5に合わせて、綴じてから折ったら良い感じだった。

もっと本気を出すならこれか。針も普通のホチキスよりちょっとゴツいやつで良さそう。誰か買ってみてほしい。

www.max-ltd.co.jp

針はステンレス製のものを使うと良い。ちょっと高いが、元が安いので誤差。ただ、上の「もっと本気を出す」やつ用の11号針はステンレス製が無い。

www.max-ltd.co.jp

最後に、中綴じ用のホチキスを使っても、どうしても多少は紙がずれるので、昔自炊用に買ったゴツい裁断機で端をちょっと切った（化粧断ちと言うらしい）。これでだいぶ見た目が良くなる。 B5ではなくなるので、他のB5の本と揃わなくなるが……端がずれていたらどうせ揃わないので、まあ良いだろう。どうせ端を落とすなら、セブンイレブンのプリンターの「ちょっと小さめ」のままで良かったかもしれない。

www.durodex.co.jp

なかなかのクオリティでは（自己満足）。

コミケ当日

前回のC99よりはだいぶ人が増えているけれど、新型コロナの前に比べるとまだまだ頒布数が少ない。いや、私のは急遽作ったコピー本だし、ろくに宣伝もしていないが、周囲のサークルを見る感じ。コミケに行ったことが無い人のイメージは、大行列で本が飛ぶように売れているというものかもしれないが、あれは一部の人気サークルだけであって、大半のサークルは元々そんなことはない。でも、もうちょっと売れていたような気がするんだよな。

会社の周りの飲食店は当然人気の店と不人気の店がある。新型コロナに伴うリモートワークで客が減り、客の合計が半分になるなら、てっきりどの店も客が半分くらいになると思っていた。実際は、人気店はたいして変わらず、不人気店から一気に客が減って、次々と潰れていった印象がある。コミケもそんな感じなのか、大手のサークルは新型コロナ前と客数があまり変わっていなかった気がする。

コミケ2日目

2日目は（サークル参加ではない）一般参加。受付時間09:00～09:30（E枠）のチケットを買っていた。遅れたらどうなるんだろうね？

【Ｑ６】一般参加の受付時間内に間に合わなかった場合、どうすれば良いですか？

【Ａ６】受付時間については、設定された時間以降であれば受付後入場可能です。ただし、アーリーチケットであっても、午前入場の開始準備が始まった後については、午前入場待機列の最後尾に並んでいただく場合がありますので、予めご了承ください。

https://www.comiket.co.jp/info-a/C100/C100EntryTicket2.html

こう書かれているけど、細かい扱いが分からない。一番後ろに回されても困るし、ちゃんと時間通りに行こう……と思っていたが、初日の疲れで寝坊。特にどうということもなく、その時点で待っていたG枠などの人達を横目にすっと入れた。次も同様の形式かもしれないのでメモ。

ゆりかもめで行った。「一般参加はあっち」と言われて歩いて行き、受け付け前の人達の横を通って、ぐるっと回って元の場所に戻ってきた。りんかい線で来るのがデフォであって、りんかい線ならそんなことも無かったのかもしれない。次は朝はりんかい線で行こう。メモ。

2022-08-17

RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013）参加記

atcoder.jp

github.com

暫定201,809点、169位。システムテスト後は8,566,178点、165位。

Seed 0から7の結果。

コンテスト開始前

1位の方の回答がTシャツに！？

1位の方の回答がTシャツに！？　これは欲しい。ということは、「映える」ようの結果が出てくる問題なのだろうな。どんなのなんだろう。

8月9日～8月14日

コミケが忙しかった。問題は見ていたけど、特に考えてはいなかった。

考察

後から参加する人の特権として、順位表から得られる情報が考察に使える。順位とスコアをグラフにプロットしてみる。

順位表をそのままExcelに貼り付けたらセルが結合されていて面倒そうだったので、JSONを保存してPythonでゴニョゴニョ。 AtCoderのスコアって、内部的には実際のスコアを100倍した整数なのか。

25万点のところでグラフが折れ曲がっている。 25万点というスコアは、1種類のコンピューターを全てクラスタにしたときに得られるスコア。そこから2種類目のクラスタを大きくできるかどうかに壁がある？　5000点でも曲がっている。これは……なんだろうね。

クラスタに他の種類のコンピューターを混ぜるべきかどうかで、やることがだいぶ変わりそう。スコアを考えてみると、50台のコンピュータのクラスタ2台よりは、間に他の種類のコンピュータを混ぜてでも繋げたほうが得だな。

ヒューリスティックコンテストと言えば、手法は焼き鈍しかビームサーチ。移動にちょっとビームサーチっぽさを感じるけど、そんなに動かせないし、焼き鈍し一択だろう（貪欲的な解法は完全に発想から抜け落ちていた。結果的にそっちのほうが正解だったっぽい）。

接続と移動の合計がコンピューター数。ということは、クラスタの個数だけコンピュータを移動することができる。この問題設定の意味は……？　とか考えていた。

焼き鈍し

まずは、移動は無しで、接続を切ったり繋げたりで焼き鈍し。本当は、クラスタの構成を変えずに繋げ直す（一度ループを作って別の場所を切る）というのができると良いのだろうな。切って繋げては一度スコアの谷を下りることになるので、遷移がしづらい。でも、時間が無いからそんなのの実装は無理。

10台のクラスタを11台にするのと、90台のクラスタを91台にするのとでは、スコアの上がり方が全然違う。これを同じ温度で扱うのは無理があるだろう。どうするかな……。スコアは台数の2乗に比例するので、スコアの平方根を使えば良いか。時間が無いので、ちゃんと検証はしていない。適当。

91,223点

上位陣が30万点であることを思うと、まずまずのスコア。方針は合っていそうだな（合っていなかった）。

線を繋ぐときに交差する線を切る

横の赤線が配線済みで、縦の青線を配線しようとするとき、今まで単に諦めていた。焼き鈍しの過程で、赤線が切れた後に、青線が繋がることを期待するしかない。それは無茶なので、線が交差していたら、諦めるのではなくその線を切るようにしてみた。

99,082点

サーバーの移動

そろそろ移動を考えるか。

移動の回数について。

これは、ローカルテスターに入っていた100個のテストケースから今の実装で得られた結果について、Kの値でグラフを分け、Nの値を横軸に、配線が終わった後の残り手数を縦軸に取っている。サーバーを移動したことによって配線しやすくなることを考慮して、このグラフのちょっと下あたりの回数を移動に割り当てれば良いだろう。本当は移動回数を色々と変えて、どのくらいを割り当てるのが最適なのかを検証するべきだろうが、そんな時間は無い。

移動の方法について。移動の順序まで考えないといけないのは面倒。ビジュアライザの結果を見るに、1マス移動するだけでもだいぶマシになりそう。で、さらに、他のサーバーの元の位置も現在の位置も移動先には選択しないとすれば、互いに干渉しなくなって楽になるはず。

移動の結果の評価について。上下左右を見て、最初にぶつかるサーバーが同種なら+1で良いだろ。時間が無いので適当。

最初に移動。その後で配線をするという作戦である。これは良くなくて、配線をしながら「ここにサーバーがあったらなぁ」というのを考えながら移動をするべきだろうが……どうやったら良いのか分からん。

184,088点

だいぶ良い感じになってきた。

種類によって重み付け

上位陣のスコアを見るに、全ての種類のサーバーで大きなクラスタを作るのは無理である。各種類がそこそこの大きさよりは、特定の種類だけ大きなクラスタになっているほうが良い。移動の段階で種類1だけ、スコアを5倍にしてみる。

201,809点

20万点を超えたし、運が良ければ景品をもらえる順位である200位以内にも入った。満足。終わり。

2022-06-05

AtCoder Heuristic Contest 011（AHC011）参加記

atcoder.jp

暫定35,184,653点（得点率70%）で89位。

追記：システムテストは2,098,827,035点（得点率70%）で89位のまま。

GitHub リポジトリ。

github.com

解の一例（seed=4）

img.atcoder.jp

最初の土日

無。5月28日（土）～6月5日（日）のコンテストで土日が2回ある。

月曜日

問題を見始める。

スライディングパズルで木を作る。問題の生成方法は、まずは全域木を作って、解くときの手数の上限回動かして崩すというものなので、全てが繋がった木が作れることは保証されている。 50%の点数が境目で、手数上限で全域木が作れると50%　手数がより少なければ点数が上がり、全域木が作れなければ、最大の木の大きさに応じて点数が下がっていく。

まだコードを書かずに、Twitterに上がるseed=0の完成図を眺めていた。全域木が完成している人は、空白が右下の人が多い。最初に正解盤面を作るときの空白は右下なので、右下の解があることは保証されている。しかし、右下以外の全域木も上がっているので、右下が必須というわけでもない。どういうことなのだろう。

そして、何をやってよいのか全く分からない。「なるべく大きな木を作りましょう」なら色々とやることはあると思うが、上がる画像を見るに、ある程度の順位を取るには、全域木が前提っぽい。普通に木を大きくしていくだけでは最後に詰まると思うんだよな。

火曜日

リポジトリを作って真面目に考え始める。（ちゃんとスライドさせるのではなく）タイルを浮かしても良いから並び替えて目標の全域木を作る → スライドパズルとして解いて目標の全域木にする　という方針が良さそうである。スライドパズルにはパリティがあって、（タイルを浮かして並び替えた）全ての盤面のうちの半分は作れない。しかし、この問題では最小サイズが35タイルなのにタイルは16種類で、必ず重複しているタイルがある。鳩ノ巣🕊️　そのタイルを入れ替えればパリティを変えられるので、必ず解ける。もちろん目標の全域木を決め打ってしまっては最適な解には辿り着けないけど、上述のように、普通にスライドさせて全域木を作るのはとても難しいだろう。

まずは見た目から入るとやる気が出る。盤面の出力。罫線素片（┗┏┃┻など）が使えそう……と思ったら、一方向にだけ出ているものが私の環境だと幅が違って合わない。結局罫線は諦めて、こうした。

   +     +     +-- --+-- --+-- --+
   |     |           |           |
   |     |           |           |
   +-- --+-- --+-- --+     +-- --+
         |     |     |     |     |
         |     |     |     |     |
   +-- --+     +     +     +     +
               |     |     |
               |     |     |
   +     +-- --+     +     +-- --+
   |     |           |           |
   |     |           |           |
   +-- --+-- --+     +-- --+     +
               |     |     |
               |     |     |
   +-- --+-- --+     +     +     +

全域木を作る方法。左側に出ているタイルの個数と右側に出ているタイルの個数は同数だよね？　その辺を考えると、実は、閉路ができないように、場面外に辺が出ないようにと作っていけば、詰むことが無かったりしない？　→　そんなことはなく普通に詰む。ですよね。 2個のタイルの交換を近傍として焼きなませばいけるだろう　→　あまり上手く行かない。 7割くらいは全域木ができるのだけど、失敗することも多い。

全域木を作るのは一旦置いておいて、目標となる盤面ができたときにスライドパズルとして解く方法を考えよう。手で解けるのだからそれをプログラムにすれば良いのだけど、とても面倒だな。左上から順に揃えていくことにして、左上から何個目まで揃っているかと、次に揃えるタイルが目標位置とどのくらい近いかをスコアにして、ビームサーチをすれば良い感じになってくれるのでは？　なってくれませんでした。各行の残り2個のタイルと最後2列は、一度崩してから並び替える必要があり、適当に書いたビームサーチではそこを乗り越えてくれない。

どちらもダメで、今回はサボろうかなと考え始める。

水曜日

種類ごとのタイル数が揃っている＆全域木ではない　から　種類ごとのタイル数が揃っている＆全域木である　を作ろうとしていた。これ、種類ごとのタイル数が揃っていない＆全域木である　からスタートしてはどうだろうか？　という発想に至る。

初期盤面。タイルの交点を中心にしたときに4辺のうち3辺が埋まっている箇所が必ずある。ここを回しても全域木であることは変わらず、タイルの種類が変わる。

これで焼きなましたら、だいたい全域木ができるようになった。タイルの種類を変えていく場合、焼きなましに失敗したらどうしようもなくなるという問題はあるが……まあ何とかなるだろう。

スライディングパズルパート。行ごとの最後2個のタイルについて、揃える過程に加点をして何とかした。

これで半分くらいは全域木が完成した50%のスコアを取れるようになった。サブミットしてみたらTLE。まあ、高速化の余地はまだいくらでもあるだろう。

木曜日

ビームサーチをする → 完成しなかったらパリティが違っていたと判断して、1箇所入れ替えてもう一度ビームサーチ　としている。1回目で完成したかどうかで実行時間が倍違う。実際に解こうとしなくてもパリティは調べられるので、調べる。

途中で止まって全く進まなくなることがある。状況を確認してみるとこうなっていた。

これ、先の図のポイントでは、4が1 ptの位置にいるので1 pt加算される。ここから2 ptの状態に進むには4を崩さないといけない。それができていなかった。隣に5があったら4が目標位置にあってもポイントを加算しないようにした。

全域木がたまに作れないことがある問題については、単に全域木を作るパートを複数回実行するようにした。ここは軽いので問題無い。

サブミットして27,529,855点。全てのケースで全域木が作れるようになると、25,000,000点以上になるので、ドヤ顔でツイートしてみる。なお、全てのケースで全域木が作れると25M点以上になることと、25M点以上なら全てのケースで全域木が作れていることは同値ではない。実際このときも、他のケースで点を稼いでいるから25M点を超えているだけで、全域木が完成しないケースもちらほらあった。

そういえば、

□rich 要る？
Sliding Tree Puzzleのseed=0で680556点を獲得!!!https://t.co/ZJs8SNYlTz #AHC011 #visualizer pic.twitter.com/doBr93BC4R
— kusanoさん@がんばらない (@kusano_k) June 1, 2022

こんなツイートをしたけれど、ビジュアライザの「使い方」に後から気が付いた。

rich モードにすると、ランダムノイズが入って同じ種類のタイルの区別が可能になります。

手間が掛かっているし、実用性もあった。同一の形状なら同じ模様だと思っていた。すみません。

金曜日

盤面を2次元配列で扱っていたのを1次元配列化。高速化に寄与するし、意外とコード的にも1次元配列のほうが楽。どうせ最後にはやるので最初からやりましょう。単純な書き換えではあるものの、どこかしらはミスるので、デバッグが面倒。

全域木から同じ種類のタイルを対応付けてスライドパズルの問題を作る部分で、今までは残っているものを貪欲に取っていたところを、距離の合計が最小になるようにした。いや、最小費用流とか全探索とかで厳密に最小にはできるだろうけど、面倒だったので適当に焼きなまし。簡単な問題だし、だいたい最適解になるだろう。たぶん。これがけっこう効いた。貪欲に取ってもだいたい最小になるんじゃないかと思ったけど、1次元で貪欲に取っているので、2次元での距離を考えれば、そりゃそうか。

今までは全ての行で左から右に揃えていたところを、左→右と右→左を交互にした。これは有効だろうと思っていたのに、あまり変わらず。まあ、悪くなることはないだろうから、いいか。

ビーム幅を盤面サイズによって変えた。手数上限が盤面幅Nの3乗で、1手あたりの処理は盤面の面積に比例するから、ビーム幅が同一ならば実行時間はNの5乗に比例ということで良いだろうか。 Nによる影響大きいな。

まだ100ケース中の数ケースで途中で詰まるものがある。見てみるとこの形だった。

この形の何がダメなのかパッと見では分からなかった。最後2個のタイルは全く揃っていない状態なので、次は4を右上に置こうとする。その時の手順を考えると、先の4と5が逆になった形に必ずなるので、揃った状態まで辿り着けない。こういうパターンが他にもありそうで怖いが……100ケースでは無くなったから、とりあえずいいだろ。問題が出てくる度に評価関数で1個1個対処するのではなく、ビームサーチ側で何とかしたくはある。

残り時間が少なくなったときにビーム幅を減らす緊急回避を入れる。これは単にTLEを回避することだけが目的ではなく、緊急回避があることによってビビらずにビーム幅を増やせるというメリットがある。今となっては手数が上限に達することはほぼ無くなったので、上限まで回しても間に合うようなビーム幅にするのは無駄。緊急回避モードに入っても意外とスコアが落ちなかった。最後のほうは残りマスが少なくて優劣が付かないからそりゃそうか。結局、緊急回避と言いつつ、数割はこのモードに入るようにしている。もっと考えを推し進めれば、ビーム幅がずっと一定 → 急に減らす　ではなく、徐々に減らしていくという手もありそうだが……やってはいない。

最後の土日

SECCON Beginners CTFと、Google Code Jam Round 3と、Pokemon GO Festで忙しくて、気が付いたら終わっていた。

パリティが合わなかったときにランダムに2個のタイルを入れ替えているけれど、これはタイルが遠いところになってしまう可能性がある。パリティが一致するようにしたまま焼きなますのは試したかった。

2022-05-15

ゆっくりMovieMaker4のFFmpegエンコードで出力した動画が再生できないときの対処法

manjubox.net

YMM4は、エンコード時にMediaFoundationとFFmpegが選べる。音声の動画全体に占める割合は微々たるものだし、高音質なほうが良いかなと思って、320 kbpsが選べるFFmpeg エンコードで出力している。

たまに、エラーも無く出力したのに再生できないことがある。

その度にエンコードし直すと時間が掛かってしまう。再生できない原因と修復方法を調べたのでメモしておく。

MP4は複数の「box」で構成されている。この内、mdat boxのサイズがなぜか間違って出力されるのが原因。

修復方法。

バイナリエディタを用意する。私はHxDを使っているけれど、何でも良い。選択した範囲のサイズを16進数で確認できる機能があると楽。

mh-nexus.de

「moov」という文字列で検索し、その4バイト前にカーソルを持ってくる。関係無いところがたまたまmoovになっているかもしれないので、周囲がスクリーンショットの雰囲気と似ているところ。最後のほうにある。

先頭に戻り、「mdat」という文字列の4バイト前を、Shiftを押しながらクリック。バイナリエディタが違って範囲選択の方法が違うなら、それに合わせて。選択した部分の長さを確認。 HxDならステータスバーに出ている。 0x7F5473C9。

mdatの前の4バイトがmdatのサイズなので、このサイズに書き換え。バイナリエディタによっては初期設定が上書きではなく挿入かもしれないので、Insertキーとかで切り替える。

保存して再生できたらOK。

あと、エンコード中にエラーで止まることもあった。これはエンコード前にゆっくりMovieMaker4を再起動するようにしたら、見ることが無くなった。