srupのメモ帳

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

yukicoder

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を用いて, その整数の桁数…

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 が一致して…

yukicoder No.483 マッチ並べ

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

yukicoder No.484 収穫

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

yukicoder No.43 野球の試合

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

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

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

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

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通りすべてを調べれば答えが求まることがわ…

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を連発してつら…

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回間違…

yukicoder No.83 最大マッチング

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

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

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

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で求められる。あ…

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

yukicoder No.202 1円玉投げ

問題 問題概要 円の中心座標が与えられる。円の半径は10cm。いくつの円をかなさならないようにおけるか。 解法 まず、Nが105なので、円の中心が与えられてるたびに、過去に置いた円すべての中心間の距離を計算しておけるかどうかを確かめるとO(N*N)となり、…

yukicoder No.430 文字列検索

問題 問題概要 文字列sの中に文字列cがいくつ含まれているかを求める問題。 解法 ローリングハッシュを使いました。ほぼ理解していないので、応用はきかないので要練習。文字列を比較するとき、1文字ずつ見比べいると、文字列の長さがmだとそこで、O(m)なっ…

yukicoder No.429 CupShuffle

問題 問題概要 数列をswapしていく。k回swapするが、k-1回文のswapの処理は与えられるが、どこか一か所のswapの処理がわからないようになっている。一番初めの数列の状態と、最後の数列の状態が与えられるので、途中一か所わからないswapの処理がどのような…

yukicoder No.428 小数から逃げる夢

問題 問題概要 0.(190桁)のような少数が与えらえる。これをn倍した値を求める。 解法 小数点以下が多くある状態で扱ってるとまずいので、全体を整数で扱うことにした。Dを整数としてあつかい、それに与えられたnをかける。あとは、これをDを整数にするために…

yukicoder No.427 テレビ

問題 問題概要 与えられた数字が3:4なのか4:3なのかを判別する問題。 解法 最大公約数で割って、考えた。 ミス 4:3か3:4しかないから、大小だけみれば十分なのか。 コード #include <iostream> #include <algorithm> #include <vector> #include <cstdio> using namespace std; typedef long long </cstdio></vector></algorithm></iostream>…

yukicoder No.60 魔法少女

問題 問題概要 省略 解法 2次元imos法を使えば楽なんですね。 imos法 いもす法 - いもす研 (imos laboratory) BITとかsegtree使うのかな、て感じだった。 2次元BIT http://hos.ac/slides/20140319_bit.pdf ミス imos!! コード 2次元imos法 #include <iostream> #includ</iostream>…

yukicoder No.412 花火大会

問題 問題概要 組み合わせの数え上げ 解法 まず、すべてソートしてく。全探索をして、それぞれの家族がどのマットを使うかを決める。それが条件を満たしたものであれば、ほかのものは選ぶ選ばないの選択がある。 dpのほうがわかりやすいな。状態数は2つで、1…

yukicoder No.12 限定された素数

問題 問題概要 LからRの範囲の中の素数が与えら数の数字(0~9)のみを使い(必ず使わないといけない)、R - Lの最大値を求めよ。 解法 素数判定はエラトステネスを利用、区間の最大値を求めるには、1~5000000までの素数でも、10000以上あるので、すべての区間を…

yukicoder No.416 旅行会社

問題 問題概要 省略 解法 union findは辺を削除することができない。問題は、クエリを与えられた順にみると、辺を削除するような形だが、クエリを逆からみれば、辺をつなげていく形になる。このようになると、union findで管理できる。 また今回学んだunion …

yukicoder No.107 モンスター

問題 問題概要 省略 解法 bitDPで解いた。 dp[mask][lim] := 集合maskのモンスターと戦った時に最大体力が lim * 100 の時に、残りの体力の最大値 として、ループで回していった。 limは100から100とばしに1600までしか使わないので、簡単な座圧的な感じで、…

yukicoder No.30 たこやき工場

問題 問題概要 省略 解法 メモ化再帰で解いた。サンプルで与えられている図のように辺を張り、dp[i] := i番目の商品が必要な数 とおき、自分の子で必要なものの数から、i番目に必要な個数を計算する形にした。商品nが必要な個数は1個なので、dp[n - 1] = 1と…