2021-03-14

AHC001方針メモ

AtCoder Heuristic Contest 001に出ましたシステス前時点で48,418,822,292点、192位でした

軽く方針メモを残していたので、そのまま記事にコピペします

AHC001方針メモ

初手、ルールを把握した後

希望の場所1マスだけを与えるプログラムをとりあえず書く(未提出なので点数は知らない)。入出力回りとビジュアライザの仕様を把握

とりあえず最初に思いついたもの

最初に希望の1マスを与えておき、そこから上下左右に範囲を伸ばす。希望する範囲で伸ばせるだけ伸ばす。O(N²)。左に伸ばせるかどうかを最初に判定するので当然だけど、ほとんどの範囲が横長になった。 41,143,612,083点 https://atcoder.jp/contests/ahc001/submissions/20686741

横長対策

範囲が横長になるのはあんまり良くなさそうだと思ったので、解消する。範囲を広げる際に一気に伸ばすのではなく1マスずつ伸ばしていくようにした。多分O(N²)にsqrt(10000)ぐらいの定数倍がつく。実行時間の増大と引き換えに45,268,726,139点(+4,125,114,056) https://atcoder.jp/contests/ahc001/submissions/20736626

他の広告枠が邪魔

ビジュアライザの出力を見ていて、他の企業の広告枠が邪魔になっていてあまり点数を伸ばせていない企業があることに気づいた。ある企業の広告枠を右に移動させてその隙間にもう少し面積を与えるみたいなことをすると点数が伸びそう。片側が広告枠でふさがれているとき反対側に1マスずつ移動させる方針でとりあえず実装。実装が面倒でした46,716,099,783点(+1,447,373,644) https://atcoder.jp/contests/ahc001/submissions/20740459

操作順序は関係あるか?

今までは適当に生成した可変長配列を舐めていろいろやっていたが、この操作順序が点数の伸びを阻害している可能性に気づいた。とりあえずループ毎にshuffleするようにした。配列の並び替えを想定したコードだったのでシャッフルを書くだけでした46,778,126,853点(+62,027,070(誤差かな?)) https://atcoder.jp/contests/ahc001/submissions/20740685

シャッフル分節約できないかな

この時点で次の手は思いついていたけど、タイミング的にお風呂とか食事の片手間にできる軽いテストをやっている。

適当にシャッフルする方針にしたときに実行時間が1秒ぐらい伸びた(1,400ms->2,400ms程)ので、これを削減できないかと思った。固定の並び順でできるだけいい点を出すには、rが小さいものを優先すればいい気がする。範囲を広げる処理はrが小さい順、既にある広告枠を避ける処理はrが大きい順と小さい順を両方試す。それぞれ46,735,106,956点 https://atcoder.jp/contests/ahc001/submissions/20741114 と46,716,569,615点 https://atcoder.jp/contests/ahc001/submissions/20741219 だったので、広告枠を避ける処理はrが大きい順にやるのがよさそう? どちらにしてもshuffleするほうがいい点数が出てるのでTLEしたときに採用する。

シャッフル節約の2

固定の並び順でなくても一定の規則にしたがって並び替えればshuffleと同等かそれ以上の効率が出ないかなと思い立つ。ある時点でs/rが小さいものの面積を大きくするほうが全体の点数からして効率がいいので、shuffleの代わりにこのソートを書く。 46,721,508,825点 https://atcoder.jp/contests/ahc001/submissions/20741491 だったので採用は無し。

シャッフル節約の3

面積を大きくしたときの効果が大きいものを優先するのが良さそうなので点数計算の式を微分した値が大きい順に処理をしてみる。やはりあんまり効果はない46,719,560,602点 https://atcoder.jp/contests/ahc001/submissions/20741974

一度広げた範囲を小さくする

一度広げた広告枠が他の広告枠の広がりを阻害している場合がある。ので、隣接している広告枠であって、自分が小さくなることで減少する点数を相手が大きくなることにより得られる点数が上回る場合に自分を小さくしてもいい。という方針で実装。50位を切って小躍りしてた47,973,416,260点(+1,195,289,407) https://atcoder.jp/contests/ahc001/submissions/20743449

このへんで無限ループになる処理パスが存在するようになったらしいので時間により処理を打ち切るようにした。ジャッジに最低4分ちょっとかかるようになりましたね?

