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、右側…

atcoder.jp N と K個の数字(D1,D2......Dk)が与えられる。N以上の数字で、D1,D2......Dk を含まない最小のものを出力せよ。 愚直（あまりこの言葉は好きではないのですが）に全探索できるかどうかを考えてみます。 最大の N は 10000 です。このとき答えが最…

atcoder.jp 「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」の配列は、並んでいる人数が決まれば一意に定まります。例えば、人数が10人なら、 ・9,7,5,3,1,1,3,5,7,9 となります。1番目の人の左には0人、右には9人いますから、差の絶対…

atcoder.jp 解説には「逆順にすると接頭辞が云々～」と書いてありますが、逆順にしなくても上手くいくみたいです。以下のコードがACコードになります。 import java.util.*; class Main { static Scanner sc = new Scanner(System.in); public static void m…

atcoder.jp 整数Nが与えられる。N=A*B と表せるような A,B のうち、桁数の大きいほうを F とする。Fのうち最小のものを出力せよ。という問題です。 Nが小さければ、1からNまで順番に調べていって、ある数 X が N の約数になっていれば、X と N/X を比較して…

atcoder.jp 相手を殴ったとき、自分の体力と同じだけ相手の体力を減らせるという設定のもと、体力 A を初期値として持つ n 体のモンスターたちが殴り合いをしたとき、最後に生き残ったモンスターの体力の最小値として考えられるものを出力せよ、という問題で…

atcoder.jp 正方形の4つの頂点座標のうち、連続した反時計周りの2点が与えられるので、残りの2点を復元せよという問題です。 解説を読んでも全く理解できません。それもそのはず、まともに解こうとしたら回転行列の考え方が必要らしく、回転行列どころか、行…

atcoder.jp 解説にある「ボタンを押す順序は関係なく、また、各行/列に対して 2 回以上ボタンを押す必要はありません」という部分がイマイチよくわからなかったので、記事を書いて理解を深めることにしました。 といっても、その疑問は以下のような図を描い…

atcoder.jp ①長さ n の数列が与えられる。この数列の各項には 0,1,2,3,4......n-1 の番号が付けられている ②数列の平均値に最も近い項の、その番号を出力せよ。 解説に「a の平均値を X とします。X は整数となるとは限りませんが、NX は平均値の定義より必…

atcoder.jp ①最初、1枚のビスケットと0円を持っている。 ②以下の操作を好きな順にk回おこなったときの、ビスケットの最大値はいくつか。 操作1：ビスケットを1枚得る 操作2：a枚のビスケットを1円に変える 操作3：1円をb枚のビスケットに変える b-a b-a>2の…

atcoder.jp ①長さnの整数列A [A1,A2,A3......An] が与えられる。 ②整数列Aの各項に [-1,0,1] から1つ選んで加算していき、整数列Bを作る。 ③全ての項の積が偶数となるような整数列Bの作り方は、何通りあるか？ 全ての項の積が偶数となるような整数列Bとは、…

atcoder.jp ①数直線上の0の地点にカンガルーがいる。 ②カンガルーは時刻iのとき、負もしくは正の方向へiだけ移動できる。 ③カンガルーが座標xに到着する時刻の最小値を求めよ。 x=16のときを考えてみます。 カンガルーは時刻5以内にxに到着することができま…

atcoder.jp 問題文の理解にずいぶん時間がかかってしまいました。ではその問題文を整理してみたいと思います。 ①半径Rの円を縦にN等分することを考える。 ②その際、N-1本の切断線ができるはずである。これをカットラインと呼ぶ。 ・カットラインに、上から1,…

atcoder.jp まず問題を整理します。 ・青いカードがn枚、赤いカードがm枚ある ・好きな文字列を一つ選ぶ ・選んだ文字列が書かれている青いカードは何枚あるか数える。1枚につき1円を得る ・同様に、選んだ文字列が書かれている赤いカードは何枚あるか数える…

atcoder.jp 学生の座標n個とチェックポイントの座標m個が与えられ、それぞれの学生をマンハッタン距離で最短のチェックポイントに移動させるときの、そのチェックポイントの番号を出力せよ、という問題です。 200点にしてはずいぶんいやらしい問題……というわ…

atcoder.jp しばらく考えたのち、座標と座標の間隔を広いほうからn-1個調べ上げることで、それをもとに各コマが移動する区間を決められるのではないか、と発想しました。最初に断っておきますと、大変回りくどいやり方で解いています。スマートな解答は後ほ…

atcoder.jp スマートに実装できなさそうだったので、他の方の解説を参考にしました。 では、例のごとく問題を単純化して考えてみます。 ①数列が与えられる ②数列から連続した区間を一つ選択し、その区間に含まれる全ての項から1を引く ③数列の全ての項を0に…

atcoder.jp 問題文がわかりづらいので整理します。 ①初項sが与えられる ②第n項を、第n-1項（Aとする）が偶数ならばA/2、奇数ならば3*A+1として求めていく ③このようにして項を順に求めていったとき、最初に要素の重複が起こるのは第何項か というふうに単純…

atcoder.jp 最も長い辺以外の二辺が、面積を求めるために必要な「直角に交わる二辺」にあたります。 短い順にソートすることでこの二辺を特定し、面積を求めて終了です。 //ABC116-A import java.util.*; class Main { static Scanner sc = new Scanner(Syst…