前に解いたような気がするけど忘れてしまってたのでメモ 解いていた問題 atcoder.jp 解法メモ 面積が記載されるので、i * j = n となるi, jの組み合わせはnの約数のいずれか 約数を列挙し、i+jが最小になる組み合わせを探す n <= 1012なので√nまで探索する約…

覚えてなかったのでメモ 解いていた問題 atcoder.jp 解法メモ (y3 - y1) / (x3 - x1) = (y2 - y1) / (x2 - x1) で判定ができる(参考リンクより) 0除算が発生しないように、(y3 - y1) * (x2 - x1) = (y2 - y1) * (x3 - x1)と式変形するとよい(解説より)。なる…

以前解いた似た問題*1の別アプローチがあったためメモ 解いていた問題 atcoder.jp 解法メモ 組み合わせの計算を愚直に行ってしまうと、今回の制約では200!というかなり大きな数字になってしまうため、Long型では正しく計算できない BigDecimal型で扱ってあげ…

題の通りです。 BigQuery は、GoogleSQL とレガシー SQL の 2 つの SQL 言語をサポートしています。*1 とのことなのですが、GoogleSQLの方だとPI()が実装されていないようで、円周率を使った計算で少し手間取ったためメモを残します。 PIを代替する方法 ACOS…

覚えてなかったのでメモ 解いていた問題 atcoder.jp 解法メモ 3点の座標から三角形の面積を求める 3点(x1, y1), (x2, y2), (x3, y3)の面積は↓のような計算式になる 1.0 / 2.0 * ((x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3)).absoluteValue 3点が直線の…

一応メモ 解いていた問題 atcoder.jp 解法メモ ユークリッドの互除法で計算する 実装メモ AtCoder 版！マスター・オブ・整数 (最大公約数編) - Qiitaを参考にKotlinで実装した ※解説（https://img.atcoder.jp/abc162/editorial.pdf）にも実装例(再帰/非再帰)…

一応準備しておこうかと思って試作。あまりちゃんと分かってないので詳細理解は追って・・・ 解いていた問題 atcoder.jp 解法メモ 二分探索する Kotlin(Java)のbinarySearchではリスト内に同値がある場合に返る値が保証されない*1*2ため、lower_boundのよう…

単純なprintだとTLEするケースに初めて遭遇したのでメモ 解いていた問題 atcoder.jp 解法メモ setとかを使って上手いこと状態を管理 私はバケットで解いてました (考察的な部分は解説参照ということで) Editorial - AtCoder Beginner Contest 294 そこまで遅…

Union-Findのお勉強をしました。 解いていた問題 atcoder.jp 解法メモ ロープの両端をノードとして、そこに最初からリンクが貼ってあるものとして考えればよい ロープの組を作っていく方法はいくつかあるけど、Union-Findでサクっと解きたい Union-Findにつ…

サクっと済ませられる方法を見つけられたのでメモ 解いていた問題 atcoder.jp 解法メモ 基数変換を実装してあげれば済む問題 けど、標準の関数でもっと簡単に記述できる。 // 2進数⇔10進数 println("4".toInt().toString(2)) // 100 println("100".toInt(2))…

ちょっと躓いたのでメモ 解いていた問題 atcoder.jp 解法メモ ポイントは3つ 大前提：「a(a>0)以下の整数のうちxで割り切れるものの個数」 ＝ 「a/x ※小数点以下切り捨て」 ex) 8以下の整数のうち2で割り切れるものの個数は8/2=4個(2, 4, 6, 8の4個) (ここを…

タイトルの通りです。 普段はDBからselectする時にorder byすることが多い気がしますが、AtCoderをやっていてプログラミング言語側でちょっと複雑なソートをしたくなったので調べました。 解いていた問題 atcoder.jp 解法メモ 問題文の通りにソートする List<String></string>…