いろいろ昔作ったコードを漁っていると, 半年前に作ったオートマトンのコードがあったのでここに供養. 作成の動機 オートマトンの講義があって, その復習というのもあったと思いますが, 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個の連続した区間を同じ色を塗ることになります. 一回以上操作を…

D - Menagerie どこか連続する2つの位置について羊狼の割り当てを決めると, 片側の決まった動物から, すべての場所の配置を決定することができます. よって, 1番目と2番目の羊狼の割り当て(2*2=4通り)を決め, それが条件を満たしているかどうかを確認し, 4つ…

D - Walk and Teleport 見た瞬間グラフを作って最小全域木を求めたくなりますが, どの頂点からどの頂点へもテレポートが可能であるため, 辺の数が最悪$10^{10}$以上に膨れることになるため, 最小全域木の構成は辛いです. そのため, 別の解法を考える必要があ…

D - Big Bang なかなか問題分が複雑で, 読解に苦労します. Pを求めるために, 以下の3つ ①平行移動のベクトル ②回転角度 ③相似拡大の大きさ を求める必要があります. A,Bの点のそれぞれの重心に着目すると, ①のみがその変化に関与していることがわかります. …

D - Good Grid 各マスが(p+q)%3 = 1 or 2 or 0 の3つのグループに分割できるため, それぞれのグループについてC通りの色を塗りつぶしたときの違和感をあらかじめ計算しておき, C^3通りの組み合わせを検証して最小値を出力して答えです. Submission #2910715 …

B - Colorful Slimes 高橋君は ・ xのコストを払って今飼っている各モンスターの色をi → (i+1+N) % N にする(操作1) ・ A[i]のコストを払って色iのモンスターを新たに飼う(操作2) の2つの行動ができます. 操作1をk回行うと決めると, A[i-0],A[i-1]..A[i-k]の…

B - Colorful Creatures 良問だと思います. まず, N個の入力のクリーチャそれぞれに対してそれぞれ固有の色が割り当てられますが, それぞれ固有の色であり, 色の数値の大小に対して優劣をつける操作がないため, 色を無視して大きさ順にソートをしても問題な…

Farey Sequence | Aizu Online Judge問題名から察せるとおり, n群目のファレイ数列の要素数を数える問題です. $n-1$群目のファレイ数列までわかっていると仮定したとき, $n$番目のファレイ数列の要素数は($n-1$群目の要素数+nと互いに素なn未満の自然数の数)…

D - 高橋君と見えざる手 / An Invisible Hand 問題文の情報量が多く, 情報を整理するのに時間がかかります. 高橋君が最適に行動したときの利益を1以上下げるために, りんごの価格を操作するというのが趣旨となります. まず高橋君の戦略を考えると, りんごが…

D - Score Attack グラフの問題としては少し特殊で, ゴールまでのコストを最大化する問題です. これは, すべてのコストを負にした最短経路問題を解くことで解を出せます. しかし, コストに負を含んでいるとダイクストラ法が使えません. そのため, ベルマンフ…

D - Fennec VS. Snuke ゲームの最善手問題です. 与えられるグラフが木構造であるというのが最大のポイントで, 閉路が存在しません. はじめに相手の色がある方へ向かって色を塗っていって相手の塗れる頂点を減らすのが最適解となります(木構造なので親を取っ…

ずっと放置してたABC101-D - Snuke Numbersを解きました. D - Snuke NumbersK番目のすぬけ数は$10^{15}$以下とありますが, $1$から$10^{15}$まで調べていると時間が足りないので, 解の候補を絞ってから解を探索する必要があります. 絞り方として, 末尾に9が…

ABC 095をセルフコンテスト. C問題までさくさく解けたがやはりD問題で詰まりました. D - Static Sushi 試行錯誤しながら実装し, なんとかサンプルと答えを合わせられたので提出するとぽつぽつとWA. あきらめて解説をちらちら見ると方針はあっていたので, 実…