https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/M 解説 根性構築。 N=1,2のときはサンプルにあるやつを答えればいい。 3≦Nのときは、00, 010, 0110, 01110, ...と構築していけばN-1個を達成できる。 なぜN-1が上限（最適解）であ…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/K 前提知識 ダブリングDP 解説 どこから手を付けるかと言うと、まずは1クエリでの計算である。 クエリ問題での方針は、「毎回高速に計算」「一気に前計算しておく」「差分だけ計算…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/E 前提知識 grundy数 解説 ゲーム問題は実験せよと古事記に書いてあるのでやる。 正確には勝ち負けだけ分かればいいので、grundy数が0になる規則性を探してくる。 ひたすら実験し…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/D 前提知識 累積和による動的計画法高速化 前提知識 DPの作り方で運命が変わる。 dp[i][xo][lst] := 数列のi個目まで確定していて、総XORがxoで、最後の要素がlstであるときの組み…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/B 解説 到達可能性といえばBFS。BFSだろうなぁと思って考えていくと解ける。 状態は(x座標, y座標, サイコロの下の面の数字, サイコロの右の面の数字)で表現する。 遷移は4方向な…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/A 解説 チームの組み合わせはC(4,2)/2通りしかないので、全通り試して実力差が最も小さいものを答えよう。 実装では、1234の順列を全列挙して、前半2人と後半2任でグループを作る…

https://www.hackerrank.com/contests/75th/challenges/many-quotients 解説 https://www.hackerrank.com/contests/75th/challenges/many-quotients/submissions/code/1321983454 死ぬほどバグった。 分母を1からNまで増やして商を見てみると、途中から5,4,3…

https://www.hackerrank.com/contests/75th/challenges/i-want-to-be-a-high-achiever 前提知識 動的計画法 解説 重要なテクがあり、これが適用できれば、ACにだいぶ近づく。 「A[i]の平均がX以上 <=> A[i]-Xの総和が0以上」 平均を実際に求めようと思うと、…

https://www.hackerrank.com/contests/75th/challenges/sashiming-string 解説 https://www.hackerrank.com/contests/75th/challenges/sashiming-string/submissions/code/1321979741 まず、何かしらの全探索対象を探す。 特徴的なのは、Sとingの位置なので…

https://www.hackerrank.com/contests/75th/challenges/nada-picnic 解説 https://www.hackerrank.com/contests/75th/challenges/nada-picnic/submissions/code/1321979520 良い問題。 なんとなくセンチメンタルになる。 答えは三択であるが、問題文からワー…

https://www.hackerrank.com/contests/75th/challenges/nada-picnic-2 解説 https://www.hackerrank.com/contests/75th/challenges/nada-picnic-2/submissions/code/1321979536 手で計算してみたが、全然わからん。 ズルをすると、以下のサイトが見つかる。 …

https://www.hackerrank.com/contests/75th/challenges/many-quotients-easy 解説 https://www.hackerrank.com/contests/75th/challenges/many-quotients-easy/submissions/code/1321979577 Nが小さいので、全探索しよう。 要素の重複を除くには、setを使う…

https://www.hackerrank.com/contests/75th/challenges/many-powers 解説 https://www.hackerrank.com/contests/75th/challenges/many-powers/submissions/code/1321980113 今回の問題の弱点はCが小さいことである。 例えば、(13 + 23 + 33 + 43 + 53 + 63 +…

https://www.hackerrank.com/contests/75th/challenges/gcd-product-easy 解説 https://www.hackerrank.com/contests/75th/challenges/gcd-product-easy/submissions/code/1321979648 制約を見てみると、iは全探索ができる。 A=1, B=10, N=6が最大であるが、…

https://www.hackerrank.com/contests/75th/challenges/bowling-3 前提知識 動的計画法 解説 https://www.hackerrank.com/contests/75th/challenges/bowling-3/submissions/code/1321979905 特殊ルールとして、前のターンでA[i]ピッタリ倒すと次のターンは点…

