問題 atcoder.jp 問題概要 N人が円周上に並んでいる． i番目の人は時刻tに宝石をもらうとSi時間後にその宝石を(i+1)番目の人に渡す． ただし，(N+1)=1とする． また，高橋君は時刻Tiにi番目の人に宝石を渡す． すべてのiについて，i番目の人が初めて宝石をも…

問題 atcoder.jp 解法 問題を読んだ段階で、ソートを行うクエリをどう扱うか（普通にソートすると計算量くってTLEっぽい）がポイントと思われる。 そこで、次のように処理する。 キュー Q1と最小値を優先的に取り出す優先度付きキューQ2を用意して、クエリを…

問題 atcoder.jp 問題概要 長さLの木材がある．以下のQ個のクエリを処理せよ． i番目のクエリは(ci,xi)で与えられる． ci=1のとき：木材の左端からxiの地点で木材を切る． ci=2のとき：木材の左端からxiの地点を含む木材の長さを出力する． 1≤L≤109 1≤Q≤2×10…

問題 atcoder.jp 解説 生成できる最小値と最大値を計算すれば、間の組み合わせ数は、おのずと割り出せる。 実装 参考 youtu.be

問題 atcoder.jp 解法 区間DPで解く。 区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです。 𝑑𝑝[𝑙][𝑟] := 区間 [ l, r ) について、最適な状況下での何かしらの値 dp[0][0]から、幅0でdp[0][0], dp[1][1], dp[2][2] ....と計算していく。 先攻後攻…

問題 atcoder.jp 解法 コンテスト参加中 「DFS(深さ優先検索)だろ！こりゃACもらった！」 と思ったら、TLEで解けなくてガッカリだったー。 ので復習。 この問題、DFSで木を上方向に戻る処理まで再帰関数で実装してしまったんだが、1に戻って終わるのが前提の…

AtCoderの問題の答え表示で、横一列表示が出て、 「あれ？どうすんの？」 と思い、調べたのでメモ >>> A = [1, 2, 3, 4, 5] >>> print(*A) 1 2 3 4 5

問題 atcoder.jp 解法 1 <= N <= 4000 なのでO(N3)だと、43 * 109 でTLEのはず。 なので、R, Gの二つの要素を固定。 すると O(16 * 106) くらい？ あとは、計算でBの要素から何個採用できるかを出す。 この方針でTLEは出ないはず。 R, Gのある場所のインデッ…

問題 atcoder.jp 解法その1 numpy + njitを使ったO(N3)解法 なんと、何も考えずに問題通り、総当たりコードを書くとACしてしまうという解法。 マジですか。 AtCoderのPythonではnumpyが使用できるが、njitを使って関数の実行速度を高速化。 実行すると、1731…

問題 atcoder.jp 数学問題。 解法 水の体積が、水筒の半分以下か以上かで処理が異なる。 水の体積が水筒の半分以下のとき 半分以下の時、水は三角柱の形でこぼれる。 水の体積が半分以下 θの角度が求める答え。 水の面積 x / a 水の底辺yの値を求める。三角…

