atcoder.jp 問題 長さ N の数列がある。 数列の長さ 3 の部分列のうち、初めて和が K 未満になるような部分列の位置を求めよ。 考察 勉強のため、二種類の解法で解きたいと思います。 累積和から部分和を求める 数列に対してあらかじめ累積和をとっておくこ…

atcoder.jp 問題 N 個の数字を A,B の2つのグループに分ける。 Aグループに属する数字の合計を sumA 、Bグループに属する数字の合計を sumB とする。 sumA, sumB の差が最小になるようにグループ分けをするとき、sumA, sumB のうち大きいほうを出力せよ。 考…

atcoder.jp 問題 N*M*L の大きさの箱に、P*Q*R の大きさの荷物はどれだけ入るか。 荷物はどの向きで入れてもよい。 考察 以前作成した nextPermutation の使いどころがやってきました。 ・Javaでnext_permutationメソッドを作ってみる - 文系プログラマーの…

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 以前記事に書いた再帰関数をそのまま流用できる問題です。 ・再帰関数で部分集合を全列挙する - 文系プログラマーのプログラミング備忘録 枝分かれの部分を "a","b","c" の3つにして、終了条件を長さが n になったときにすればよいです。 void so…

atcoder.jp 冷静にシミュレーションします。 N 本の鉛筆は、最初に必ず販売できるので、まずこれを答えに足します。 次に、以下の操作を鉛筆が m 本未満になるまでおこないます。 ・回収した鉛筆から製品を作る（N/m*n 本作れる） ・製品を作った後に出た余…

atcoder.jp この問題は以前満点解法を記事にしましたが、部分点解法がDPなので、DPのいい練習になると思って部分点解法の記事も書いてみることにしました。 といっても、基本的には解説にある通りに実装するだけで、 イメージしやすいという点では一次元のDP…

atcoder.jp 「DPの一番簡単なやつ」です。 余談ですが、この問題、以下の問題と寸分違わず同じになっています。 ・C - 柱柱柱柱柱 void solve () { int n = nextInt(); int[] ar = nextIntArray(n); int[] dp = new int[n]; dp[0] = 0; dp[1] = Math.abs(ar[…

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 答えは ・(H+W-2)! / (H-1)! * (W-1)! % 1000000007 です。 部分点50点は上記の式を計算するだけ、部分点100点はDPをすることで得られますが、 満点101点は W,H 満点を得るためにはフェルマーの小定理（？）、逆元（？）などを求める必要があるみ…

atcoder.jp 前回の記事にあるプログラムを使って解いています。 jpliterature.hatenablog.com 入力・出力部分 static int h, w; static Point s, g; static char[][] map; static int x; static ArrayList<Integer> list = new ArrayList<>(); void solve () { //入力</integer>…

atcoder.jp 6枚のカードに対して、N 回の交換操作をおこなう。 N 回目の操作では、左から N%5 番目のカードと、右から N%5+1 番目のカードを交換する。 操作を N 回おこなったあとのカードの並びを出力せよ。 N は最大で 10^9 なので、愚直にシミュレーショ…

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 区間が N 個与えられる。 最も多くの区間に被覆されている値の、その区間の数を求めよ、という問題です。 解説にあるように、imos法を使うみたいです。 imos法は累積和を応用したアルゴリズムで、実装はとても簡単です。 区間の最小値～最大値に…

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 与えられた文字列が、指定の手順で作られたかどうか判定する問題です。 手順は、まず "b" を初期文字列として設定し、その後、 ・両端に "a" と "c" を付ける ・両端に "c" と "a" を付ける ・両端に "b" と "b" を付ける ・以下、この繰り返し …

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はやったこともないと書きましたが、一応、おぼろげには理解しているつもりです。累…