競技プログラミング
複数変数の初期化 複数行の読み込み Array.fill 複数変数の初期化 例えば、1 2 3のように空白区切りで3つの標準入力を受け取るために、次のようなコードをよく書きます。 val sc = new Scanner(System.in) val v, e, r = sc.nextInt() これは左辺の変数の個…
C++で書いたライブラリをScalaで書き直しています。ダイクストラ法全体として以下のようなコードになりました。 case class Edge(to: Int, w: Long) case class Graph(n: Int) { val g: Array[Array[Edge]] = Array.fill(n)(Array.empty) def push(from: Int…
scanLeftはfoldLeftの途中経過の値を保持するような関数。 これを使えば、累積和の計算が簡単にできる。 初期値が一番最初に挿入されるので、元の配列より大きさが+1されていることに注意する。 val a = Array(1, 2, 3) val d = a.scanLeft(0L)(_ + _) print…
始めに 今までC++で競技プログラミングをしてきたのですが、業務でScalaを書いていることもあり、ScalaでAtCoderを解いてみようと思います。大半が解いたことある問題かつ、目的はScalaに慣れることなので、解説は省いています。 勉強途中であることもあり、…
始めに 今までC++で競技プログラミングをしてきたのですが、業務でScalaを書いていることもあり、ScalaでAtCoderを解いてみようと思います。大半が解いたことある問題かつ、目的はScalaに慣れることなので、解説は省いています。 勉強途中であることもあり、…
始めに 今までC++で競技プログラミングをしてきたのですが、業務でScalaを書いていることもあり、ScalaでAtCoderを解いてみようと思います。大半が解いたことある問題かつ、目的はScalaに慣れることなので、解説は省いています。 勉強途中であることもあり、…
始めに 今までC++で競技プログラミングをしてきたのですが、業務でScalaを書いていることもあり、ScalaでAtCoderを解いてみようと思います。大半が解いたことある問題かつ、目的はScalaに慣れることなので、解説は省いています。 勉強途中であることもあり、…
問題はこちら atcoder.jp 縦マス、横マスからなる迷路がある。マス(i, j) は # のとき壁であり、. のとき道である。ます目 (C_h, C_w) から(D_h, D_w) に移動することを考える。 以下の二つの移動方法がある。 移動A: 現在いるマスと上下左右に隣接する道の…
問題はこちら leetcode.com 二分木とそのルートのノードが与えられる。二つの葉のノードは、その最短距離が distance 以下だったときに「良いペア」となる。この「良いペア」となる葉の数を求めなさい。 考え方 dfsする。今見ているノードに対して左側と右側…
問題はこちら leetcode.com 湖が無限個存在している。その全ては今水は入っていない（=空）だが、 番目の湖に雨が降ると満杯になる。 満杯の状態の湖に雨が降ると、洪水が起きてしまう。 以下のような rains 配列が与えられるので、洪水を避けるようにしたい…
問題はこちら atcoder.jp 回じゃんけんを行う。買った場合、以下のように点が与えられる。 グーで勝った時、 点 チョキで勝った時、 点 パーで勝った時、 点 ただし、ちょうど 回前に出した手と同じ手は出せない。 相手の出す手が事前に全て文字列 で与えら…
問題はこちら atcoder.jp 長さ の正整数列 に対して、その部分集合 を考える。その部分集合に含まれる部分集合 の和が になるようなものの個数を求めよ。 考え方 集合単位でDPをしていくことを考える。部分集合に含まれる部分集合という考えが少し難しいが、…
問題はこちら leetcode.com 二つの配列 nums1 と nums2 が与えられる。同じ長さの空でない部分列を nums1, nums2 から順序を変えずに選んだ時の内積の最大値を求めよ。 考え方 DPの典型問題（解けませんでしたが... ） LCSと関わりが深いので、こちらの記事…
問題はこちら atcoder.jp 1から9までの数字からのみなる、文字列 が与えられる。 次の条件を満たす整数の組 の総数を求めよ。 条件: の 文字目から 文字目までを10進法の整数としてみると、この整数は2019の倍数である。 制約: 考え方 はじめに を二重ループ…
問題はこちら atcoder.jp 以下の条件を満たす正の整数のうち、小さい方から 番目のものを求めよ。 を10進数で表した時、隣り合うどの二つの桁の値についても、差の絶対値が1以下。 考え方 基本的に解説放送を聞いて自分の言葉に直しただけ。 www.youtube.com…
問題はこちら atcoder.jp マス に二つの数 が書かれている．一回の移動で または に移動する．マス から に移動しながら，数の片方を選び に．もう片方を に追加する．移動する経路を とする時，以下の値を偏りと呼ぶ． 数を自由に選びながら移動した時の，…
問題はこちら atcoder.jp 長さ の整数列 と正の整数 が与えられる。 の空でない連続する部分列であって、要素の和を で割った余りが要素の数と等しくなるものの数を求めよ。 以下は0-indexで話を進める。 考え方 要素の和の余りに関する問題なので、とりあえ…
問題はこちら atcoder.jp 個の点がある。その点に対して、以下のように回の操作を行い、辺を追加する。 となる頂点と頂点 の間にコストの辺を追加する。 最終的な頂点からまでの最短距離を求めよ。 以降は0-indexとして話を進める。 解法1 - seg木でdp が与…
問題はこちら 考え方 解答 別解 問題はこちら atcoder.jp までの箱がある。 個目の鍵のコストは であり、 種類の箱を開けることができる。全ての箱を開けるために必要な費用の最小値を答えよ。不可能な場合は を出力せよ。 考え方 まず、これは割と複雑な遷…
問題はこちら atcoder.jp 長さ の順列 が与えられた時、区間 に対して以下を計算せよ。 全ての重複しない区間において、二番目に大きい数の和。 考え方 簡単バージョンとしてこの問題があるので見ると良い。 atcoder.jp step1 - 問題の言い換え 愚直にやると…
問題はこちら atcoder.jp 長さ の文字列 が与えられる。L は自分の左に L が来た時、R は自分の右に R が来た時、幸福になるという。以下の操作を 回以下繰り返して、幸福なものを最大いくつにできるか答えよ。 操作: となる を選び、 ] 内にある文字列を左…
問題はこちら codeforces.com 頂点数 の木が与えられる（木なので辺の数は ）。 以下のような 個のクエリ が投げられるので、それぞれに対する答えを出力せよ。 求めるものは以下を満たす頂点 , , のペアの個数。 頂点 と を結ぶパスの中で、辺の最大の重み…
問題はこちら codeforces.com 長さ の 配列 が与えられる。一回の操作によって任意の要素一つ、 を2で割って切り捨てることを行う。 （つまり、 ） 個の等しい要素を 中で得るには、何回操作を行えばいいか、その最小値を求めよ。 考え方 全ての を、0になる…
問題はこちら 考え方 解答1 - 解の候補を絞る 解答2 - 貪欲とpriority_queueを使う 解答3 - K個以上になる境目の値を二分探索 問題はこちら atcoder.jp 美味しさは以下のように表される。 種類のケーキ 種類のケーキ 種類のケーキ この時、それぞれのケーキ…
問題はこちら atcoder.jp から となる を選び、 とする。この時、 以下の操作回数で の最大公約数として考えられるもののうち、最大のものを求めよ。 考え方 step1 - 解の候補 まず、 に+1して、 に-1するという操作は、 の値を一つ に移動する操作と考える…
問題はこちら atcoder.jp 今回はほぼ解説放送と解説ブログを参考にした自分用のメモ。 考え方 JSC2019予選 - D 「Classified」 (600) - Mister雑記 [AtCoder 参加感想] 2019/08/25:JSC2019予選 | maspyのHP 奇閉路が存在しないようにグラフを分割できれば良…
問題はこちら atcoder.jp 考え方 なんか自分で書いててもあまり納得感がないかもしれない... 記事を書いた後に自分がわかりやすかったものを参考として載せておきます。 misteer.hatenablog.com Cで僕が考えたこと・累積的な何かを考えるとよさそう・[L, R]…
Sequence Decomposing 問題はこちら atcoder.jp 問題文は次のように言い換えることができる。すなわち、「数列 が与えられた時に、その数列を狭義単調増加部分列に分ける。その分け方の最小値を求めなさい」という問題と同値になる。 考え方 sample1について…
道路の老朽化対策について タイトルだけ見ると政策の説明みたいだけど、競技プログラミングの問題。 問題はこちら。 atcoder.jp 都市をつなぐ道路が与えられるので、都市を頂点、道路を辺としてみたグラフを考えることにする。 Unionfindを使ってクエリごと…
Cell Distance 問題はこちら atcoder.jp 数式があるので、それを文章にする。 「 行 列のマス目のうち、 マスに駒をおく。このコストは全ての駒のペアのx座標の差 + y座標の差の和で計算される。これを全ての配置について和を取りなさい。」 考え方 愚直にや…
