Mavenメモ

作成する

mvn archetype:generate -DgroupId=com.example -DartifactId=sample # createはremoved
mvn eclipse:eclipse # eclipseプロジェクトを生成する場合

実行する

  • 方法1
mvn exec:java -Dexec.mainClass="com.example.App"
mvn # activeByDefaultをtrueにしているのでプロファイルの指定を省略しても良い
mvn -Ptest-profile
mvn
mvn exec:java

依存関係抱き合わせのjar作成

pom.xml · GitHub のadd部分を追加して以下のコマンドを実行。

mvn package assembly:single
java -jar "target\sample-1.0-SNAPSHOT-jar-with-dependencies.jar"
java -jar "target\test-jar-with-dependencies.jar"

次数からグラフを復元する

degree setから復元する

Dをdegree set {d1, d2, d3, ..., dn } (d1 < d2 < ... < dn)として、f(D)をdegree setを満たすグラフを返す関数とすると

f(D) = dn+1頂点のクリーク - f({dn - d1, dn - d2, ... , dn - d(n-1)})

となる

出題例

次数全体から復元する

判定だけならErdős–Gallai theorem - Wikipedia

復元するならHavel–Hakimi algorithm - Wikipedia

出題例

rustupで特定のバージョンのコンパイラをインストールする

例えば 1.10にする場合、以下のコマンドで切り替えられる。

rustup default 1.10.0

戻したいときには以下のコマンド(uninstallはしなくとも良いが)

rustup default stable
rustup uninstall 1.10.0
rustup default nightly-2018-01-03

参考 How to downgrade "stable"? - help - The Rust Programming Language Forum

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