2021-04-05

春休みの日記

blog

久しぶりです。まぁじです。

春休み何もしてなかったのでブログだけ書こうと思いました。

よろしくおねがいします。

呪術廻戦 1~15巻+0巻

アニメがかなり流行ってて見てたんですが、難しい用語が多くて字幕なしではきつかったので全巻買いました。アマプラで字幕出す方法あったら教えてください。

ネットで見た感じだと「キャラに愛が感じられない」「キャラが死にすぎ」みたいな意見が多かったんですが、確かになろう系に比べたら味方死ぬけど言うほどかな……？って感じでした。意味無くハッピーエンドになってもつまらないですし。

あと高専検索(？)の件でかなり燃えてましたね。高専志願の中学生(明らかに18歳以下)が高専って検索してR18腐/夢が出てくるのだけはさすがに勘弁って感じです。

WATCH DOGS 2

ハッカー,デザイナー集団のデッドセックに加入したマーカス(身体能力抜群でハッキングも得意な陽キャ)を操作して、不正にデータを集めたり監視したりしているctOS2.0とその親玉ブルーム社と戦う…というゲームです。3年ぶりくらいにゲームクリアできたくらいには楽しかったです。

ゲームしてて、主張したい意見や作りたい理想があってプログラミング(広義のハッキングみたいなもんでしょ)ができるマーカス達が羨ましくなりましたし、そうなりたいなって思えるゲームでした。

ちなみに1とかレギオンを選ばなかった理由は中古で一番安かったからです。

成績

教授の靴舐めまくったらGPA3.62でした。

あとがき

春休み、午前2時に寝て11時に起きて花粉症で死ぬみたいな毎日してたので社会復帰できるか不安です。#春から新入生✨

2021-03-02

JuliaでUnionFindを使ってみる(DisjointSets - DataStructures.jl)

Julia 競技プログラミング AtCoder

お久しぶりです。まぁじです。

まえおき
実行環境
自力実装したUnionFind法
- 自力実装の利点・欠点
IntDisjointSetsを使ったUnionFind法
自力実装よりIntDisjointSetsの方が早い事例（2023/7/12追記）
参考資料

まえおき

今回はDataStructures.jlにあるDisjointSetsについてです。競技プログラマーならUnion-Find法の方が聞き覚えがあると思います。

日本語でいうと「素集合データ構造」で、木構造を用いて

グループの併合 (union / unite)
それぞれのデータが同じグループに存在するかの判定 (find)

が高速にできます。

詳しいアルゴリズムや応用はこのスライドやこのページを読むとわかりやすいと思います。

実行環境

Juliaのインストールは既に済んでいるものとします。
ちなみに使ってるエディタはVSCodeで、Julia Extensionを入れて使ってます。

julia> versioninfo()
Julia Version 1.5.3
Commit 788b2c77c1 (2020-11-09 13:37 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: Intel(R) Core(TM) i3-8130U CPU @ 2.20GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, skylake)

自力実装したUnionFind法

あまり複雑なアルゴリズムではないので、20行ほどで書けます。

名前	説明
par	各要素の親を表す(初期値は自分が親)。
siz	各要素を親とするグループの大きさを表す(初期値は1)。
root(x)	xの親を探す。
unite!(x,y)	xのノードとyのノードを結合。小さい方が親となる。
issame(x,y)	xのノードとyのノードの親が同じかを返す。

※ちなみに、慣例上Juliaにおいて破壊的処理は!を付けることになっているので、結合処理はunite!になってます。

あとはこれをmain関数内にペタリして処理をするだけです。

par=Vector{Int}([i for i=1:n])
siz=ones(Int,n)
function root(x::Int)
    index=par[x]
    while par[index]!=index
        index=par[index]
    end
    return index
end
function unite!(x::Int,y::Int)
    rx,ry=root(x),root(y)
    if rx==ry
        return 0
    elseif rx>ry
        rx,ry=ry,rx
    end
    par[ry]=rx
    siz[rx]+=siz[ry]
end
function issame(x::Int,y::Int)
    isequal(root(x),root(y))
end

例：ACL Beginner Contest 「C - Connect Cities」
(Submission #20614886 - ACL Beginner Contest)

自力実装の利点・欠点

DataStructures.jlを使うよりもパッケージの読み込み時間がないので早い
このコード内ですべて完結しているのでバグの原因を見つけやすい
コードが比較的長くなる
サイズMのUnion-Find木を作らなければならないところを、コピペミスしてサイズNでWA ~~(実体験)~~

IntDisjointSetsを使ったUnionFind法

DataStructures.jlのインストール

DataStructures.jlがインストールされていない場合、先にPkgを開いてインストールしてください。

コマンド入力時に]を押すとPkgのコマンドを入力できます。

