2018-08-01から1ヶ月間の記事一覧
問題 B - Neutralize 解法 貪欲ができないか考えます. ある薬品を0にしたいときはK個を巻き込む必要があります. また, 個以上の区間を0にしたいときはこれを繰り返すことで実現することができます. しかし, サンプルケースを見てみるとこれは厳しそうである…
問題 No.672 最長AB列 - yukicoder 解法 まず愚直解を考えます. 左端を決めて左から文字列を見ていき, A, B,の数を数えながら右に行き, AとBの数が同一になったら最大値を更新します. この解法はでTLEです. この解法を詰めていきましょう. まず,ABの数が同一…
問題 No.390 最長の数列 - yukicoder 解法 DPをします. としておきます. 遷移は, です. 右のを固定して配るDPにすると, 計算量はなります. 左を固定すると約数の列挙にかかるためとなり, ギリギリ間に合います. 提出 #279345 No.390 最長の数列 - yukicoder …
問題 No.462 6日知らずのコンピュータ - yukicoder 解法 まず, がであるときを考えます このとき, 〜 桁のビットまで, ビットを立てる順番の場合の数がそのまま場合の数になります. 一度立てたビットは元に戻さないため, これらの数列たちはすべて異なるもの…
問題 No.491 10^9+1と回文 - yukicoder 解答 の性質に着目します. にたとえば123456をかけると, になります. ほかの数値に対しても, 数値が左側と右側にコピーされているような感じになります. これに着目すると, が回文となる場合は, 回文を掛け算した場合…
問題 No.496 ワープクリスタル (給料日前編) - yukicoder 解法 dpします. どんなdpかというと, です. まずこのdpテーブルにまで徒歩でいったときのコストを入れておきます. このdpテーブルに対し, ワープクリスタルを１つずつ使っていき, コストが小さくなる…
問題 No.314 ケンケンパ - yukicoder 解法 ケンケンパの生成について, 3つの状態があります. パで終わっている 末尾にケンが1回連続で出現して終わっている 末尾にケンが2回連続で出現して終わっている 遷移しうる状態は 1 → 2 2 → 1 , 3 3 → 1 よりDPを組み…
問題 D - AtCoder Express 解法 まず, サンプルをみると速度・時刻が0.5刻みで決まっていきそうなことがわかるので, 時刻・速度ともに２倍に引き伸ばします. これで多少は考えやすくなります. 前方向から順に速度を決めていくと, 減速しきれない区間が現れた…
問題 D - Checker 解法 まず愚直な解法について考察します. この問題の１辺が大きさの市松模様について, まずどこかの黒い正方形の左下に座標を置きます. 市松模様は無限に続いているので, この黒い正方形について右に1から2K-1, 上に1から2K-1ずらしていけ…
問題 https://yukicoder.me/problems/no/607 解法 駅に到着するごとに条件を満たしているかを調べる必要があります. 駅に到着してからの人員の増減を配列に入れて管理し, その都度累積和を取り直します. までの累積和のなかで2つ選ぶと, その差分を見ればそ…
A問題 問題 A: Garden - AtCoder Beginner Contest 106 | AtCoder 解法 道を端っこに移動させるとの面積になります. 提出 Submission #3027981 - AtCoder Beginner Contest 106 | AtCoder B問題 問題 B: 105 - AtCoder Beginner Contest 106 | AtCoder 解法 …
問題 No.523 LED - yukicoder 解法 LEDをポチポチする順番を順列にして考えてみると, 例えばN=3のとき, ①①②②③③の並べ方を数える問題になります. このとき, 同じ番号のものは区別せず, 場合の数はとなります. 一般のNに対して答えは次の式で表されることがわ…
いろいろ昔作ったコードを漁っていると, 半年前に作ったオートマトンのコードがあったのでここに供養. 作成の動機 オートマトンの講義があって, その復習というのもあったと思いますが, Haskellの勉強が主だった思います. Haskellは代数構造を扱いやすいので…
オリジナル問題です. 問題 加藤さんは以下の素数の硬貨2円,3円,5円,7円,...をそれぞれ枚持って買い物にきました. 加藤さんが円の商品をお釣りがないように手持ちで支払うとき, 用いる硬貨の枚数の最小値はいくつでしょうか？ 制約 解法 前回の三角数の問題に…
#278149 No.634 硬貨の枚数1 - yukicoder 真っ先にDPを考えるも制約から空間的にも時間的にも不可能でお手上げ. 解説を見る.任意の自然数は高々三つの三角数の和で表すことができる. より一般には多角数定理というものがあるようです. 多角数定理 - Wikipedi…
No.673 カブトムシ - yukicoder とりあえず年目の元旦のときのカブトムシの数を漸化式で表してみると, が成り立ちます. これを解くと, となります. これをあるについて, で割った余りを求めたい訳ですが, 上の漸化式(特に下の式)を計算してから余りを取るに…
No.679 不思議マーケット - yukicoder個の必ず買わせることができる商品を先に買わせ, 条件を満たしているものから貪欲に買わせることで最大値を得ることができます. 条件を満たしている商品は, 買う順番が少し後になっても条件を満たしたままであることがポ…
No.699 ペアでチームを作ろう２ - yukicoderDPができないので全探索します. #277997 No.699 ペアでチームを作ろう２ - yukicoder
yukicoderもやりはじめました. No.698 ペアでチームを作ろう - yukicoder という制約をみておおっ...と思い, とりあえず全探索の計算量を見積もりました. まず人いたときの二人組の作り方の場合の数について考察します. が偶数ということなので, そのときの…
バッチェ冷えました...unratedで正直助かりました. A - AtCoder Crackers がで割り切れるとき0, そうでないとき1です. Submission #2983810 - AtCoder Beginner Contest 105 B - Cakes and Donuts オイオイ互除法か？と思いましたが制約をみて全探索. B問題…
D - 11 個の数列の中で1組のみ等しいものがあり, それ以外は互いに異なる要素であることがポイントです. 問題を少し簡単にして, この等しいもの2つの中から１つのみを取り除いて個の数列について, k個の部分列の個数を考えてみます. この数列において要素は…
D - Simple Knapsack ナップザック問題ときたら真っ先に重みでDPか価値でDPか半分全列挙かどれかだろうなあと思って制約を見たらももも大きくてDPできず, さらにはの値も100と半分全列挙するには多すぎます. しかし, 特殊な制約 というものがあります. この…
3276 -- Face The Right Way 蟻本問題です. 左から牛を見ていき, 後ろを向いていた牛がいたらその牛を左端としたK個の区間の牛の前後をひっくり返し, 右へと見ていく. 左端からK個の区間がとれなくなるまで繰り返し, 残った区間の牛がすべて前を向いているか…
3320 -- Jessica's Reading Problem 蟻本の問題です. 全要素を満たすまでページをめくり続け, 満たしたら答えの値を更新して左のページを減らし, 全要素を満たさなくなったらページをめくり...とすることで最適解が得られます. 区間の単調性からしゃくとり法…
D - 食塩水 問題を見ると, とてもDPがしたくなります. 入力のアルファベットがNとKでそれぞれ制約1000以下, 解説でO(NK)で解けます!と書いてあるところまで想像しDPを考えました. しかし, 食塩水の濃度をテーブルにもたせるとすれば, 水の重さも共に持たせな…
D - Recording 真っ先にいもす法（今日知りましたが）を適用したくなりますが, そのまま適用してしまうとチャンネルそのままで録画するときの最適解を出せないです. そこで, まずチャンネルごとにいもす法を適用して, 連続で録画できる番組, それぞれのチャ…
D - Worst Case A*Bより小さな積となる二組の整数のマッチングを最大化する問題です. ただしA,Bを用いてはいけません. A,Bを用いないことや重複を考えず, まず貪欲にマッチングを作ることを考えます. A*Bが十分大きいとして, ２項(C,D)(C 同じようにしてC = …
A問題 A - Rated for Me 条件分岐をします. 提出 Submission #2950380 - AtCoder Beginner Contest 104 B問題 B - AcCepted 素直に条件を満たしているかどうか確認します. こういうのをやるときはboolを返す関数をつくると実装が楽なんだなあと解説生放送を…
C問題コンテスト中に解きたかったなあA: コンテスト名 - Mujin Programming Challenge 2018 | AtCoder substrで入力の先頭5文字を見て"MUJIN"になっているかを見る. Submission #2941754 - Mujin Programming Challenge 2018 | AtCoderB: セキュリティ - Muj…
いろいろ考えてみたものの, 解法が思いつかず解説を見ました. B - Contiguous Repaintingこの操作において一回以上操作を行うとき, 最後の操作が存在しており, そのときに塗る色は白か黒で, K個の連続した区間を同じ色を塗ることになります. 一回以上操作を…
