Codeforces で 初ACを獲得するまでの記録です。 登録は Googleアカウント で手早く済ませられるので、省きます。 問題を選択する ProblemSet から問題一覧を見ることができます。 右端のチェックを押すとAC者数順にソートされるみたいなので、今回は一番AC者…

AtCoder Beginner Contest 121 に参加しました。 順位は悲惨なので書きたくないです。 A - White Cells atcoder.jp h行w列を塗りつぶすと、重複して塗られるマスが h*w 個できます。 よって答えは H*W - (h*W+w*H-h*w) です。 B - Can you solve this? atcod…

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…

judge.u-aizu.ac.jp 動的計画法の問題です。 ・dp[i] = i 段目まで上るときの上り方の総数 とします。 0段目、1段目まで上るときの上り方の総数は、明らかに 1 です。 ・dp[0] = 1 ・dp[1] = 1 2段目まで上るときの上り方の総数は、2 です。 0,1,2 と上る上…

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 満点を得るためにはフェルマーの小定理（？）、逆元（？）などを求める必要があるみ…

階乗を求めるアルゴリズムというと、再帰関数を用いたものが広く知られています。 static long factorial (int i) { if (i==1) {return 1;} else {return i*factorial(i-1);} } for文を用いても同様の計算ができますが、これらの 1*2*3*4......N と順番に乗…

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 なので、愚直にシミュレーショ…

ある数を素因数分解して、その結果を返すメソッドを作ります。 素因数分解とは、Wikipediaによれば ・ある正の整数を素数の積の形で表すこと だそうです。ある数Nを ・N = 2^a * 3^b * 5^c * ...... を表すということですね。今回は、N をこの形で出力するメ…

前回の記事の続きです。 jpliterature.hatenablog.com 前回は、スタート地点から各地点までの歩数を求め、それを int型配列moves に格納しました。 今回は moves をもとに、スタート地点からゴール地点までの道のりを表示してみたいと思います。 実装方針 ・…

Java で幅優先探索をおこなうには、Queue というデータ構造を使います。 ja.wikipedia.org キューは先入れ先出し、すなわち、先に入れられたデータから順に取り出されるデータ構造です。 ところてん式といったほうがわかりやすいかもしれませんね。 では、こ…

典型問題、基本的な問題、類似的な問題などのメモです。 アルゴリズム系 全探索 ・C - Synthetic Kadomatsu ・C - たくさんの数式 / Many Formulas ・C - 755 動的計画法 ・C - 柱柱柱柱柱 min(dp[i-1], dp[i-2]) ・C - Strange Bank コイン問題 シミュレー…

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

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

AtCoder Beginner Contest 120 に参加しました。 結果は ABC 3完、順位は 753 位でした。 A - Favorite Sound atcoder.jp B/A（切り捨て）回聞けます。ただし、 C 回以上聞く必要はありません。 よって、min(B/A, C) が答えになります。 B - K-th Common Div…

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" を付ける ・以下、この繰り返し …

judge.u-aizu.ac.jp 数列 S と数列 T が与えられます。 数列 T のそれぞれの要素のうち、数列 S に含まれているものの個数を求める問題です。 ごく普通の二分探索の問題です。本来であれば自作の二分探索関数を書いて解くべきなのでしょうけれど、ここは遠慮…