Cygwin + ImageMagick を使ってPDFから連番のJPGを生成

Cygwin + ImageMagick を使ってPDFから連番のJPGを生成する方法についてメモします。

準備

Cygwinインストーラを用いて" ImageMagick"と"ghostscript"をインストールします。

そのあと、Cygwinのコンソールで which convertしてみてください。/bin/convert/usr/bin/convertなどと表示されれば ImageMagickを呼び出す準備ができています。

もし/cygdrive/c/Windows/system32/convertWindowsに組み込まれているコマンド)が表示されるようであれば正しく ImageMagickがインストールされていない可能性があります。 ImageMagickをインストールし直すなり、ImageMagickにPATHを通すなりしてください。

処理

PDFの名前をsource.pdfとします。以下のコマンドにより、0001.jpg, 0002.jpg, ... が生成されます。

$ convert source.pdf %04d.jpg

ただ、上記コマンドだと、生成される画像の品質が非常に悪いことがあります。そのときは--density 300などと解像度を指定します。

$ convert --density 300 source.pdf %04d.jpg

参考

`

TopCoderの環境構築メモ

Windows 10にTopCoderのための環境を構築したときの簡易的なメモです。

Javaランタイムのインストール

Java Appletの入手

  • Googletopcoder java appletで検索して出てくるリンクからアプレットをダウンロード。現時点での直リンクはこちら

サイトリストの追加

http://topcoder.com
http://www.topcoder.com
http://arena.topcoder.com
https://topcoder.com
https://www.topcoder.com
https://arena.topcoder.com   
  • 追加後の画面の一例 f:id:minus9d:20190430092319p:plain

greedプラグインの導入

greedプラグインを入れることで、テンプレートを自動挿入したり、手元でのテストが簡単に行えたりが簡単になる。

私の場合は以下のように設定ファイルを書いている。

  • workspaceとして設定したディレクトリに greed.confという名前で以下のファイルを作成
greed.language.cpp.templateDef.source.templateFile = "my_template.cpp"
greed.language.python.templateDef.source.templateFile = "my_template.py"
  • ディレクトリにmy_template.cppという名前で以下のファイルを作成
#include <iostream>
#include <sstream>
#include <string>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <cstring>
#include <fstream>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

using namespace std;

class ${ClassName} {
    public:
    ${Method.ReturnType} ${Method.Name}(${Method.Params}) {
        return ${Method.ReturnType;zeroval};
    }
};

${CutBegin}
${<TestCode}
${CutEnd}
  • ディレクトリにmy_template.pyという名前で以下のファイルを作成
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import re
import string

class ${ClassName}:
    def ${Method.Name}(self, ${Method.Params}):
        return ${Method.ReturnType;zeroval}

${CutBegin}
${<TestCode}
${CutEnd}

Google Code Jam 2019のインタラクティブ問題を解くときのメモ

Google Code Jam でインタラクティブ問題が初登場したのはリニューアル後の2018年。2019年にも引き続きインタラクティブ問題が出題されたのだけれど、ローカルでのデバッグ用にGoogleが提供するデバッグツールの使い方が2018年から変わっていたので、その使い方を忘れないようにメモしておきます。

準備

まず、手元にPython環境を用意します。手元で動かす限りPython 2でもPython 3でもどちらでもよいようですが、今ならPython 3の一択でしょう。

次に、interactive_runner.pytesting_tool.py、2種類のデバッグツールを、問題文に付記されたリンクからダウンロードします。このうち、interactive_runner.py はインタラクティブ問題に共通するスクリプトで、testing_tool.pyはその問題に特有のスクリプトです。

実装

次に、問題を解くスクリプトを実装します。例えば、Google Code Jam 2019 Round 1Aで出題された Golf Gophers のSmallを解くC++のコードを gist に示します。

実装には以下のことに気をつける必要があります。

  • 標準出力したあとは必ずflushする。
    • これをしないとツールが待ち状態になってTLEしてしまいます。
    • C++でのflushは、標準出力のあとに毎回必ず cout << flush; とすればよいです。
    • Python 3でのflushは、print('answer', flush=True) などとflush=Trueをprintに加えればよいです。もしくは、以下のようなprint2関数を定義しておき、print2('answer')などとprintの代わりにprint2を使うようにする手もあります。
def print2(*args, **kwargs):
    print(*args, **kwargs)
    sys.stdout.flush()
  • デバッグプリントは標準エラー出力で行う。
  • 問題文の指示に従った入出力を行う。
    • 例えば、 Golf Gophers の場合、解答を出力したあとにその結果が正しいか否かをverdictで受け取り、これが-1だったらすみやかにプログラムを終了させねばなりません。そうしないとデバッグツールがずっと待ち状態になってしまいます。

C++のようなコンパイルを要する言語で実装した場合は実行ファイルを生成しておきます。ここでは実行ファイルをa.outとします。

ツールの実行

C/C++にて実行ファイルa.outを生成した場合、以下のようにツールを実行します。

$ python interactive_runner.py python testing_tool.py 0 -- ./a.out

Pythonにてsolve.pyという名前のスクリプトファイルを作成した場合、以下のようにツールを実行します。

$ python interactive_runner.py python testing_tool.py 0 -- python solve.py

(solve.pyに実行権限をつけている場合)
$ python interactive_runner.py python testing_tool.py 0 -- ./solve.py

ここで、第3引数にある'0'はSmall用のテストケースを、'1'はLarge用のテストケースを使うことを意味します。テストケースはtesting_tool.pyに埋め込まれているので自由に改変可能ですが、問題により埋め込み方は異なるので読み解きが必要です。たとえば

Google Code Jam 2019 Round 1Aの Golf Gophers であれば以下の部分を修正する必要がありました。

CASES = ([1, 2, 3],
         [1, 2, 3]) # fill in your own cases
QS = (365, 7)

Google Code Jam 2019 Qual DのDat Baeであれば以下の部分を修正する必要がありました。

def getTestCases(test_number):
  F = (10, 5)[test_number]
  # You can edit or add your own test cases here.
  cases = [Case([1, 2, 3], 4, F), Case([2, 3, 5], 6, F), Case([1000], 1024, F)]
  return cases

ツールの実行結果の見方

無事正答を出すプログラムで上記ツールを実行すると以下のように表示されるはずです。

Judge return code: 0
Judge standard error:
Solution return code: 0
Solution standard error:
(標準エラー出力の結果がここにまとめて表示される)

エラーがある場合は以下のようにどのテストケースで落ちたかが表示されます。

Judge return code: 1
Judge standard error: Case #1 (1) failed: Wrong guess: 3. Expected: 1.

Solution return code: 0
Solution standard error:
(標準エラー出力の結果がここにまとめて表示される)

参考URL

中綴じ小冊子の自作メモ

中綴じ小冊子を自作するために調べた簡単なメモです。

セブンイレブン

セブン‐イレブンのマルチコピー機で同人活動をもっと手軽に・もっと楽しく! にある「中とじ冊子」に従うと作成できます。

kinko's

以下の2種類の方法があるようです。

  1. いちど印刷をして、印刷した紙をスキャンしながら中綴じ製本
  2. 有料でPCを借り、PCから印刷
    • こちらは紙を経由しないので画質は劣化しない。ただし試してません

Pythonにてリストの最後の要素を消すにはdelかpop()を使う

Pythonにて長さ100000のリスト arr があるとします。このリストの末尾を削除するとき

arr = arr[:-1]

とする方法は非常に遅いので要注意です。arr[:-1]により新規にリストが作成されてしまうのが原因です。ついカジュアルにこのような書き方をしてしまいがちなので注意が必要です。

上記方法に比べ、

del arr[-1]

arr.pop(-1)

とする方法だと1000倍ほど高速です。

検証用コードを以下に示します。

import time


ARRAY_SIZE = 100000
REPEAT_NUM = 1000


def func1():
    arr = [0] * ARRAY_SIZE
    for i in range(REPEAT_NUM):
        arr = arr[:-1]
        arr.append(0)


def func2():
    arr = [0] * ARRAY_SIZE
    for i in range(REPEAT_NUM):
        del arr[-1]
        arr.append(0)


def func3():
    arr = [0] * ARRAY_SIZE
    for i in range(REPEAT_NUM):
        arr.pop(-1)  # pop()の戻り値(指定したindexの値)はここでは使っていない
        arr.append(0)


def main():
    s = time.time()
    func1()
    print("func1() time:", time.time() - s)

    s = time.time()
    func2()
    print("func2() time:", time.time() - s)

    s = time.time()
    func3()
    print("func3() time:", time.time() - s)


main()

実行例は以下です。

$ python3 tmp.py
func1() time: 1.9272332191467285
func2() time: 0.0010654926300048828
func3() time: 0.0011544227600097656

Windows 10でディスクを入れるとVLCが起動するのを防ぐ

Windows 10でトレイにCDを入れるとVLC自動起動して再生が始まってしまう現象に困っていました。

以下の手順により、自動起動を防ぐことができるようになりました。

  1. Explorerを起動
  2. 光学ドライブを右クリックし、「自動再生を開く」を選択
  3. 「何もしない」を選択

kaggle Traveling Santa 2018 参加記

kaggleの最適化コンペ "Traveling Santa 2018" にソロで参加しました。結果は1874チーム中328位。着手したのが2018/12/22と遅く、冬休みはまるまる何もできず。かけた時間がいくら何でも少なすぎました。スコアが平凡であまり価値はありませんが、記録としてやったことをメモしておきます。

問題概要

2次元座標上に197769個の都市が与えられる。都市には0から197768までの番号が付いている。0から始まりすべての都市を1つずつ通る経路のうち、「経路の総距離」と「ペナルティ」の和からなるスコアが小さくなるような経路を見つける。

ここで、ペナルティは、経路を構成する都市のうち10個おきに発生しうる。もしその都市の番号が素数ならペナルティなし、素数でないなら、その都市と次の都市との間の距離に0.1をかけた値がペナルティとなる。正確な理解のためには https://www.kaggle.com/seshadrikolluri/understanding-the-problem-and-some-sample-paths を参照すること。

初期検討 - 自力実装

都市番号順に並べるだけの愚直解で 446884407.52。スコア計算が正しくできていることを確認。

初期解を求める方法を2つ実装。

1つ目はNearest Neighbor法。都市0から始めて、未使用の都市のうちもっとも近い都市を繋いでいく方法。これでスコアは1812602.18点。

2つ目は挿入法。都市0→都市1→都市0と戻る最小構成の経路を最初に作成。総距離の増加長をもっとも短くなる場所を選んで都市2, 都市3, ...を順に挿入していく。スコアを記録し忘れたがNN法よりはよかったはず。

当初は、これらで得られる経路を初期解として、後述する経路組み換えを行いスコア改善を狙った。焼きなましも実装した。しかしスコアの改善に行き詰まり、1652066.12点が限界。

Concordeの導入

カーネル https://www.kaggle.com/blacksix/concorde-for-5-min を実行。これは巡回セールスマン問題のソルバであるConcordeを実行するというもの。わずか5分で1518313.05点が出て衝撃を受ける。 これで603位相当。

Concordeは商用利用不可とあったので使って良いのか不安だったが、https://www.kaggle.com/c/traveling-santa-2018-prime-paths/discussion/72767 を読むとConcordeを使ってよいことがわかる。 そこで今後はConcordeの解を初期解として使っていくことにする。

経路組み換えの実装

Concordeで得られる経路を初期解とする。これに以下の経路組み換えを行い、スコアの低減を目指した。

  1. 2都市のスワップ
  2. 1都市を経路から削除し他の場所に挿入
  3. 経路の一部分をreverse

スコアを高速に計算できるように、「経路の総距離」と「ペナルティ」とを分けて持つ工夫をした。上記のどの経路組み換えを行っても「経路の総距離」は一瞬で計算できる。「ペナルティ」は残念ながら再計算が必要だが、それでも最悪で全都市の1/10について再計算すればよい。

また、例えば2都市を入れ替えるとき、遠くにある2都市を入れ替えても意味がない。そこで、各都市についてその近傍の都市をN個(N=10, のちに20) 持っておくようにした。これによりスコアが改善する可能性がある経路組み換えだけを実行できる。

Concordeの初期解に対して上記の経路組み換えを適用して山登りすることで、130ポイントほどスコアが向上することを確認できた。

本当は上記以外にもより複雑な経路組み換え法 (3-optなど) を実装したかったのだが、餅とおせちを食べるのに忙しくなり進捗がなくなる。その間に次々と激強カーネルが投稿された影響で順位が大幅に下がっていることに気付く。これらの激強カーネルの結果を初期解として、上記経路組み換えを行って少しだけスコア改善したものを投稿、というしょうもないことを片手間でしばらくやった。スコア改善に寄与したのは上記の方法のうち2と3だけだったように思う。スコア改善とはいっても改善幅はほんのわずかで、行き詰まりを感じる。

そこで焼きなましを導入してスコア改善を図ったが、スコアが低下したまま向上してくれず、全然うまくいかなかった。

セグメント単位の焼きなまし

終了日前日、経路を適当な長さ(100程度)のセグメントに分割し、セグメント単位で焼きなましを行うことを思いつく。ハイパーパラメータの調節をする暇は全然なかったし、一晩しか回せなかったので全セグメントを舐めきることもできなかったのだが、それでも効果はあった。終了直前に投稿されたカーネルのスコア1515564.01から、1515562.86まで改善。だがここで時間切れ。コンペ終了後も12時間ほど動かしたら1515561.30になったことからまだ少しはポテンシャルがあった。もっと早くこの方針に辿りつくべきだった。とはいえブロンズ圏内である1515493.13までたどり着くためにはこれだけでは足りなかったと思われる。

反省点

  • 他人のカーネルを使わせてもらうばかりで中をほとんど読まなかった。PythonのNumbaを使って高速計算したり、C++のコードを文字列としてファイル保存・コンパイルすることでC++のコードを動かしたり、Concordeのソースを持ってきてビルドして実行したりといった技が詰まっていたので後でも勉強したい。
  • 久しぶりにC++を書くと経路組み換え時のスコア計算がバグだらけでデバッグが大変だった。数十都市からなるミニデータでデバッグするのは有用だったのでもっと簡単にデータを切り替えられるようにしたい。
  • 経路を長さ10程度のセグメントに区切って、全経路順を生成してスコア最小のパスを選ぶ実装は簡単なのでやっておくべきだった。