srupのメモ帳

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

abc

ABC 009 D - 漸化式

問題 問題概要 与えられた漸化式によって導かれるM番目の値を求めよ. 解法 andとxorの演算は, (G, 和, 積) := ({1,0}, xor, and)とすると, 環をなしている. また, 行列の演算は半環であれば, 成り立つ. これらのことから, 通常の行列ライブラリの和をxorへ, …

ABC 029 D - 1

問題 問題概要 1以上N以下の全ての数字のなかに数字1が全部でいくつ含まれているか? 解法 脳死しているので桁dpをする. dp[i][j][k] := i桁目まで見て, j==1ならNより小さい, 1を使った数がk回となる数字の総数 という状態を決めてやればいい. 漸化式の遷移…

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が含まれていなければ…

ABC 037 D - 経路

問題 問題概要 任意のマスからスタートして、数字の大きい方へ進める。経路の総数を求める。 解法 dp[i][j]:= y=i,x=jから始めた時の経路の総数 として、再帰関数を用いて、周りの4方向どこへも進めないマスから順に埋めていけばいい。メモ化しておけばTLEに…

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…

ABC 032 C - 列

問題 問題概要 省略 解法 しゃくとり法をやるだけなんだけど、すぐにうまくできない。 ミス 尺取り法バグらしまくってうまくできない。 コード 尺取り法 #include <iostream> #include <cstdio> #include <set> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #de</algorithm></vector></set></cstdio></iostream>…

ABC 031 D - 語呂合わせ

問題 問題概要 省略 解法 この問題のポイントは、数字に対して、割り当てられる文字の長さが3文字までであるから、1~9の数字を何文字にするかきめれば、その長さが矛盾しないものか確かめられる。 実装で困った点は、kが決まっていないので、単純にループで…

ABC 031 C - 数列ゲーム

問題 問題概要 省略 解法 いわれたとおりにシミュレーションを行う問題。高橋君の位置を固定して、その時に青木君が丸を付ける場所を探し、その時高橋君の得点を記録しておく。これを高橋君が選べるすべての場所について調べ、高橋君の得点が最大となるとき…

ABC 030 C - 飛行機乗り

問題 問題概要 省略 解法 貪欲に選んでいけばいい。なぜなら、飛行時間はxとyで決まっているので、乗れるだけ早い時間にのり、もう一方の空港に行っているほうが得。(損はない) 実装方法だが、今どちらの空港にいるのかが判断できるものと、いまの時刻がわか…

ABC 030 B - 時計盤

問題 問題概要 省略 解法 時計を1周分を360度と考えて、それぞれの針が何度回ったかを計算する。最後に注意しなければならないことがあり、針の角度の差を取ると、180度を超えることがあるが、それは角度の大きいほうを図ってしまったいるので、小さいほうを…

ABC 028 D - 乱数生成

問題 問題概要 省略 解法 場合分けする。 3つの数字が異なるとき、1つは、kで決まり、残りの2つは、kより小さいものから1つ、kより大きいものから1つ選べばよいので、その時の3つの数字の組み合わせを考える、(k - 1)*(n - k)となり、さらに、引く順番を考…

ABC 028 C - 数を3つ選ぶマン

abc

問題 問題概要 省略 解法 abcdeは重複を許さずに選ばなければならない。あとは、できるすべての作り、それをソートして、3番目答えとなる。a<b<c<d<eのため、1番目と2番目が等しいということはないので、単純にソートして3番目を選ぶだけで十分かな。 ミス 今回のセットはabc27と比べるとレベルが違いすぎる。 コード #include <iostream> #include <cstdio> #include <set> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #d…</algorithm></vector></set></cstdio></b<c<d<eのため、1番目と2番目が等しいということはないので、単純にソートして3番目を選ぶだけで十分かな。>

ABC 027 B - 島と橋

問題 問題概要 省略 解法 まず、すべての住人の数を求めて、それを島の数で割り切れなければ、-1を出力すればいい。また、住民の合計と、島の数から、1つの島に住んでいなければならない人数もわかる。橋を架けなければならない場所の判定は、橋の左側と、右…

ABC 026 D - 高橋君ボール1号

問題 問題概要 省略 解法 2分探索でとく。関数はだいたい増加しているような関数であるので、解をもつ範囲の左端をL、右端をR、真ん中をM とすると、t=Mの時に、関数の値が100を超えるなら、中間地の定理より(あたりまえ)、左側の部分に解を必ず一つはもつ…

