srupのメモ帳

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

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…

codeforces 225 div1 C. Propagating tree

問題 問題概要 (1)頂点vにxを加算し、その子に-xを加算し、またその子にxを加算する。 (2)頂点xの値を求める 解法 オイラーツアーで求めた順番で隣あうものは頂点の深さの差が1である。これを利用すれば、プラスマイナスの加算をsegtreeを2つ使って行うこと…