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

srupのメモ帳

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

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>…

yukicoder No.40 多項式の割り算

問題 問題概要 多項式を(x3 - x)で割った余りの多項式を求める問題. 解法 普通の筆算のように計算していけばいい. b[i + 2] += b[i] の部分が筆算で部分. ミス dの大きさによる場合分けを入れていなくて1WA. コード #include <bits/stdc++.h> using namespace std; typedef </bits/stdc++.h>…

yukicoder No.33 アメーバがたくさん

問題 問題概要 アメーバが初期座標が与えられる. 1つのアメーバは1秒間で左右に絶対値でDだけ移動することができる. 同じマスにいるアメーバはくっつく. T秒後にアメーバは何匹になっているか. 解法 まず実験してわかることは, 初期座標の MOD D が一致して…

ARC 046 B - 石取り大作戦

問題 問題概要 プレイヤーが交互に1個以上の石をとる. 最後に石をとったプレイヤーの勝利. 先手はA個まで, 後手はB個まで石をとることができる. 最適に行動したときどちらが勝利するか. 解法 まずN<=Aの時は先手がN個とって勝ち. 次に, 二人のプレイヤーが合…

SRM 600 div1 easy ORSolitaire

問題 問題概要 はじめはX=0でそこからnumbersとして与えられた数字の中の任意のものとORをとり, Xを更新して再びnumbersの中の任意のものとのORを繰り返していく. この処理をどのように繰り返してもgoalに行けなくなるようにするには, numbersからいくつの数…

SRM 546 div1 easy KleofasTail

問題 問題概要 xが偶数のとき x / 2 xが奇数のとき x -= 1 ができる. [A, B]の数で上の操作を繰り返してKになるものの総数を求めよ. 解法 まず, 問題では小さくなる操作が与えられているが, 求めたいのはKになるかなので, Kから[A, B]の区間にいけるかを求め…

SRM 661 div1 easy MissingLCM

問題 問題概要 lmc(1..M)=lcm(N+1,M)となる最小のMを求める. 解法 まず, 1,..,N,N+1,…,M N+1,…,M のlcmが一致することから,1…Nの中にlcmを作るのに寄与したものがいないので, 1…Nのなかに含まれる最大の素数の2倍の数がすくなくともMまでに含まれていなけれ…

SRM 662 div1 easy FoxesOfTheRoundTable

問題 問題概要 きつねの身長があたえられる. 円形に並べらた時, 隣あうきつねの身長差の絶対値の最大値Dとして, Dの最小値を求める. 解法 貪欲法でとけるみたい. 偶数番目を左側, 奇数番目を右側にして, 左側を昇順, 右側を降順にしてやればいいみたい. なん…

SRM 666 div1 easy WalkOverATree

問題 問題概要 木構造の情報が与えられる. すべての辺のコストを1として, コストLいないで通ることができる頂点の種類数の最大値を求める問題. ただしstart地点を0として, start,goal も通った頂点としてカウントする. 解法 一番の方針として, 頂点を巡った…

yukicoder No.483 マッチ並べ

問題 問題概要 指定された場所にマッチを置く. マッチの置き方は上下の2通りの選択肢がある. 置き方を工夫して, 頭薬の部分が重ならないようにおけるかを判断せよ. 解法 単純にやるには, すべてのマッチ棒を上下試してやればいいが, 2nかかるため無理. そこ…

yukicoder No.484 収穫

問題 問題概要 i番目の木はA[i]の実が実る. 時刻1で隣の木にいどうすることができる. 移動しなくてもよい. このような条件ですべての実を回収するのにかかる時間の最小値を求める. 解法 区間dpで解けるみたい. 今回の問題を考えるにあたって重要な考察は, i…

queueの要素に構造体やclassを使う

c++

概要 queueの中に構造体,classを入れる方法. 以下のように, 構造体やclassを定義して, queue<> の <> のなかに型をいれればいい. STLだからね. pushするときは, que.push(構造体名{})てな感じでやればいい. 構造体もclassも同じこと. コード 構造体 #include <bits/stdc++.h></bits/stdc++.h>…

ABC 054 D - Mixing Experiment

問題 問題概要 タイプAとBの混合比がMa:Mbとなる薬を作らないければならない. 薬局の情報がNこあたえられ, それぞれの薬局でタイプAとBの薬をそれぞれいくら持っているかの情報とその値段が与えられる. いくつかの薬局で薬を買ってそれらをすべて使い, Ma:Mb…

ABC 054 C - One-stroke Path

問題 問題概要 頂点1をスタートとして, すべての頂点を一度だけ訪れるパスは何通りあるか. 解法 Nが最大8であるので, パスを全探索することができる. パスを全部書き出すと, 1は決定しているので, 2からNまでのすべての順列になる. よって, すべてのパスの数…

ABC 054 B - Template Matching

abc

問題 問題概要 “#"と”.“からなる画像(文字列や何本か)が2つ, A, Bとして与えられる. Bの画像がAの画像の中に含まれるかどうかを調べる. 解法 BがAに含まれるかを単純に調べた. Bの左上がAのどこにあるかですべて試して, 一致するものがあるかを調べた. 下記…