(@v1.5) Pkg> add "DataStructures"

(Int)DisjointSetsの説明

DataStructures.jl内にはDisjointSetsとIntDisjointSetsが存在します。
DisjointSetsはIntDisjointSetsのラッパーであり、辞書を用いてマッピングしているのでChar型とか数字以外でもUnionFindができるらしいです(必要か？)。
※d=DisjointSets(1:N)と宣言することで同様に使えます。

名前	説明
IntDisjointSets(N)	要素数NのUnionFind木を宣言。
union!(d,x,y)	xのノードとyのノードを結合。xが親になる。
root_union!(d,x,y)	xのノードとyのノードのそれぞれ親を結合。
find_root!(d,x)	xのノードの親を返す。
in_same_set(d,x,y)	xのノードとyのノードが同じグループにあるかを返す。
d.ngroups	木構造内のグループ数を返す。
num_groups(d)	おそらくd.ngroupsと同様。

# プログラムの例
using DataStructures
uf=IntDisjointSets(5)
union!(uf,2,3)
@show uf 

root_union!(uf,1,3)  #ここをunion!(uf,1,3)にすると1の親が2になる
@show uf

@show find_root!(uf,3)
@show in_same_set(uf,1,4)
@show uf.ngroups
@show num_groups(uf)

# 出力。@showに各行が対応
uf = IntDisjointSets{Int64}([1, 2, 2, 4, 5], [0, 1, 0, 0, 0], 4)
uf = IntDisjointSets{Int64}([1, 2, 1, 4, 5], [1, 1, 0, 0, 0], 3)
find_root!(uf, 3) = 1
in_same_set(uf, 1, 4) = false
uf.ngroups = 3
num_groups(uf) = 3

IntDisjointSetsを用いた提出例
https://atcoder.jp/contests/abl/submissions/20614444

DisjointSetsを用いた提出例(こちらではngroupsは使えないっぽいです)
https://atcoder.jp/contests/abl/submissions/20614009

IntDisjointSetsを用いる利点・欠点

コードが割と短く簡潔に書くことができる
効率よく書かれている(はず)のでコード自体は早い
root_union!やnum_groupsなど様々な種類の関数があるため使いやすい
DataStructures.jlをインポートする時間がかかるのでAtCoderでは少し不利

自力実装よりIntDisjointSetsの方が早い事例（2023/7/12追記）

ABC229-E (E - Graph Destruction)

i=1,2,…,N について、頂点 i まで消した時にグラフはいくつの連結成分に分かれていますか？という問題。逆から見てUnion-Findの典型。

自力実装の提出(TLE)： https://atcoder.jp/contests/abc229/submissions/43509722

IntDisjointSetsを使った提出(AC, 943ms)： https://atcoder.jp/contests/abc229/submissions/43510042

IntDisjoinSetsを使おう（戒め）

参考資料

https://juliacollections.github.io/DataStructures.jl/latest/disjoint_set/
Union find(素集合データ構造)
競プロ覚書：Union-Find まとめ - pyてよn日記
 https://ei1333.github.io/algorithm/union-find.html
素集合データ構造 - Wikipedia

応用
重み付き Union-Find 木とそれが使える問題のまとめ、および、牛ゲーについて - Qiita

2021-02-19

ffmpegを用いてフォーマット変換(mp3⇔wav,画像⇔動画)

まぁじです。最初はpydupを使って変換しようと思ってたんですが、どうやらffmpegのラッパーらしいのでこちらをつかうことにしました。これはその備忘録です。

やること

ffmpegをWindowsにインストール
パスを通す
ファイルの詳細を見る
mp3ファイル→wavファイルへの変換
wavファイル→mp3ファイルへの変換
動画を複数枚の画像に変換
複数枚の画像を動画に変換
動画ファイルのオプション変更

ffmpegをWindowsにインストール

ffmpegはCUIで操作し、動画・音声を変換したり再生したりできるフリーソフトウェアです。

ここではWindowsのインストール方法だけ説明します(Linux/MacOS/Windowsすべて動くらしいです)。

ffmpeg公式サイトのダウンロードページにアクセスし、Windowsマークにカーソルを合わせると"Windows builds from gyan.dev"が出るのでクリックします。

f:id:halss:20210103223938p:plain

ビルドページに飛ぶので、スクロールしてreleaseの"～/ffmpeg-release-essentials.zip"をクリックするとダウンロードが始まります。