https://www.hackerrank.com/contests/oyamac/challenges/uniform-linear-sushi 前提知識 区間スケジューリング問題 解説 https://www.hackerrank.com/contests/oyamac/challenges/uniform-linear-sushi/submissions/code/1321978723 ある寿司を食べている時…

https://www.hackerrank.com/contests/oyamac/challenges/uniform-linear-sushi-2 解説 https://www.hackerrank.com/contests/oyamac/challenges/uniform-linear-sushi-2/submissions/code/1321978912 前の問題同様に貪欲法で解ける。 2人の空き時間をcu1, c…

https://www.hackerrank.com/contests/oyamac/challenges/tiktak-1 解説 https://www.hackerrank.com/contests/oyamac/challenges/tiktak-1/submissions/code/1321978529 順番に60のあまりを取って60で割るというのを繰り返して答えを求めていく方法でACした…

https://www.hackerrank.com/contests/oyamac/challenges/sumsumsum 解説 https://www.hackerrank.com/contests/oyamac/challenges/sumsumsum/submissions/code/1321978637 まずは全探索を考えてみよう。 ABCDxyzは全部整数でなので、等式になるためにはxyz…

https://www.hackerrank.com/contests/oyamac/challenges/storage 前提知識 bitsetによる動的計画法高速化 解説 https://www.hackerrank.com/contests/oyamac/challenges/storage/submissions/code/1321979183 見た目、ナップサック問題に近いし、yes/no系動…

https://www.hackerrank.com/contests/oyamac/challenges/rot-and-rot 前提知識 行列累乗 解説 https://www.hackerrank.com/contests/oyamac/challenges/rot-and-rot/submissions/code/1321979239 今回の操作はxにコマがあるとすると、A(A+1)x+Bによって次の…

https://www.hackerrank.com/contests/oyamac/challenges/fizzbuzz-20 解説 https://www.hackerrank.com/contests/oyamac/challenges/fizzbuzz-20/submissions/code/1321978445 有名なFizzBuzz問題。 なんとも愚直に解いてしまった。 yukicoderのFizzBuzz問…

https://yukicoder.me/problems/no/1012 解説 https://yukicoder.me/submissions/447483 クエリ問題であるが、今回は各クエリを高速に計算していく方針で考える。 O(1)かO(logN)くらいを目指そう。 まず、絶対値を含む問題でよくある方針として、絶対値を外…

https://yukicoder.me/problems/no/1014 解説 https://yukicoder.me/submissions/447568 技xから技yへコンボがつなげられる関係を有向辺として考えることにする。 すると、N頂点の有向グラフが形成できる。 このグラフをもとにアルゴリズムを考える。 まずは…

https://yukicoder.me/problems/no/1013 前提知識 ダブリング 解説 https://yukicoder.me/submissions/447484 ダブリングを知らないと、この発想は難しいかもしれない。 知らない場合は、検索して学んできてほしい。 「K回行動を行ってどの要素に移動してい…

https://yukicoder.me/problems/no/1011 前提知識 累積和を用いた動的計画法高速化 解説 https://yukicoder.me/submissions/447477 109+7数え上げ、かつ、既視感のある問題なので、DP解法から考え始める。 すると、以下のDPなら解けることが分かる。 dp[turn…

https://yukicoder.me/problems/no/1010 解説 https://yukicoder.me/submissions/447470 完全に雰囲気で解いてしまったので、あまり参考にならないかもしれない。 この問題は貪欲法で解ける。 貪欲は「縦と横で長さが小さい方から折れるまで折って、その後、…

https://yukicoder.me/problems/no/1009 解説 https://yukicoder.me/submissions/447469 ヒントとして書かれている区分求積法を実装することで答えた。 座標が微妙にずれている気もするが、誤差の範囲に収まってくれるだろう。 104くらいの分割でよさそうだ…