横にずらせばまだ大きくできるやつがあるのでは

範囲を小さくするときに、他の枠に触っている辺を1マス引くことで小さくしている。これをほかの枠に触っている辺と垂直方向の辺を引くことでも小さくするようにする。 48,314,228,405点( +340,812,145) https://atcoder.jp/contests/ahc001/submissions/20761270

面積を縮小したタイミングで処理を終了したら損かも?

処理を時間で打ち切っているので、面積を縮小したタイミングで終了するという損が発生する可能性があると思った。最後100msは面積を縮小する処理を行わないようにした。乱数のブレ程度の点数低下が発生したのであんまり大きな影響はないかもだけどこのままいく。 48,263,482,621点 https://atcoder.jp/contests/ahc001/submissions/20762796

垂直方向に引く処理を変えてみる

ほかの枠に触っている辺と垂直方向の辺を引く処理で、引く/引かないの二値だったのをにぶたんしてどこまで引くかという処理にしてみた。点数が下がったので非採用 47,278,131,191点 https://atcoder.jp/contests/ahc001/submissions/20764167

面積を広げる処理専用の時間を伸ばす

最後100msは面積を広げる処理のみを行っていたのを、最後1500msまで伸ばした。ほとんど変わらない 48,261,114,447点 https://atcoder.jp/contests/ahc001/submissions/20764507

水平に引く処理をもうちょっと賢くする

今までは全枠のペアに対して判定をしていたのを、おなじ枠に接している複数の枠を同時に考慮してやるようにした。若干点数が下がった48,256,842,441点 https://atcoder.jp/contests/ahc001/submissions/20766227

いろいろ試したところ、これはこの時点だと処理が重い割に改善効率が良くないので全体的にあんまり良くはないらしいことがわかった。

正方形に近づける

枠が細長い長方形になった場合他の枠を阻害することが多いと思ったので、縦横比が極端な場合にそれを補正して正方形に近づけるような処理を追加した。

最初に一度広げる

現状の改善策が、他の枠に触れているという条件で動くものが多いので、横長対策のときのコードで一度限界まで広げるのを第一段階として実施した後処理を開始するようにした。これにした場合に水平に引く処理を賢くしたものが結構いい働きをしてくれるようになった。

採用しなかった方針

試してないから知らんけど多分そんなに良くない方針

希望に答える企業とそうでない企業を取捨選択する

ある企業には適当な1マスのみを枠として与え(0ポイント)、それ以外の企業に100%の枠を与えるみたいなこと。

[x,y]=meshgrid(0:1e-3:1)
mesh(x,y,1-(1-min(x,y)./max(x,y)).^2)

これをプロットすると上のほうはなだらかになってるので、ある企業は100%、ある企業は0%という取捨選択をするよりもすべての企業に80%応える方が高得点になると思って不採用点数の計算式が2乗じゃなくてルートだったらアリかも。

2020-09-29

Code With Meためしてみた

JetBrainsからCode With MeというサービスがEAPで出ました! blog.jetbrains.com

概要は↑のリリース記事をどうぞ

ぱっと見る限り、Visual Studio Live Shareのようにリモートでエディタに接続してペアプロなどできる機能のようです。 Live Shareの発表時点で"JetBrainsIDEで使えるようにならないかなぁ"とか思ってたので、これは試すしかないと思い軽く触ってみました。

現段階ではまだEAPであるため、ご利用の際は自己責任で☆

さて、JetBrains系IDE(RiderとDataGripを除く)の2020.2.xに対応しているらしいので、ちょうど起動していたCLion2020.2.3で試してみます。

プラグインのMarketplaceにCode With Meのプラグインが追加されているのでインストールしました。

f:id:White_Green:20200929012337p:plain

すると、IDEの右上のほうにこのようなボタンが出現

f:id:White_Green:20200929012659p:plain

これを押したところからEnable Access and Copy Invitation Linkを押すと

f:id:White_Green:20200929012740p:plain

招待リンクがコピーされたようです

f:id:White_Green:20200929012906p:plain

コピーされたリンクをブラウザで開くと、接続用ソフトのIntelliJ Clientがダウンロードされて起動します。同時にIDE側では接続許可のダイアログが出ていました

