2019-02-01から1ヶ月間の記事一覧

AtCoder Grand Contest 020:B - Ice Rink Game

問題 https://atcoder.jp/contests/agc020/tasks/agc020_b 考え方 考えていたこと ナイーブに考えると 回目のラウンド前にいた人数を とするとラウンド後は となることは分かる。1 回目のラウンド前にいる人数を として を順に 回適応すると最終的な人数が決…

AtCoder Grand Contest 006:B - Median Pyramid Easy

問題 https://atcoder.jp/contests/agc007/tasks/agc007_b 考え方 の場合は中央値になりえないので必ず NO になる。そうでない場合、例えば の場合は可能かどうかというと可能である。 で実験すると容易に分かる。 上の段の中央値になる場合の条件について考…

AtCoder Grand Contest 007:B - Construct Sequences

問題 https://atcoder.jp/contests/agc007/tasks/agc007_b 考え方 えー、難しい... の順列 の順番になるように を構築する。その際に は単調増加で は単調減少になるようにする必要がある。 いろいろな条件をいっぺんに考えることが難しいときは、ひとつずつ…

AtCoder Beginner Contest 119:D - Lazy Faith

問題 https://atcoder.jp/contests/abc119/tasks/abc119_d 考え方 各クエリに対して ないしは で答えないといけない。神社用と寺用のTreeSet(二分探索木)に各 をあらかじめ入れておけばクエリごとにある位置 に対して左右にある最短の神社と寺の位置を求める…

AtCoder Grand Contest 004:B - Colorful Slimes

問題 https://atcoder.jp/contests/agc004/tasks/agc004_b 考え方 典型っぽい。ある変数を固定すると、最適な操作が見えてくる問題。 何を固定するか? 最小の秒数を 秒として二分探索 「 秒で全色のスライムを集めることができるか?」というYes/No問題に切…

AtCoder Grand Contest 005:B - Minimum Sum

問題 考え方 式だけみるとぱっと何を求められているかわからないので、まずはナイーブに の実装で実験してみる。そうすると区間の数について最小になる要素を求めて、その総和を求める問題であることが分かる。 さて、区間の数をまとめて計算したい。「最小…

yukicoder:No.794 チーム戦

問題 https://yukicoder.me/problems/no/794 考え方 きれいな問題で好き。 はソートしても問題がないのでソートする。マッチングする際に が大きい値ほど候補になる相手が厳しく、候補が絞られるので が大きい値から考えていく。 サンプル1 の場合ソート後の…

AtCoder Grand Contest 002:B - Box and Ball

問題 https://atcoder.jp/contests/agc002/tasks/agc002_b 考え方 実験??実験のコツがわかるようになりたい...。 赤いボールが入っている箱から 回の操作によって到達できる可能性がある箱については赤いボールが入りうる。ただし操作後に操作元の箱 x が…

yukicoder:No.793 うし数列 2

問題 https://yukicoder.me/problems/no/793 考え方 うし数列を 10 進数で桁ごとに考える。例えば の場合、 となる。項をまとめるのに等比数列の和の公式を用いた。そうすると後は各項ごとに modつきの累乗を取り、 で割る操作は逆元を取れば良い。 #318620 …

全国統一プログラミング王決定戦 エキシビジョン:F - コラッツ問題

問題 https://atcoder.jp/contests/nikkei2019-ex/tasks/nikkei2019ex_e 考え方 サンプル2から であることが分かっているので、これを利用する。 を満たす を とすると である。この結果の両辺に すると となる。左辺は の偶奇によって仮定の式を適応するこ…

全国統一プログラミング王決定戦本戦:C - Come Together

問題 https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_c 考え方 難しいが過去にも300点で似たような問題があるので、点数は相応な気はする... どこに着目して考察するべきだったか まずは H 軸、W 軸ごとに独立して考えることにしよう…

SoundHound Inc. Programming Contest 2018 -Masters Tournament-:E - + Graph

問題 https://atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_e 考え方 考えていたこと グラフは連結であるから、ある頂点のコストを決め打ちすると頂点と辺の関係から他の頂点のコストが一意に決まることが分かる。なの…

CODE FESTIVAL 2018 Final (Parallel):D - Three Letters

問題 https://atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_d 考え方 考えていたこと 文字 の長さについて つの箇所を全探索というナイーブな考察以外に思いつかなかった...。 文字なので、真ん中を固定して全探索し…

AtCoder Regular Contest 058:E - 和風いろはちゃん / Iroha and Haiku

問題 https://atcoder.jp/contests/arc058/tasks/arc058_c 考え方 考えていたこと 条件を満たす数列はどのような数列であるか考えた。 を全探索する。そのとき の区間の長さを求めておいて、各区間の長さの要素の和が なる要素の組み合わせを考えると、これ…

DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選:D - チップ・ストーリー ~黄金編~

問題 https://atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_d 考え方 ある数 を 進数で表記したときにどのようになるか考えると解ける。つまり を 進数で表記したときに下の桁の数から で表されたとすると と表すことができる。 であるから につ…

