QTreeWidgetを使ってExifViewerを作る

前回紹介したQt for PythonのQTreeWidgetを使って簡単なExifViewerを作ってみる。
コード全体(60行くらい)は最後に記載。

takuroooooo.hatenablog.com

目次

全体構成

構成は下記図のような感じ。
入力はJPEGファイルのみ対応。

ExifViewer完成画面

今回作るExifViewerの画面。
GUIはQt for Pythonで作る。

以下コードの簡単な説明をしていく。

処理手順

1.JPEGからExifを取得する

まずPILを使ってJPEGの中にあるExif情報を取り出す。
PILはpip install pillowでインストールできる。

Exif情報は_getexif()を使うとExif情報が辞書形式で取得できる。

from PIL import Image
exif = Image.open(img_path)._getexif()

exif変数は辞書になっていて、{tag_id: value}の形式になっている。exifはどんな情報なのかを識別するためのtag_idがあらかじめ用意されている。tag_idは16バイトの数字で定義されている。

www.vieas.com

viewerで表示するときはtag_idだと何の情報なのかよくわからないので、人間が分かるtag_nameに変換する。
これはfrom PIL.ExifTags import TAGS, GPSTAGSを使うと簡単に変換できる。

下記コードはtag_idとtag_nameとtagの値を出力するコード。

from PIL.ExifTags import TAGS, GPSTAGS
for tag_id, value in exif.items():
    tag_name = TAGS[tag_id]
    print(tag_id, tag_name, value)

これを実行すると以下のような出力が得られる。