問題 atcoder.jp 解法 K個の石の山に対して、 dp[k] := k個の石からなる山で先手が勝ち状態か(=1なら勝ち状態） というdpを設計。 数が小さい方から、Kまでの石の山をシミュレーションしてdpの数値を埋めていく。 まずはk = 0と非常に単純な状態から調べてい…

問題 atcoder.jp 解法 問題を一見すると 「どの商品に何枚半額割引券を使えばよいか？」 という問題に見える。 だが半額割引券を1枚ずつ使っても結果は変わらない。 なので、 「一番値段が高い商品に1枚ずつ割引券を使う」 という貪欲法で解ける。 あとは、…

問題 atcoder.jp 解法 最小値を計算量低く取り出すデータ管理構造、優先度付きキュー（priority queue）を使うことがポイント。 Pythonではheapqとして提供されている。 全体に対する玉の数の上下はoffset変数を作って管理。 玉を追加する時は、offset値を引…

問題 atcoder.jp 解法 数列A、数列Bが2 x 105なので、A,Bの全要素に対して総当たりだと、2 x 105の2乗なので108越えでTLE確実。 なにか最適化する必要がある。 おそらく二分探索だろうと、検索したところ、そういえばbisectという便利ライブラリがPythonには…

問題 atcoder.jp 解説 A5 - B5 = X で、Xの制約条件が 1 <= X <= 109 ゆえに、Aは大体1000くらいまでだろ？ という当たりをつける。 Bは負の値もありえるので、-1000から1000までの範囲で総当たりをかける。 実装 素直に計算したのが、実行時間70ms。 はまや…

問題 atcoder.jp 解答 周期性を利用したコードでAC。 なかなか難しかった。 感想 dpを使ったダブリングが想定解答。 こっちもやってみたいが、一回力尽きたので後ほど。 実装 参考 blog.hamayanhamayan.com

問題 atcoder.jp 解答 BFS(幅優先探索)で、あっさり解ける。 BFSの探索をかけて、ans[i]に部屋iの一個前の部屋番号を記録。 ansが一通り揃っているなら、"Yes"の後にまとめて表示。 感想 問題読んで、dfsかbfsだろうな？とは思うが、どっちだろう感ある。 は…

問題 atcoder.jp 解法 辺の重みが全て1であることから、この問題はBFS(幅優先探索)を用いる。 実装 参考 atcoder.jp www.youtube.com

問題 atcoder.jp 解法 DP（動的計画法）で解く。 公式動画で最初に説明されている、貰うDPのパターンで実装してみた。 dp[i][j]を、「Sのi文字目までを使って、chokudaiのj文字目まで選択する方法」と定義。 dpを解いていく。 実装 参考 www.youtube.com atc…

問題 atcoder.jp 解法 計算式を関数に実装し、試しに数値を入れてみて答えに規則性があるかどうかを見てみる。 すると、mod Bでループしていることがわかる。 よって、最大値の候補はx = Nかx = B-1。 それぞれの値の答えを求めて比較。 答えとする。 B-1 <=…

問題 atcoder.jp 解法 計算式を関数に実装し、試しに数値を入れてみて答えに規則性があるかどうかを見てみる。 すると、mod Bでループしていることがわかる。 よって、最大値の候補はx = Nかx = B-1。 それぞれの値の答えを求めて比較。 答えとする。 B-1 <=…

問題 atcoder.jp 解法 defaultdictを使って、数列Aの数値の出現回数をカウント。 Aの各数値の組み合わせ数nCrも計算してa_tmpに保存。 組み合わせ数の公式nCrを、真面目に計算してしまうと計算量が多くてTLEになってしまう。 問題は２つのボールを選び出す方…

問題 atcoder.jp 解法 整数Nを素因数分解する。 公式のpdfより引用。 N = p1e1 × ... × pkek と素因数分解されるとします。このとき、各 pi に対して、 z = pi1, pi2, ... と順番に選んでいくのが最適です。 素因数分解は、検索すればやり方はすぐわかるのだ…

問題 atcoder.jp 解法 街がN、経路がN-1であることから木構造であることがわかる。 木構造の頂点間の最短距離が奇数なら道で。 偶数なら街で出会う。 最短距離の偶奇を求めるために、各頂点の深さを計算。 深さから、頂点間の距離がわかる。 途中に共通の祖…

問題 atcoder.jp 解法 素直に書く。 展望台とつながっている隣の展望台と高さを素直に比較。 より高い展望台が無いかを調べる。 実装としては、無向グラフ。 実装

問題 atcoder.jp 解法 街がN、経路がN-1であることから木構造であることがわかる。 木構造の頂点間の最短距離が奇数なら道で。 偶数なら街で出会う。 最短距離の偶奇を求めるために、各頂点の深さを計算。 深さから、頂点間の距離がわかる。 途中に共通の祖…

問題 atcoder.jp 難しい問題。 解法 動的計画法で解く。 線路のコスト計算はC x (|i - i'| + |j - j'|)円。 この計算式から絶対値を外していく。 i' <= i, J' <= jとすれば C x i - C x i' + C x j - C x j' = C x i + C x j - C x i' - C x j' = C ( i + j …

問題 atcoder.jp 解法 いわゆる「しゃくとり法」で解ける問題。 数列cの中からK個の連続した数値を選び、その種類が最大になる範囲を総当たりで調べる。 わけだけど、ベタに作ると計算量が多すぎる。 範囲の左端と右端を決定し、色数を計算。 色数が最大か？…

問題 atcoder.jp 解法 数列A, Bを、それぞれ先頭から何個目まで使用することができるか？という問題。 数列A, Bを、しゃくとり法で走査する。 数列Aはゼロから。 数列Bは最後尾から条件を満たす位置を走査して、最大値を調べる。 実装

問題 atcoder.jp 解法 しゃくとり法という単語をAtCoderの解法でよく聞くが、やったことなかったので、やってみる。 ある条件を満たす数列の範囲を、しゃくとり虫のように長さを変えながら探索するアルゴリズムで 条件〇〇を満たす区間 (連続する部分列) の…