srupのメモ帳

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

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))ぐらいの数字…