36864 ExifVersion b'0220'
37121 ComponentsConfiguration b'\x01\x02\x03\x00'
40960 FlashPixVersion b'0100'
36867 DateTimeOriginal 2008:10:22 16:28:39
36868 DateTimeDigitized 2008:10:22 16:28:39
・
・
34853 GPSInfo {1: 'N', 2: ((43, 1), (28, 1), ....
・
・

GPSTAGSはExif情報の中にあるGPS情報に対して使う。GPS情報はtag_nameがGPSInfoの中にある。GPSInfoは{tag_id: value}という形式の値を持っているので、同じようにGPSTAGS[tag_id]とすればtag_nameが取り出せる。

今回はExif情報とGPS情報を親ツリーとして表示したいので、まずはExif情報からGPS情報だけを取り出す関数をつくる。こうしておくことで後々のコードをわかりやすく書ける。

def extract_gps_info(exif):
    for exif_id, exif_value in exif.items():
        exif_tag = TAGS.get(exif_id, str(exif_id))
        if exif_tag == 'GPSInfo':
            del exif[exif_id] # Exif情報からGPS情報を削除する.
            return exif_value # GPS情報をリターンする.
    return None

exif = Image.open(img_path)._getexif()
gps = extract_gps_info(exif)

2.Exif情報を使ってTreeを生成する

{tag_id: value}形式のExif情報とGPS情報が取得できたので、次にこの情報を使ってTreeを作成する。
Treeの生成はQTreeWidget()とQTreeWidgetItemを使う。 今回はcreate_top_level_itemという関数を作って、Exif情報のツリーとGPS情報のツリーを生成する。
この関数でリターンしたQTreeWidgetItemをQTreeWidget.addTopLevelItem()の引数にすることでTreeに登録している。

def create_top_level_item(top_name, id_val, id_to_name):
    top_level_item = QTreeWidgetItem([top_name])  # 親ツリーアイテム生成

    for tag_id, val in id_val.items():
        tag_name = id_to_name.get(tag_id, str(tag_id))
        child_item = QTreeWidgetItem([tag_name, str(val)])  # 子ツリーアイテム生成
        top_level_item.addChild(child_item)  # 親に子を追加

    return top_level_item

qw_tree = QTreeWidget()
qw_tree.resize(500, 500)
qw_tree.setAlternatingRowColors(True)
qw_tree.setHeaderLabels(["name", "val"])

# Exif情報のツリーをつくる.
top_level_item = create_top_level_item('exif', exif, TAGS)
qw_tree.addTopLevelItem(top_level_item)

# GPS情報のツリーをつくる.
if gps is not None:
    top_level_item = create_top_level_item('gps', gps, GPSTAGS)
    qw_tree.addTopLevelItem(top_level_item)

全体コード

import sys
from PySide2.QtWidgets import QApplication, QTreeWidget, QTreeWidgetItem
from PIL import Image
from PIL.ExifTags import TAGS, GPSTAGS


def extract_gps_info(exif):
    for exif_id, exif_value in exif.items():
        exif_tag = TAGS.get(exif_id, str(exif_id))
        if exif_tag == 'GPSInfo':
            del exif[exif_id]  # Exif情報からGPS情報を削除する.
            return exif_value  # GPS情報をリターンする.
    return None


def create_top_level_item(top_name, id_val, id_to_name):
    top_level_item = QTreeWidgetItem([top_name])  # 親ツリーアイテム生成

    for tag_id, val in id_val.items():
        tag_name = id_to_name.get(tag_id, str(tag_id))
        child_item = QTreeWidgetItem([tag_name, str(val)])  # 子ツリーアイテム生成
        top_level_item.addChild(child_item)  # 親に子を追加

    return top_level_item


def main(img_path):
    app = QApplication([])

    exif = Image.open(img_path)._getexif()
    # for tag_id, value in exif.items():
    #     print(tag_id, TAGS[tag_id], value)
    gps = extract_gps_info(exif)

    qw_tree = QTreeWidget()
    qw_tree.resize(500, 500)
    qw_tree.setAlternatingRowColors(True)
    qw_tree.setHeaderLabels(["name", "val"])
    
    # Exif情報のツリーをつくる.
    top_level_item = create_top_level_item('exif', exif, TAGS)
    qw_tree.addTopLevelItem(top_level_item)

    # GPS情報のツリーをつくる.
    if gps is not None:
        top_level_item = create_top_level_item('gps', gps, GPSTAGS)
        qw_tree.addTopLevelItem(top_level_item)

    # qw_tree.expandAll()
    qw_tree.show()

    sys.exit(app.exec_())


if __name__ == "__main__":
    if len(sys.argv) != 2:
        sys.exit()
    img_path = sys.argv[1]
    main(img_path)

---

QTreeWidgetの基本的なこと

最近仕事で処理結果をGUIで表示させたいことがあったのでPythonのQtを勉強してみた。

PythonのQtにはPyQtとQt for Python(PySide2)があるけど、今回は最近登場したQt for Python(PySide2)を使って簡単なTree構造の作り方をまとめてみようと思う。

Qt for Pythonは以下のコマンドでインストールできる。

pip install pyside2

Qt for Python公式ページ www.qt.io

目次

TreeのベースとなるWindowを表示する

import sys
from PySide2.QtWidgets import QApplication, QTreeWidget

app = QApplication(sys.argv)

qw_tree = QTreeWidget()
qw_tree.show()

sys.exit(app.exec_())

基本的なこと

• QtではWidgetと呼ばれる部品を使うことで色々なGUIを作ることができる。
• QApplication()はWidget関連の初期化をするので、Widgetを使う前に実行しなければならない。
• QTreeWidget()はツリー形式のGUIを作るためのWidget。
• Widgetを表示するためには、show()を実行する。show()は全てのWidgetが持つメソッド。
• sys.exit(app.exec_())でQtのメインループに入る。

ということで、GUIを作るためにはQApplication()とsys.exit(app.exec_())の間で

1. 必要なWidgetを定義
2. Widgetのメソッドであるshow()を実行

が必要になる。

TreeにHeaderをつける

import sys
from PySide2.QtWidgets import QApplication, QTreeWidget

app = QApplication(sys.argv)

qw_tree = QTreeWidget()
qw_tree.setHeaderLabels(["name", "tel", "mail"])  # Headerをつける
qw_tree.show()

sys.exit(app.exec_())

QTreeWidget.setHeaderLabels(labels)

• リスト形式の変数を渡すとヘッダを生成してくれる。
• 同様にヘッダを生成することができるメソッドにQTreeWidget.setHeaderItem()とQTreeWidget.setHeaderLabel()があるが、できることは一緒なのでsetHeaderLabels()を使っておけばOK。

TreeにItemを追加する

import sys
from PySide2.QtWidgets import QApplication, QTreeWidget, QTreeWidgetItem

app = QApplication(sys.argv)

qw_tree = QTreeWidget()
qw_tree.setHeaderLabels(["name", "tel", "mail"])
qw_tree_parent_item = QTreeWidgetItem(['family'])  # Treeに追加するItemを生成
qw_tree.addTopLevelItem(qw_tree_parent_item)  # TreeにItemを追加する
qw_tree.show()

sys.exit(app.exec_())

QTreeWidgetItem(names)

• list形式の変数を渡すとTreeに追加するItemを生成してくれる。
• QTreeWidget.addTopLevelItem()に生成したItemを設定すると、TreeにItemが登録される。
• QTreeWidget.addTopLevelItems()を使うと複数Itemをリスト形式で渡すことができる。

Itemに子Itemを追加する

import sys
from PySide2.QtWidgets import QApplication, QTreeWidget, QTreeWidgetItem

app = QApplication(sys.argv)

qw_tree = QTreeWidget()
qw_tree.setHeaderLabels(["name", "tel", "mail"])
qw_tree_parent_item = QTreeWidgetItem(['family'])
qw_tree_parent_item.addChild(QTreeWidgetItem(['A', '111-111-111', 'aaa@gmail.com']))  # Itemに子Itemを追加
qw_tree.addTopLevelItem(qw_tree_parent_item)
qw_tree.expandAll()  # TreeのItemを全て開く
qw_tree.show()

sys.exit(app.exec_())

QTreeWidgetItem.addChild(Item)

• QTreeWidgetItem.addChild(Item)を使うとItemに子Itemを追加できる。
• QTreeWidget.expandAll()を使うとデフォルトでTreeが開いた状態になる。
• QTreeWidget.expandAll()はQTreeWidgetItem.addChild(Item)の後に呼ぶ。

Treeに複数のItemをつける

これまでやってきたことを繰り返すだけで簡単に階層構造のTree GUIが作れる。

import sys
from PySide2.QtWidgets import QApplication, QTreeWidget, QTreeWidgetItem

app = QApplication(sys.argv)

qw_tree = QTreeWidget()
qw_tree.setHeaderLabels(["name", "tel", "mail"])

qw_tree_parent_item_1 = QTreeWidgetItem(['family'])
qw_tree_parent_item_1.addChild(QTreeWidgetItem(['A', '111-111-111', 'aaa@gmail.com']))
qw_tree_parent_item_1.addChild(QTreeWidgetItem(['B', '222-222-222', 'bbb@gmail.com']))

qw_tree_parent_item_2 = QTreeWidgetItem(['school'])
qw_tree_parent_item_2.addChild(QTreeWidgetItem(['C', '333-333-333', 'ccc@gmail.com']))
qw_tree_parent_item_2.addChild(QTreeWidgetItem(['D', '444-444-444', 'ddd@gmail.com']))

qw_tree.addTopLevelItem(qw_tree_parent_item_1)
qw_tree.addTopLevelItem(qw_tree_parent_item_2)
qw_tree.expandAll()
qw_tree.show()

sys.exit(app.exec_())

ソースコード

github.com

AtCoder Beginner Contest 139

9/1のABC139は4AC5WAだった。初めてコンテスト中にD問題解けたけど、いつものD問題よりも難易度が低く正解している人が多かった印象。

atcoder.jp

A問題

問題

3文字の文字列が２つ入力されて何文字一致しているかカウントする問題。

自分の回答

単純にループで数えただけ。他の人の回答も同じような感じだった。

s=input()
t=input()
 
cnt=0
for i in range(3):
    if s[i] == t[i]:
        cnt+=1
print(cnt)

B問題

問題

整数A、Bが与えられて、Aを1回加算するという操作を何回繰り返すとBにたどり着くかという問題。しかし、Aを1回加算するという操作を行うたびに合計数が-1される。初期値は1。 なので操作を1回行うと、合計数に A-1 が加算される。

自分の回答

上記操作をループで実行すればいいのだけれどもここで1WAしてしまった。

間違ったコード

def MAP():
    return map(int, input().split())
 
a,b=MAP()
 
t=1
cnt=0
while True:
    t -= 1
    t += a
    cnt += 1
    # このif文がループの先頭になければならない
    if b <= t:
        break
print(cnt)

このコードだとループの中の処理が必ず１回行われてしまう。そのため入力のB(プログラムの変数ではb)が1のときに間違った答えを出力してしまう。

正解したコード

def MAP():
    return map(int, input().split())
 
a,b=MAP()
 
t=1
cnt=0
while True:
    # if文をループの先頭に移動した。
    if b <= t:
        break
    t -= 1
    t += a
    cnt += 1
print(cnt)

ループを抜けるif文をループの先頭に書いて条件を満たしている場合は何もしないで抜けるようにした。
最初からちゃんとwhile t < b:と書いておけばよかった...境界条件は今後注意してしていこうと思う。

他の人の回答みて勉強になったこと

そもそもループしないでも

• 1回の操作でA-1を加算する。
• 初期値は1

なので（切り上げる）で答えがでる。切り上げは以下のように書くことができる。

def ceil(x,y):
  return -(-x//y)

print(ceil(b-1, a-1)

C問題

問題

長さNのある数列が与えられて自分 >= 右隣が最大何回続くか？という問題。

自分の回答

1 <= N <= 10⁵ なので単純にループで数えていけばいい。
自分 >= 右隣 ならカウンターを+1する。
自分 < 右隣 ならカウンターをリセットする。
を繰り返していき、カウンターの最大値を求める。

ちなみに与えられる数列がものすごく長い場合、sys.stdin.readline()を使うとinput()より数百msec速くなったことがあるので、こっちを使うようにしている。

import sys

input = sys.stdin.readline

def LIST():
    return list(map(int, input().split()))

N=int(input())
H=LIST()

p=H[0]
cnt = 0
max_cnt = 0
for h in H[1:]:
    if p >= h:
        # 自分 >= 右隣
        cnt += 1
        max_cnt = max(max_cnt, cnt)
    else:
        # 自分 < 右隣
        cnt = 0
    p = h

print(max_cnt)

D問題

問題

ある数列A={1,2,...,N}とそれを並べ替えた数列P={P1,P2,...PN}があって、

A[0] % P[0] = M0
A[1] % P[1] = M1
A[2] % P[2] = M2
・
・
・
を合計していったとき、最大値がいくつになるか？という問題。(%は余りを求める演算子)
Pをどうやって並べるかは自由。

自分の回答

例えば、A={1,2,3,4,5}だった場合、P={2,3,4,5,1}という数列Pを作ると余りの合計が最大値になる。

• 1 % 2 = 1
• 2 % 3 = 2
• 3 % 4 = 3
• 4 % 5 = 4
• 5 % 1 = 0

つまり自分より+1大きい数に割ってもらえれば、余りが自分自身になり、それが余りとしての最大値になる。
（4だったら、5(=4+1)に割ってもらえれば、余りは4になる。）

これを考慮すると余りの合計とは1〜N-1の総和ということになる。（上記例だと1,2,3,4を足したものが答え）
1〜Nの総和はガウスの公式で

で求めることができる。

...なのだけれどもコンテスト中にいろいろ勘違いしてしてしまって回答が汚くなってしまったので割愛。 綺麗に書けば以下のように2行程度で書ける。

N = int(input())
print((1+N-1)*(N-1)//2)

結果

5WAが効いて茶色パフォーマンス止まりだった。

転倒数とBinary Indexed Treeについて考える

前回のAtCoderのコンテストで転倒数というものが出題された。 atcoder.jp 転倒数というものを知らなかったので転倒数についてまとめてみる。またコンテストの問題をBinary Indexed Treeで解いてどういう処理の流れになっているかを整理する。コンテストの問題はBITを使わなくても解けるがBITを使うと高速に転倒数をカウントできるとのこと。(コンテストのテストケースで7倍速度の差があった。)

転倒数とは

ある数列に関して以下の条件を満たす組の数のこと
「自分より右にあって かつ 自分より値が小さい」

例えば、[3 1 2]という数列Aがあったとする。この数列の転倒数は2になる。 数え方は以下の通り。

数列Aの左端から見ていくと、
* 3からみたときの転倒数は、1と2の2つ。
* 次に1から見たときの転倒数は一つもないので0。
* 最後の2には右側に数字がないので転倒数は0。
ということで転倒数は合計2つになる。

表っぽく表現するとこんな感じになる。
一番上の行が数列になっていて、その下の行が転倒数の組み合わせになっている。

問題B - Kleene Inversion

前回のAtCoderの問題「B - Kleene Inversion」では、この数列AをK回繰り返したときの数列Bの転倒数を求めるというものだった。

先の数列A=[3 1 2]を使って表現すると、
K=1： B=[3 1 2]
K=2： B=[3 1 2 3 1 2]
K=3： B=[3 1 2 3 1 2 3 1 2]
となる。(先ほどの例はK=1のときの転倒数を求めたことになる。)

この問題は解説動画の33分あたりにある通り、数列A内で発生する転倒数と2つの数列A間で発生する転倒数を数えることで解くことができる。

www.youtube.com

ここで数列A内で発生する転倒数と2つの数列A間で発生する転倒数とはどういうものかを整理してみる。

数列A=[3 1 2]内で発生する転倒数

これは数列A=[3 1 2]の中で数えた転倒数の数のことで、最初の例で数えた転倒数のことを指す。

2つの数列A間で発生する転倒数

これはK=2のときに発生する転倒数の中で2つの数列を跨っているもののこと。
数列A=[3 1 2]を2回繰り返したときの数列[3 1 2 3 1 2]の転倒数の合計は以下のように7つになる。

この中で2つの数列を跨っている転倒数は3つある。
(以下の表の青枠の3つ)

他の4つは、数列A=[3 1 2]内で発生する転倒数のこと。
(以下の表の赤枠)

こうやってみると赤枠はKの数だけ発生することが分かる。
また青枠の数はK=2なら1つ、K=3なら3つ、K=4なら6つというように組み合わせの公式で求めることができる。

2つの数列A間で発生する転倒数というのは数列A=[3 1 2]を降順にソートした状態[3 2 1]の転倒数と一致する。

Binary Indexed Treeによる転倒数のカウントについて考えてみる

転倒数はBITを使ってカウントすることができる。
以下のコードはB - Kleene InversionをBITで解いたもの。言語はPython。

MOD = 10 ** 9 + 7
 
 
def MAP():
    return list(map(int, input().split()))
 
 
class BinaryIndexedTree:
    def __init__(self, tree_size):
        self.tree_size = tree_size
        self.tree = [0] * (self.tree_size + 1)
 
    def add(self, i, x):
        while 0 < i <= self.tree_size:
            self.tree[i] += x
            i += i & -i
 
    def sum(self, i):
        s = 0
        while 0 < i:
            s += self.tree[i]
            i -= i & -i
        return s
 
 
def count_inversion(A, max_num):
    bit = BinaryIndexedTree(max_num)
    x = 0
    for i, a in enumerate(A, start=1):
        bit.add(a, 1)
        x += i - bit.sum(a)
    return x
 
 
def main():
    N, K = MAP()
    A = MAP()
 
    tento_int = count_inversion(A, 2000)  # Aの内部で発生する転倒数
    tento_ext = count_inversion(sorted(A, reverse=True), 2000)  # AiとAjの間で発生する転倒数
 
    x = tento_int * K
    y = tento_ext * K * (K - 1) // 2
    print((x + y) % MOD)
 
 
if __name__ == "__main__":
    main()

数列[3 1 2]の転倒数を数える場合、上記コードの標準入力には、

3 1
3 1 2

を与える。

BITについては、Binary indexed treeを参照。

BITメソッド

BIT.add(i,x)

BITはadd(i,x)でインデックスiに値xを登録して、sum(i)でインデックス1〜iまでの累積和を計算するもの。 これをうまく使うと、 sum(i)で
「自分と自分より左にある かつ 自分以下の値」
をカウントできる。
自分とはインデックスiのことで、例えばsum(3)は数字1と2と3がそれまで何個登場したか(何回add(i,x)されているか)を計算する。

BIT.sum(i)

これまでadd(i,x)で登録した数字の数をtotalとすると、total-sum(i)で
「自分と自分より左にある かつ 自分を超えている値」
をカウントできる。
これは転倒数の定義と同じ意味のことを言っているので、BITで転倒数が求まることが分かる。

count_inversion()

コード中のcount_inversion()が実際にどうやってBITで転倒数をカウントしているかを整理する。
整理しやすいようにBITのサイズを4とする。(コードでは2000になっている。)

BITの最初の状態は 以下のように0初期化されている。
インデックスは1始まりで青マスがBITを表現している。

1回目のループ(数列[3 1 2]の3を処理する)

最初のループでi=1、a=3が入り、bit.add(a, 1)を実行するとBITクラスのself.treeは

となる。
緑マスは更新されたマス。(1が加算された。)
次に x += i - bit.sum(a)
で転倒数を求めている。

bit.sum(a)は、ループ1回目はa=3なのでbit.sum(3)になる。これは図の赤い数字の総和を返すので0+1=1が返る。

これは先にも触れた通り、 「自分と自分より左にある かつ 自分以下の値」 をカウントした結果になる。これは数列[3 1 2]の赤文字の中で3以下の数字をカウントしたものという意味なので答えは1。

i=1なのでx += i - bit.sum(a)はxに0を加算している。
iはこれまでbit.add(a, 1)で登録した数字の総数を意味している。
i - bit.sum(a)は「自分と自分より左にある かつ 自分を超えている値」を表しているので、0という結果が合っていることが分かる。（[3 1 2]赤文字の中で3を超えている数字はない。）

2回目のループ(数列[3 1 2]の1を処理する)

2回目のループでi=2、a=1が入り、bit.add(a, 1)を実行するとBITクラスのself.treeは

となる。
1回目のループと同様にx += i - bit.sum(a)で転倒数を求めている。

bit.sum(1)は赤い数字の合計なので1が返る。
これは数列[3 1 2]の赤文字の中で1以下の数字をカウントしたものという意味なので答えは1。

i=2なのでx += i - bit.sum(a)はxに1を加算している。（[3 1 2]赤文字の中で1を超えているものは3だけなので1つ。）

3回目のループ(数列[3 1 2]の2を処理する)

3回目のループでi=3、a=2が入り、bit.add(a, 1)を実行するとBITクラスのself.treeは

となる。
1,2回目のループと同様にx += i - bit.sum(a)で転倒数を求めている。

bit.sum(2)は赤い数字の合計なので2が返る。
これは数列[3 1 2 ]の赤文字の中で2以下の数字をカウントしたものという意味なので答えは2。

i=3なのでx += i - bit.sum(a)はxに1を加算している。（[3 1 2 ]赤文字の中で2を超えているもの3だけなので1つ。）

count_inversionが返す値

3回のループでx=2になっている。
これは数列[3 1 2]の転倒数と一致する。

参考リンク

• Binary indexed tree

• 転倒数 [いかたこのたこつぼ]

AtCoder 第一回日本最強プログラマー学生選手権-予選-

8/24にAtCoderで第一回日本最強プログラマー学生選手権-予選-が開催された。学生以外も参加できてレーティングが変化するとのことだったので参加したが、Aしか解けなかった...

atcoder.jp

A問題

問題

1〜M月、1〜D日から構成される高橋暦の中で積の日が何日あるかをカウントする問題。

m月d日としてときの
はdの10の位
はdの1の位
とすると、積の日の条件は

• 
• 
• 

となる。

ループして上記条件に該当する日が何日あるかをカウントすればいいだけ。

自分の回答

M,D=map(int, input().split())
 
seki=0
for m in range(1,M+1):
    for d in range(1,D+1):
        str_d = str(d)
        if len(str_d)==2:
            d10 = int(str_d[0])
            d1  = int(str_d[1])
            if d10 >= 2 and d1 >= 2 and d10*d1 == m:
                seki+=1
print(seki)

他の人の回答みて勉強になったこと

10の位と1の位を分割するのにstrで文字列に変換する必要はなく、以下の書き方で変換できる。

d10 = d % 10 # dの10の位
d1 = d // 10 # dの1の位

また組み込み関数divmod()を使うと一行で書ける。

d10, d1 = divmod(d, 10) # (dの10の位, dの1の位)

divmod()を使うと下記のように書き直せる。

M, D = map(int, input().split())
seki = 0
for m in range(1, M + 1):
    for d in range(1, D + 1):
        d10, d1 = divmod(d, 10)
        if d10 >= 2 and d1 >= 2 and d10 * d1 == m:
            seki += 1
print(seki)

B問題

問題

数列AをK回繰り返しものを数列Bとしたとき、数列Bの中に転倒数はいくつあるか。(答えはで割った余りで表示する。)

転倒 (数学) - Wikipedia

B問題は時間内に解くことはできなかった... 数列Aの中で発生する転倒数と、繰り返される数列A間で発生する転倒数がありこれらを別々に考えて計算する必要があった。

数列Aの中で発生する転倒数をtento1とすると、

となり、

2つの数列A間で発生する転倒数をtento2とすると、

とすることができる。
は組み合わせの公式。K個の中から2つ選んだときの組み合わせ数を求めている。

上記２つの結果を足したものがが答えとなる。 (とはループなどで数える。 )

(時間外の)自分の回答

N,K=list(map(int, input().split()))
A=list(map(int, input().split()))
 
MOD=10**9+7
 
def count(A,N):
    arr=[0]*N
    for i, ai in enumerate(A[:-1]):
        cnt=0
        for aj in A[i+1:]:
            if ai > aj:
                cnt+=1
        arr[i]=cnt
    return arr
 
s1=sum(count(A,N))
s2=sum(count(sorted(A,reverse=True),N))
v=K*(K-1)//2
print((s1*K+v*s2)%MOD)

はs1、はs2に対応している。

他の人の回答みて勉強になったこと

転倒数を数えるのにBinary Indexed Tree(以下BIT)を使っている人がいた。

フェニック木 - Wikipedia

BITを使うことで転倒数を効率的に数えることができるみたい。
BITはもともと累積和を効率的に数えるためのデータ構造だが、使い方を工夫することで転倒数を数えることにも使えるらしい。

BITについては以下のスライドが参考になった。

Binary indexed tree from HCPC: 北海道大学競技プログラミングサークル

www.slideshare.net

「BIT 転倒数」で検索すると色々記事が出てくるので、どういう仕組みなのか調べてみようと思う。

AtCoder始めました

8月5日からAtCoderを始めた。

atcoder.jp

AtCoderとは

AtCoderとはホームページによると

オンラインで参加できるプログラミングコンテスト(競技プログラミング)のサイトです。リアルタイムのコンテストで競い合ったり、約2000問のコンテストの過去問にいつでも挑戦することが出来ます。

というもので、
ざっくり言うと出題される問題の解をプログラムで書いて、どれだけ早く問題を解けたかで競い合うもの。 調べてみるとプログラミングコンテストというものはAtCoderに限らず様々なものが定期的に開催されているよう。

codeforces.com

www.topcoder.com

csacademy.com

定期的に開催されるコンテストに出場して良いパフォーマンスを出すと自分のレート（レベルみたいなもの）が上がっていく仕組みがあり、現在のレートによって色で自分の実力が表現される。
例えば、レートが0以上400未満だと灰色、400以上800未満だと緑色のように400区切りで色分けされている。何色かがその人のある程度の実力を表しており、みんな上位の色になることがコンテスト参加へのモチベーションになっている。

各色がどの程度の実力なのかはAtCoderの中の人がブログでまとめてくれている。 chokudai.hatenablog.com

AtCoderを始めた理由

自分のレベルって他者と比べてどの辺りなのか興味があったので登録してみた。
まだ始めたばかりなのでなんとも言えないが、まだ一番下の灰色なのでまずは茶色を目指してコンテストに継続して参加していこうと思う。

AtCoder登録してから2週間でやったこと

1.過去問解いた

まずはAtCoder Problemsというサイトを使って過去問解いて経験積むのが効果的という記事を見たのでAtCoder Beginner Contestの過去問(主にAB問題)を180問ほど解いた。

2.コンテスト出た

コンテスト出なきゃレート上がらないので参加できそうなやつは出るようにしている。（解ける問題が少なくて順位が低い...）

3.人のコード読んだ

自分が解いた問題に関しては他の人がどんなプログラムを書いたのか読むようにしている。これがとても勉強になる。言語としてこういう書き方できるだという発見があったり、問題の解き方が参考になったりすることが多い。

今後やろうと思っていること

以下のQiitaの記事が参考になりそうなのでこれらを読みつつC問題の過去問を解いていこうと思う。

• [AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiita
• AtCoder 版！蟻本 (初級編) - Qiita
• AtCoderの問題を分類しました - Qiita

Random Erasing Data Augmentation

Data augumentation関連の論文メモ
図は論文からの引用

目次

概要

入力画像上に所定パラメータに従った矩形領域を生成するRandom Erasingというデータ拡張手法の提案。

論文リンク

https://arxiv.org/pdf/1708.04896.pdf

著者

• Zhun Zhong †§
• Liang Zheng §
• Guoliang Kang §
• Shaozi Li †
• Yi Yang §

†：Cognitive Science Department, Xiamen University, China
§：University of Technology Sydney

従来の課題

• トレーニングデータに対して、モデルの重みパラメータが多いと汎化能力が低下し、トレーニングデータに対してoverfittingしてしまう。
• occlusion は汎化能力に対する影響が強い。しかしocclusionがあるトレーニングデータは少ない。
• occlusion を施した画像を手動で生成することもできるがコストがかかる上に、occlusionのバリエーションも限定されてしまう。

提案手法

アルゴリズム

Radnom Erasing

• トレーニング中に、入力画像に対して矩形を重畳することでocclusionに対応したデータ拡張を実現する。
• 矩形を生成するために以下のパラメータを決定する。
  • 矩形を描画する画像上のx,y座標
  • 矩形の幅と高さ
  • 矩形を埋める値
• 実装が容易。

以下詳細なアルゴリズム

記号	意味
p	Random Erasingを実行する確率
S	入力画像の面積
H, W	入力画像の高さと幅
sl, sh	入力画像面積に対する矩形面積の比率のレンジ
r1, r2	画像上に描画される矩形のアスペクト比のレンジ
Se	画像上に描画される矩形の面積
He, We	画像上に描画される矩形の高さと幅
re	画像上に描画される矩形のアスペクト比 He/We
xe, ye	画像上に描画される矩形のxy座標

実験では以下の設定パラメータが一番性能が良いとされている。

• p=0.5
• sl=0.02, sh=0.4
• r1=1/r2=0.3, r2=3.3

結果

Classificationの結果。 異なるモデル、データセットにおいてもRandom Erasingを使用することでテストエラーが下がっている。

矩形領域を埋める値

矩形領域をどんな値で埋めるか4パターン実験した。

1. RGBそれぞれ[0-255]のランダム値を割りあてる。(RE-R)
2. ImageNetの平均値 [125, 122, 114]。(RE-M)
3. 全て0。(RE-0)
4. 全て255。(RE-255)

実験では1のランダム値で矩形を埋める方法が最も性能が良かった。

Object Detectionへの適用

Object Detectionではトレーニングデータに物体の位置情報(bounding box)があるので、論文では３つの方法が実験されている。

1. 矩形を描画する位置を画像全体から選択する。(IRE)
2. 矩形を描画する位置をbouding box内から選択する。(ORE)
3. 1と2を組み合わせる。(I+ORE)

実験では3の方法が最も性能が良かった。

自分の実装

github.com

---