ひらめの日常

日常のメモをつらつらと

atcoder

Scalaで競技プログラミング: ABC114-C 755

始めに 今までC++で競技プログラミングをしてきたのですが、業務でScalaを書いていることもあり、ScalaでAtCoderを解いてみようと思います。大半が解いたことある問題かつ、目的はScalaに慣れることなので、解説は省いています。 勉強途中であることもあり、…

Scalaで競技プログラミング: ATC001-A 深さ優先探索

始めに 今までC++で競技プログラミングをしてきたのですが、業務でScalaを書いていることもあり、ScalaでAtCoderを解いてみようと思います。大半が解いたことある問題かつ、目的はScalaに慣れることなので、解説は省いています。 勉強途中であることもあり、…

Scalaで競技プログラミング: ABC167-C Skill Up

始めに 今までC++で競技プログラミングをしてきたのですが、業務でScalaを書いていることもあり、ScalaでAtCoderを解いてみようと思います。大半が解いたことある問題かつ、目的はScalaに慣れることなので、解説は省いています。 勉強途中であることもあり、…

Scalaで競技プログラミング: ABC151-C Welcome to AtCoder

始めに 今までC++で競技プログラミングをしてきたのですが、業務でScalaを書いていることもあり、ScalaでAtCoderを解いてみようと思います。大半が解いたことある問題かつ、目的はScalaに慣れることなので、解説は省いています。 勉強途中であることもあり、…

AtCoder: ABC176-D Wizard in Maze (400)

問題はこちら atcoder.jp 縦マス、横マスからなる迷路がある。マス(i, j) は # のとき壁であり、. のとき道である。ます目 (C_h, C_w) から(D_h, D_w) に移動することを考える。 以下の二つの移動方法がある。 移動A: 現在いるマスと上下左右に隣接する道の…

AtCoder: ABC149-D Prediction and Restriction (400)

問題はこちら atcoder.jp 回じゃんけんを行う。買った場合、以下のように点が与えられる。 グーで勝った時、 点 チョキで勝った時、 点 パーで勝った時、 点 ただし、ちょうど 回前に出した手と同じ手は出せない。 相手の出す手が事前に全て文字列 で与えら…

AtCoder: ABC169-F Knapsack for All Subsets (600)

問題はこちら atcoder.jp 長さ の正整数列 に対して、その部分集合 を考える。その部分集合に含まれる部分集合 の和が になるようなものの個数を求めよ。 考え方 集合単位でDPをしていくことを考える。部分集合に含まれる部分集合という考えが少し難しいが、…

AtCoder: ABC164-D Multiple of 2019 (400)

問題はこちら atcoder.jp 1から9までの数字からのみなる、文字列 が与えられる。 次の条件を満たす整数の組 の総数を求めよ。 条件: の 文字目から 文字目までを10進法の整数としてみると、この整数は2019の倍数である。 制約: 考え方 はじめに を二重ループ…

AtCoder: ABC161-D Lunlun Number (400)

問題はこちら atcoder.jp 以下の条件を満たす正の整数のうち、小さい方から 番目のものを求めよ。 を10進数で表した時、隣り合うどの二つの桁の値についても、差の絶対値が1以下。 考え方 基本的に解説放送を聞いて自分の言葉に直しただけ。 www.youtube.com…

AtCoder: ABC147-E Balanced Path (500)

問題はこちら atcoder.jp マス に二つの数 が書かれている.一回の移動で または に移動する.マス から に移動しながら,数の片方を選び に.もう片方を に追加する.移動する経路を とする時,以下の値を偏りと呼ぶ. 数を自由に選びながら移動した時の,…

AtCoder: ABC146-E Rem of Sum is Num (500)

問題はこちら atcoder.jp 長さ の整数列 と正の整数 が与えられる。 の空でない連続する部分列であって、要素の和を で割った余りが要素の数と等しくなるものの数を求めよ。 以下は0-indexで話を進める。 考え方 要素の和の余りに関する問題なので、とりあえ…

AtCoder: 第二回日本最強プログラマー学生選手権-予選- D Shortest Path on a Line (600)

問題はこちら atcoder.jp 個の点がある。その点に対して、以下のように回の操作を行い、辺を追加する。 となる頂点と頂点 の間にコストの辺を追加する。 最終的な頂点からまでの最短距離を求めよ。 以降は0-indexとして話を進める。 解法1 - seg木でdp が与…

AtCoder: ABC142-E Get Everything (500)

問題はこちら 考え方 解答 別解 問題はこちら atcoder.jp までの箱がある。 個目の鍵のコストは であり、 種類の箱を開けることができる。全ての箱を開けるために必要な費用の最小値を答えよ。不可能な場合は を出力せよ。 考え方 まず、これは割と複雑な遷…

AtCoder: ABC140-E Second Sum (500)

問題はこちら atcoder.jp 長さ の順列 が与えられた時、区間 に対して以下を計算せよ。 全ての重複しない区間において、二番目に大きい数の和。 考え方 簡単バージョンとしてこの問題があるので見ると良い。 atcoder.jp step1 - 問題の言い換え 愚直にやると…

AtCoder: ABC140-D Face Produces Unhappiness (400)

