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に対して、ダ…