はまやんはまやんはまやん

hamayanhamayan's blog

2019-11-01から1ヶ月間の記事一覧

う し た ぷ に き あ く ん 笑 ビ - ム [yukicoder 935]

https://yukicoder.me/problems/no/935 尺取法 解説 https://yukicoder.me/submissions/402911 んーと思って見てると制約が弱めなことに気がつく。 よって、O(NQ)はまずできそう。 つまり、ビームの始点は全探索可能。 始点からビームでどこまで伸ばせるかを…

Explosive energy drink [yukicoder 934]

https://yukicoder.me/problems/no/934 解説 https://yukicoder.me/submissions/402813 リアクティブ問題。 色々考えると思いつくけど、どういう道筋で思いつくんだろうね。 ある魔剤以外を混ぜたときに、 爆発する→ある魔剤は爆発に必要ない 爆発しない→あ…

おまわりさんこいつです [yukicoder 933]

https://yukicoder.me/problems/no/933 解説 https://yukicoder.me/submissions/403112 これ難しくないか? ん?まじで何も分からん。 多倍長整数で殴れそうな気もするけど、ほんとか? あれっ?あれっ? こんなときはランキングを見るとヒントがあったりす…

解法破綻!高橋君 [yukicoder 932]

https://yukicoder.me/problems/no/932 解説 https://yukicoder.me/submissions/402564 便利なカンマで分割する関数を作ろう。 (この機に作ると主にyukicoderで役に立つ。自分が使ってるやつも借りてきたやつなんですけどね) string S; //----------------…

