srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

ABC 219 C - Neo-lexicographic Ordering

abc

問題 問題概要 指定された辞書順で文字列をソートする。 解法 文字列を27進数として考え、数に変換する。文字列の長さが異なるもの同士を比較するときは注意が必要である。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; int main () { stri</bits/stdc++.h>…

ブレゼンハムアルゴリズム

与えられた始点と終点の間に連続した点を置き、近似的な直線を引くためのアルゴリズムである。y = ax + b を近似する場合、ある整数 x に対して、y の値を計算し、その値を四捨五入して整数値にした値を近似値とすればよい。 この操作を始点から終点までのす…

pthreadによるスレッド間でのカウンタの共有

まず以下のプログラムのように、変数xを複数のスレッドが共有し、それぞれのスレッドがCOUNT_NUM回、変数xをインクリメントする処理を行う。 あるスレッドが(*(int *)i) += 1を実行する間に、他のスレッドも同じ部分を実行すると、競合が起こり、最終的に変…

store to load forwarding

あるメモリアドレスに書き込む命令の後に同じアドレスから読み込む命令が続くとき, store forwarding が行われる. mov DWORD [esi], edi mov eax, DWORD [esi] 上の例だと1行の書き込みが実際にL1$に書き込む前に, Store Bufferに書き込まれ, 読み込む命令は…

main()の前後で関数を呼び出す

GCCの拡張機能を使って行っています. #include <stdio.h> __attribute__((constructor)) void foo() { printf("hello, before main\n"); } __attribute__((destructor)) void bar() { printf("hello, after main\n"); } int main(int argc, char const *argv[]) { pri</stdio.h>…

CPUキャッシュの最適化について

Non-blocking Cache キャッシュメモリの構成法の一つであり, キャッシュミスが起こり, それが処理されている最中でも, cache アクセスを可能にする. さらにメモリレベルの並列性(Memory-level parallelism) を使用することで, 同時に複数のキャッシュミスを…

自己書き換えコード(self-modifying code)

自己書き換えコードとは, 実行時に自分自身の命令を書き換えるコードのことである. 以下のコードでは, foo() 関数の i++ の命令を i += 2に自己書き換えしている. 順に説明していくと, まず mprotect() 関数でfoo関数の命令が書かれているページに読み, 書き…

Intel Pin の使い方

DBI

Dynamic Binary Instrumentation (DBI) は実行時にバイナリに命令を挿入することによって, プログラムの実行トレースから情報を取り出す技術であり, それを用いたツールの一つである Intel Pin を使っていく. 以下で簡単に使っていく手順をメモしていく. 公…

next_permutation の逆 辞書順の大きい順番

comp を指定する https://cpprefjp.github.io/reference/algorithm/next_permutation.html 上のサイトを見ると, 第三引数に比較関数を取れるので, 比較関数を作れば辞書順の逆でやることも可能. プログラムは以下の通りになる. #include <bits/stdc++.h> using namespace st</bits/stdc++.h>…

aoj 2827 凸多角形柱工業都市

問題 問題概要 スタートからゴールまで最短距離で移動したい. 影を通れば距離には加算されない. (2017 ICPC国内模擬 E) 解法 建物とその影を考えて多角形を作り, N個の多角形どうしの距離を計算して辺を作り, ダイクストラで最短距離を計算すれば良い. 建物…

aoj 1318 Long Distance Taxi

問題 問題概要 グラフがあたえられる. 各頂点のいくつかはガソリンステーションでガソリンを入れることができる. ガソリンがなくならずに, スタートからゴールに行くまでの最短距離を求める. またLPGのタンクの最大容量もあたえられる. 車の燃費は10km/Lであ…

九州大学プログラミングコンテスト2014 H - お風呂は気持ちいい

問題 問題概要 頂点の間の容量が与えられる. 複数のスタートから一つのゴールまで最大どのくらいのものを運ぶことができるか. 解法 G個のスタート地点があるので, スタート地点の頂点を新たに作り, そこから魔導石に近い魔法使いへ辺の容量がINFの辺をはる. …

aoj 2402 Milky Way

問題 問題概要 五芒星が与えられる. スタートの星からゴールの星までの移動の最小距離を求める. 星の中は移動距離に入らない. 解法 星と星の距離は, 各星は5つの辺からなっていることから, 5つの辺ぞれぞれを総当りで調べて, その中の最小値が距離になる. こ…

aoj 1157 Roll-A-Big-Ball

問題 問題概要 ボールが通る線分とそれをじゃまするN個の直方体が与えられる. 直方体に重ならずに線分をスタートからゴールまで通ることができるボールの半径の最大値を求める. 解法 長方形と線分の距離をdとして求める半径をrとすると, d <= hのとき, r = d…

aoj 2009 Area Separation

問題 問題概要 頂点を(-100,-100)、(100,-100)、(100,100)、(-100,100) とする正方形とn個の線分が与えられる. 線分の両端は正方形の辺上にある. 線分により正方形がいくつに分割されるかを求めよ. 解法 順番に線分を書いていくことを考える. いま書く線分と…

aoj 1176 Planning Rolling Blackouts

問題 問題概要 長方形が与えられ, そのますに値が入っている. 長方形を分割してくが, 分割方法は区切られた長方形を一つ選び, それを縦か横どちらに切って分ける. 分割できるのは, 分割後に任意のグループを一つ選び, 抑制需要(残ったグループのますの値の合…

Codeforces #223 Div1. C. Sereja and Brackets

問題 問題概要 ‘('と’)‘が含まれた文字列が与えられる. その文字列のl番目からからr番目のまでの文字を考えたときに, その中にカッコの対応が最大でいくつできるかを書くクエリごとに答える. 解法 segtreeを使えばよい. 状態として区間[l, r)の中で, すでに…

C言語 ポインタ同士の引き算

アドレスの差分にはならない. int main(void){ int a[2]; int k = &a[1] - &a[0]; return 0; } 上のコードを実行したら, kを表示すると結果は1となる. 4ではない. ポインタ同士の引き算は内部でアドレスの値を引いた後にそのポインタが指している変数の型の…

Codeforces #197 Div2 D Xenia and Bit Operations

問題 問題概要 奇数回目に数列を左から隣同士を見て, ORを計算し, 偶数回目に数列を左から見て, XORを計算する. それぞれのステップで数列の要素数は半分になる. 数列の要素数が1になるまでこれを繰り返す. はじめの数列がm回変化するので, m個の数列に対し…

ABC 009 D - 漸化式

問題 問題概要 与えられた漸化式によって導かれるM番目の値を求めよ. 解法 andとxorの演算は, (G, 和, 積) := ({1,0}, xor, and)とすると, 環をなしている. また, 行列の演算は半環であれば, 成り立つ. これらのことから, 通常の行列ライブラリの和をxorへ, …

ABC 029 D - 1

問題 問題概要 1以上N以下の全ての数字のなかに数字1が全部でいくつ含まれているか? 解法 脳死しているので桁dpをする. dp[i][j][k] := i桁目まで見て, j==1ならNより小さい, 1を使った数がk回となる数字の総数 という状態を決めてやればいい. 漸化式の遷移…

CODE THANKS FESTIVAL 2015 G - カメレオン

問題 問題概要 頂点1からNまでの最短コストを求めよ. ただし辺のコストtに加えて, 辺を通る時の色が決められているので, 色を変えるのにもコストがかかる. xからyに色を変える場合のコストは, |x-y|である. 解法 拡張ダイクストラをすればいい. dist[i][j]と…

yukicoder No.492 IOI数列

問題 問題概要 a1 = 1, ai = 100ai-1 + 1という数列がある. 第N項を1000000007と101010101010101010101で割ったあまりを求める. 解法 前半の解 数列の一般項を求めて計算するだけ. ただし, 数が大きくなるため, 逐次modをとったり, powmodでやらないと行けな…

yukicoder No.491 10^9+1と回文

問題 問題概要 1以上N以下の整数で、109 + 1 の倍数かつ回文の数の個数を求めな 解法 109+1の倍数かつ回文になるには, 109+1に回文をかければ良い. よって, Nを109+1で割った数以下の整数で, 回文の個数を数えれば良い. よって, dfsを用いて, その整数の桁数…

Codeforces #361 (Div.2) D. Friends and Subsequences

問題 問題概要 [l, r]の区間を考えた時に, al, .. , ar の最大値と bl, .. , br の最小値が一致する区間の総数を求める. 解法 区間の左端を固定して, 右端を伸ばしていくと, aの最大値は単調増加, bの最小値は単調減少していくので, 区間を伸ばしていくとど…

ARC 045 B - ドキドキデート大作戦高橋君

問題 問題概要 N人の人がM個の教室を掃除する. 一人が掃除する連続区間の教室が与えられる. ひとつの教室につき一人以上が掃除をしていればいい. どの区間を掃除する人はさぼることができるか. さぼる人は 同時に1人として考える. 解法 まずimos法を利用して…

ARC 045 A - スペース高橋君

arc

問題 問題概要 与えられた文字列に応じて出力する文字列を変更する. 解法 string s; while(cin>>s){ //処理 } 上記のような方法で, スペースまでの文字列を受け取り, 終了したらwhileを抜けれる. ミス なし. コード #include <bits/stdc++.h> using namespace std; typedef </bits/stdc++.h>…

ARC 044 B - 最短路問題

問題 問題概要 A1をstartとした時の頂点までの最短経路の情報が与えられる. その木の高さで作ることのできるグラフは何通りあるか, mod1e9+7で答えろ. 解法 まず, A1からの最短経路の情報が与えられているはずなので, A1以外で最短経路が0であればそのよう…

ARC 044 A - 素数判定

arc

問題 問題概要 Nが素数ならPrime Nが合成数で, 1の位が2,5で割り切れず, 各桁の和が3で割り切れないとき, Prime それ以外なら Not Prime 解法 まず, 普通に素数判定をし, 素数ならPrime. 次に, 1のくらいが2, 5で割り切れず, 各桁の和が3で割り切れないけれ…

Codeforces 400 (Div. 1 + Div. 2, combined) B. Sherlock and his girlfriend

問題 問題概要 i番目のものをi+1として考えて, 色を塗っていく. 塗る色はその数の素因数と同じ色にしてはいけない. 塗る色の最小数を求める問題. 解法 その数しか素因数を持たない素数はすべて同じ色で塗ることが可能. そのようにすると, 素数でない数はすべ…