srupのメモ帳

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

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つ使って行うこと…

yukicoder No.458 異なる素数の和

問題 問題概要 N以下の数字を相異なる素数のみで表すことを考える。素数の数の種類の合計値が最大のときの最大値を求めよ。 解法 dpで解ける。 dp[i] := 合計がiとなるときの和の回数の最大値 として、これをループで求めていけばいい。 ただし、今回注意し…

yukicoder No.457 (^^*)

問題 問題概要 省略 解法 「同じ文字は何度でも使用可能ですが、一つの'('')'の組み合わせから錬成出来るのは左向き、右向きそれぞれ1つです。」といのがポイント? "(^^)"が、何個あるから求める。'(' を決めて、そこから "^^" の順で "^^" が何回分でたかを…

yukicoder No.472 平均順位

問題 問題概要 毎回のコンテストで解いた問題数における順位があたえられる。すべてのコンテストでの解いた問題数の合計があたえられる。すべてのコンテストでの順位を最小にするときの最小値を求めよ。 解法 dp[i][j] := i番目までのコンテストで、j問解い…

yukicoder No.469 区間加算と一致検索の問題

問題 問題概要 区間に一様に加算するクエリと現在の数列の状態が一番初めにいつ現れたかを求めるクエリがある。 解法 想定解にも書いてあることだが、 H(x) + H(y) = H(x+y), kH(x) = H(kx) が成り立つようなhash関数を用いれば、今回のクエリに対して、数列…

yukicoder No.274 The Wall

問題 問題概要 ブロックを縦に並べる。ブロックは、180度回転をすることができる。ブロックをすべて縦に並べた時に、同じ列にブロックが1つのみになる並べ方があるかを求める問題。 解法 愚直に考えると、1つのブロックに対して、落とす方法が2通りなので、2…

yukicoder No.470 Inverse S+T Problem

問題 問題概要 3つの文字でできている文字列があたえられる.それらを前後で分けて、すべての文字列が相異なるように分けられるなら分けろ。 解法 考察として、文字を分けるのは1-2または2-1の2通りしかないので、2n通りすべてを調べれば答えが求まることがわ…

ARC 033 C - データ構造

問題 問題概要 タイプ 1 : S に数 X を追加する。 タイプ 2 : S に含まれる数のうち X 番目に小さい数を答え、その数を S から削除する。 この2つを高速に行うことができるデータ構造を使えばよい。 解法 今回の問題は、Xがあまり大きくない。よって、バ…

ARC 033 B - メタ構文変数

問題 問題概要 省略。 解法 SA と SB の両方に現れる要素の個数は、一方の集合の要素がもう一方にあるかを単純に調べるだけでできる。 SA と SB の少なくともどちらか一方には現れる要素の個数は、setを使い、重複がないようにいくつあるかを調べれば簡単に…

ARC 032 B - 道路工事

問題 問題概要 省略。 解法 union find を使って、連結成分がいくつできているかを数得ればよい。連結成分を1つにするのに必要な辺の数は答えになるので、答えは(連結成分の数-1)となる。 ミス なし。 コード #include <bits/stdc++.h> using namespace std; typedef long </bits/stdc++.h>…

SECCON CTF 2016 SECCON CTF 2016

この記事はKobe University Advent Calendar 2016 - Adventarの13日目です。 SECCON CTF 2016オンライン予選に参加した感想を書きます。 SECCON 12月10日と11日にSECCON CTF 2016 オンライン予選なるものに参加していました。 2016.seccon.jp 今回のコンテス…

yukicoder No.455 冬の大三角

問題 問題概要 省略。 解法 3点の1つを始点として、他の点までのベクトルを2つ求める。そのベクトルの外積を取り、外積の計算結果が0にならないならば、3つの点が一直線上にならないことになり、そこに点を置けば良いことになる。 ミス なし。 コード #inclu…

yukicoder No.23 技の選択

問題 問題概要 省略。 解法 期待値dpの問題。 残りのHPを基準に考える(下のソース)。 aを選びとき、(残りHPがiのときの期待値) = (残りHPがi + aのときの期待値) + 1(回) bを選ぶとき、(残りHPがiのときの期待値) = (残りHPがi + bのときの期待値) + 1.5(回)…

yukicoder No.322 Geometry Dash

問題 問題概要 省略。 解法 比較する問題。比較する関数は、比較するものを2つのみ並べたときのそれぞれの場合においてかかる時間を計算する。それを利用して比較すれば行けた。 ミス ラムダ式を使ったよ。 コード ラムダ式 #include <bits/stdc++.h> using namespace std; </bits/stdc++.h>…

yukicoder No.437 cwwゲーム

問題 問題概要 省略。 解法 何番目の文字を使用したかをsetで保持しながら、再帰関数でやった。再帰関数の中は、条件を満たすものを3重ループで全探索している。メモ化再帰しなくてもギリギリ通る。メモ化すると、だいぶ速くなった。 ミス TLEを連発してつら…