AtCoder Regular Contest 068:E - Snuke Line

問題 https://atcoder.jp/contests/arc068/tasks/arc068_c 考え方 これは難しい... 考えていたこと imos法で区間を含むか数える、がこれは重複して数えてしまうのでダメ。 を全通り試すことは でできるのでこれは全探索 解説見た 公式解説のベースに考えてい…

Educational DP Contest / DP まとめコンテスト:Z - Frog 3

問題 https://atcoder.jp/contests/dp/tasks/dp_z 考え方 ConvexHullTrick を用いる。もらうDPを考えよう。 足場 に至るときの最小のコスト と定義する。この時DPの遷移は となる。 の部分は に関する1次関数と捉えることができて なる における1次関数たち…

第4回 ドワンゴからの挑戦状 予選:D - ディスクの節約

問題 https://atcoder.jp/contests/dwacon2018-prelims/tasks/dwacon2018_prelims_d 考え方 まずは最小値に単調性があるので、最小値 を二分探索することにしよう。つまり以下の問題を考える。ディスク使用量をコストと呼ぶこととする。 「最小値を とすると…

「みんなのプロコン 2019」:F - Pass

問題 https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_f 考え方 操作の結果の文字列を考えていく。ある文字列が構成されていると仮定したときに次の文字を置くことができる場合は、赤/青のボールごとに考えればシンプルに求…

Mujin Programming Challenge 2018:F - チーム分け

問題 https://atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_f 考え方 放送解説が秀逸。chokudaiさんが考察の進め方を解説している。 さて、まずは入力の数列をソートしても問題ないのでソートしておく。状態を定義するが、どのように状態を定義す…

「みんなのプロコン」本選 オープンコンテスト:B - チーム決め

問題 https://atcoder.jp/contests/yahoo-procon2017-final-open/tasks/yahoo_procon2017_final_b 考え方 差の最大値を最小化したい。これはよくある典型問題で、最小化したい値 を二分探索することで最小値を求めることができる。問題を言い換えると 「差を…

AtCoder Regular Contest 067:E - Grouping

問題 https://atcoder.jp/contests/arc067/tasks/arc067_c 考え方 漸化式的な考え方でDPをする。難しい。 人未満のグループのみで 人を分ける場合の数 と定義する。 を用いると 人のうち 人はすでにグループが決まっているため残りの 人のグループ分けについ…

AtCoder Regular Contest 098:E - Range Minimum Queries

問題 https://atcoder.jp/contests/arc098/tasks/arc098_c 考えたこと だとするともとの数列 をソートして連続する 個の要素の最小値をとればよいことはわかった。これはしゃくとり法とかで でできる。 選べない数を除々に決めていきたいが、これは小さい数…

AtCoder Regular Contest 097:E - Sorted and Sorted

問題 https://atcoder.jp/contests/arc097/tasks/arc097_c 考え方 状態を決め打ちできるかどうかが一番重要な考察な気がする。つまり dp[i][j] := 左から [1,i] までの黒 'B' の数と [1,j] までの白 'W' の数が正しく並べるようにするときの最小のswap回数 …

AtCoder Regular Contest 061:E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

問題 https://atcoder.jp/contests/arc061/tasks/arc061_c 考え方 まずは問題文の条件通り、路線ごとの駅にノードを対応させてグラフを構築する。駅と会社でそれぞれの頂点の役割が変わってくるので座圧の要領で拡張点に index を付与しておく。 同じ駅で会…

「みんなのプロコン 2019」:D - Ears

問題 https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d 考え方 まずはすぬけくんが散歩する操作をシミュレーションする。そうすると散歩による操作を数列で表すことができることがわかる。その数列はある性質を持っていて…

AtCoder Regular Contest 081:E - Don't Be a Subsequence

問題 https://atcoder.jp/contests/arc081/tasks/arc081_c 考え方 基本的な考え方は放送解説がわかりやすい。 dp[i] := 位置 i 以降で条件を満たす最小の文字列の長さ とする。そのとき dp[i] = min(dp[next[i][j]] + 1) となる。next[i][j] は 位置 i 以降…

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019:E - Weights on Vertices and Edges

問題 https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_e 考え方 連結成分について連結した状態から、除々に辺を切断して非連結にしていきたい。UnionFindは頂点の連結しかできないがどうするか?という問題である。 逆に非連結の状態か…

AtCoder Beginner Contest 117:D - XXOR

問題 https://atcoder.jp/contests/abc117/tasks/abc117_d 考え方 考えていた解法(貪欲) bitのXORを考える問題なので、bitの桁ごとに考えていこう。bitごとに独立して考えることができる。 について という制約がなければ本当にbitごとに上から貪欲でOK。た…

SoundHound Inc. Programming Contest 2018 -Masters Tournament-:D - Saving Snuuk

問題 https://atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_d 考え方 解は なる 年それぞれについて解を出力する必要がある。各年度それぞれについてダイクストラをするのではTLEになる。 まず からそれぞれの都市への…