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

srupのメモ帳

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

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 を使って、連結成分がいくつできているjかを数得ればよい。連結成分を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…

SRM 690 div2 easy DoubleString

問題 問題概要 文字列Sが与えられる。その文字列がS = T + T となる文字列Tが存在するか。 解法 Tが2回続くので、TはSの文字列の長さの1/2なので、Sを前後で二等分した文字列どおしが同じものであるかを見ればよい。 ミス なし。 コード #include <iostream> #include <string></string></iostream>…

SRM 692 div2 easy PriorityQueue

問題 問題概要 食堂にならんでいる。並んでいる順番で前から順に、その人がどんな行動をするかが与えられる。行動は2通りで、 b := 一番前に横入りする e := 最後尾に戻る である。先に並んでいたのに、前に横入りされると、不満がたまる。それぞれの人に対…

yukicoder No.146 試験監督(1)

問題 問題概要 椅子に隣同士に座ることはできない。一つに机に椅子がいくつある椅子が、何個あるかが与えられるので、最大で何人座ることができるかを求める。 解法 2人掛けなら1人、3人掛けなら2人、4人掛けなら2人、5人掛けなら3人が最大で座れる数となる…

yukicoder No.9 モンスターのレベル上げ

問題 問題概要 手持ちのモンスターから、レベルの一番低くくて、その中でも、一番先頭回数が少ないモンスターから使う。モンスターは戦わせるとレベルが上がる。敵は円に並んでいる。どこから始めてもよいが、1回ずつ順番に戦う。このときに、最も先頭回数が…

yukicoder No.360 増加門松No.307 最近色塗る問題多くない?

問題 問題概要 省略 解法 bfsで書いた。やることはシンプルで、色を変えた場所から隣接している同じ色だった部分の色も同時に変わるので、そのようなマスをbfsで探索して色を変えていけばいい。これを実装すると、O(HWQ)となり、TLEしてしまう。ここをどう…

yukicoder No.258 回転寿司(2)

問題 問題概要 N個の寿司が並んでいる。順番に食べていくが、連続して食べることはできない。寿司にはおいしさがそれぞれ決まっている。食べた寿司のおいしさの合計の最大値を求めよ。またどの寿司を食べたかも求める。経路復元。 解法 動的計画法で解く。dp…

yukicoder No.225 文字列変更(medium)

問題 問題概要 SをTにするときの編集距離の最小を求める問題。編集距離のdpの漸化式については以下のサイトが参考になる。 解法 dpで解くことができる。 dp[i][j] := 文字列Sのi番目までで、文字列Tのj番目までを作ることを考えた時の操作回数の最小値として…

yukicoder No.316 もっと刺激的なFizzBuzzをください

問題 問題概要 a,b,cのどれかの倍数になる数字の個数を求める。 解法 包徐原理で解く。高1のどっかでやる3つの場合の公式を使えば解くことができる。 wikipediaの3つの有限集合に対して書かれている公式をそのまま使えばいい。 包除原理 - Wikipedia 集合a,…

SRM 693 div2 medium BiconnectedDiv2

問題 問題概要 グラフはi - i+1 と i - i+2 を結ぶ2つ辺が貼られている。 二重連結グラフの状態を保ったまま辺を取り除き、辺のコストを最小にしたときの辺のコストの合計を求める。 解法 biconnected graph(2重連結グラフ)とは、任意の頂点を1つ取り除いて…

SRM 693 div2 easy TriangleEasy

問題 問題概要 グラフが与えられる。そのグラフの中に三角形を作る。最小でいくつの辺を加えればできるか。 解法 まず、辺が1つもなければ、必要な最小の辺の数は3となる。次に辺がある場合を考える。u - v の辺がある場合を考える。このとき、u - x(xはvで…