verilog書く人

自称ASIC設計者です。どなたかkaggle一緒に出ましょう。

AtCoder Beginner Contest 128 E Roadwork 別解

問題

N個の工事が行われ、それぞれの工事はS_i-0.5, t_i-0.5に座標X_iで行われる。

Q人の歩行者が存在し、それぞれ時刻D_iに座標0を出発する。

歩行者は一度工事に遭遇するとそこで停止する。

各歩行者が座標いくつまで歩けるか出力せよ。

解法

想定解法全然違うけど、座標圧縮と遅延評価セグメント木(Range Minimum Query)知っていればそれを使う方が思いつきやすい気がする。

S, T, Xの工事はS - X <= D < T - Xなる時刻Dの歩行者を足止めをすることになる。

複数存在しうるそれらの工事のうち、もっとも小さいXを持つ工事が、その歩行者が歩ける距離である。

そこで、遅延評価セグメント木を用意して、全ての工事について、[S - X, T - X)の最小値をX以下に更新する。

ただし、S - X, T - Xの存在範囲は大きいので、座標圧縮を行う。

この際、クエリを全て先読みして、Dもすべて座標圧縮の対象とする。

セグメント木を全ての工事について更新したら、クエリDに対して[D, D + 1)の最小値を出力すればよい。

ここで、座標圧縮の際に辞書を作って、クエリに対して圧縮後の座標を入手できるようにしておく。 (二分探索してもよい。)

続きを読む

Ubuntu 18.04でPycharmをランチャーとお気に入りに登録する。

PyCharmを公式からダウンロードして展開して/bin/pycharm.shを叩けば実行できるが、 常に左に表示されているgnomeのお気に入りバーにこんな感じで登録されていた方が立ち上げやすい。

f:id:segafreder:20190429152842p:plain

続きを読む

Ubuntu 18.04でGDBビルドチャレンジ

GDBはUbuntuならばsudo apt-get install build-essentialでインストールすることができるが最新版を使いたい場合は自分でビルドする必要がある。

 

さて、GDBビルドチャレンジだが基本的にはこの記事が正確なのでその通りやればよい。

本の虫: GCCのSVN trunkをビルドする方法

特にflexをインストールせずにmakeすると、syslex.c not foundというメッセージが出る。

慌ててsudo apt-get install flexしても、やはり同じメッセージが出る。

この場合、もう一度ダウンロードしなおして、./configureからやり直すのが手っ取り早い。

 

一応手順

 

 公式からtar.gzをダウンロードし、展開

 

sudo apt-get install flex libgmp-dev libmpfr-dev libmpc-dev libisl-dev
cd gdb-8.2
./configure --disable-multilib
make -j2  # if you want to use 2 cpu
make install

 

自作している競技プログラミング用IDE for Rust進捗

大分動作は安定してきたので、もうAtomはやめてこちらに移りました。

ファイアーエムブレム由来でrujaionという名前にしました（暫定）

 

github.com

 

続きを読む

ThinkPad13 + Ubuntu16.04でやった設定

CapsLockキーのCtrl化

コマンド一発でCapsLockをCtrlに変える方法 | Linux Fan

 

の通りやればよい。

$ sudo gedit /etc/default/keyboardで

XKBOPTIONS="ctrl:swapcaps"

の行を加える。

ただし、

$ sudo systemctl restart console-setup

しても設定は反映されなかったが、再起動すると無事CapsLockキーは無効になった。

 

Bluetoothの起動時無効

Bluetooth 無効化 - からっぽの日記(2011-07-08)

 

を行う。

$ sudo gedit /etc/sysfs.conf

して、

devices/platform/thinkpad_acpi/bluetooth_enable = 0

の行を追加する。

 

トラックポイントの感度調整

 色々調べたが、thinlpadでもX13だけドライバの場所が違うので、方法が違ったりする。

結局。

$  xinput --list --short
⎡ Virtual core pointer id=2 [master pointer (3)]
⎜ ↳ Virtual core XTEST pointer id=4 [slave pointer (2)]
⎜ ↳ ETPS/2 Elantech TrackPoint id=13 [slave pointer (2)]

みたいな表示を出して、TrackPointのドライバの名前を調べる。
$ xinput --set-prop "ETPS/2 Elantech TrackPoint id" "Device Accel Constant Deceleration" 0.35

とかやると速くなる。最後の数字が小さいほど速い。0.1とか入れると扱いづらくなるので注意。

 これを.bashrcにいれるなりして起動時に実行されるようにする。

ホントはsystemdとか使った方がいいんだろうけど、まだうまくいってない。