ABC 026 C - 高橋君の給料

問題 問題概要 省略 解法 上司から直属の部下に対して辺を張り、有向グラフを作成する。それを利用して、dfsを行う。部下がいないとき、つまり、グラフ上で葉の部分に該当する部下の給料は1なので、1を返す。部下が存在するとき、つまり、葉以外の頂点では、…

ABC 024 B - 自動ドア

問題 問題概要 省略 解法 aは昇順に並んでいるので、時系列に沿った形で見ていく。ドアが開き始めた時間をl、閉じる予定の時間をrおき、aiがrより小さいなら、なら、時間がtよりすくないが延長され、rより大きいなら、一度ドアが閉じ、そのあと、時間がtだけ…

ABC 024 C - 民族大移動

問題 問題概要 x軸上をスタートからゴールまで到達するのにかかる最短時間を求める問題。ただし、時間ごとに、動けるx軸上の位置が与えられる。 解法 ループが存在するわけでなく、ただ単にx軸上を動くだけなので、実験すると貪欲にやればいいことがわかる。…

ABC 022 D - Big Bang

問題 問題概要 相似比を求める問題 解法 Aの座標に対して行われた操作は平行移動と回転なので、AとBは相似である。よって、相似比を求めれば、よいことなる。どこを見て相似比をみるかは多くの解法があるみたい。 一番簡単なのは、重心からの距離が最大の点…

ABC 022 C - Blue Bird

問題 問題概要 省略 解法 ダイクストラでやろうと思うと、閉路の最短距離を出すのは普通にやったらできない。求めるのは0から初めて、0に戻るような閉路で最短距離。そのような経路は、0 -> u -> v -> 0 ものである。同じ道を2度通ることはできないので、u…

ABC 021 C - 正直者の高橋くん

問題 問題概要 省略 解法 bfsで解いた。よくある最短距離を求めるときにやる、bfsは一度、到達したところは2回目以降むしをするが、今回は、初めて到達したあとも、その位置に最短距離として、ほかの経路から到達して来る可能性があるので、bfsで初めに到達…

abc 020 C - 壁抜け

問題 問題概要 省略 解法 2分探索and最短経路問題。 xを小さくしていけば、かならず、ゴールにたどり着け、無限に大きくしていけば、どこかで、たどり着けなくなる。このような場合、求めるxを2分探索で効率よく絞り込んでいける。あとは、そのxに対して、ダ…

abc 019 D - 高橋くんと木の直径

問題 問題概要 木の直径を求める問題。 解法 木の直径を求めるアルゴリズムは、 1.任意の頂点sから最も遠い頂点をxを求める 2.頂点xから、最も遠い頂点yを求める 3.頂点xからyの距離が木の直径となる これを実装すればいい。 ミス なし。 コード #include <iostream> #</iostream>…

abc 019 C - 高橋くんと魔法の箱

abc

問題 問題概要 省略 解法 2倍したものは同じものとしてみなせるため、まずすべての数字を2で割れるだけ割る。そのあと、数字の種類が答えとなる。 ミス なし。 コード #include <iostream> #include <cstdio> #include <vector> #include <set> #include <algorithm> using namespace std; typedef long</algorithm></set></vector></cstdio></iostream>…

ABC 016 D - 一刀両断

問題 問題概要 多角形を1つの直線で分断すると、いくつに分断されるかを求める問題。 解法 公式解説がわかりやすい。 分割された多角形の数 = 切っている本数+1 = (多角形と線分の交点の数 / 2) +1 = (線分と交差する多角形の辺の本数 / 2) +1 ミス 写経。…

ABC 016 C - 友達の友達

問題 問題概要 省略 解法 dfsで友達の友達を求めることにした。この時に、dfsの引き数として、現在の頂点と、前回の頂点、探索回数、スタート時点の頂点を持つことにした。前回の頂点は元の頂点に戻るのを禁止しするため。スタート時点を保持しておくのは、…

ABC 015 D - 高橋くんの苦悩

問題 問題概要 省略 解法 ナップザック問題に選んでいい品物の個数を制限する制約を追加した問題。 dp[i][j][l] := i番目のスクショまで見て、j枚貼り、幅lを使っているときの重要度の最大値 として、ループで値を埋めていく。 ミス なし。 コード #include <iostream></iostream>…