f:id:White_Green:20200929013129p:plain

ここで接続許可をすると、IntelliJ Client側でIDEで開いているファイルにアクセスできました。少し編集を試してみましたが、IntelliJ Clientから編集してもタイムラグを全く感じない程度の時間でIDE側のコードが変更されます。素晴らしいです。 Rustのプロジェクトを開いていたためIntelliJ Client側から実行を試してみましたが、どうやら実行はIDE側でされて出力等がIntelliJ Client側で見れるという構造になっているようです。使い勝手としてはリモートに接続されていることを感じることも無くいつもと同じ感覚で実行ができました。ただプラグインによる出力の整形には対応していないらしく、cargo testを実行した際の表示が文字のみで少し見にくかったです。IDEだと専用のUIがあるのですが、ここはIntelliJ Clientでも将来的に対応されることを期待しています。

現在は同じPC内でIDEとIntelliJ Clientの両方を開くというテストしか行っていないため、別PCや別ネットワークからのアクセスもまた試したいです。

2020-09-25

ループを分割する

スレッド生成等で、[0, length)のforループをn個のブロックに分割したい場合があります。スマートな方法を思い出そうとして手間取ったので備忘録としてコードを残しておきます。 n個のブロックに分割ではなくa個づつのブロックに分割したい場合はn=length/aまたはn=(langth+a-1)/aなどとすればOKです。

for block_num in 0..n {
    // block_num ∈ [0, n)
    for index in block_num * length / n..(block_num + 1) * length / n {
        // index ∈ [block_num * length / n, (block_num + 1) * length / n)
        // do something
    }
}

2020-08-20

【Rust】型黒魔術+associated constによる計算速度改善

Rust

Rustのtraitでは、associated type(関連型)とassociated const(関連定数)という機能が使えます。

trait SomeTrait {
    const ASSOCIATED_CONST: usize;
    type AssociatedType;
}

struct StructA;
impl SomeTrait for StructA{
    const ASSOCIATED_CONST: usize = 10;
    type AssociatedType = i32;
}

struct StructB;
impl SomeTrait for StructB{
    const ASSOCIATED_CONST: usize = 100;
    type AssociatedType = i128;
}

このように、traitを実装する構造体によって振る舞いを変えることができます。 associated typeについては、演算子オーバーロードをしたことがある人は見たことがあると思います。

さて、このassociated typeですが、ジェネリクスと組み合わせることで黒魔術的なことができます。

struct Math;
struct T;
struct F;

trait TAnd<A, B> { type Result; }

impl TAnd<F, F> for Math { type Result = F; }
impl TAnd<F, T> for Math { type Result = F; }
impl TAnd<T, F> for Math { type Result = F; }
impl TAnd<T, T> for Math { type Result = T; }

このような定義をすることで、 <Math as TAnd<F, T>>::Result というような書き方で構造体 F を表すことができます。これの何が嬉しいかというと、これは繰り返し適用可能です。例えば、 <Math as TAnd<<Math as TAnd<F, T>>::Result, T>>::Result みたいなことができます。さらに、trait境界を利用することでジェネリクスの利点を大きく活用できます。例えば以下のような感じです。

trait TAnd3<A, B, C> { type Result; }

impl<A, B, C> TAnd3<A, B, C> for Math
    where Math: TAnd<A, C>,
        Math: TAnd<<Math as TAnd<A, B>>::Result, C>
{
    type Result = <Math as TAnd<<Math as TAnd<A, B>>::Result, C>>::Result;
}

~~だんだん黒魔術じみたコードになってまいりました。~~ これで、Andが定義されている構造体に対して3変数のAndをとることができます(多分)。また、associated constに対しても同じようにジェネリクスでいろいろできます。

さて、これを使えば何ができるかというと、行列のサイズをコンパイル時に決定できます。これによって、コンパイラによる最適化時に行列のサイズがわかるため少し計算速度が上がると予測しました。また、行列計算のときは行列のサイズが等しいなどの計算が定義されるための制約がありますが、これがコンパイル時に満たすことを保障できるメリットはあります。

ということで、実際に書いて検証してみました。コードは以下のGitHubにあげてあります。型計算の~~黒魔術~~メイン部分については src/lib.rs を、行列演算の実装と測定プログラムについては ct_math_test/ をご覧ください

