問題 提出コード 解法 日間で、日目に自炊を行ったと仮定します。 このとき、得られる幸福度は以下のようになります。 はじめの2つの項が食堂で食べることによって得られる幸福度、最後のΣの部分が自炊によって得られる幸福度になります。 これを式変形する…

問題 提出コード 解法 番目の山に降った雨の量をとします。 すると、以下のような式が成り立ちます。 ということで、これらの式をまとめてを求めることを考えてみます。 上の式から順番に、式1,2,...Nと名付けると、 式番号が奇数のものはそのまま、偶数のも…

問題 提出コード 解法 最悪ケースを考えると、サンプルにあるような17711通りのパターンになります。 ということで、全部列挙してから文字列をソートし、10個出力するのが十分間に合います。 あとは、全部列挙する方法を考えていけばよいです。 操作終了後の…

問題 提出コード まずは、すぬけ君とふぬけ君がどちらか1人だけの時に、目的地にたどり着くことができるかを調べます。 それぞれ、の範囲に岩#が2個以上連続して配置されている場合、プレイヤーが移動した結果、Pをプレイヤーとすると、 P##のようになり、こ…

問題 提出コード 解法 0.5うんぬんという条件がありますが、結局は時刻の間で座標に到着した場合、その人はそれ以上進めない、ということになります。 これを言い換えると、時刻の間に座標を出発する人は、少なくともより先に進むことができなくなります。 …

問題 提出コード 解法 問題の条件を整理すると、 として、 となるので、つまり、 となります。 ということで、かつを割り切るようなの総和が答えとなるので、で約数を列挙し、その総和を求めれば良いです。 感想 割り算の式を思い出すと、ぱっと解ける問題で…

問題 提出コード 解法 まず、それぞれの文字列の中に含まれるABの個数を調べます。これは、文字列をどのように連結しても、個数が変化することはないので、そのまま答えに加算されます。 では、文字列の連結によってあらたに増えるABの個数を調べます。 文字…

問題 提出コード 解法 それぞれのターンで、ある頂点を指定すると、その頂点を根とする木について、葉になっている頂点が消えることになります。 そして、どのような頂点の選び方をしても、木についている頂点を減らすのに一番時間がかかる部分は、木の直径…

問題 提出コード 解法 とを同じ数字にそろえる場合に、3パターンの選択の方法があります。 を選び、以外を選ぶパターン はになり、は据え置きです。 この方法だと、かつが偶数の場合にそろえることができます。 とを選ぶパターン ,になります。ので、の場合…

問題 提出コード 問題 まず、最悪手でソートすることができます。これは、から順番に、一番左側に移動していけばよいです。 ということで、さらに効率的な方法を探ります。 今回の操作では、両端に数字を移動させることはできますが、逆に真ん中に数字を挿入…

問題 提出コード 解法 まずは、が奇数の場合について考えます。 太郎目線で考えると、"初手で行ける範囲内に青いマスが存在していれば必ず勝利できる"となります。 何故かというと、青いマスが最初のマスに隣接していた場合、初回の行動で太郎君はその青いマ…

問題 提出コード 解法 まず、順番は全く関係なく、できるだけ多くの4人グループを作成していくことだけを考えればよいです。 先にグループを決めてしまえば、決めたグループの中の誰かが先頭に来た時点で、他の人達と相乗りをすればよいです。 ということで…

問題 提出コード 解法 解の候補について、フロアのうち最下層の階数を、フロアの総数をとします。すると、の階を借りることになるので、料金は次のようになります。 これがと一致するので、結局 という条件が成り立つことになります。 を1つ固定すると、は式…

問題 提出コード1 提出コード2 GCD求める関数書いてますが関係ないです。 解法 提出コード1は、単純に場合分けしていきます。 現在の高橋君の票数を、青木君の票数をとします。 まず、1手前と比率が同じであった場合 その回をスルーします。 高橋君、もしく…

問題 提出コード 解法 自分はシミュレーションをしました。 相手がを出してきたときは、必ずこちらもをだして相手にポイントが渡らないようにし、そして余ったを出せる回数で得点を稼ぐ、といった方針です。 ということで、まずは相手のの回数をカウントしま…