aoj 2152 Restrictive Filesystem

問題 問題概要 W,D,Lの命令が与えられる。Wは書き込む数字とサイズ、Dは削除する数字、Rは読み込む場所を標示するという命令。書き込むは前から貪欲に、開いている部分にサイズ分書き込むこと。 解法 Wできる区間(空き区間)をprioroty_queueで保持することに…

yukicoder No.368 LCM of K-products

問題 問題概要 Aの要素の中から、K個選んだ積のすべての要素の最小公倍数を求める。 解法 最小公倍数は、Bの要素を素因数分解したときの、各素因数に対して、Bの要素の中で最大の個数を持つものの積であらわされる。 今回の問題では、BはAの要素をK個選んだ…

yukicoder No.167 N^M mod 10

問題 問題概要 nm mod10 を求める。 ただし制約が大きい。 解法 数として計算するころはできないよね。今回の問題はmod10を求める問題なので、nをm回かけた後の下一桁だけがわかればよい。下一桁がわかればよいということは、nの下一桁のみをm回かければよい…

yukicoder No.320 眠れない夜に

問題 問題概要 100マス計算のようなマスが与えられる。その中で積の値が、小さいほうから数えて、K番目に位置する値を求めよ。 解法 分枝限定法で解けるみたい。n=1とn=2の時は間違えることはないので、nの時フィボナッチ数列の値を求めるまでに、n-2回間違…

ARC 037 C - 億マス計算

問題 問題概要 100マス計算のようなマスが与えられる。その中で積の値が、小さいほうから数えて、K番目に位置する値を求めよ。 解法 editorialがわかりやすい。 AtCoder Regular Contest 037 解説 from AtCoder Inc. www.slideshare.net 答えをmidとすると、…

ARC 037 B - バウムテスト

問題 問題概要 連結成分の中で、閉路がなく、木である連結成分の個数を求める。 解法 閉路を検出する問題。dfsで探索して、すでに探索した頂点をmemoで記録しておいて、同じところに2度来たら、その連結成分は閉路を持つので木ではないのでカウントしない。 …

ARC 036 C - 偶然ジェネレータ

問題 問題概要 省略 解法 ランダムウォークの表のようなものを考えて、+y方向に、(1-0の数)、-y方向に(0-1の数)として表を考える。そして、dp配列に、dp[i][j][k] := i番目まで見て、(1-0)の最大値がjで、(0-1)の最小値がkの時の場合の数 として、更新してい…

ARC 036 B - 山のデータ

arc

問題 問題概要 省略 解法 山の中央と決めて、その左右に条件を満たしながら、伸ばせるだけ伸ばした時がその時の山の最大となる。これを山の中央に対してすべて行うと TLEしてしまう。そこで、 if(h[mid - 1] < h[mid] && h[mid] > h[mid + 1]) という条件を…

yukicoder No.83 最大マッチング

問題 問題概要 省略 解法 数を大きくするには、桁数を増やせばよい。そのように考えて数を作るためのマッチの本数を見ると、1が2本で作れるので、一番少なくてすむので、基本1をたくさん作ればよいということになる。ただし、nが奇数の場合もあるので、その…

yukicoder No.77 レンガのピラミッド

問題 問題概要 省略 解法 奇数列のピラミッドに対して全探索を行う。i列のピラミッドを作るときに、足りないブロックの数と、余ったブロックの数それぞれの列に対してカウントする。答えは、足りないところに余りから追加するためのコストが、tarinaiで、 余…

ARC 035 C - アットコーダー王国の交通事情

問題 問題概要 省略 解法 まず、ワーシャルフロイドで、任意の2点間の最短距離を計算しておく。そのあとは、辺が一つ追加されるだけなので、追加される辺が、x-yであれば、任意の2点間の最短距離は、i -> j = i -> x -> y -> j = i -> y -> x -> j のなか…

ARC 035 B - アットコーダー王国のコンテスト事情

問題 問題概要 省略 解法 解く時間が小さい順にといていけば、ペナルティーが最小になる。何通りあるかは、同じもののなかで並び替えてもペナルティーが最小であることに違いはないので、同じ数字がx個あれば、x!通り存在することになるので、それらをかけ合…

yukicoder No.134 走れ!サブロー君

問題 問題概要 巡回セールスマン問題に辺のコストを加えたもの。 解法 巡回セールスマン問題ですね。bitDPで解きました。ただ今回の問題は、荷物をどれだけ持っているかで、1単位を移動するのにかかる時間が異なるので、それを前計算で、weight[mask] := mas…

天下一プログラマーコンテスト2015予選A C - 天下一美術館

問題 問題概要 マスの状態を一致させるために、必要な最小コストを求める問題。 解法 はじめは、貪欲に、左上から見ていき、交換して変えて、一致するところを優先的にやればいけると思い書いたが、WA。原因は単純で、左上から貪欲にやるだけではだめで、ど…