github.com

ある程度の速度で計算可能な行列の和と積の計算速度について、サイズをコンパイル時に決定したものがそうでないものの何%の時間で処理を完了したかというグラフがこちらです

f:id:White_Green:20200820165804p:plain — 計算速度差測定結果

f:id:White_Green:20200820165807p:plain — 計算速度差測定結果

なんと、和演算においては最大50%、積演算においては最大75%もの処理時間削減に成功しています。極値でなくとも、10%程度の削減は安定してできているようで、十分な効果があるのではないでしょうか。おそらくコンパイル時にループ展開がされることが効いているのだと思われますが、これほどまでとは。ということで、コンパイラの最適化はすごいという話でした。

測定プログラムについて補足

計算のプログラムについては、両者ほぼコピペの同じものを利用しています。積演算については、あまりにも遅かったのでキャッシュ最適化をしました。その関係でボトルネックがキャッシュから移動している可能性があります。和演算は特に最適化をしていないので、キャッシュがボトルネックになって最適化が効きにくくなっている可能性がありますので、二つの演算に対する比較は単純にはできません。また、利用したプログラムはシングルスレッドですべての計算を行うものです。

2020-07-08

加算器性能比較

比較対象

順次桁上げ加算器
4bitごとの桁上げ先見加算器(桁上げが0,1のものを両方計算してマルチプレクサで選択するやつ)
8bitごとの桁上げ先見加算器(同)
prefix加算器

のそれぞれ16bit,32bit,64bitのもの

比較方法

シミュレータの動作を録画して解析

測定方法

使用ツール

論理回路シミュレータ : Minecraft Java Edition 1.12.2 + ProjectRed

動画解析用ツール : Adobe Premiere Pro

測定内容

nbitの加算器の動作を測定する場合、(2ⁿ-1)+1を計算する。

測定結果

順次桁上げ加算器

16bit : 3.03s
32bit : 6.08s
64bit : 15.27s
4bitごとの桁上げ先見加算器
16bit : 1.07s
32bit : 1.20s
64bit : 2.13s
8bitごとの桁上げ先見加算器
16bit : 1.26s
32bit : 2.03s
64bit : 2.15s
prefix加算器
16bit : 0.25s
32bit : 1.02s
64bit : 1.12s

f:id:White_Green:20200708031031p:plain

まとめ

prefix加算器は計算が速い

期待してたほど面白い結果じゃなかった...

2019-11-30

Rustのマクロが面白かったのでBrainfuckの処理系を作ってしまった

Rust

タイトルの通りです

Rustのマクロを初めて触ったのですが、結構いろいろできそうでした(というかチューリング完全らしい)

条件付きですが自分で構文のパースもできるようで、これは何かできないかとおもったところで思いついたのがBrainfuckでした

Rustのマクロについては、こちらの記事がかなり詳細に書いてくださっているので構文などはこちらをご参照ください qiita.com

また、Brainfuckの仕様についてはWikipediaのものに従ったつもりです ja.wikipedia.org

コード

さて、私が書いたBrainfuckを処理するマクロがこちらです

3-43行がマクロの定義です 9パターンの分岐があります

まずいちばん上のパターンは最初に呼ばれ、メモリやポインタの定義を担当します memoryという配列がBrainfuckが扱えるメモリ領域になります

2番目は一番最後に呼ばれ、処理内容をすべて処理し終わったときに該当し、何もしないという命令を返します

3番目以降で実際に命令を処理しています慎重に見れば、一番前の命令のみパターンマッチし、2番目以降は再帰的に処理していることがわかると思います(1番下のみ例外)

46,47行目がこのマクロの呼び出し側ですこのコードはABCと出力するBrainfuckのコードですコンパイル時にマクロによりRustのコードに置換され、コンパイルされます

問題点

このコードの問題点として、字句解析は基本的にRustのパーサ(トークナイザ?)が行うため、Rustの言語仕様で演算記号として定義されてる>>などが正常に処理されません間にスペースを入れれば正常に動くのですが、このあたりはできればもう少し柔軟にできればよかったですね