ABC 015 C - 高橋くんのバグ探し

問題 問題概要 省略 解法 nやkは小さいので、全探索できるな。でも、kが毎回変わるから、単純にループを書こうと思うと、kに応じて、ループの回数を変えたコードを書かなければならなくなり、めんどくさいので、dfsで何回ループをしなければならないかを引数…

ABC 014 D - 閉路

問題 問題概要 木のグラフが与えられる。その木に対して、辺を1つ加えでできる、閉路の長さを答える。 解法 まず、LCAを求める。LCAについては、蟻本。多くのクエリが与えられるので、いちいち親をたどっていては、間に合わない。そこで、頂点vから、2k回上…

ABC 013 D - 阿弥陀

問題 問題概要 省略。 解法 まず、簡単にわかることは、D=1の場合において、上側の何番目から始めたら、下側の何番目につくかというのを求める。それを利用して、それぞれの列から開始して、d回後にどこにいるかを求めればいい。しかし、このようにやってし…

ABC 014 C - AtColor

問題 問題概要 もっとも多くの区間に含まれている数字を囲んでいる区間の総数を求める問題。 解法 区間が始まる点を+1、区間が終わる点を-1することで、[a, b]をインクリメントする必要がなくなり、最後に一度だけ、全体をなめるだけで、最大数がわかる。 ミ…

ABC 045 B - 3人でカードゲームイージー / Card Game for Three (ABC Edit)

問題 問題概要 省略。 解法 書かれていた通りに、シミュレーションをする。 ミス なし コード #include <iostream> #include <cstdio> using namespace std; string s[3]; int main(void){ cin >> s[0] >> s[1] >> s[2]; int now = 0; while(1){ if(s[now].size() == 0){ if(no</cstdio></iostream>…

ABC 045 A - 台形 / Trapezoids

abc

問題 問題概要 省略。 解法 台形の面積の公式を利用。 ミス なし コード #include <iostream> #include <cstdio> using namespace std; int main(void){ int a, b, h; cin >> a >> b >> h; printf("%d\n", (a + b) * h / 2); return 0; }</cstdio></iostream>

ABC 043 B - バイナリハックイージー / Unhappy Hacking (ABC Edit)

問題 問題概要 省略 解法 条件通りにの文字列を作る。 0の時は、文字列の末尾に0を付け加え、1の時は文字列の末尾に1を付け加え、Bの時は、文字列の末尾を取ればよい。 ミス ClangだとACだけど、GCCだとREでよく分からない。 [追記] @mmxsrup 空の文字列に対…

ABC002 C - 直訴

abc

問題 問題概要 3つの座標が与えられる。その3点を頂点とする三角形の面積を求める問題。 解法 3 点 (0,0), (a,b), (c,d) で構成される三角形の面積は、|ad−bc|⁄2という公式で求められる。この公式を用いるため、三角形の頂点の1つが原点になるように平行…

ABC041 D - 徒競走

問題 問題概要 M個のクエリ満たす数字の並びを求める問題。 解法 まず、 どのような数字が数字の集合としてあり得るのかを計算してflagに入れておく。そして漸化式でdpを解く。感覚的には空集合の場合の数から全集合の場合の数へ、集合の数を増やす感じに計…

ABC041 C - 背の順

問題 問題概要 与えられた数字をソートして、もとの添え字の番号を出力する。 解法 pairは1つ目の要素でソートした後、2つ目の要素でソートするので、pairに(身長, 番号)を入れることで、身長でソートした番号がわかる。 ミス 特になし。 コード #include <iostream> #</iostream>…

ABC041 B - 直方体

abc

問題 問題概要 直方体の体積を求める問題 解法 ただ計算するだけだが、2辺をかけるとlong long型を超える可能性があるので、modをとることでオーバーフローを防ぐ。 体積 = a * b % mod * c % mod ミス 特になし コード #include <iostream> #include <cstdio> using namespace</cstdio></iostream>…

ABC041 A - 添字

abc

問題 問題概要 指定された添え字の番号を出力する 解法 やるだけ ミス 特になし コード #include <iostream> #include <string> using namespace std; int main(void){ string s; cin >> s; int n; cin >> n; printf("%c\n", s[n - 1]); return 0; }</string></iostream>