yukicoder

No.267 トランプソート

Quiz https://yukicoder.me/problems/no/267 Submission https://yukicoder.me/submissions/350277 解法 vector<pair<int, int> > Aをソートすると、firstの昇順でソート、firstが同じグループの中ではsecondの昇順でソートされる それを使うことを見越して絵柄(D, C, etc)</pair<int,>…

No.71 そろばん

Quiz https://yukicoder.me/problems/no/71 Submission https://yukicoder.me/submissions/350266 考察 N=5 普通のそろばんと同じ数 1, 4に分けると0〜9までの10種類を表現できる 一方、サンプルケースでは2, 3に分けることで11種類を表現できる 等分すると…

No.754 畳み込みの和

Quiz https://yukicoder.me/problems/no/754 Submission https://yukicoder.me/submissions/350209 解法 N=3で書いてみると以下の和を求めればいいと分かる 配列AかBの累積和を持っておけば、和はO(N)で求められる

No.496 ワープクリスタル (給料日前編)

Quiz https://yukicoder.me/problems/no/496 Submit https://yukicoder.me/submissions/342341 類似問題(一次元) https://tdpc.contest.atcoder.jp/tasks/tdpc_contest https://tdpc.contest.atcoder.jp/submissions/5127160 解法 上記一次元のDPと同じ解…

No.74 貯金箱の退屈

Quiz https://yukicoder.me/problems/no/74 Submit https://yukicoder.me/submissions/339953 解法 1枚だけでflipできるコインを調べておく 2枚flipのとき a, bを一緒にflipできるなら、Union Findでunite(a, b)しておく 「一緒にflipできるグループ」ごとに…

No.416 旅行会社

Quiz https://yukicoder.me/problems/no/416 Submit https://yukicoder.me/submissions/339563 解法 破壊される辺以外を張っておく 破壊クエリを逆から読みながらその辺を復活させていく 木がつながったかはUnion Findで管理する 辺を繋げる前に、今回の接続…

No.390 最長の数列

Quiz https://yukicoder.me/problems/no/390 Submit https://yukicoder.me/submissions/19573 解法 公式解説の通りではあるが、各dp[i]についてiの約数を列挙してdpを更新してACした 配るDPがオススメされていたが、制限時間ギリギリそうな列挙でトライした …

No.477 MVP

Quiz https://yukicoder.me/problems/no/477 Submit https://yukicoder.me/submissions/336588 解法 他の人は数式で解いていたが、私は二分探索で解いた 二分探索 left = 0 (絶対にMVPが取れない) right = inf (絶対にMVPが取れる) center = (left + right) …

No.561 東京と京都

Quiz https://yukicoder.me/problems/no/561 Submit https://yukicoder.me/submissions/336212 解法 動的計画法を使う dp[2][N] dp[i][j] i : 0:東京 1:京都 j : j日目 (0-index)の仕事を終えた後のお金 とする 前日の稼ぎと当日の稼ぎの関係は 前日東京→ 当…

No.198 キャンディー・ボックス2〜三分探索〜

Quiz https://yukicoder.me/problems/no/198 Submit https://yukicoder.me/submissions/335991 解法 キャンディーの目的値を決めると操作回数が決まり、これは下に凸の関数になる 三分探索すればいい 学び while(right-left>3){ ll p0 = (2 * left + 1 * rig…

No.65 回数の期待値の練習

Quiz https://yukicoder.me/problems/no/65 Submit https://yukicoder.me/submissions/335985 解法 振る回数の更新式は提供されている E(K)以降は、もうK回を達成しているので振る回数は0であることに気づけば、後ろからのDPができる

誤差と桁あふれはできれば避けたい

誤差と桁あふれに注意する必要があるよい問題(教材)がある。 Quiz https://yukicoder.me/problems/no/648 Submit https://yukicoder.me/submissions/335262 解法 t秒後の合計はt * (t+1) / 2 それとnが一致する整数があればいい tについて解の公式で解く …

No.314 ケンケンパ

Quiz https://yukicoder.me/problems/no/314 Submit https://yukicoder.me/submissions/330500 他の人の解法 dp[i][j] : i番目まで見たとき、ケンの数が j である場合の数 解法 私は、直前2つの状態を見れば遷移が決まることから、 dp[i][j][k] i 番目まで見…

No.3 ビットすごろく

Quiz https://yukicoder.me/problems/no/3 Submit https://yukicoder.me/submissions/330413 解法 ある地点からの移動先は(2箇所以下に)固定されている よって、ある地点に戻って来たら、それは最短距離ではない 同じ地点を訪れないようにしながら最短距離を…

No.4 おもりと天秤

Quiz https://yukicoder.me/problems/no/4 Submit https://yukicoder.me/submissions/330176 解法 天秤の両方を気にするのは大変 重さの合計 / 2 を片側で作れるかで判定すればいい 各重りを使う・使わないで分岐したらO(2100)となってしまう dp[i][j] : i番…

No.786 京都大学の過去問

Quiz https://yukicoder.me/problems/no/786 Submit https://yukicoder.me/submissions/329556 解法 dp[i] : i段登るときのパターン数とする dp[i]は、 dp[i-2]から2段UP dp[i-1]から1段UP という遷移から来ることができるので、 dp[i] = dp[i-2] + dp[i-1] …

No.806 木を道に

Quiz https://yukicoder.me/problems/no/806 Submit https://yukicoder.me/submissions/328743 解法 公式解説の通り、Σmax(Deg(i)-2, 0) ポイント グラフを次数で見る 最終形の性質を観察する そして現状と比較して、その差が、すべき操作

カタラン数〜括弧の対応のパターン〜

Quiz https://yukicoder.me/problems/no/790 Submit https://yukicoder.me/submissions/328008 概要 対応の取れた括弧は何パターンあるか ()()() ((())) など 解法 各位置にどちらの括弧を置くか全パターン生成してからチェックする またはカタラン数 青チャ…

No.800 四平方定理

Quiz https://yukicoder.me/problems/no/800 Submit https://yukicoder.me/submissions/324836 Note 4変数で半分を全探索 これは蟻本「おみくじ」で見たやつだ! x, yは全探索, z, wから作れるパターンは事前に作っておく 二分探索 解いてみる https://yukic…

No.793 うし数列 2

Quiz https://yukicoder.me/problems/no/793 Submit https://yukicoder.me/submissions/318975 Note 10N (N=1018) ここに高速累乗を使う。log(N) 3で割ったもののmodなのでフェルマーの小定理を使う