ちなみにessentialsよりfullの方が使えるライブラリが多いらしいですが、Windows標準で解凍できる圧縮ファイルがessentials.zipしかないのでダウンロードしてます。

fullをダウンロードしたいなら7-zipとかLHazのような解凍ソフトを窓の杜からインストールするといいと思います。

f:id:halss:20210103225341p:plain

※2021/1/3現在です。今は変化している可能性があります。

パスを通す

Windows+Q
「環境変数を編集」と入力
pathをクリック
編集
新規
先ほどダウンロードしたffmpeg.exeの場所を登録

私の場合は\ffmpeg-4.3.1-2021-01-01-essentials_build\binにあったのでこれを追加しました。

f:id:halss:20210103230629p:plain

起動できるか確認

コマンドプロンプトを起動し、ffmpegと入力してバージョン等が出れば成功です。

$ ffmpeg
ffmpeg version 4.3.1-2021-01-01-essentials_build-www.gyan.dev Copyright (c) 2000-2021 the FFmpeg developers
  built with gcc 10.2.0 (Rev5, Built by MSYS2 project)
~~~~~~~~~~~~~~略~~~~~~~~~~~~~~

ファイルの詳細を見る

動画・画像ファイルを用意しffmpeg -i <filename>で詳細を表示します。

$ ffmpeg -i sample.MP4

ffprobe -i <filename>の方が怒られません。

$ ffprobe -i sample.MP4

mp3ファイル→wavファイルへの変換

用意した"sound1.mp3"をwavファイルに変換してみます。 ffmpeg -i <inputfile>.mp3 <outputfile>.wavでファイルを変換して出力できます。

$ ffmpeg -i sound1.mp3 sound1.wav

wavファイル→mp3ファイルへの変換

用意した"sound2.wav"をmp3ファイルに変換してみます。上の逆で、ffmpeg -i <inputfile>.mp3 <outputfile>.wavでファイルを変換して出力できます。

$ ffmpeg -i sound1.mp3 sound1.wav

動画を複数枚の画像に変換

ffmpeg -i <inputfile>.mp4 <outputfile>.jpgでフレームレート×秒数[枚]の画像ファイルが生成されます。ただし、出力ファイルはそのままだと重複してしまうので、%03dとして番号を振れます。(3桁で0埋め)

$ ffmpeg -i sample.mp4 sample%03d.jpg

また、オプションで1秒あたりの枚数(フレームレート)を変更することも可能です。

$ ffmpeg -i sample.mp4 -r 10 sample%03d.jpg

複数枚の画像を動画に変換

ffmpeg -i <inputfile>.jpg <outputfile>.mp4で動画ファイルが生成されます。連番画像であれば動画にすることが可能なようですが、通常の(連番でない)画像における方法は不明です。

$ ffmpeg -i sample%03d.jpg sample.mp4

動画→画像の変換のようにフレームレートの設定や、コーデックの設定、macOSで開けるようにするなどができます。

$ ffmpeg -r 60 -i sample%03d.jpg -vcodec libx264 sample.mp4
$ ffmpeg -i sample%03d.jpg -pix_fmt yuv420p sample.mp4

あとがき

紹介した方法のほかにもGIFファイルへの変換やサイズ変更などかなり豊富にオプションが存在するのでいろいろとみてみることをお勧めします。

参考文献

それFFmpegで出来るよ！ - Qiita

FFmpegで動画をGIFに変換 - Qiita

2021-01-01

TOEIC初受験しました

blog

高専4年生のまぁじです。
11/15午前の256回TOEICを受験しました(すでに去年ですが)。

はじめに

同じことをしたからと言って同じ点数が取れるわけではないです。
多分学びはないので普通に勉強してください。

教訓

会場にヒートテックは着ていくな。暑い。
どうしても間に合わないのであれば先にPart7を同じ番号で塗っておこう。
リスニングは最初こそ気を抜かないようにした方がいい。

使った本

TOEIC勉強でよく使われるらしい金フレ・銀フレは買ってないです。
もともと興味ないことや繋がりのないことを丸々暗記するのが苦手で、多分続かないと思ったからです。

はじめて受けるTOEIC(R)L&Rテスト全パート完全攻略

各パートごとに問題・解説と単語が載ってます。量は少なめですが解説多い方がいい人はおすすめです。
全部1周して、模試だけ2周しました。
Amazon Prime会員だと無料で読めるっぽい(要出典)ので少し悲しかったです。

公式TOEIC Listening & Reading 問題集 6

初めてで形式に慣れておく必要があると思って買いました。3日前と1日前に1回やって終わりました。

