読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

City Construction [HackerRank World CodeSprint 11]

https://www.hackerrank.com/contests/world-codesprint-11/challenges/hackerland

問題概要

N頂点M辺の有向グラフがある。
ここでQ個のクエリを処理する。

  • 1 x d : 新たに頂点を1つ用意し、d=0ならxから新頂点へd=1なら新頂点からxへ有向辺をはる
  • 2 x y : 頂点xから頂点yへ到達可能かを判定
続きを読む

壊れたアクセサリー [yukicoder No.517]

http://yukicoder.me/problems/no/517

続きを読む

A or...or B Problem [AtCoder Grand Contest 015 D]

http://agc015.contest.atcoder.jp/tasks/agc015_d

続きを読む

Evilator [AtCoder Grand Contest 015 B]

http://agc015.contest.atcoder.jp/tasks/agc015_b

続きを読む

A+...+B Problem [AtCoder Grand Contest 015 A]

http://agc015.contest.atcoder.jp/tasks/agc015_a

続きを読む

競技プログラミングにおける数え上げ数学計算問題まとめ

数え上げ数学計算

問題

階乗の逆元をかけて計算する系

【発展的話題】 CRT(中国人剰余定理)とルーカスの定理を使うと解ける二項定理

問題1 解説
問題2 解説

前提知識
hamayanhamayan.hatenablog.jp

上記の2問題で求められる計算は
C(a,b) mod m
a,b <= 10^18, m<10^6(素数じゃないかも)
である。

計算手順
1. modを素因数分解する
2. 各素因数の累乗をmodとして二項定理を解く(uwiさんのサイトのこの部分の手法を使う)
3. それぞれ解けた答えでCRTを解くと答えが出る

【発展的話題】 ウィルソンの定理

N! mod Mを解くのに必要
(M-1)! ≡ -1 (mod M)という定理がウィルソンの定理

Windows BashでGKLEEを動作させるまで

GKLEEとは

  • GPUプログラムの検証ソフトウェア
  • Utah大学の研究成果 サイト

実行環境

  • Windows 10 Home 64bits
  • Windows Bash
  • GKLEE コミットf77577343c67a3f1815ce5e802e2c933f8df876a

環境構築

1. 必要な物を入れる

sudo apt-get install git bison flex libboost-dev gcc-multilib g++-multilib

普通に入れると、cmakeのバージョンが足りないので、以下のサイトを参考にこれだけ最新を入れる
https://askubuntu.com/questions/610291/how-to-install-cmake-3-2-on-ubuntu-14-04

2. 最新版を持ってきて、ビルド用フォルダを作る

cd ~
git clone https://github.com/Geof23/Gklee.git
cd Gklee
mkdir build
cd build

3. ビルドする

cmake ..
make -j4

時間が結構かかります
あとサイズも結構でかいので、注意

4. パスを通す

cd ~
vim .bashrc

これでbashrcの末尾に

export KLEE_HOME_DIR=~/Gklee
export PATH=$KLEE_HOME_DIR/bin:$PATH

を挿入し、

source .bashrc

で反映させる

テスト

cd ~/Gklee
git clone https://github.com/Geof23/GkleeTests.git
cd GkleeTests/deadlock_0
../execute_test.sh deadlock_0.cu

をすると、実行できる。gklee_log.txtに結果が書いてある(デッドロック起きてるぞって結果)