yu/logs/*

技術メモ など

AtCoder

AtCoder ABC144 C 解法メモ (Kotlinで)約数列挙したい

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

AtCoder ABC181 C 解法メモ 3点の座標が同一直線上に存在するか判定したい

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

AtCoder ABC185 C 解法メモ Kotlinで途中の値がLong(64Bit整数)型に収まらないような数式の計算をしたい(※階乗を用いた組み合わせの計算とか)

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

AtCoder ABC224 C 解法メモ 3点の座標から三角形の面積を求めたい

覚えてなかったのでメモ 解いていた問題 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 ABC162 C 解法メモ (Kotlinで)最大公約数を求めたい(ユークリッドの互除法)

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

AtCoder 鉄則本 B11 解法メモ Kotlinで超簡易版lower_bound, upper_bound

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

AtCoder ABC294 D 解法メモ KotlinでTLEせずに10^6くらいの出力をしたい(出力の高速化)

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

AtCoder ABC293 D 解法メモ KotlinでUnion-Findしたい

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

AtCoder ABC156 B 解法メモ (Kotlinで)10進数⇔2進数の変換をしたい

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

AtCoder ABC048 B 解法メモ a以上b以下の整数のうち、xで割り切れるものの個数を求めたい

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

AtCoder ABC128 B 解法メモ (Kotlinで)複数項目をキーにしてリストをソートしたい

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

AtCoder ABC276 C 解法メモ (Kotlinで)prev_permutationしたい ※ついでにnext_permutationも

前にnext_permutationの実装で試行錯誤したものの、すっかり忘れてしまっていたので備忘を兼ねて 解いていた問題 atcoder.jp 解法メモ いろいろ参考にしてnext_permutation、prev_permutation相当のものを事前に実装しておいちゃう 今回の問題はprev_permuta…

AtCoder ABC159 A 解法メモ n個のものからk個選ぶ組み合わせを計算したい(二項係数)

昔数学で習ったはずなんだけれども思い出せない&実装にあたりちょっとハマったのでメモ。 解いていた問題 atcoder.jp 解法メモ 二項係数と呼ばれるもの(もの?)で導出可能 private fun readLn() = readLine()!! private fun readStrings() = readLn().split…

AtCoder ABC149 C 解法メモ (Kotlinで)素数を列挙したい(エラトステネスの篩)

エラトステネスの篩と呼ばれる方法で素数を列挙することができるようだったので、参考リンクのものを参照しながらKotlinで書いてみた 解いていた問題 atcoder.jp 解法メモ エラトステネスの篩と呼ばれる方法で素数列挙が可能 /** * エラトステネスの篩を利用…

AtCoder ABC266 C 解法メモ 2点のなす角が180度未満かどうか判定したい

基本は公式解説の通りですが、自分の言葉で整理しておきたいなというメモです。数学が弱い。 解いていた問題と解説 atcoder.jp atcoder.jp 解法メモ 結論 外積の正負を使って判定する 導出 ベクトルa, bの外積は平行四辺形の面積の絶対値と等しい 外積 a=(a1…

AtCoder ABC263 C 解説の深さ優先探索をデバッグ実行しながら理解した

ABC263にて、C問題が解けませんでした。 atcoder.jp (↓無茶苦茶に実装しようとして結局実装しきれなかったもの) atcoder.jp 上記ゴリ押し実装の修正も試みたものの、どんどん肥大化してバグを取り切れませんでした・・・ 仮に次に同じ問題が出たときにもう…

AtCoder メモ 「⌊x⌋とか⌈x⌉とか、この角括弧と似たような記号ってなんだっけ?」 → floorとceiling

AGC145Bの解説を読んでいて、意味を把握できず若干面食らってしまったのでメモ タイトルの通り、関数の名前で言うとfloorとceilingが対応 例まで含めて以下に記載されているので分かりやすい Floor and ceiling functions - Wikipedia メモ 負数が絡まない場…

Kotlinでのソートメモ sort()は元のリストを書き換える、sorted()は元のリストを書き換えない

タイトルの通りです。*1 playgroundで確認してみました。 参考 sort - Kotlin Programming Language sorted - Kotlin Programming Language *1:※sorted()しか知らずにAtCoderの問題を解いていて、「別に元の値書き換えてくれていいんだけどな」というケース…

AtCoder ABC175 B 解法メモ 3辺の長さが与えられた時の三角形の成立条件

実装よりも判定条件の方が分からなかった・・・。Kotlinで解いています。 解いていた問題 B - Making Triangle 解法メモ n <= 100なので3重ループを回しても106なので全探索が間に合う AtCoderでは108までなら全探索しても間に合う(ってどこかで見た) ↓こ…

AtCoder ABC133 B 解法メモ 平方根の値が整数になるかを判定したい

考え方のメモです。Kotlinで解いています。 解いていた問題 B - Good Distance 2点間の距離が整数になるかを判定する問題 2点間の距離を求めるにあたり平方根が絡んでくる 平方根の値が整数になるか(√を展開したあとに整数になっているか)を判定したいが・・…

Kotlin for competitive programming(競技プログラミングのためのKotlin)を読んでみた

KotlinでAtCoder参加中(灰色)です。 言語仕様を確認しに行こうと久々にKotlin Programming Languageを見に行ったところ、「Kotlin for competitive programming | Kotlin(競技プログラミングのためのKotlin)」というページがあったので、少し読んでみまし…