next_permutation は c++ の関数で、与えられた順列の次の順列を戻します（1234 → 1243）。 AtCoder のある問題を解くにあたってこの関数が必要になったので、Java には用意されてないのかな～と探してみましたが、私が探してみた限りでは存在していませんで…

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 ・長さ N 数列のうち，連続した K個の要素を選ぶ．その後，選んだ要素それぞれの値を，選んだ要素の中の最小値で置き換える． という操作で与えられた数列の要素を全て等しくするとき、その値は "1" にしかなりません。なぜなら、仮に2に等しくし…

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

私は主に AtCoder, yukicoder, AIZU ONLINE JUDGE を利用して競プロの学習をしています。現在の学習状況はというと、AtCoder は100,200点問題を全AC・300点問題を半分ほどAC、yukicoder はレベル1問題を全AC、AIZU ONLINE JUDGE はまあそれなりといった感じ…

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

AtCoder Beginner Contest 119 に参加しました。 結果はAB2完、順位は1019/2732位でした。 A - Still TBD atcoder.jp かなり難しくないですか。実装に手間取りました。最終的には、文字列を8ケタの数値に変換して、その数値が20190430以下であるかを比較して…

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" に…

Java で二分探索を実装する際、わざわざ左端と右端と中央をループの中であれやこれやしなくても、クラスライブラリの java.util.Arrays に二分探索をおこなってくれるメソッドが存在しています。 仮に、以下のような配列があったとします。 int[] ar = {2,4,…

以下の記事では、ビット全探索による部分集合の全列挙を勉強しました。 jpliterature.hatenablog.com 今回の記事では、同じことを再帰関数でやってみようと思います。 さて、再帰関数で部分集合を全列挙するにあたり、こんな問題を作ってみました。 問題文 …

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

プログラミング関連の書籍にありそうなタイトルですが、以下の記事の続編になります。 jpliterature.hatenablog.com 上記の記事では、ビット全探索を使って問題を解きました。しかし私自身、ビット全探索、もといビット演算子についてよく理解していません。…

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 を比較して…

judge.u-aizu.ac.jp LinkedList で解こうとしたら思い切り TLE を喰らいました。他の方の解答を見ると全員が自作のDequeクラスを作って解いているので、つまりはそういうことなんだと思います。 import java.util.*; class Main { static Scanner sc = new S…

docs.oracle.com ArrayListクラスはサイズ変更可能な配列です。サイズを超えて要素を追加しようとした場合には、配列と違ってサイズを自動で増やしてくれます。ところで、競プロでは Map や Set をよく使いますが、この ArrayList を使った記憶はほとんどな…