ABC 054 A - One Card Poker

abc

問題 問題概要 2人に数字が渡されて, 対戦を行う. 数字によって強さがきまり, そのルールは, 2<3<4<5<6<7<8<9<10<11<12<13<1 であり, 1だけ特別である. 解法 まず, a,bが等しい時はdrawなので、それを処理する. つぎに, a,bどちらにも1が含まれていなければ…

yukicoder No.43 野球の試合

問題 問題概要 野球の試合の対戦成績の表がもらえる. 表は埋まっていない部分があるので, そこを任意に決めた場合, 自チームは最高で何位になるか. また、同じ順位に複数のチームがあったとしても, 数字が抜けることはない. 解法 nが最大6でありとても小さい…

pwnable kr cmd1 メモ

pwn

cmd1 解法 #include <stdio.h> #include <string.h> int filter(char* cmd){ int r=0; r += strstr(cmd, "flag")!=0; r += strstr(cmd, "sh")!=0; r += strstr(cmd, "tmp")!=0; return r; } int main(int argc, char* argv[], char** envp){ putenv("PATH=/fuckyouverymuch"); i</string.h></stdio.h>…

yukicoder No.160 最短経路のうち辞書順最小

問題 問題概要 最短経路を復元する。経路復元。 解法 ダイクストラでやる。経路復元は蟻本を参照。 気をつけることは、s->gの最短経路を求めるのではなく、今回は、向こうグラフであることを利用して、g->sへの最短経路を求め、そのついでにもとめられるpre…

ABC 037 D - 経路

問題 問題概要 任意のマスからスタートして、数字の大きい方へ進める。経路の総数を求める。 解法 dp[i][j]:= y=i,x=jから始めた時の経路の総数 として、再帰関数を用いて、周りの4方向どこへも進めないマスから順に埋めていけばいい。メモ化しておけばTLEに…

yukicoder No.267 トランプソート

問題 問題概要 文字列をソートする。 解法 単純に文字列を比較することはできない。ただし、1文字目は4種類、2文字目は13種類しかないので、その文字を通常のsortで比較できるように文字列をAから順に利用して置換することで、通常通りsortが行えるようにな…

yukicoder No.18 うーさー暗号

問題 問題概要 i文字目はi文字前へずらしら文字に置換した文字列を求める問題。 解法 Aからのindexを求めて、i番目ならi文字前へずらせば良い。ただし、そのまま d -= i + 1 としてしまうと、マイナスになる場合もあるので、先に2600(=0(mod26))ぐらいの数字…

ABC 036 C - 座圧

問題 問題概要 座標を圧縮する問題。 解法 与えられた数字を座圧する問題。ソートした後に、重複を消去し、二分探索で元の数字のindexを調べれば、圧縮後の座標がわかる。 ミス なし。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef</bits/stdc++.h>…

ABC 035 D - トレジャーハント

問題 問題概要 省略 解法 一つの場所でできるだけ長く滞在すれば良い。できるだけ長く滞在するには、ある頂点iまで最短距離で行き、iからスタート時点まで市短距離で戻ってこればよい。そして残りの時間滞在すれば良いことになる。 求めるものは、0->iまでi-…

ABC 035 C - オセロ

問題 問題概要 オセロの向きを求める。 解法 一つずつやっていたらO(NQ)になるので、lとrの位置だけを記録してそれぞれの場所を何回ひっくり返されたかを記録すれば良い。ひっくり返された回数が、奇数であれば1、偶数であれば0である。区間に一様に1を加算…

ABC 034 D - 食塩水

問題 問題概要 n個の中から、k個を選んで濃度を最大にするときの最大値。 解法 単純に貪欲ではできない。蟻本p132の平均の最大化で紹介されているように、濃度を決めた上で、式変形をしてから、それを元に貪欲に選んでいけばその濃度を達成できるかを確かめ…

ABC 034 C - 経路

問題 問題概要 道順の総数 解法 高校数学でやった気がする。 (w + h - 2)! / ((w-1)! * (h-1)!) の値を求めるだけでよい。ただ、割り算が入った形の計算式で、modを取らないといけないので、逆元だったり、フェルマーの小定理を使って求めればいい。 ミス な…

ABC 033 D - 三角形の分類

問題 問題概要 N個の点が与えられる。3点選んで三角形を作るとき、鋭角、鈍角、直角三角形はそれぞれいくつずつできるかを求める。 解法 単純にやると、n3になってしまうため、TLE。。そこで、まず1点をきめて他の点へのベクトルを求めて、1点を原点とした偏…

ABC 033 C - 数式の書き換え

問題 問題概要 和と積の計算式があたえられる。計算結果を0にするためにはいくつの数を0にすれば良いか。その最小値を求めよ。 解法 数字がすべて1桁なので、マイナスとかもありえない。だから、'+'の間の式の計算結果がすべて0であれば、全体の計算結果も0…