Ubuntu 17.04にVivado 2017.2をインストールした

VivadoやXilinx SDKをLinux (Ubuntu) で動かすメモ (Ubuntu 16.04 LTS, Vivado 2016.4, 64bit環境) - Qiitaを参考にしてインストールした。参考記事との差分だけ書く。

時間がないので推敲せずに書き散らかす。

アクセス権の書き換え

root権限でインストールした後に一般ユーザーでvivadoを起動したところ、起動はするがコンソールにPermission deniedとエラーが出力されていた。

https://japan.xilinx.com/support/answers/62240.htmlの通りアクセス権を書き換えて解決した
(ちなみにAR# 62240では~/.Xilinx/Vivado以下のアクセス権だけ書き換えているが、それだけだと、xsdk起動時に~/.Xilinx/SDKディレクトリの作成に失敗してしまったので~/.Xilinx以下のアクセス権を書き換えた)

https://japan.xilinx.com/support/answers/62240.html に、末尾にroot権限でインストールするのは非推奨と書いてあるので、次回からは一般ユーザー権限としてインストールしよう…)

Cable Driverのインストール方法

cd /opt/Xilinx/Vivado/2017.2/data/xicom/cable_drivers/lin64/install_script/install_drivers
sudo ./install_drivers

xsdkの起動

GTK+3を無効にしなくても動いた?)

Documentation Navigator

docnav: error while loading shared libraries: libpng12.so.0: cannot open shared object file: No such file or directory

と表示されて起動できず。 dependencies - E: Package 'libpng12-0' has no installation candidate [ubuntu 16.10 Gnome] - Ask Ubuntuに書かれている通り、Ubuntu – Package Download Selection -- libpng12-0_1.2.54-1ubuntu1_amd64.debから落として入れた。 (i386のライブラリは無くても動く?)

AtCoder Regular Contest 080 - F - Prime Flip

F: Prime Flip - AtCoder Regular Contest 080 | AtCoder

メモ

a_{i}x_{i}のところだけ1で、他は0の数列。 b_{i} = a_{i} \oplus a_{i-1}とする。

[l,l+p)を反転するとb_{i}上ではb_{l}, b_{l+p}の2点の反転となる。 よって。 なので

  • b_{i}上での距離が素数の2点は1回の操作で同時に反転できる。
  • b_{i}上での距離が偶数の2点はゴールドバッハの予想より2回の操作で同時に反転できる(ゴールドバッハの予想は少なくとも10^{7}以下の数では成り立つので)
  • b_{i}上での距離が奇数の2点は、1回の操作で距離が偶数の2点に変換できるので、3回の操作で反転できる。

まず、距離が素数になるペアをなるべく多く作る、これにはコスト1かかる。 残った点の中で偶数座標の点同士、奇数座標の点同士でペアを組む、これにはコスト2かかる。 最後に偶数座標と奇数座標が1つずつ残っていたらペアを組む、これにはコスト3かかる。

トータルでかかったコストが答えとなる。 間に合うかどうかしらないが、最小費用流でも解けそう。

感想

自力では全く解けなかったが面白かった。 本番ではずっとa_{i}のまま考えていて、b_{i} = a_{i} \oplus a_{i-1}と変換する発想が全く無かった。 この前作ったPushRelabelの最大流ライブラリがverifyできた。Dinicよりメモリ使用量が多いうえに遅かったが。

gist.github.com

Codeforces Round #428 (Div. 2) D. Winter is here

Problem - D - Codeforces

自分で見返したときにわかるようなメモ書き。

f(x) := gcdがxの倍数になるような全てのクランの強さの総和 g(x) := gcdがちょうどxになるような全てのクランの強さの総和

とすると、f(x), g(x)は以下のように計算できる。

f(x) = \displaystyle \sum_{k=0}^{x} {k \displaystyle \binom {x}{k}} = 2^{x-1}x

g(x) = f(x) - \displaystyle \sum_{i=2}^{\infty} g(ix)

ここまでくれば答えは\displaystyle \sum_{x=2}^{\infty} g(x)xで求まる。

gist.github.com

f(x)の計算はwolframalphaに本番は投げたが、他の参加者のブログを見ると(1+x)^{n}微分から導出できるらしい。
Wolfram|Alpha: Computational Knowledge Engine

(1+x)^{n}を展開して微分すると\sum_{k=1}^{n} k \displaystyle \binom {n}{k}x^{k-1}になり、x=1を代入すると求めたい式と一致する。(1+x)^{n}微分してx=1を代入すると2^{n-1}nとなる。

よって\sum_{k=1}^{n} k \displaystyle \binom {n}{k} = 2^{n-1}n

ライブラリ その1

手元のライブラリ整理もかねて書く。(適当に書き散らかしたままだったり蟻本とかスパソにあるのをjavaで書き直しただけだったりするものも多いが)

BIT

Binary Indexed Tree または Fenwick Tree。

詳細は以下の資料に書いてある。hos.ac ドメインがいつまであるかは不安ではあるが。 http://hos.ac/slides/20140319_bit.pdf

無駄に2, 3次元のBITなど入っているが年に一回も使わない。 gist.github.com

AtCoder Grand Contest 018 - B - Sports Festival

問題

B: Sports Festival - AtCoder Grand Contest 018 | AtCoder

メモ

本番では全スポーツ実施状態を考えることすら思いつかなかった。

全部のスポーツを実施する状態を考える。 最も参加者が多いスポーツを実施しないことにする操作を繰り返し、最小値を求めればよい。 どんなスポーツの選び方をしても貪欲解以上の参加者がいることが示せるので、この貪欲法で最小値が得られる。

gist.github.com

AtCoder Grand Contest 018 - A - Getting Difference

問題

A: Getting Difference - AtCoder Grand Contest 018 | AtCoder

解法

x=gcd(A[1], … A[n])とおく。 行う操作はgcdであることに気付けば、この操作で作れる数はxの倍数になることがわかる。 なので、各A[i]について何回かxを引いてKにできるか判定すればよい。

gist.github.com

TCO17 Round 2C Easy CanidsSeesaw

問題

n匹の狼とn匹の狐がいる。 狼iの重さはwolf[i]、狐iの重さはfox[i]。 狼は入力で与えられた順で並んでいるが、狐の順番は自由に並べ替えられる。 i=1~nについて Σwolf[1..i] < Σfox[1..i] なら1ポイント獲得できる。 ちょうどkポイント獲得できるようなfoxの並べ方を求めよ。

解法

本番では辞書順最小の並びを求めるような方針で解いた。

が、バブルソート解の方が解法の正当性が証明しやすいし、実装も簡単でいい。 獲得できるポイントは辞書順最小のとき最小、辞書順最大のとき最大。 で、隣り合った要素をスワップしたときの獲得ポイントの変化は高々1なので、最小<=k<=最大ならば、バブルソートしていくと、どこかで必ずkポイント獲得する並びが得られる。

gist.github.com