yukicoder No.32 貯金箱の憂鬱

問題 問題概要 硬貨の枚数を最小枚数に変更する。 解法 まず、合計金額を求める。それを1000円、100円、25円、1円の順に優先的に変換していけばいい。 ミス なし。 コード #include <iostream> #include <queue> #include <vector> #include <cstdio> #include <algorithm> using namespace std; typedef </algorithm></cstdio></vector></queue></iostream>…

yukicoder No.433 ICPC国内予選の選抜ルールがこんな感じだったらうれしい

問題 問題概要 優先順位のつけ方が与えられる。どの順番に選ばえばいいか。 解法 priority_queueで解いた。大学ごとに何人選ばれたかが優先順位をつける要因となるので、はじめの状態でそれぞれの大学が何人ずつ選ばれるかがわからないので、いきなりすべて…

yukicoder No.432 占い(Easy)

問題 問題概要 隣りあったの数字をたす。足した値が2桁になるときは10の位と1の位の数字をたす。1桁ならそのまま。この操作を続けていき、さいご1桁になった時、どのような数字になるかを求める。 解法 与えられう数字Sの桁は大きいので文字列として受け取る…

yukicoder No.431 死亡フラグ

問題 問題概要 死亡フラグと生存フラグが与えられる。死亡フラグが2本以上立っていれば、死亡。しかし、生存フラグが立っていれば、死亡フラグによらず生存している。どのような状態か求めよ。 解法 死亡フラグが何本立っているかをd1+d2+d3で求められる。あ…

srm 700 div2 medium XMarksTheSpot

問題 問題概要 Oは宝を含んでいる場所。?は宝を含んでいるかどうかがわからない場所。?の場所を宝が含んでいるか含んでいないかのすべての場合について、宝が含まれる可能性のある面積を求め、その合計を求める。 解法 今回は単純にbit全探索をすればいい。?…

SRM 700 div2 easy Xylophone

SRM

問題 問題概要 1がA、2がB、、7がGと対応している。そして、8から順にまたそれが続く。この時、何種類のアルファベットを含んでいるか。 解法 周期7で繰り返すので、mod7をとって、その値をsetにいれて重複をなくせばいい。 ミス 特になし。 コード #include <iostream></iostream>…

SRM 688 div2 easy ParenthesesDiv2Medium

問題 問題概要 カッコの文字列が与えられる。カッコが対応する形に変更する。ただし変更できる文字の数は、((文字数)/2)+1まで。 解法 動的計画法で解いた。変更できる文字の数に制限があるので、最小の数で対応づけができるものを求めた。dp[i][j] := i番目…

aoj 0109 Smart Calculator

問題 問題概要 数式を計算する。 解法 参考サイト とてもわかりやすい。 構文解析 Howto · GitHub ミス しっかりとした構文解析は初めて。 コード #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cctype> #include <cstdio> using namespace std; typedef long long ll;</cstdio></cctype></algorithm></vector></string></iostream>…

SRM 688 div2 easy ParenthesesDiv2Easy

SRM

問題 問題概要 カッコの階層が最大どこまで行くか。どこまで深くいくか。 解法 '('の時は+1、')'の時は-1していくなかでの最大値が答えとなる。 ミス 特になし。 コード #include <iostream> #include <string> #include <vector> #include <cstdio> #include <algorithm> using namespace std; typedef lo</algorithm></cstdio></vector></string></iostream>…

SRM 692 div2 medium Dubs

問題 問題概要 LとRが与えられる。LとRの間に、2桁以上で、最後の2桁の数字が同じで数がいくつあるか。 解法 桁dpで解いた。dp[i][j][k] := 整数p(L, R)を考えた時に、i番目の桁まで考えて、j=1の時は考えている数がp未満であることが決定していて、j=0の時…

SRM 689 div2 medium NonDeterministicSubstring

問題 問題概要 文字列AとBが与えられる。Bの文字の中には?が含まれていて、それを1または0に変換したものが、文字列Cとなる。文字列Aの連続部分列と文字列Bが一致いしている文字列Cの数を求める。(重複しているものは数えない) 解法 一番初めに思いついた解…

SRM 689 div2 easy SimilarUserDetection

問題 問題概要 文字列がいくつか与えられる。その文字列のなかに同じものが2つ以上あるかを判別する。ただし、0(ゼロ)とO(オー)は同じもの、1(いち)とl(Lの小文字)とI(iの大文字)は同じものとして考える。 解法 方針としては、文字列を変換して、重複を確認…

SRM 690 div2 medium GerrymanderEasy

問題 問題概要 AとBが与えられる。そのなかから、連続するK以上の部分のAの合計と、Bの合計をそれぞれ出して、(Bの合計)/(Aの合計) の最大値を求める。 解法 全探索で通る。単純にすべての区間について、(Bの合計)/(Aの合計)を出していけばいい。これだとn=1…