ちなみに、マクロの書き方を調べてたのは、これでパーサを定義できないかなとか考えてたからなんですけど、変数名等の識別子に関して自分で1文字ずつパースすることは同じ理由でできなさそうなので諦めました... マクロにBNF渡してパーサを定義するとかちょっと便利そうだったんですけどね　残念

追記

面白かったので>>と<<をサポートしてみた。https://t.co/AFkBatY4J4
分割すればOK。あるいは>>が来たら2回moveでもいいけどね。https://t.co/7SEEtm6ewx
— κeen (@blackenedgold) November 30, 2019

>>や<<は> >や< <に置換するようなルールを作れば対応できるという提案をいただいた
私のコードだと実は>>や<<以外にも->等がエラーになりますが、同様に対応するルールを作れば対応できそう

(この方法でもやはりパーサの定義までは繋がりそうにないのが悲しいところ)

2019-06-26

計算量の表現 (O|Θ|Ω)記法まとめ

計算機科学計算量

アルゴリズムの計算量を表現する方法として、 $O$ 記法や $\Theta$ 記法、 $\Omega$ 記法があります。
それらの定義と違いについてまとめていきます。

定義

何らかのアルゴリズムの計算量が自然数から自然数への関数 $f(n)$ で表されるとするときそれぞれの定義はこのようになっています $$ O(g(n))=\lbrace f:\mathbb{N} \rightarrow \mathbb{N}|\exists{c}>0\exists{n_0}\forall{n}>n_0[f(n)\leq cg(n)]\rbrace $$ $$ \Theta (g(n))=\lbrace f:\mathbb{N} \rightarrow \mathbb{N}|\exists{c_1}>0\exists{c_2}>0\exists{n_0}\forall{n}>n_0[c_1g(n)\leq f(n)\leq c_2g(n)]\rbrace $$ $$ \Omega (g(n))=\lbrace f:\mathbb{N} \rightarrow \mathbb{N}|\exists{c}>0\exists{n_0}\forall{n}>n_0[cg(n)\leq f(n)]\rbrace $$ ここで、 $f(n)\in O(g(n))$ であるときに、そのアルゴリズムの計算量は $O(g(n))$ であるといいます。 $\Theta$ および $\Omega$ についても同様です。

解説

上の定義をみて「なるほど」ってなった人はここより先は読む必要はありません。

まず、 $\Theta$ について解説していきます。それ以外のものはこれを少し変化したものだからです。 $$ \Theta (g(n))=\lbrace f:\mathbb{N} \rightarrow \mathbb{N}|\exists{c_1}>0\exists{c_2}>0\exists{n_0}\forall{n}>n_0[c_1g(n)\leq f(n)\leq c_2g(n)]\rbrace $$ 定義を再掲しておきます。
まず、 $$ \Theta(g(n))=\lbrace f:\mathbb{N} \rightarrow \mathbb{N}|\cdots \rbrace $$ この部分は、 $\Theta(g(n))$ は $f:\mathbb{N}\rightarrow \mathbb{N}$ (自然数から自然数への関数)からなる集合だといっています。この部分は正直無視してもいいと思います。
|よりも右側ではその関数の条件を指定しています。 $$ \exists{c_0}>0\exists{c_1}>0\exists{n_0}\forall{n}>n_0[c_1g(n)\leq f(n)\leq c_2g(n)] $$ 日本語で表記するなら「 $c_0(>0)$ と $c_1(>0)$ 、 $n_0$ が存在してそれらはすべての $n(>n_0)$ に対して $c_1g(n)\leq f(n)\leq c_2g(n)$ が成立する」というところでしょうか
左側から順に表記しているので日本語と記号の対応関係は探してください
つまり、 $f(n)$ の増加を $g(n)$ の定数倍で挟めるということです
直感的には、計算量が $\Theta(g(n))$ というのは $n$ が大きいとき計算量を $g(n)$ の定数倍でだいたい近似できると思えばいいと思います

$O$ および $\Omega$ については、 $\Theta$ の式から $c_1$ か $c_2$ のどちらかが無いものなので、
$f\in O(g(n))$ であるとき、 $f(n)$ は $n$ が十分大きいとき、 $g(n)$ の定数倍より大きくない
$f\in \Omega(g(n))$ であるとき、 $f(n)$ は $n$ が十分大きいとき、 $g(n)$ の定数倍より小さくない
ということを表すので $O$ は計算量の上限を、 $\Omega$ は計算量の下限を表してるといえます。