Wrong Answer on test 233 (Hard Version) [Codeforces Round #602 (Div. 1, based on Technocup 2020 Elimination Round 3) D2]

https://codeforces.com/contest/1261/problem/D2 解説 「そのままの点数 < 入れ替え後の点数」が満たされればいい。 言い換えると、「0 < 入れ替え後の点数 - そのままの点数」を満たせばいい。 i番目の数をxと決めると、h[i]=xであればそのままの点数が+1…

Sugoroku [AtCoder Beginner Contest 146 F]

https://atcoder.jp/contests/abc146/tasks/abc146_f 解説 https://atcoder.jp/contests/abc146/submissions/8635768 DPして復元する。 後ろからまずは最短手数になるようにDPしよう。 i番目のマスが0で最短距離がdp[i]であれば、dp[i-1]~dp[i-M]がdp[i]+1…

Rem of Sum is Num [AtCoder Beginner Contest 146 E]

https://atcoder.jp/contests/abc146/tasks/abc146_e 解説 https://atcoder.jp/contests/abc146/submissions/8635001 まずは常套手段として、右端を全探索して条件を満たす左端を探すことにしよう。 連続する和について考えるので、累積和を考えれば良さそう…

Coloring Edges on Tree [AtCoder Beginner Contest 146 D]

https://atcoder.jp/contests/abc146/tasks/abc146_d 解説 https://atcoder.jp/contests/abc146/submissions/8632543 貪欲に色を決めて塗っていけば達成できそう。 根を1つ決めて貪欲に色を塗っていく。 あとは、実装を頑張る。 各頂点で必要な色は次数と一…

Buy an Integer [AtCoder Beginner Contest 146 C]

https://atcoder.jp/contests/abc146/tasks/abc146_c 前提知識 二分探索 解説 https://atcoder.jp/contests/abc146/submissions/8630477 x

ROT N [AtCoder Beginner Contest 146 B]

https://atcoder.jp/contests/abc146/tasks/abc146_b 解説 https://atcoder.jp/contests/abc146/submissions/8629425 前の問題同様に文字を数に変換して+Nをすることで変換をする。 +Nするときは、ループの構造を考えるために26で割ったあまりで考える。 あ…

Can't Wait for Holiday [AtCoder Beginner Contest 146 A]

https://atcoder.jp/contests/abc146/tasks/abc146_a 解説 https://atcoder.jp/contests/abc146/submissions/8629033 SUN,MON,TUE,WED,THU,FRI,SATを0,1,2,3,4,5,6と変換して考えてみよう。 すると、答えは7-S'となる。 文字列だと差を出しにくいので、数値…

Digit Sum Replace [DISCO Presents Discovery Channel Code Contest 2020 Qual D]

https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_d 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8587942 コードがかちゃかちゃだが、方針を伝える。 以下の様な考察で解にたどり着く。 ぱっと見て最適な動きが思いつかない…

Majority of Balls [DISCO Presents Discovery Channel Code Contest 2020 Qual E]

https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_e 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8589071 N個ならんで質問をしよう。 1つずつずらしながら質問をしたときに答えの色が変わるポイントがある。 例えばiからN個…

Digit Sum Replace [DISCO Presents Discovery Channel Code Contest 2020 Qual D]

https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_d 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8587942 コードがかちゃかちゃだが、方針を伝える。 以下の様な考察で解にたどり着く。 ぱっと見て最適な動きが思いつかない…

Strawberry Cakes [DISCO Presents Discovery Channel Code Contest 2020 Qual C]

https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_c 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8587526 実装方針としては、まずは縦にスライスして、横にスライスする。 cnt[x] := x座標がxであるいちごの個数 これを数え…

Iron Bar Cutting [DISCO Presents Discovery Channel Code Contest 2020 Qual B]

https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_b 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8587116 どの切れ目を選ぶかを全探索する。 ある位置で切ったとして、片方の長さがlft, もう片方の長さがrhtであるとき、 操…

DDCC Finals [DISCO Presents Discovery Channel Code Contest 2020 Qual A]

https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_a 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8586587 賞金額の合計を求めよう。 1位、2位、3位の賞金を入れておき、どっちも1位なら追加で40万与える。 int X, Y; //----…

Tahoiya ga Tokuiya [TSG LIVE! 4 プログラミングコンテスト E]

https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-tahoiya-ga-tokuiya/problem 前提知識 動的計画法 解説 https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-pr…

LCM Interval [TSG LIVE! 4 プログラミングコンテスト F]

https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-lcm-interval 前提知識 Disjoint Sparse Table 想定解はSliding Window Aggregationだが、本解法では使ってない 解法 https://www.hackerrank.com/contes…

Constructable [TSG LIVE! 4 プログラミングコンテスト C]

https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-constructable 嘘解法かも https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-constructable/submissi…

Three Sushi Game [TSG LIVE! 4 プログラミングコンテスト B]

https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-three-sushi-game 解説 www.hackerrank.com 寿さんは自由に手を決めることができるので、毎回最適な手を出せばいい。 サンプルには丁寧にも全てのパター…

Live Performers [TSG LIVE! 4 プログラミングコンテスト A]

https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-live-performer 解法 https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-live-performer/submissions/…

よくあるボールを移動するやつ [yukicoder 929]

https://yukicoder.me/problems/no/929 解説 https://yukicoder.me/submissions/400103 なんとなく貪欲でやれば良さそうな気がする。 先頭からなければ前から持ってくるか、後ろから持ってくるかすればいい。 これはボールに最初にある場所の添字を付けて、…

軽減税率? [yukicoder 928]

https://yukicoder.me/problems/no/928 解説 https://yukicoder.me/submissions/399903 不等式にして条件を満たすラーメンを考えてみる。 floor( (1+P/100)x ) < floor( (1+Q/100)x ) + A floorは切り捨ての関数である。 両辺のfloorについてなんとかするの…

Second Permutation [yukicoder 927]

https://yukicoder.me/problems/no/927 解説 https://yukicoder.me/submissions/399615 2番目に大きいものとあるが、最も大きいものを考えてみる。 与えられた文字を降順で並べると、最大の数が得られる。 サンプル1にもあるように、最大の321の下2桁をスワ…

休日の平均 [yukicoder 926]

https://yukicoder.me/problems/no/926 解説 https://yukicoder.me/submissions/399496 最後の「一週間の内の休日の位置が変わった場合でも平均の休日数は変わらないことが証明できます。」が あるおかげで簡単に解けそうだ。 一週間の先頭C日間が休日として…

Average Length [AtCoder Beginner Contest 145 C]

https://atcoder.jp/contests/abc145/tasks/abc145_c 解説 https://atcoder.jp/contests/abc145/submissions/8483703 まず、Nが非常に小さい。 経路は全部でN!通りあるが、最大でも40320通りなので、これは全探索ができる。 C++だとnext_permutationを使うと…

Circle [AtCoder Beginner Contest 145 A]

https://atcoder.jp/contests/abc145/tasks/abc145_a 解説 https://atcoder.jp/contests/abc145/submissions/8482353 円の面積の公式はπr2なので、半径がr倍されれば、面積はr2倍となる。 よって、r2が答え。 int R; //------------------------------------…

Laminate [AtCoder Beginner Contest 145 F]

https://atcoder.jp/contests/abc145/tasks/abc145_f 必要知識 座標圧縮 動的計画法 解説 https://atcoder.jp/contests/abc145/submissions/8491333 必要な知見として高さを操作するが、最初に与えられているHiの高さにするか0にするかしかない。 中途半端な…

Knight [AtCoder Beginner Contest 145 D]

https://atcoder.jp/contests/abc145/tasks/abc145_d 前提知識 二項係数 mod 素数を高速に計算する方法 解説 https://atcoder.jp/contests/abc145/submissions/8484697 400点にしては問題が難しい感じがする。 何か全探索対象を探そう。 まず、(+1,+2)か(+2,…