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

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

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

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

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