問題1 atcoder.jp 問題タイプ グラフ グラフの問題に慣れるのに良い問題. それぞれの展望台と繋がっている道のグラフを作って、それらを比較する. 気を付けるところ 展望台Nから展望台N'を比較する際に、道がある全ての展望台より自展望台が高い場合のみ、co…

概要 左から文字列を１つずつ確認して、次の文字と同じか、同じではないかを確認する問題. 最終的にはユニークなCharを連結して出力する. 10 aabbbbaaca 答え abaca atcoder.jp 問題タイプ 区間分割・連長圧縮と呼ばれるアルゴリズム. ランレングス圧縮、RLE…

概要 atcoder.jp 問題形式 連想配列 解法の中での重要な要素 Pythonでは、通常のdictとdefaultdictが存在する. 簡単に違いをまとめると: dict keyが存在しない場合、エラーになってしまう. 例えば、dict[key] += 1をした際に、keyがない場合はエラーになるの…

Merge Sort 概要 arrayを二分していって値の比較をしていくSortアルゴリズム 計算量は O(N log(N)). 詳細 www.youtube.com サンプル問題 Kth Largest Element in an Array - LeetCode サンプルコード class Solution: def findKthLargest(self, nums: List[i…

問題 atcoder.jp 公式解説を見ても右側の例が何を言ってるのか理解できない... 解き方 まずは、問題が円形の要素であること。 これは単純に要素を*2するだけなのでわかる。 次に隣り合う要素の和が全体和の÷10と一致するか？というところ。 累積和 累積和が…

問題 atcoder.jp これは解きたかったなぁ、、 素朴に素因数分解を1-NまでやってるとTLEになるのは当たり前なんですが、 割っていく問題ではなく、二乗できるかどうか、なのでi*iの値がNより小さいか同値であればそれはNGの数字としちゃっていいんですよね。 …

問題 atcoder.jp 深く考えすぎて全くわからず！ 意外と単純な問題らしい... こういうのを三角形として捉えなくてよいようです。 下記は多角形として捉えたらよいようです。 解き方 自身の位置から自分の位置、左、左上、上をみて#になっていたらその数をカウ…

考え方 これもほぼほぼ数学的なセンスが必要です Sort済みの場合、0 ≤ P < Q < R < Nに必ずなっている P+Q>Rだけを調べればいい訳は、ソート済みの場合はP<Q<Rに必ずなっている前提のため(1,2,5,8,10,20)、 1,2,5をP,Q,Rとすると、 P(1)+R(5)>Q(2), Q(2)+R(5)>P(1)は必ず満たされる。 この場合、P(1)+Q(2)>R(5)のみ満たされないため、それだけ調</q<rに必ずなっている前提のため(1,2,5,8,10,20)、>…

難題っぽいです。普通に難題です。なにしたらいいのかあんまりよくわかりません。 解説はこちらを見てください。（丸投げw） codility-lessons-jp.blogspot.com import java.util.*; public class Solution { public static void main(String[] args) { Syst…

考え方 苦手な数学の発想問題です。なんでprefix sumのセクションにあるんや...？ もしBが11なら、11 / 2 = 5 11までの数字は: 1,2,3,4,5,6,7,8,9,10,11 2で割れる数字は: 2,4,6,8,10 -> 5 あってます。 もしAが6なら、6 / 2 = 3 6までの数字は: 1,2,3,4,5,6…

考え方 全体の数の合計値 / 全体の数の平均値より、最小の値は2個ずつの平均値、または3個ずつの平均値のどちらかに存在する らしいです。あんまりしっくりきていないので完璧な方ぜひおしえてください。 まあ、一応下記例から読み取れるとしたら、確かに全…

アルゴリズムの一種で、値のithからjthまでの合計値を効率良く取得するために使用する ほぼほぼ累積和と変わらないと思っています 参考 codechacha.com 問題 app.codility.com 問題の英語的にはっきり言って一見では何したらいいのか意味不明でしたw 渡され…

参考: www.geeksforgeeks.org 問題例: ALDS1_3_B: Queue コード JavaでクラスをC/C++の構造体みたいに使うやり方に苦戦した。 import java.util.Scanner; class Main { static int quantum; static int currentElapsedTime; class Data { String processName…

これは結構直感的なソートアルゴリズム。 アルゴリズム概要 単純に、外側はソート済みを意味するループで、 内側は現在のソート済みでないindexから全ての要素を探索して、最小値を見つけてそのindexを取得する 現在の外側ループのindexの要素と最小値index…

バブルソートとバケットソートを勘違いしている日々もありました アルゴリズム概要 1つ前の要素と現在の要素を比べて、1つ前の要素の方が大きければswapしていくソート 計算量 とりあえずバブルソートは安定したソートです 注意 if(a[i] < a[i-1]) {の部分は…

頭ではわかっていても、コードに落とし込むとなると難しいよなあ... アルゴリズム概要 Insertion(挿入)ソートなので、ソート済み部分にぴったり対象値を挿入するソート方法 もう少し具体的に言うと、小さい値を見つけたらそれよりも大きい値の左側にちゃんと…

B - Billiards えっえっ？解説読んでも見ても全く意味不明なんですけど、、 って方他にいないですかね。（いないか） 僕は全くもって意味不明だったのでメモします。 まず、この問題を特には数学2の知識が必要です。 内分点の求め方 詳しくは、下記の動画を…

B - Trapezoid Sum Bが解けなかったよ。。というわけで僕みたいなアホにもわかる解説を書いてみる。 計算量考慮しないといけないけど これは数学の公式を覚えてるか、変動する上限下限に対応できるいもす法を知ってるかじゃないとなので、まあいまのレベルじ…

フィボナッチとかくらいしか、再帰を使ったことないのですが 動的計画法（DP）を勉強中にメモ化再帰、という単語が登場し、こりゃあスゴイ！と思ったのでメモ。 概要 各数字における答えをメモしておく。 再帰関数は同じ値に対する計算を何度も行うので、処…

これはまたどこかで使えそうなので記事化 C - Sum of product of pairs 制約のが <= 105 なので、まあ二重ループは使えません、と。 で、どうしたらいいかが全くわからず、なんか累積和っぽいなーと思いつつも結局わかりませんでした。 以前何度か読んだ下記…

全く持って忘れてましたよね。。 参考 integraldx.info a,b,cの三辺の三角形の場合、 a < b + c, b < a + c, c < a + bが成立していればOK。 かつ、もしaの辺が一番長いとわかっている場合は、a < b + cのみ確認を行えばいいらしい。 問題 atcoder.jp 提出し…

数学？算数の問題ですね。。 単純に下記を覚える [時針]1分ごとに変わる角度: 0.5度 (360/12*60) [分針]1分ごとに変わる角度: 6度 (360/60) double hDegree = (h*60+m)*0.5; double mDegree = m*6; double degree = Math.abs(hDegree-mDegree); 参考 dorilu.…

C - Repsept 一応解説でもCにしてはムズイとなってたのでよしとする（？）ダメだけど、、 下記のmodの世界での規則系に気付けるかどうか。 その世界でもn*10+7してmod kした値は単純にn%kした答えと同じになる 単純にn%kした場合、ループの最大回数を何にし…

C問題が解けるためには避けては通れない道っぽい.... 2進数とか16進数とかすごい嫌いw まずは理解できるまで下記を読みまくるのがいい気がする. 参考 qiita.com qiita.com drken1215.hatenablog.com lovedvoraklayout.hatenablog.com ちなみに、ABC167のC問…

ITパスポート以来ですわ.... ビット探索を勉強するために、まずは2進数の勉強ですw 10進数から2進数 10進数を2で割った余りを求めるだけ。 例えば10であれば、下記のように2でmodしたもので、一番上が一番右の2進数の数となる。 10(10進数) -> 1010(2進数) -…

階乗とは 10! と書いたりするようですが、1~10までの整数値を掛け合わせた値です. 回帰呼び出しで実装 10までの階乗をループなしで求めます。 public class Main172 { static int value = 1; static int sum = 1; public static void main(String[] args) { …

問題 onlinejudge.u-aizu.ac.jp 1 から n までの数の中から、重複無しで３つの数を選びそれらの合計が x となる組み合わせの数を求めるプログラムを作成して下さい。 例えば、1 から 5 までの数から３つを選んでそれらの合計が 9 となる組み合わせは、 1 + 3…

Brute Force（全探索）でガンガン探すよりも、もちろん二分探索法のほうが結果として処理が早くなる可能性があるので、めもめも 二分探索法とは qiita.com binarySearch()とは ほぼ、Collectionsの中身しか見ていないけど、パッとコードを見て二分探索法かな…

atcoder.jp で撃沈でした！ 問題 端的に言うと、数字が与えられるので、それに対応するアルファベットを出力せよ。という問題 例えば、1ならa、27ならaaみたいな感じ。 これも覚えておけば次使えるテクニックなので、めもめも。 アルファベットは26進数であ…

残念、今日のはB問題でさえ無理でした。 ずっと同じ座標にいることがあれば"YES"と出力するもんだと思ってたら永遠に正解しないのでギブアップでした。 atcoder.jp まあこれは単純に追いかけ算だったわけですね... https://www.chugakujuken.com/pdf_data/up…