あなたは、joisinoお姉ちゃんと以下のようなゲームをしています。

最初、何も書いていない紙がある。

joisinoお姉ちゃんが一つの数字を言うので、その数字が紙に書いてあれば紙からその数字を消し、書いていなければその数字を紙に書く。これを $N$ 回繰り返す。

その後、紙に書かれている数字がいくつあるかを答える。

joisinoお姉ちゃんが言った数字が、言った順番に $A_{1}, . . ., A_{N}$ として与えられるので、ゲーム終了後に紙に書かれている数字がいくつあるか答えてください。

　　　リンク：C - Write and Erase

で、私が考えたプログラムは以下の通り（言語は全てjava）。

１．０から９億９９９９万９９９９までの数字に対応したboolean型の配列を用意し、

　　数字が読み込まれるたびに論理値を切り替える。

　　結果：Runtime Error

　　ちょっと考えれば至極当たり前の話。こんなアルゴリズムではメモリがいくらあっても足らない。

２．ArrayListのインスタンスを用意し、数字が読み込んだ時リスト内に数字があればそれを消去し、なければリストにその数字を追加する。

　　結果：Time Limit Exceeded

　　なかなかいい案だと思ったが、テストケースの最後の２個がTLEとなってしまった。

ここからすごく時間をかけた。forループを減らしたりアルゴリズムを変えたりしたがどうしてもTLEが解消されない。

数十分考えた後に考えた結果、「ArrayListをもっと高速化できないか？」ということだった。

「ArrayList　高速化」ググってみると・・・トップにこんなブログが見つかった。

d.hatena.ne.jp

要するにArrayListよりHashSet使った方が処理がとても早くなるよ、ということだった。なので早速プログラムに組み込むことにした。ArrayListの宣言をHashSetに変えるだけでOK。メソッドの変更も不要だった。

そしてプログラムを提出すると・・・あっさりとAcceptedになった。

TLEの時はアルゴリズム自体は正しいんだから、処理に時間がかかってる部分を見つけて修正するとか、検索してより高速なクラスを使用するといったことが必要だと学んだ。

TLEの時に下手にアルゴリズムを変更してもあまりいい結果にはならないということだ。

2017-08-15

ASLRについての個人的なメモ

Windows Serverの勉強をする中でASLRという言葉が出てきた。気になったのでメモ。

ASLR（Address Space Layout Randamization）とは

名前の通り、データとか命令とかをメモリ配置を番地順に置くのではなくてランダムに配置する機能。配列とかもランダム番地に設置されるらしい。

なぜこんな機能があるのかというと、セキュリティ対策。ランダムに配置することで攻撃者がメモリから全データの入手を困難にする。ASLRがないと配列は番地順になっているので、メモリ番地を順々にインクリメントすれば配列内のすべてのデータを入手することができてしまう。

詳しいことは以下のサイトから拝読しました。

http://qiita.com/satoru_takeuchi/items/5c80c4e255e21c5b4b8a

しかしそんなASLRもJavaScriptで無効化する攻撃手法が発見されたらしい。

http://pc.watch.impress.co.jp/docs/news/1044822.html

要するにWebページにスクリプトを仕込んでおけば自動的にASLRが無効になる攻撃。

しかもほぼすべてのCPUに対して有効。パソコンだろうがスマホだろうが関係なし。

いやーJavaScriptって怖いなー。