verilog書く人

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

AtCoderで青になるまでにやったこと

一年一ヶ月ほどの苦心の末、ようやく青コーダーになりました。感慨深いです。

f:id:segafreder:20190603235753p:plain
rate

全く独自性のないブログタイトルですが、なるべく他の人が書いてないことを書くようにします。胡散臭い箇所はスキップしてみてください。

続きを読む

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)の最小値を出力すればよい。

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

続きを読む

AtCoder Beginner Contest 126 XOR Matching 別解

問題: 非負整数 M (≤17) と非負整数 K (≤109) が与えられる。以下の条件を満たす0 ~ 2M の数列が存在するか判定し、存在するなら一例を示せ。

続きを読む

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

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

f:id:segafreder:20190429152842p:plain

続きを読む

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

GDBUbuntuならば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

 

続きを読む