atcoder.jp 問題 問題 i は、解いたときに貰えるスコアが 100*i 点、問題数が p[i] 問、全ての問題を解いたときに貰えるボーナススコアが c[i] である。これらの問題を解いてスコア G以上 を得るとき、少なくとも何問の問題を解かなければならないか。 考察 …

atcoder.jp 問題 省略 考察 ※以下、0オリジン 問題文を ・Xの指定された部分を連結すると S,Tになる ではなく、 ・S,T を指定された通りに並べたとき、矛盾なく X を作ることができるか と読み換えて考えます。 N=6, M=3 のとき、S,T は表のように並べること…

atcoder.jp 問題 最初、3人はクッキーを A,B,C 個持っている。 操作を1回おこなうごとに、それぞれの人は「他の2人が持っているクッキーの個数の平均値」を同時に受け取る。 いずれかの人のクッキーが奇数になるまで操作をおこなうとき、操作は何回可能か。 …

atcoder.jp 全ての文字列に共通する文字を取り出して、辞書順最小の文字列を合成する問題です。 解説はコードの中に埋め込んだので、そちらをご覧ください。 方針としては、 ・1番目の文字列に含まれる文字を共通文字とする ・2番目以降の文字列について、そ…

atcoder.jp 実装力が問われる問題だと思います。 長さ N の文字を長さ N-1 の文字に変える際、N の i 文字目と i+1 文字目のどちらかを選びますが、このとき選ぶ文字を「寄せる文字」と呼ぶことにします。 S の長さは最大でも 100 なので、寄せる文字を a～z…

atcoder.jp N が与えられた時点で各桁の和が最大である場合と、そうでない場合に分けて考えます。 与えられた時点で最大であるような N とは、 ・2桁以上で、先頭の数字以外が全て 9 である N です。 これには 99, 199, 399999 などが該当します。 2桁以上と…