入門英文問題精講 4訂版

なんかおすすめされてたんで1週間前に買いました。半分くらいやって本番でした。
結構英文が読みやすくなった気がします。

DUO 3.0

これも1週間前に買いました。5ページくらいしかやってませんでした(今もちょこちょこ進めてます)。

結果

L295点、R315点の合計610点でした。とりあえず600点目標だったので何とかなってよかったです。

TOEICの結果出た！！！！！！！610点だ！！！！！！！！！！！！！！やった！！！ー！！！！！ pic.twitter.com/N6MoZOREdj
— まぁじ (@Hals_SC) 2020年12月3日

あとがき

舐めすぎて1週間前に始めたら周りがガチで焦りました。次こそ(次があるかはわかりませんが)、毎日習慣立てて頑張るようにしたいです。
あとは会場で暑すぎてマスク外そうとしたら怒られたので、僕が全面的に悪いし半袖着て来ればよかったなと思いました。

2020-11-17

Juliaのchmax, chminマクロについて

Julia 競技プログラミング

おはこんばんにちは！(死語)
まぁじです。ちょっと@chmaxを使う機会があったので書いてみます。

はじめに

実行環境は以下の通りです。AtCoderのコードテスト(version 1.4.0)でも動くことを確認しました。

$ julia --version
julia version 1.3.1

注意・マクロはコードの一番上に置いた方がいいです。
実行する関数より前にないとエラーが出ます。

chmax, chminについて

change maximum/minimumの略で、

chmax(a,b)はa=max(a,b)と同じ働き
chmin(a,b)はa=min(a,b)と同じ働き

これを用いてコードを短くしたりミスを減らしたりします。

ちなみに、人によってはさらに値を交換したかでtrue/falseを返すこともありますが、今回はそちらは書きません。けんちょんさんの記事などにC++のコードがありますのでそちらを参考にしてください。

Juliaのmacroについて

マクロは以下のように使います。$を用いると変数や式の展開ができます。

macro hoge(a, b, ...)
    :($a * $b)  # ここに処理を書く
end

# 実行するときにはマクロ名の前に@をつける
@hoge(1, 2, ...) # 関数の実行と同様

# もしくはこう書いてもいい
@hoge 1 2 ...  # 引数をスペースで区切る

また、マクロの展開後に変数名が衝突すると自動で名前が置き換わるのですが、esc関数を用いて既存の変数を呼び出すことができます。

julia> macro hoge2(a,b)
           esc(:($a=$a*$b)) # aにa*bを代入するマクロ
       end
@hoge2 (macro with 1 method)

julia> num=10
10

julia> @hoge2(num,10)  # num=num*10=100
100

マクロは関数とは違い、引数を評価せずに実行します。なので値ではなく式を渡すときは注意してください。

chmax, chminの簡単な実装

これを踏まえてそのまま実装してみます。(ハイライトが全然効かない…)

# ifを用いたchmax
macro chmax1(a,b)
    esc(:(
    if a<b
        $a=$b
    end
    ))
end

# max関数を用いたchmax
macro chmax2(a,b)
    esc(:($a=max($a,$b)))
end

# ifを用いたchmin
macro chmin1(a,b)
    esc(:(
    if a>b
        $a=$b
    end
    ))
end

# min関数を用いたchmin
macro chmin2(a,b)
    esc(:($a=min($a,$b)))
end

a=1として試してみましょう。

julia> @chmax1(a,2)
julia> a
2

julia> @chmin1(a,-1)
julia> a
-1

きちんとマクロが動いています。

chmax, chminを一つのマクロにする

マクロの引数として、変数や式のほか関数も与えることができるので、

minを与えたらchmin
maxを与えたらchmax

という風に改造してみましょう。

macro chmaxmin(f,a,b)
    esc(:($a=$f($a,$b)))
end

マクロ名は@chmaxminとでもしておきます。(長すぎる気もしますが)
a=1として実行してみます。正常に動いています。

julia> @chmaxmin(max,a,10)
10

julia> @chmaxmin(min,a,-100)
-100

たのしい競技プログラミングを！ありがとうございました。

参考

Julia Documentation · The Julia Language

お気楽 Julia プログラミング超入門

動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita

2020-11-06

おめでとう

blog

おめでとう Advent Calendar 10日目です。

おめでとう！ おめでとう！

おめでとう！

おめでとうございました。

おめでとうお祝い料金1000000009円を持って明日の9時、公園に来てください。

以上です。

2020-11-06

授業がはじまる

blog

おりたたみ

ご入会ありがとうございます！5000万円を指定の口座にお振込みください！