問題はこちら atcoder.jp 長さ の文字列 が与えられる。L は自分の左に L が来た時、R は自分の右に R が来た時、幸福になるという。以下の操作を 回以下繰り返して、幸福なものを最大いくつにできるか答えよ。 操作: となる を選び、 ] 内にある文字列を左…

AtCoder: ABC123-D Cake 123 (400)

問題はこちら 考え方 解答1 - 解の候補を絞る 解答2 - 貪欲とpriority_queueを使う 解答3 - K個以上になる境目の値を二分探索 問題はこちら atcoder.jp 美味しさは以下のように表される。 種類のケーキ 種類のケーキ 種類のケーキ この時、それぞれのケーキ…

AtCoder: ABC136-E Max GCD (500)

問題はこちら atcoder.jp から となる を選び、 とする。この時、 以下の操作回数で の最大公約数として考えられるもののうち、最大のものを求めよ。 考え方 step1 - 解の候補 まず、 に+1して、 に-1するという操作は、 の値を一つ に移動する操作と考える…

AtCoder: 第一回日本最強プログラマー学生選手権-予選- D Classified (600)

問題はこちら atcoder.jp 今回はほぼ解説放送と解説ブログを参考にした自分用のメモ。 考え方 JSC2019予選 - D 「Classified」 (600) - Mister雑記 [AtCoder 参加感想] 2019/08/25:JSC2019予選 | maspyのHP 奇閉路が存在しないようにグラフを分割できれば良…

AtCoder: 第一回日本最強プログラマー学生選手権-予選- C Cell Inversion (500)

問題はこちら atcoder.jp 考え方 なんか自分で書いててもあまり納得感がないかもしれない... 記事を書いた後に自分がわかりやすかったものを参考として載せておきます。 misteer.hatenablog.com Cで僕が考えたこと・累積的な何かを考えるとよさそう・[L, R]…

AtCoder: ABC134-E Sequence Decomposing (500)

Sequence Decomposing 問題はこちら atcoder.jp 問題文は次のように言い換えることができる。すなわち、「数列 が与えられた時に、その数列を狭義単調増加部分列に分ける。その分け方の最小値を求めなさい」という問題と同値になる。 考え方 sample1について…

AtCoder: ABC040-D 道路の老朽化対策について (500)

道路の老朽化対策について タイトルだけ見ると政策の説明みたいだけど、競技プログラミングの問題。 問題はこちら。 atcoder.jp 都市をつなぐ道路が与えられるので、都市を頂点、道路を辺としてみたグラフを考えることにする。 Unionfindを使ってクエリごと…

AtCoder: ABC127-E Cell Distance (500)

Cell Distance 問題はこちら atcoder.jp 数式があるので、それを文章にする。 「 行 列のマス目のうち、 マスに駒をおく。このコストは全ての駒のペアのx座標の差 + y座標の差の和で計算される。これを全ての配置について和を取りなさい。」 考え方 愚直にや…

AtCoder: ABC131-F Must Be Rectangular! (600)

Must Be Rectangular! 問題はこちら atcoder.jp 考え方 解説放送が一番わかりやすいと思うので、そちらを見ると良い。 https://www.youtube.com/watch?v=XI8exXVxZ-Qwww.youtube.com 座標を二部グラフで捉えるという考え方は典型らしい。 下記の座標を、x座…

AtCoder: ABC128-E Roadwork (500)

Roadwork 問題はこちら atcoder.jp 考え方 まずは、 に出発した人がどのような条件を満たした時に の地点で通行止に引っかかるかを考えてみる。すると、1秒ごとに1進むので、以下の条件を満たしているときに通行止に引っかかるということが分かる。 これを愚…

AtCoder: ABC130-E Common Subsequence (500)

Common Subsequence 問題はこちら atcoder.jp この問題はLCS(Longest common subsequence)と関わりが深いのでまずはそれから書いてみる。 LCS 最長の共通部分列の長さを求めてくださいというのが典型的な問題。次のような例を考えてみる。 s: abcd t: acfed …

AtCoder: Tenka1 2019-C Stones (300)

Stones 問題はこちら atcoder.jp 自分が気づいたところ 全ての石が黒 or 白になると勘違いをし, WA 左端から ... と白が続いている時は無視し,そのさきは全て黒 or 白になると勘違いし,WA 右端から ### と黒が続いている時も無視できることに気づくが,黒…

AtCoder: ABC045-D すぬけ君の塗り絵 (400)

すぬけ君の塗り絵 問題はこちら atcoder.jp 自分が気づいたところ なので,全てのマス目を調べていくのは間に合わなさそう.そこで,黒く塗られているマス目だけに注目することにした. 一つの黒いマス目が影響を及ぼすマス目は,周囲の9マスだけである.こ…

AtCoder: ABC095-D Static Sushi (500)

Static Sushi 問題はこちら atcoder.jp 自分が気づいたところ 最大でも反対方向に向きを変える動きは一回だけなので,反転する場所を一つ決めてそこから反転した後の最大値を求めることを考えた. これだと,計算量は反転する場所が ,反転後の最大値探索が…

AtCoderで水色になるまでやったこと

2019/12/23追記: ※このブログはABCがABCDの4問だった頃の記事になりますので,現在では当てはまらないことも多いですがご承知ください. 2019/03/24のABC122で水色になりました. 自分が割と苦労して水色になったのと,同じようなブログがかなり参考になった…