上限と下限しか表さないので、計算量が $f(n)=5n^3+2n^2+3n+1$ のとき、この計算量は $O(n^3)$ ですが、 $O(n^5)$ であるともいえます。なんなら $O(n!)$ と書いても間違いではありません。 $\Omega$ についても同様で、 $\Omega(n)$ とか $\Omega(\log n)$ 、 $\Omega(1)$ と書いても間違いではありません。

例

例えば、計算量が $f(n)=5n^3+2n^2+3n+1$ で表されるとき、この計算量は $\Theta(n^3)$ であるといえます。

$\Theta(n^3)$ の定義より、ある $n_0$ よりも大きいすべての $n$ に対して $$ c_1n^3\leq 5n^3+2n^2+3n+1 \leq c_2n^3 $$ が成立する $c_1$ と $c_2$ が存在します。
これを各辺 $n^3$ で割ると $$ c_1\leq5+\frac{2}{n}+\frac{3}{n^2}+\frac{1}{n^3} \leq c_2 $$ $n$ が十分大きいとき、 $\frac{2}{n}+\frac{3}{n^2}+\frac{1}{n^3}$ は0に収束するので、これを満たす $ｃc_1$ と $c_2$ は存在します

逆に、計算量が $f(n)=2n^2+3n+1$ で表されるとき、この計算量は $\Theta(n^3)$ ではありません。

$f\in \Theta(n^3)$ であるなら $\Theta(n^3)$ の定義より、ある $n_0$ よりも大きいすべての $n$ に対して $$ c_1n^3\leq 2n^2+3n+1 \leq c_2n^3 $$ が成立する $c_1$ と $c_2$ が存在するはずです。
これを各辺 $n^3$ で割ると $$ c_1\leq \frac{2}{n}+\frac{3}{n^2}+\frac{1}{n^3} \leq c_2 $$ $n$ が十分大きいとき、 $\frac{2}{n}+\frac{3}{n^2}+\frac{1}{n^3}$ は0に収束するので、どんな大きな $n$ に対してもこの式が成立する $c_1(>0)$ は存在しません。

実用上簡単な方法として、計算量の式のうち、1番発散が早い項から係数を外して $g(n)$ として $O(g(n))$ にするとOKだったりします
アルゴリズムの計算量で扱うのは最悪計算量であることが多いので $O$ のみわかれば十分な場合も多いです(競プロだとだいたいこれ)
( $\Theta$ 及び $\Omega$ については必ずしも成立しません(例:インサートソートは $\Omega(n)$ で $O(n^2)$ なので $\Omega$ は発散が早い項を入れるだけではだめで、 $\Theta$ を定義できません))

ちなみに、発散が早い項というのは、早い順に
$n!> 2^n > \cdots > n^3>n^2> n\log n>n >\log n>1$ といった感じです( $\sqrt{n}$ がどこに入るのかいまいち把握してないけど $\log n$ と同じかちょっと大きいぐらいと思っている)

まとめ

$O$ と $\Theta$ での表記は深く考えずにだいたい同じだと思ってもそんなに問題ない(自分で書くときには書き分ける)
$\Omega$ はほとんど使わない

AHC001方針メモ

初手、ルールを把握した後

とりあえず最初に思いついたもの

横長対策

他の広告枠が邪魔

操作順序は関係あるか?

シャッフル分節約できないかな

シャッフル節約の2

シャッフル節約の3

一度広げた範囲を小さくする

横にずらせばまだ大きくできるやつがあるのでは

面積を縮小したタイミングで処理を終了したら損かも?

垂直方向に引く処理を変えてみる

面積を広げる処理専用の時間を伸ばす

水平に引く処理をもうちょっと賢くする

正方形に近づける

最初に一度広げる

採用しなかった方針

希望に答える企業とそうでない企業を取捨選択する

測定プログラムについて補足

比較対象

比較方法

測定方法

使用ツール

測定内容

測定結果

順次桁上げ加算器

4bitごとの桁上げ先見加算器

8bitごとの桁上げ先見加算器

prefix加算器

まとめ

コード

問題点

定義

解説

例

まとめ