srupのメモ帳

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

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言語 ポインタ同士の引き算

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として考えて, 色を塗っていく. 塗る色はその数の素因数と同じ色にしてはいけない. 塗る色の最小数を求める問題. 解法 その数しか素因数を持たない素数はすべて同じ色で塗ることが可能. そのようにすると, 素数でない数はすべ…

Codeforece 400 (Div. 1 + Div. 2, combined) A. A Serial Killer

問題 問題概要 文字列が2つ与えられる. ひとつの文字列を指定された文字列に置換する操作を行うクエリに応える. 解法 setで管理しながら, 置換される方をeraseして, 加える方をinsertしていけばいい. ミス なし. コード #include <bits/stdc++.h> using namespace std; type</bits/stdc++.h>…

codeforces 401 div2 D. Cloud of Hashtags

問題 問題概要 与えられた文字列をすべて与えらた順番で辞書順にする. そのために各文字列から末尾の文字を好きなだけ取り除いていい. 取り除く文字の最小数を求める問題. 解法 一番後ろの文字はそのままにできることがわかるので, 後ろから順番に見ていき, …

codeforces 401 div2 B. Game of Credit Cards

問題 問題概要 数列a, bが与えられる. 数列bは好きな順番に変更することができる. (1) a[i] > b[i] となる i の個数の最小数 (2) a[i] < b[i]となる i の個数の最大数 を求める問題 解法 2部マッチングの最大数を使ってとく. 数列bを任意の順番に動かすこと…

codeforces 401 div2 A. Shell Game

問題 問題概要 カップを3つ用意して, その中のどこかに玉をいれる. カップの番号を左から0, 1, 2としてn回動かす. その動かし方は, 奇数回の時は0と1を入れ替えて, 偶数回の時は1と2を入れ替える. n回入れ替えたあとの位置が与えられるので, はじめ何番目の…

Defcon Quals 2015 : babyecho

問題 問題概要 明らかなfsbがある. さらにスタックが+xである. しかし文字数制限がある. 解法 % file babyecho babyecho: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), statically linked, for GNU/Linux 2.6.24, BuildID[sha1]=c9a66685159a…

yukicoder No.488 四角関係

問題 問題概要 ノード間のつながりが与えられる. 任意の4つのノードの組み合わせを考えて, その4つのノード間のつながりだけを考えたときに四角形となっている組み合わせがいくつあるか. 解法 n=50なので, すべての任意の4つの組み合わせの総数nC4を全部計算…

yukicoder No.487 2017 Calculation(2017の計算)

問題 問題概要 2017 + (2017*2017)2017 のMOD Mを計算. 解法 2017*2017のを2017乗するととても大きな値になるので逐次MODをとりながら計算していく. 掛け算足し算の計算ではすべて計算したあとにMODをとっても, 計算途中でMODをとって計算していっても結果は…

yukicoder No.486 3 Straight Win(3連勝)

問題 問題概要 OXXXOXXのようなOとXからなる文字列が与えられる. OはEastの勝ちで, XはWestの勝ちを表している. 先に3連勝したほうを勝ちとする. どちらが勝つか. 勝者がない時はNAを出力. 解法 連続した3文字が同じ文字であるかを判定し, 先に同じ文字にな…

yukicoder No.485 方程式のお勉強

問題 問題概要 A*x = B の方程式の解を求める問題. ただし, 解が少数になる場合はNOを出力. 解法 BをAで割り切れるか, 割り切れないかで場合分けする. ミス なし. コード #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typede</int></bits/stdc++.h>…