東京海上日動プログラミングコンテスト 2020に参加しました(AtCoder)
東京海上日動プログラミングコンテスト 2020に参加しました。
結果は上にある通り、初めてレートが下がりました・・・（つらい）
反省点を書きます。
ちなみに、前回のABCの結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
準備
最近いろいろ忙しかったので、ほとんど何もしていないです。
（就活などが忙しいと言い訳させてください・・・）
経過
今回は準備はしていないけど、とりあえず出て、A・B問題までは手堅くいこうと思って出ました。
A問題が簡単だったので1分ほどで解き、B問題にとりかかりました。
しかし、B問題の意味がいまいちわかりません。
問題文を見ても、1秒ごとに更新とも読み取れますし、途中で捕まるとダメとも読み取れます。
（問題設定ガバガバ過ぎやしませんか・・・）
とりあえず、鬼ごっこなので間で捕まってもダメと読んで、提出しました。
そして、C問題にとりかかって開始から30分くらいでB問題が間違っているのに気づきました。
そう、結果を見ずに次の問題に取り組んでしまったんですね。
B問題の結果は１つのテストケースだけがWAとなっていました。
今回は、ここではまってしまいました。
結局解消方法がわからず、C問題を解くことで逆転を目指すも、解けず・・・
開始以来初の大失敗で幕を閉じました。
結局原因は割り算時のキャスト不足です。
なんで気づかなかったんでしょう。
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); long A = sc.nextLong(); long V = sc.nextLong(); long B = sc.nextLong(); long W = sc.nextLong(); long T = sc.nextLong(); long dis = Math.abs(A-B); long speed = V - W; if(speed <= 0) { System.out.println("NO"); }else if((double)dis / speed <= T){ System.out.println("YES"); }else { System.out.println("NO"); } } }
結果
結果は特にいうことはありません。
ただただ、大惨敗です。
正直、記事にするのも迷いました。
というわけで、東京海上日動プログラミングコンテスト 2020の結果でした。
本日のABCで巻き返したいと思います。
ワーシャルフロイド法について
またまたAtCoderの記事です。
Web開発の記事は次回の予定です。
ちなみに前回のABCの結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
ワーシャルフロイド法とは
全頂点の最小の重みの和（最短経路など）を求めるときに使います。
ダイクストラ法と違い、重みに負の値があるときも計算可能です。
計算量はO(V^3)なので、時間はかかります。
ただし、負の閉路（重みの和が負となる閉路）があるときは正しい答えを出せません。
しかし、負の閉路があることの検出は可能です。
説明についてはこちらのサイトがわかりやすいかなと思います。
triple-four.hatenablog.com
どのように解くのか（Javaの場合）
ライブラリを作って以下のサイトに上げました。
github.com
使い方は以下のような感じです。
//重さを格納する配列 long[][] w = new long[N][N]; //大きい値の設定 long INF = 10000000L; //ワーシャルフロイド法用のインスタンスを作成 WF wf = new WF(c, INF); //各重みを設定 for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { c[i][j] = sc.nextLong(); } } //すべての頂点間の最小の重みの和（最短距離）を返す long[][] min_w = wf.getAllDis(); //負の閉路検出(必ずgetAllDisの後で行う) boolean isNegativeCycle = wf.isNegativeCycle();
作ったライブラリを使って２問ほど解いてみました。
1つ目は、AtCoder Beginner Contest 079 D - Wall です。
atcoder.jp
この問題はワーシャルフロイド法を使うことさえわかってしまえば、あとは1と各数字との最小の重みの和を求めるだけです。
このように、最短経路でないときも使えるんですね。
import java.util.Arrays; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int H = sc.nextInt(); int W = sc.nextInt(); long[][] c = new long[10][10]; long INF = 10000000; WF wf = new WF(c, INF); for(int i=0; i<10; i++) { for(int j=0; j<10; j++) { c[i][j] = sc.nextLong(); } } long[][] min_c = wf.getAllDis(); long min_maryoku = 0; int[][] A = new int[H][W]; for(int i=0; i<H; i++) { for(int j=0; j<W; j++) { A[i][j] = sc.nextInt(); if(A[i][j] != -1 && A[i][j] != 1) { min_maryoku += min_c[A[i][j]][1]; } } } System.out.println(min_maryoku); } //ワーシャルフロイド法 public static class WF{ long[][] d; long INF; public WF(long[][] d, long INF) { this.d = d; this.INF = INF; //初期化 for(int i=0; i<d.length; i++) { Arrays.fill(d[i], INF); } //自分自身との距離を0に設定 for(int i=0; i<d.length; i++) { d[i][i] = 0; } } //全頂点間の最短距離(重みに負の値あり)(ワーシャルフロイド法)(O(V^3)) public long[][] getAllDis(){ long[][] new_d = new long[d.length][d.length]; System.arraycopy(d, 0, new_d, 0, d.length); for(int k=0; k<new_d.length; k++) { for(int i=0; i<new_d.length; i++) { for(int j=0; j<new_d.length; j++) { if(new_d[i][k] != INF && new_d[k][j] != INF) { new_d[i][j] = Math.min(new_d[i][j], new_d[i][k]+new_d[k][j]); } } } } return new_d; } //負の閉路検出(O(V)) public boolean isNegativeCycle() { for(int i=0; i<d.length; i++) { if(d[i][i] < 0) { return true; } } return false; } } }
2つ目は、AtCoder Beginner Contest 074 D - Restoring Road Network です。
atcoder.jp
この問題は水色diffです。
水色レベルになってくると、考察が必要になってきます。
各頂点間の最短距離がすでに与えられているので、
ワーシャルフロイド法を使って、
他の頂点を経由した方が距離が短くなる場合は-1、
別の経由地を使って最短距離と同じになる場合はその2点間のエッジを切ればよいです。
この解答ではグラフを使わず、あらかじめ与えられる最短距離をすべて加え、
エッジを切る際は代わりにその2点間の最短距離を引きます。
この時注意するのは、エッジを切った情報を記録しておかないと2種類以上最短経路がある場合種類の数だけ引いてしまうので、エッジを切った情報を記録するようにする点です。
（ここでWAを出しました。）
最終的な解答はこちらです。
import java.util.Arrays; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); long[][] A = new long[N][N]; long ans = 0; for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { A[i][j] = sc.nextLong(); ans += A[i][j]; } } //2点間がつながっているか boolean[][] connected = new boolean[N][N]; for(int i=0; i<N; i++) { Arrays.fill(connected[i], true); } for(int i=0; i<N; i++) { connected[i][i] = false; } for(int k=0; k<N; k++) { for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { //別の経由地を通ったほうが距離が短くなる場合 if(A[i][j] > A[i][k] + A[k][j]) { System.out.println(-1); return; } //別の経由地を通っても最短距離になる場合 else if(connected[i][j] && i != k && j != k && A[i][j] == A[i][k] + A[k][j]) { ans -= A[i][j]; connected[i][j] = false; //2重で引くのを防ぐ } } } } //無向グラフなので2で割る ans /= 2; System.out.println(ans); } }
というわけで、ワーシャルフロイド法についての記事でした。
まだ、ベルマンフォード法と最小全域木問題があるので、そこについても勉強したいと思います。
今週末はABCがないみたいなので、次回のABCまでにこの2つを勉強したいと思います。
ABC169のD問題について【Java】
今回もAtCoderの記事です。
昨日の解けなかったD問題の復習をしました。
昨日のABC169の結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
コンテスト中に出した答え
コンテスト中に出した答えはこちらです。
エラトステネスの篩を応用して解こうとしましたが、素数判定に使う配列の個数がintを超えてしまったため、うまくいきませんでした。(WAです)
import java.util.Arrays; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); long N = sc.nextLong(); int sqrt = (int)Math.sqrt(N); boolean[] isPrime = isPrimeN(sqrt); long ans = 0; for(int i=2; i<=sqrt; i++) { long n = N; if(isPrime[i]) { for(long j=i; j<=N; j*=i) { if(n >= 2 && n % j == 0) { ans++; n /= j; }else break; } } } if(ans == 0 && N >= 2) ans++; System.out.println(ans); } //n以下のすべての数の高速な素数判定(エラトステネスの篩) public static boolean[] isPrimeN(int n) { boolean[] isPrime = new boolean[n+1]; Arrays.fill(isPrime, true); isPrime[0] = false; isPrime[1] = false; //割れる数はsqrt以下 for(int i=2; i<=Math.sqrt(n); i++) { if(isPrime[i]) { for(int j=i*i; j<=n; j+=i) { isPrime[j] = false; } } } return isPrime; } }
修正した結果
Twitterを見てると解法らしきものが1文ほどで書いてあったので、それをもとに自力で修正してみました。
解法としては素因数分解を使い、同じ数のうちは1個たまったらカウントし、次は2個たまったらカウントし・・・という風にカウントするまでにたまる上限の数を1ずつ増やしていきました。
自作の素因数分解用のライブラリでは、最小の約数を返すようになってるので、例えば24の場合は
2, 2, 2, 3
と値を返すので、2が1個たまったら答えを+1、次は２が2個たまったら答えを+1、約数の値が変わったらまた3が1個たまったら答えを+1とし、これを繰り返すことで最後に答えの値を返します。
プログラムは次のような感じです。（もうちょっときれいに書けた気もする）
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); long N = sc.nextLong(); int ans = 0; long n = N; long before_yakusuu; long yakusuu = -1; long count = 0; //指数 long limit = 0; //現在の必要上限(1, 2, 3, ...と増やしていく) while(n >= 2) { before_yakusuu = yakusuu; yakusuu = fact(n); if(yakusuu == -1) { break; } if(yakusuu != before_yakusuu) { count = 1; limit = 0; }else { count++; } if(count > limit) { ans++; limit++; count = 0; } n /= yakusuu; } System.out.println(ans); } //最小の約数を返す(素因数分解用) public static long fact(long n){ if(n < 2) return -1; for(long i=2; i<=Math.sqrt(n); i++) { if(n % i == 0) return i; } return n; } }
というわけで、ABC169のD問題の復習でした。
コンテスト中には、素因数分解を使ったアプローチでは何となくTLEになるのではと思っていましたが、間違いでした。
今回は完全に間違ったアプローチで解いてしまったので、そこから時間内に修正できるように練習を重ねていきたいです。
AtCoder Beginner Contest 169に参加しました！ (ABC169)
AtCoder Beginner Contest 169 (ABC169) に参加しました。
やってしまったな・・・という感じです。
感想を書いていきます。
ちなみに昨日の結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
準備
昨日からの進捗はありません。
これが原因かなという感じです。
経過
A問題はとても簡単だったので、例を試さずに提出してACしました。
B問題ではオーバーフローをし、1WAしてしまいました。
オーバーフローするかもしれないけどまあいいか、と思って提出してしまったのですが、それが仇になりました。
C問題はdoubleの精度の問題だと思って、小数を100倍してから答えを100割ってWAでした。
なぜなんでしょうか。ちょっとわかりません。
結局BigDecimalを使って書き直し、ACしました。
D問題についてはエラトステネスの篩を応用すればできそうだと思いましたが、Nが10^12と大きいので配列だと扱えません。
何を思ったかNのルートまでを調べればいいと勘違いし、WA。
Nのルート以上でも素数があることに気づき、どうにかNまでの素数判定を実装しようとするも間に合いませんでした。
（どうやら素因数分解だったようですね。[23:11追加]）
念のため、B問題とC問題の解答を載せておきます。（Javaですけど）
B問題
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); long[] A = new long[N]; for(int i=0; i<N; i++) { A[i] = sc.nextLong(); if(A[i] == 0) { System.out.println(0); return; } } long ans = A[0]; for(int i=1; i<N; i++) { if(A[i] <= (1000000000000000000L / ans)) { ans *= A[i]; }else { System.out.println(-1); return; } } System.out.println(ans); } }
C問題
import java.math.BigDecimal; import java.math.RoundingMode; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); String A = sc.next(); String B = sc.next(); BigDecimal bA = new BigDecimal(A); BigDecimal bB = new BigDecimal(B); BigDecimal ans = bA.multiply(bB); ans = ans.setScale(0, RoundingMode.DOWN); System.out.println(ans); } }
結果
A～Cの３完です。
今回は痛いところを突く問題が多く、苦手なタイプの問題でした。
自分の勉強の甘さを強く感じました。
D問題は解けそうで解けないのがすごくもやもやしますね。
しっかりと復習したいと思います。
というわけで、ABC169の結果でした。
自分の甘さを感じて大反省という感じです。
今回のD問題はどの色の難易度かはわかりませんが、解くべき問題だったような気がするので、次回までには解けるようにしていきたいです。
NOMURA プログラミングコンテスト 2020に参加しました！(AtCoder)
NOMURA プログラミングコンテスト 2020に参加しました。
今回はARCクラスということでC問題以降が難しかったです。
感想を書いていきたいと思います。
ちなみに、前回のABC168の結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
準備
前回のコンテスト（もう2週間前になりますね）から準備してきたことはこちらです。
- ABC167, ABC168の解けなかったD問題の見直し
- ワーシャルフロイド法（の一部）
ワーシャルフロイド法についてはもう少し問題を解いて、近いうちに記事にします。
経過
今回は問題の配点が100-200-600-700-900-1000だったので、C問題以降はかなり難しいと予想し、A・B問題の早解きを狙いました。
A問題については問題の意味が最初わからなかったものの、入力例を見て意味を理解し、3分ほどで解きました。
B問題については解法を考えることに時間がかかりましたが、冷静に考えれば?にDを入れればいいことに気づき、比較的時間をかけずに解けました。
（?Dの時、PDとしてもDDとしても同じように博士・PD 指数が1増えるため）
A・B問題でトータル9分ほどで、良いスピードで解けたんじゃないかと思います。
念のため、私の答えを載せておきます。（Javaですけど）
A問題
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int h1 = sc.nextInt(); int m1 = sc.nextInt(); int h2 = sc.nextInt(); int m2 = sc.nextInt(); int K = sc.nextInt(); int hm1 = h1 * 60 + m1; int hm2 = h2 * 60 + m2; System.out.println(hm2-hm1-K); } }
B問題
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); String T = sc.next(); T = T.replace("?", "D"); System.out.println(T); } }
結果
A・Bの2完でした。
過去最高パフォーマンスです！
緑になるためにこれからも頑張ります。
というわけで、NOMURA プログラミングコンテスト 2020の結果でした。
明日もABCがあるので、この調子で頑張りたいです。
Web開発の勉強５- サーバーサイドプログラミング入門３
お久しぶりの投稿となってしまいました。
今回はWeb開発の勉強に関する記事です。
このシリーズの前回の記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
内容
教材としては「N予備校」の「 プログラミング入門Webアプリコース 」を使ってます。
www.nnn.ed.nico
前回、1年間キャンペーンに申し込んでキャンペーンが適用されるのかわからないと書きましたが、無事適用されたみたいです。
N高の授業システム、N予備校の無料キャンペーンに参加頂いた皆様に「N予備校生」の権限を付与しました。設定から確認ください。応募条件を満たしているのに付与されていない方は記載事項の不備の可能性があります。
— Ｎ高等学校（学校法人角川ドワンゴ学園） (@nhigh_info) May 28, 2020
名前、Twitter ID、N予備校IDを記載して問い合わせください→https://t.co/X3oN02Vg6x
ちゃんと「N予備校生」になってます。
こんなに充実した教材を1年間も無料にしていただき、本当にありがとうございます。
これからもN予備校を使って勉強に励みます。
内容のほうですが、今回はこの3章の27. デザインの改善 まで終わりました。
具体的な内容としては次のような感じです。
- SQLを使わずデータベース（PostgreSQL）を使う方法（sequelize）
- テンプレートCSSの利用（Bootstrap）
内容盛りだくさんです。
ダイクストラ法について
今回はAtCoderの記事です。
ちなみに、昨日AGCがあったのですが、ちょっとだけ問題を覗いて解けそうになかったので早めに退散しました。
次回からはratedの対象が2000～になるみたいですね。
あれだけ難しい問題がそろっているので、対象を絞るのも仕方のないことなのかなと思います。
（昨日は1問も解けなくてもレートが上がった方がそこそこいたようですし）
次回のNOMURA プログラミングコンテスト 2020 (ARCクラス) には参加する予定です。
さて、今回はダイクストラ法について勉強しました。
ダイクストラ法とは
最短経路を求めるアルゴリズムです。
BFSとの違いは、BFSはグラフの辺の重みが等しい時にしか使えませんが、ダイクストラ法は辺の重みが正であればそれぞれ重みが違っても使うことができます。
BFSは計算量がO(V+E)で解けますが、ダイクストラ法はO(ElogV)です。
基本的にBFSで解ける場合はBFSで解くという感じですね。
このアルゴリズムの考え方は以下のサイトがわかりやすかったです。
https://nw.tsuda.ac.jp/lec/dijkstra/
どのように解くのか（Javaの場合）
ライブラリを作ってGithubに上げました。
github.com
このライブラリの使い方について簡単に説明します。
まずグラフを作ってそれを引数としてDijkstraクラスのインスタンスを作ります。
次に、問題文で求められているものに必要なメソッドを呼び出します。
例えば、下のような感じです。
//無向グラフの作成 UDGraph g = new UDGraph(n); //インスタンスを生成 Dijkstra dk = new Dijkstra(g); //メソッドを呼び出す（この場合、最短経路を返す） Deque<Integer> path = dk.getMinPath(a, b);
作ったライブラリを使って、1つ問題を解いてみました。
解いた問題は、JOI 2008 予選 6 - 船旅 です。
atcoder.jp
自作のライブラリの部分はスペースの都合上、省きました。
import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); UDGraph g = new UDGraph(n); Dijkstra dk = new Dijkstra(g); while(sc.hasNext()) { int num = sc.nextInt(); if(num == 0) { int a = sc.nextInt(); int b = sc.nextInt(); long cost = dk.getMinWeight(a, b); if(cost == Long.MAX_VALUE) System.out.println(-1); else System.out.println(cost); }else if(num == 1) { int c = sc.nextInt(); int d = sc.nextInt(); long e = sc.nextLong(); g.addEdge(c, d, e); } } } //ここから下は自作のライブラリ }
というわけで、ダイクストラ法についてでした。
久しぶりに週末にAtCoderのコンテストがないので変な気分です。
（慣れって怖いですよね。）
来週の週末はNOMURAさんのコンテストと、ABCがあるのでそこまでに練習量を増やせて行けたらなと思います。
Web開発の勉強４- サーバーサイドプログラミング入門２
今回はWeb開発の勉強の記事です。
第4回も前回と引き続き、Node.jsを用いたサーバーサイドプログラミングの勉強です。
このシリーズの前回の記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
内容
教材としては「N予備校」の「 プログラミング入門Webアプリコース 」を使ってます。
www.nnn.ed.nico
5月31日まで無料です。
追加で応募者全員に1年間無料にするキャンペーンをしていたのですが、もう終わってしまっています。
ちなみに、私は申し込んだのですが、キャンペーンが適用される場合、連絡は来るのでしょうか・・・
期限後も連絡がないので、6月1日からキャンペーンが適用されるのか現時点ではわかりません。
今回はこの3章の18. 認証で利用者を制限する まで終わりました。
内容としては次のような感じです。
- HTTPサーバーとログ保存
- フォームを使ったGETとPOSTの場合の処理
- Pugを使った動的なフォームの作成
- Herokuを使ったWebサービスのデプロイ
いよいよ本格的にWeb開発という感じですね。
中身としては楽しくなってきました。
ちなみに、VirtualBoxでSimlinkエラーが出た時の対処法は以下の記事が役に立ちました。
var.blog.jp
感想
入門編にもかかわらず、結構重いなという感想は変わりません。
ただ、この入門編が終われば、Web開発やってますと言っても恥ずかしくないレベルの知識は身につくと思います。
個人的には、3章が終わった時点で普通のWebアプリが作れそうなので、3章が終わったら一度自分で何か作ってみようかなと思います。
というわけで、Web開発の勉強の記事でした。
まだ、3章はあと半分ほどありますが、着実に進めていきたいと思います。
3章が5月末までに終わればいいかな・・・
ABC168のD問題で解法が同じなのにTLEしてしまったわけ【Java】
今回はABC168の復習をしました。
先日のABC168のD問題で、解法が全く同じにもかかわらずTLEを出し続けて沼にはまりました。
それが悔しかったので、この原因を調べてみました。
ちなみにABC168の結果がこちらです。
developer-bpeldi2oerkd8.hatenablog.com
コンテスト中に出した答え
コンテスト中に出した答えはこちらです。(長いですけど)
ちゃんとBFSを使って解いているにも関わらず、TLEしました。
import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; import java.util.Queue; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); Graph g = new Graph(N); for(int i=0; i<M; i++) { int A = sc.nextInt(); int B = sc.nextInt(); g.addEdge(g.getNode(A), g.getNode(B)); g.addEdge(g.getNode(B), g.getNode(A)); } boolean[] visited = new boolean[N]; Arrays.fill(visited, false); //BFS Queue<Node> queue = new ArrayDeque<>(); queue.add(g.getNode(1)); while(!queue.isEmpty()) { Node n = queue.poll(); //訪問済み visited[n.value-1] = true; for(Edge edge : n.edges) { Node node = edge.to; if(!queue.contains(node) && !visited[node.value-1]) { queue.add(node); if(node.root != null) { System.out.println("No"); return; }else { node.root = n; } } } } System.out.println("Yes"); for(int i=2; i<=N; i++) { System.out.println(g.getNode(i).root.value); } } //一般的なグラフ public static class Graph{ int n; Map<Integer, Node> nodes; //(ノード番号, ノード) //1~Nまでをもつグラフ public Graph(int n) { this.n = n; nodes = new HashMap<>(n); for(int i=0; i<n; i++) { nodes.put(i+1, new Node()); } } public Graph(int n, int[] values) { this.n = n; nodes = new HashMap<>(n); for(int i=0; i<n; i++) { nodes.put(values[i], new Node(values[i])); } } public Node getNode(int node_n) { //ノード番号を指定してノードを取得 return nodes.get(node_n); } public void addEdge(Node from, Node to) { //重みが1のグラフの場合(重みが均等な場合にも場合によっては使える) from.edges.add(new Edge(to, 1)); } public void addEdge(Node from, Node to, long weight) { //エッジの重みが異なる場合 from.edges.add(new Edge(to, weight)); } public void removeEdge(Node from, Node to) { //指定したノード間のエッジを削除 from.edges.remove(new Edge(to, 1)); } } public static int count = 0; //ノードを表すクラス public static class Node{ int value; List<Edge> edges; boolean visited = false; Node root; public Node(){ value = count+1; edges = new ArrayList<Edge>(); count++; } public Node(int value) { this.value = value; edges = new ArrayList<Edge>(); } @Override public boolean equals(Object obj) { if(obj instanceof Node) { Node n = (Node)obj; if(this.value == n.value) return true; else return false; } return false; } @Override public int hashCode() { return Objects.hash(this.value); } } //エッジを表すクラス public static class Edge{ Node to; //行き先 long weight; //重み public Edge(Node to, long weight) { this.to = to; this.weight = weight; } @Override public boolean equals(Object obj) { if(obj instanceof Edge) { Edge e = (Edge)obj; if(this.to.equals(e.to)) return true; else return false; } return false; } @Override public int hashCode() { return Objects.hash(this.to); } } }
原因の分析
TLEになった原因をJavaの実行時間を測るSystem.nanoTimeを使って地道に調べました。
すると、意外にも自作のライブラリのほうではなく、BFSの実装部分のほうに原因があるとわかってきました。
（自作のライブラリが原因だと思ってかなりの時間を使ってしまったのは内緒です。）
さらに絞り込んでいくと、どうやらif(!queue.contains(node) && !visited[node.value-1])で時間を消費していることがわかってきました。
どう考えても、!visited[node.value-1]には時間がかかるはずがないので、（配列だからO(1)でとってこれるはず）
原因は!queue.contains(node)にあると推測しました。
TLEになった原因
結局TLEになった原因は、queueに多くの要素が含まれるようになったとき、queue.containsに多くの時間がかかってしまうことでした。
queue.containsメソッドの内部処理はよく知りませんが、要素を1つずつ確認していくのであればO(N)の時間がかかってしまうので、ここで時間がかかっていたのだと思います。
対処法としては、queueに加えるときに、visited=trueとして、訪問済みにしてしまうことです。
こうすれば、queueに加えるときに訪問済みかどうか調べるだけでいいので、O(1)の時間しかかかりません。
修正したプログラムはこちらです。
（自作のライブラリの部分は同じなので省略しています。）
import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; import java.util.Queue; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); Graph g = new Graph(N); for(int i=0; i<M; i++) { int A = sc.nextInt(); int B = sc.nextInt(); g.addEdge(g.getNode(A), g.getNode(B)); g.addEdge(g.getNode(B), g.getNode(A)); } boolean[] visited = new boolean[N]; Arrays.fill(visited, false); //BFS Queue<Node> queue = new ArrayDeque<>(); queue.add(g.getNode(1)); visited[0] = true; while(!queue.isEmpty()) { Node n = queue.poll(); for(Edge edge : n.edges) { Node node = edge.to; if(!visited[node.value-1]) { queue.add(node); //queueに加えたときに訪問済みにしてしまう visited[node.value-1] = true; if(node.root != null) { System.out.println("No"); return; }else { node.root = n; } } } } System.out.println("Yes"); for(int i=2; i<=N; i++) { System.out.println(g.getNode(i).root.value); } }
さらに、これだと制限時間ギリギリなので、入出力を変えてみました。
入力にネットで拾ってきたFastScannerを使ったバージョンと、それに加え、出力をPrintWriterにしたバージョンの実行時間を計ってみた結果がこちらです。
上から、
FastScanner+PrintWriter (563ms)
FastScannerのみ (1099ms)
そのまま (1648ms)
です。
いや、すごい威力ですね。
今回のように、入出力が長い行になる場合は迷わずFastScanner, PrintWriterを使ったほうがよさそうです。
というわけで、ABC168のD問題の復習でした。
BFSは知っていたのに時間内にACできなかったのは悔しいですが、結果的に勉強になりました。
BFSのテンプレを今回の形に修正しておきます。
次こそは、４完できるように頑張ります。
AtCoder Beginner Contest 168に参加しました！ (ABC168)
AtCoder Beginner Contest 168 (ABC168) に参加しました。
やはり演習不足を強く実感しました・・・。
感想を書いていきます。
ちなみに、前回の結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
準備
前回から勉強したのは次の1つです。
- 累積和
やはりどう考えても勉強不足ですね。
演習量の不足も強く感じました。
経過
スタート後、いつもの通りA・B問題をサクッと解き、C問題に進みました。
C問題は余弦定理を使う問題でしたね。
数学は苦手ではないので、20分ほどで解きました。
提出した回答がこちらです。
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int A = sc.nextInt(); int B = sc.nextInt(); int H = sc.nextInt(); int M = sc.nextInt(); int pass_time = H*60 + M; double digA = (0.5 * (double)pass_time) % 360; double digB = (6 * pass_time) % 360; double C = Math.sqrt(A*A + B*B -2*A*B*Math.cos(Math.toRadians(Math.abs(digA-digB)))); System.out.println(C); } }
cosの中身がラジアンなことを忘れて、ちょっと詰まりましたが、ノーミスでここは通しました。
問題はD問題でグラフの問題と最短経路なのでBFSだなと思い、実装を進めました。
ただ、まずNoを出す条件がわからなかったので、ここでまず詰まりました。
考えた結果、閉路と同じ感じでやればいいのかと思い、やってみたところ間違ってはいないようでした。
ただ、要素の数が大きいとき、TLEが出てしまい、ここを解消できずにコンテストが終わりました。
なぜ、TLEが出ているのか理由がわかっていません。
念のため、提出したものを載せます。
import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; import java.util.Queue; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); Graph g = new Graph(N); for(int i=0; i<M; i++) { int A = sc.nextInt(); int B = sc.nextInt(); g.addEdge(g.getNode(A), g.getNode(B)); g.addEdge(g.getNode(B), g.getNode(A)); } boolean[] visited = new boolean[N]; Arrays.fill(visited, false); //BFS Queue<Node> queue = new ArrayDeque<>(); queue.add(g.getNode(1)); while(!queue.isEmpty()) { Node n = queue.poll(); //訪問済み visited[n.value-1] = true; for(Edge edge : n.edges) { Node node = edge.to; if(!queue.contains(node) && !visited[node.value-1]) { queue.add(node); if(node.root != null) { System.out.println("No"); return; }else { node.root = n; } } } } System.out.println("Yes"); for(int i=2; i<=N; i++) { System.out.println(g.getNode(i).root.value); } } //一般的なグラフ public static class Graph{ int n; Map<Integer, Node> nodes; //(ノード番号, ノード) //1~Nまでをもつグラフ public Graph(int n) { this.n = n; nodes = new HashMap<>(n); for(int i=0; i<n; i++) { nodes.put(i+1, new Node()); } } public Graph(int n, int[] values) { this.n = n; nodes = new HashMap<>(n); for(int i=0; i<n; i++) { nodes.put(values[i], new Node(values[i])); } } public Node getNode(int node_n) { //ノード番号を指定してノードを取得 return nodes.get(node_n); } public void addEdge(Node from, Node to) { //重みが1のグラフの場合(重みが均等な場合にも場合によっては使える) from.edges.add(new Edge(to, 1)); } public void addEdge(Node from, Node to, long weight) { //エッジの重みが異なる場合 from.edges.add(new Edge(to, weight)); } public void removeEdge(Node from, Node to) { //指定したノード間のエッジを削除 from.edges.remove(new Edge(to, 1)); } } public static int count = 0; //ノードを表すクラス public static class Node{ int value; List<Edge> edges; boolean visited = false; Node root; public Node(){ value = count+1; edges = new ArrayList<Edge>(); count++; } public Node(int value) { this.value = value; edges = new ArrayList<Edge>(); } @Override public boolean equals(Object obj) { if(obj instanceof Node) { Node n = (Node)obj; if(this.value == n.value) return true; else return false; } return false; } @Override public int hashCode() { return Objects.hash(this.value); } } //エッジを表すクラス public static class Edge{ Node to; //行き先 long weight; //重み public Edge(Node to, long weight) { this.to = to; this.weight = weight; } @Override public boolean equals(Object obj) { if(obj instanceof Edge) { Edge e = (Edge)obj; if(this.to.equals(e.to)) return true; else return false; } return false; } @Override public int hashCode() { return Objects.hash(this.to); } } }
結果
A～Cの３完でした。
やはり、D問題が鬼門で、演習量がまだ足りてないなと感じました。
このままだと緑まで遠いので、もっと頑張ります。
というわけで、ABC168の結果でした。
やはり演習量を増やすことが大事だと思ったので、次回までには演習量を増やしたいと思います。
累積和について
AtCoderの記事です。
今回は累積和について学習しました。
前回のABCの結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
なかなか思うように進まないことも多いですが、焦らず着実に進めていきます。
累積和とは
累積和とは、その名の通り、配列などで初めの値からそこまでの和を記録するものです。
使い方としては、ある区間の和を複数回求める必要があるときに使います。
これを行うと前処理にO(N)かかりますが、値を取り出すときはO(1)で取り出せるので、計算量の削減ができます。
どのように解くのか（Javaの場合）
基本的には累積和を格納する用の配列を用意し、あらかじめ累積和を格納します。
このとき、配列の大きさはN+1にしないといけないことに注意が必要です。
大まかなテンプレは次の通りです。
//前処理 int[] a = new int[n]; int[] sum = new int[n+1]; sum[0] = 0; for(int i=0; i<n; i++) { a[i] = sc.nextInt(); sum[i+1] = sum[i] + a[i]; } //最大値を求める int max = 0; for(int i=1; i<=n-k+1; i++) { //取り出し int s = sum[i+k-1] - sum[i-1]; max = Math.max(max, s); } //処理
テンプレは正直問題によって違うので難しいですね。
これを応用した2次元累積和もあります。
実際に問題を２つ解いてみました。
１つめは AGC023のA問題 Zero-Sum Ranges です。
atcoder.jp
解法は分かったのですが、nCrの求め方をライブラリで求めようとしてはまりました。
今回はr=2なので、公式通りに計算すればエラーなく通ります。
import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); long[] sum = new long[N+1]; int max = 0; sum[0] = 0; Map<Long, Integer> count = new HashMap<>(); count.put(0L, 1); for(int i=1; i<=N; i++) { sum[i] = sum[i-1] + sc.nextLong(); if(count.containsKey(sum[i])) { int new_c = count.get(sum[i])+1; count.put(sum[i], new_c); max = Math.max(max, new_c); } else { count.put(sum[i], 1); max = Math.max(max, 1); } } long ans = 0; for(int value : count.values()) { ans += (long)value * (value-1) / 2; } System.out.println(ans); } }
もう1つは、2次元累積和の問題で、ABC005のD問題 おいしいたこ焼きの焼き方 です。
atcoder.jp
やはり難しい。
水色diffということもあってか、一筋縄ではいきません。
問題の意味を間違えてとらえていたのと、最大値の更新の式を間違え、かなりの時間格闘しました。
import java.util.Arrays; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[][] D = new int[N][N]; int[][] sum = new int[N+1][N+1]; sum[0][0] = 0; sum[0][1] = 0; sum[1][0] = 0; //2次元累積和 for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { D[i][j] = sc.nextInt(); sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + D[i][j]; } } //面積がN*N以下のたこ焼きの美味しさの合計の最大値 int[] delis = new int[N*N+1]; Arrays.fill(delis, 0); for(int i=1; i<=N; i++) { for(int j=1; j<=N; j++) { int max = 0; int area = i * j; for(int k=0; k<=N-i; k++) { for(int l=0; l<=N-j; l++) { int deli = sum[k+i][l+j] - sum[k+i][l] - sum[k][l+j] + sum[k][l]; max = Math.max(max, deli); } } delis[area] = Math.max(delis[area], max); //面積がarea以上の値について最大値を更新 for(int k=area+1; k<=N*N; k++) { delis[k] = Math.max(delis[k], delis[area]); } } } int Q = sc.nextInt(); int[] ans = new int[Q]; for(int i=0; i<Q; i++) { int P = sc.nextInt(); ans[i] = delis[P]; } for(int i=0; i<Q; i++) { System.out.println(ans[i]); } } }
ということで、累積和についてでした。
2次元累積和についてはまだ練習が必要ですね。
いもす法やしゃくとり法についてはまた今度やります。
このあと、21:00からABCがあるので、頑張ります。
Web開発の勉強３- サーバーサイドプログラミング入門１
お久しぶりのWeb開発の記事です。
前回からだいぶ空いてしまいましたが、
第3回はサーバーサイドプログラミング入門ということで、
いよいよNode.jsを使った開発に取り組みました。
このシリーズの前回の記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
内容
前回に引き続き、教材としては「N予備校」の「 プログラミング入門Webアプリコース 」を使ってます。
5月末までは無料ですが、そこからは有料になってしまいます。
www.nnn.ed.nico
ただ、5月20日までのキャンペーンとして、
TwitterでフォローとRTをすると、
全員が1年間無料になるキャンペーンをやっているらしいです。
私もこの後やる予定です。
（念のためですが、これはステマとかではなく、親切心で紹介しています。）
今回はこの3章の11. 例外処理まで終わりました。
内容としては、次のような感じです。
- Node.jsの使い方
- yarnについて
- Slackのボット開発
やはり、自分の作ったプログラムが実際に動くと感動しますね。
結構バグがでたり、エラーが出たりして大変だったのですが、何とか形になりました。
感想
結構重いですね。
入門だからとなめてかかると、結構驚きます。
ただ、中身としては濃いですね。
今まで何となくの知識だったJSONが出てきたとき、
なるほどJavascriptのオブジェクトだからあの形式なんだ、
と発見がありました。
（知ってる方からすれば、何を今更と思うでしょうが）
進みが遅いので、もう少しスピードアップしないとやばいですね。
というわけで、Web開発の記事でした。
やはり、yarn周りでエラーが頻繁に出るのが謎ですね。
再インストールで治ることも多いのですが、原因がよくわかりません。
スピードを上げるため、1日の目標を決めて頑張りたいと思います。
AtCoder Beginner Contest 167 (ABC167) に参加しました！
AtCoder Beginner Contest 167 (ABC167) に参加しました。
うーん、ちょっと悔しいですね。
感想を書いていきます。
ちなみに、前回の結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
経過
今回もスタートがスムーズでした。
（AtCoder社さんありがとうございます。）
A・B問題についてはスムーズに解けました。
C問題はちょっと時間がかかりました。(40分くらい)
見た感じ、重み付きナップザック問題かなと思ったのですが、まだやってないのでやばいなと思いました。
ただ、どこかのサイトでC問題までは全探索で何とかなるという風に書いてあったのを思い出し、なんとかbit全探索で通しました。
そのコードがこちらです。（汚いかもしれませんが）
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int X = sc.nextInt(); int[] C = new int[N]; int[][] A = new int[N][M]; long C_sum = 0; long[] A_sum = new long[M]; for(int i=0; i<N; i++) { C[i] = sc.nextInt(); C_sum += C[i]; for(int j=0; j<M; j++) { A[i][j] = sc.nextInt(); A_sum[j] += A[i][j]; } } //すべて選ぶ for(int i=0; i<M; i++) { if(A_sum[i] < X) { System.out.println(-1); return; } } long ans = C_sum; for(int i=0; i<(1<<N); i++) { long sum = C_sum; long[] Ai_sum = new long[M]; System.arraycopy(A_sum, 0, Ai_sum, 0, A_sum.length); for(int j=0; j<N; j++) { //選択しない if((1 & (i >> j)) == 0) { sum -= C[j]; for(int k=0; k<M; k++) { Ai_sum[k] -= A[j][k]; } } } boolean ok = true; for(int j=0; j<M; j++) { if(Ai_sum[j] < X) { ok = false; break; } } // System.out.println("ans: " + ans); if(ok) { ans = Math.min(ans, sum); // System.out.println("ans_change: " + ans); } } System.out.println(ans); } }
D問題は、そのまま順にたどっていくとTLEになるのは見えていたので、loopを作り、loopの余りをとることで計算時間を短縮しようとしましたが、TLE・・・。
原因は今の段階ではわかっていません。
この後、解説を見たいと思います。
結果
A~Cまでの3完です。
正直悔しいですね。
まだまだ、演習量が足りないので、増やせて行けたらと思います。
というわけで、ABC167の結果でした。
これからも引き続き、勉強を頑張っていきます。
素数について
お久しぶりとなってしまいました。
今回もAtCoderの記事です。
Web開発のほうはもう少しで記事として書けるくらいの内容までいくので、しばしお待ちください。
ちなみに、前回のABCの結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
どのように解くのか（Javaの場合）
自作のライブラリを作り、それを利用する形です。
Javaですが、自分のライブラリはここに置いたので、よかったら参考にしてください。
（バグがあったらすみません。）
github.com
このライブラリを使って、実際に問題を解いてみました。
解いた問題はABC084のD問題 2017-like Number です。
atcoder.jp
高速な素数判定にエラトステネスの篩（ふるい）を使います。
また、累積和も使わないとおそらくTLEします。
（累積和についてはまた今度記事にします。）
import java.util.Arrays; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); boolean[] isPrime = isPrimeN(100000); int[] sum = new int[100001]; sum[0] = 0; for(int i=1; i<=100000; i+=2) { if(like2017(i, isPrime)) sum[i] = sum[i-1] + 1; else sum[i] = sum[i-1]; sum[i+1] = sum[i]; } int Q = sc.nextInt(); for(int i=0; i<Q; i++) { int l = sc.nextInt(); int r = sc.nextInt(); System.out.println(sum[r]-sum[l-1]); } } public static boolean like2017(int n, boolean[] isPrime) { if(n % 2 == 0) return false; if(isPrime[n] && isPrime[(n+1)/2]) return true; else return false; } //n以下のすべての数の高速な素数判定(エラトステネスの篩) public static boolean[] isPrimeN(int n) { boolean[] isPrime = new boolean[n+1]; Arrays.fill(isPrime, true); isPrime[0] = false; isPrime[1] = false; int sqrt = (int)Math.sqrt(n); //割れる数はsqrt以下 for(int i=2; i<=sqrt; i++) { if(isPrime[i]) { for(int j=i*i; j<=n; j+=i) { isPrime[j] = false; } } } return isPrime; } }
これは緑diffですが、やはり緑くらいになってくると、複数の知識を組み合わせた問題が多いですね。
あと、あまり関係ないんですが、Arrays.fillなんて便利なものがあったんですね・・・。
今度から使っていきたいと思います。
というわけで、素数についての記事でした。
本日もABCがあるので、頑張りたいと思います。
Web開発についての記事は次回か次々回には記事にしたいと思います。
AtCoderの茶色になるまでにやったこと 【Java】
先日のAtCoder Beginner Contest 166 (ABC166)で茶色になりました！
茶色を達成したときの結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
天才は見向きもしない色なのですが、我々凡人にとっては、茶色になるのは意外と大変です。
（どのくらい勉強するのか目安がわかりませんよね）
私も茶色くらいだったらすぐ行けるだろ、と思っていたのですが、結局達成するまでに10回かかってしまいました。
おそらく、もっとかかる方はかかると思います。
今回は備忘録として、茶色になるまでにやったことを書きたいと思います。
茶色になるまでに停滞している方、これから茶色になるために勉強しようとしている方の参考に少しでもなれば幸いです。
AtCoderの常識を覚える
ある程度、AtCoderをやっていると自然に覚えていくものなのですが、AtCoder界隈で常識とされていることがそこそこの量あります。
まずは、AtCoderに何回か参加して、こういった常識を知ることが大切だと思います。
ぱっと思いついた常識はこんな感じです。
- コンテストに積極的に参加する（特に、初心者のうちはAtCoder Beginner Contest (ABC) だけ参加すればよい）
- A問題から順に解いていく（ただし、回によっては難易度が入れ替わっていることがあるので、わからなければ1つ先の問題も見る）
- 必ず、自分のパソコンに開発環境を用意する（ブラウザ上だとどうしても速度が遅いので）
- 自分にプログラミングの基礎能力が身についていない場合は、もう少し勉強してから参加する（ガチのプログラミング初心者は周りのレベルが高すぎて、普通に心が折れます）
3つ目については長くなるので、次の項目を見てください。
4つ目については、あまりネットで言われていませんが、AtCoderは正直ガチの初心者向けではないことです。
回にもよりますが、A・B問題がスラスラと解けるレベルでないと挫折してしまうと思うので、PaizaやProgateなどである程度力をつけてから参加したほうがいいかもしれないです。
paiza.jp
自分のパソコンに開発環境を構築する
何回かコンテストに参加すると、必ず通る道だと思います。
やはりAtCoderでは速さを競うので、ブラウザ上では遅いと感じます。
なので、必然的に自分のパソコン上に開発環境が必要になってきます。
これは、メソッドや変数などを自動で補完してくれ、よく使う処理も便利なコマンドで補完してくれます。
ちなみに、Eclipseはこちらのサイトでダウンロードできます。
mergedoc.osdn.jp
こちらのサイトの最新版のJava版のFull Editionをダウンロードすれば大丈夫です。
インストール方法、使い方などはこちらのサイトが参考になります。
www.sejuku.net
他にも、AtCoderで人気なC++やPythonでも使える環境として、Visual Studio Code (VS Code) があります。（人気ですね）
azure.microsoft.com
AtCoderで必要な知識をつける
ここからは、よく他の方も紹介されているアルゴリズムやデータ構造、計算量に関することです。
やはり、色を変えるためにはこれらの知識が不可欠だと感じます。（私も今勉強中です）
こちらのサイトが非常にわかりやすいです。
qiita.com
こちらのサイトにあるように、基本的な文法に加え、まず全探索になれることから始まります。
あと、計算量に関する知識も必要です。
ただ、現段階では私もそこまで詳しくなく、茶色の段階ではAtCoderで時間制限に間に合うのは回以下という知識さえあればいいと思います。
そして、ここまで終わったら、さらにSetやMapなどの標準ライブラリの知識と使い方、二分探索などの他のアルゴリズムの知識をつけていきます。
こちらのサイトを参考に勉強しています。
qiita.com
このようにしていると、いつの間にか茶色に到達しているはずです。
（ちなみに、茶色に到達するまで平均10回といわれているので、あきらめずにコンテストに参加し続けるのも大切だと思います。）
というわけで、AtCoderで茶色になるまでにやったことを紹介させていただきました。
まだ、ブログ経験が浅いもので、分かりにくいところがあるかと思いますが、そこのところは見逃してください。
この記事が茶色を目指している方の参考に少しでもなれば嬉しいです。
これからも、AtCoderの勉強を続けていくつもりなので、もしよかったら読者になっていただけると嬉しいです。
（ツイート・はてなブックマークなどもしていただけると嬉しいです。）