問題 提出コード 解法 まず、の際は答えがになるのは自明なので、それ以外の場合について考えます。 個の空き瓶を個の新品と交換したとき、手元にある瓶の個数は個減ります。この減る個数は一定です。 よって、個の瓶が個未満になるまで交換することができる…

ということで、今回は各問題についての簡単な解法と、その感想です。 まだ解けていない問題もいくつかあるので、ご容赦ください… 運営側としてどんなことをしたか、についてはこちらの記事をご覧ください。 emtubasa.hateblo.jp 各問題の方針と感想 A - WAse…

問題 提出コード Sushi問題は難しいことで有名です（要出典） 解法 ループする系の期待値は、こんな感じで立式すると見えてきます。 今回は、お皿にのっているお寿司の数を利用します。 3個のっている寿司が皿、2個が皿、1個が皿だとして、そこから全ての寿…

問題 提出コード 人生初の嘘解法を通しました！！！割と条件を省いて書いたのですが通ってしまったので、サンプルが弱いと思います(ACしない凡例が存在します)。 例えば、自分のコードだと 5 0 0 0 2 2 という入力で答えが6になります(本来、このような入力…

問題 提出コード グランディ数を利用する問題は、ぱっとみで使うだろうなーというのがわかっても、そこから答えに結び付けるのが難しくていつも解くのに時間がかかります… 解法 お互いが操作できなくなる状態では、必ず2種類の文字になっていて、それが交互…

問題 提出コード 解法 について全探索をすると間に合わないです。ので、について全探索をして、そのときのを求めればよいです。 全てが以上以下になる解が存在するという保証があるので、はこの範囲で全探索をします。 を、となるような式にうまく変形します…

問題 提出コード 解法 まず、答えが仮にxであったとします。そのとき、xは1回目の操作でどこにいくか、ということを考えてみると、 x - 1 - x/k となります。k、2k、3k…の人が処刑されるので、その人数分引けばいい、ということです。 次に、後ろから考えま…

問題 提出コード 解法 考察は終わっていましたが実装が間に合いませんでした。 まず、木を作るのに必要な要素は3つあります。 sの最後の文字が0 辺を1つ選んだ時点で、サイズはnより小さくなってしまうので、条件を満たすことができません。 sの最初の文字が…

問題 提出コード 解法 後ろから攻めていき、最後が空文字列になるかどうかで判定します。 猫の鳴き声をCATとすると、mCATeCATw となっているはずなので、まず両端がそれぞれmおよびwになっているかどうか判定します。この時点で辻褄があっていなければ答えは…

問題 提出コード 解法 この問題は、初期状態であるABCから2手分ぐらいを書き出し、あとは後ろから見ていくということに気づくと、うまく解くことができます。 後ろから見ていったとき、ABCと綺麗に並んでいる部分は、かならず1手前で1文字を置換した結果でき…

問題 提出コード 解法 散らばっている情報を、まずはK×Kマスの中に押し込みます。 例えば、(x,y)がWという希望は、(x+K,y)、もしくは(x,y+K)がBという希望と同じであり、また(x+K,y+K)がWであるという希望とも同じです。 これを利用すると、白を0、黒を1と表…

問題 提出コード 解法 ぱっとみ幅優先、っぽくみえて全然違いました。 プランのi番目の位置と時刻から、i+1番目の時刻に、指定された位置に行くことができるかどうかを全部調べていきます。 i=0のときはt、x、y全て0とします。 i番目の情報をt[i],x[i],y[i]…

問題 縦と横が長さR,Cの長方形があり、それをいくつかの条件に基づいて切断し、指定された3つの面積(M,J,K)になるように分けろ、という問題です。 切断の条件は3つで、 長方形の辺と平行に切断する 一度切れ込みを入れたら、その部分は端から端まで切断する …

D - 閉路 提出コード 初めてLCAを扱う問題に触れました。 現在の木の根を適当に決めます。どこでもいいです。 新しく追加する辺の2つの頂点の番号をa,bとします。このとき、閉路の長さは、 (aの根からの深さ)+(bの根からの深さ)-2×(aとbの共通の祖先で最も近…

友だちの誘い方 提出コード まずは脳死でいもす法を書いてみます。それぞれの入力に対し、 memo[a]に1を、memo[b+1]に-1を足して、memo[0]から累積和をとっていきます。 すると、i<=memo[i]+1のとき、i-1人を誘うことができるようになっていますので、この条…