atcoder.jp 与えられた 3 x 3 の数字が特定の形式になっているかどうかを判定する問題です。 問題の形式になっている 3 x 3 の数字の並びには、例えば以下のようなものが考えられます。 b[1] b[2] b[3] a[1] 2 4 6 a[2] 4 6 8 a[3] 4 6 8 ここで、a[1]=2, a[…

atcoder.jp 文字列 S の部分文字列のうち、K 番目に小さいものを出力せよ、という問題です。 解説にもあるように、部分点を取るだけなら非常に簡単です。 長さ1、長さ2、長さ3......長さ S.length() の部分文字列を全て求めてから、ソートして、K 番目に小さ…

atcoder.jp 解説にある方法で簡単に解くことができますが、勉強のためにスタックで解いてみます。 文字列の i 文字目を c としたとき、 ・c と スタックの最初の値 が異なるとき → スタックをpopする ・c と スタックの最初の値 が同じ or 空のとき → スタッ…

atcoder.jp 私にとってはかなり難しい問題でした。よって、何段階かに分けて理解します。 剰余の式を理解する まず、以下の式変形を見てください。 ・(a+b) % K = (a+c) % K ・b % K = c % K 以前も何かの問題で見た気がしますね。a=5, b=4, c=8, k=4 のとき…

atcoder.jp 数直線上に N 個の座標がある。最初、立っている座標は x=0 である。 N 個のうち K 個の座標を訪れるとき、移動距離の総和の最小値として考えられるのはいくつか、という問題です。 訪れる K 個の座標は、連続していたほうがよいです。わざわざ1…

atcoder.jp 累積和の問題です。 ある人 i をリーダーに選んだとき、向く方向を変える必要があるのは、 ・i より左側にいる W ・i より右側にいる E です。この2つの合計が最小になるようにリーダーを選びます。 長さ N+2 の配列 W と、同じく長さN+2 の配列 …

atcoder.jp チームの中央値をなるべく大きくすることを考えます。 中央値の個数は3人1組なので N 個です。 N 個の値（N人）を参加者 3N 人のうちのどこから選ぶか。 最初に考え付いたのは以下のような選び方です。A がチームの最小値、B がチームの中央値、C…

atcoder.jp 操作が0回目のとき、すなわち何もしていないときの高・中・低の所持している値と 高-中 の値は、 ・A, B, C（A-B） です。1回目のときは、 ・B+C, A+C, A+B（B-A+C-C = B-A） ですね。同様に2回目は、 ・2A+B+C, A+2B+C, A+B+2C（2A-A+B-2B+C-C =…

atcoder.jp i 番目のボタンを押すと、数列の A(0) から A(i) までの項が全て +1 されます。ボタンを押した項だけだと勘違いしてました。 仮に長さ2の数列があり、0番目の項はボタンを100回押せばよく、1番目の項はボタンを10回押せばよいとします。このとき…

atcoder.jp 数直線上において、初期座標 X と、目的地の座標が N 個与えられる。距離 D ずつしか移動できないとき、全ての目的地を訪れることのできる D のうち最大のものを求めよ、という問題です。 D=1 としてしまえば、あきらかに全ての目的地を訪れるこ…

atcoder.jp Sに含まれる文字を「変換元」、Tに含まれる文字を「変換先」と呼ぶことにします。このとき、変換先はただ1つであり、変換元も同様にただ1つである必要があります。 仮に S=abb, T=xyz の場合を考えてみます。変換操作では、1種類の文字を別の1種…

atcoder.jp この問題は解説を読んでも全く理解できなかったので、以下の解説サイトを参考に、やったこともないDPで解いてみることにしました。 nomikura.hatenablog.com DPはやったこともないと書きましたが、一応、おぼろげには理解しているつもりです。累…

atcoder.jp 右上の領域の正方形の数を数えてから、4倍して答えを求めます。 「右上の領域にある正方形」が円に含まれているかどうかは、正方形の右上の頂点が円に含まれているかどうかということに等しいです。よって、右上の頂点に注目して数えていくことに…

atcoder.jp 文字列 S の好きな場所に好きなだけ "A" を挿入して "AKIHABARA" を作れるならYES、作れないならNOを出力せよ、という問題です。 "A" を好きな場所に好きなだけ挿入して "AKIHABARA" にできるような S とは、以下のような構造のものです。 ・[0個…

atcoder.jp N個の数値が与えられる。これらの数値に以下の操作をほどこして、3つの値 A,B,C を作る。必要となるコストのうち、最小のものを求めよ、という問題です。 ・数値を1増やす（コスト1） ・数値を1減らす（コスト1） ・2つの数値を足して新しい数値…

atcoder.jp Map の中に List を入れるという構造に慣れていないので、難しかったです。実装も難しかったんですが、この問題、制限時間がかなり厳しくなっていて、TLEに苦しみました。制限時間は2000ms。私が提出したACコードの実行時間は約1400msでした。C++…

atcoder.jp 文字列 T が文字列 S の一部分と一致するかどうかを、S の全ての場所（S.length-T.length+1 箇所）で試します。 "?" を無視して一致を判定していき、もし T が S の一部分と一致するなら、S のその場所を T に、S に含まれる全ての "?" を "a" に…

atcoder.jp M,A,R,C,H の5つから3つを選ぶ組み合わせは 5C3 から 10通り です。解説には「たかだか10通りなのだから全て試せばよい」とありますが、ちょっと面倒くさいので、ついさっき記事を書いたビット全探索で解いてみることにしました。 import java.ut…

atcoder.jp 文字列Sの全ての部分集合を数値として足し合わせた総和を求めよ、という問題です。 実装方針は明確だけれども実装方法が難解というパターンです。再帰関数を使っても解けると思うのですが、あいにく再帰関数は苦手なのでビット全探索を使います。…

atcoder.jp 与えられた数列の項を操作して累積和を [正,負,正,負......] もしくは [負,正,負,正......] の形にするとき、操作回数の最小値を求めよ。ただし、累積和は一度でも0であってはならない、という問題です。 偶数項を正とするのか、奇数項を正とする…

atcoder.jp 7,5,3 がそれぞれ1個以上含まれている数を 753数 と呼ぶ。1以上N以下の整数のうち、753数は何個あるか。 N が 10^9 なので全探索は不可能です。そこで、再帰関数を用いて 7,5,3 のみで構成されるN以下の数字を全て作っていき、その中から753数の…

atcoder.jp 与えられた数列の項を書き換えて [a,b,a,b,a,b,a,b] のような形にするときの、操作回数の最小値を求めよ、という問題です。 与えられた数列の偶数番目だけを抜き出した偶数列と、奇数番目だけを抜き出した奇数列にわけて考えます。偶数列・奇数列…

atcoder.jp まず思いついたのは全探索解法です。 ・石を左端に置くか右端に置くか ・石の色は黒か白か この4パターンから、裏返せる石の数が最多であるものを選び、そのつど石を裏返しながら手数を数えていくというものです。文字列長が 10 くらいなら現実的…

atcoder.jp 数列が与えられる。全ての隣り合う2項の和を x 以下にしたい。各項から引く値の総和の最小値はいくつか、という問題です。 入力例2で考えてみます。最初の2項は [1,6] ですが、これの和を1以下にしなくてはなりません。このとき、左側から1、右側…