首折鯖

雑記や漫画などを投稿します。

首折鯖

雑記や漫画などを投稿します。
  • 固定された記事
+2

漫画「朝の準備」

首折鯖

    • ARC 094 D - Worst Case [Python]

      問題はこちら。 A <= B として一般性を失わない。解説はO(1)解法っぽいんだけどO(log A_max)解法しか思いつかなかった。あとsqrtを使うと誤差に悩まされがちなので二分探索でやった。 import sysreadline = sys.stdin.readlinedef main(): Q = int(readline()) for _ in range(Q): A, B = map(int, readline().split()) if A ==

      首折鯖

      • ABC 025 C - 双子とoxゲーム【Python】

        問題はこちら。 ゲームの盤面が少ないので全探索できる。先手後手のスコアの和が一定ということに気が付かなかったのと再帰関数を使う発想が出てこなかったのでダメだった。そして解き方が分かったうえで実装が大変だった。 盤面をbitで表現すればもうちょっと効率が良くなると思うしdictも使わなくていいが、何位のbitが盤面のどこに対応してるのかとか考えるのが嫌だったのでやらなかった。 今年度中に1000問解きたかったけど忙しくて無理かも。 import sysreadline

        首折鯖

        • Donutsプロコンチャレンジ2015【Python】

          問題はこちら。 import sysreadline = sys.stdin.readlinedef main(): N = int(readline()) H = list(map(int, readline().split())) ans = [0] * N s = [] for i, h in enumerate(H): ans[i] = len(s) while len(s) > 0 and s[-1] < h: s.pop() s.appen

          首折鯖
        • 固定された記事

        漫画「朝の準備」

        首折鯖
        +2

        マガジン

        • プログラミング
          134本
        • 漫画
          9本
        • 雑記
          0本

        記事

          CODE FESTIVAL 2014 予選B D - 登山家　【Python】

          問題はこちら。 ある山小屋から見える山小屋の数は右手に見える山小屋の数と左手に見える山小屋の数の和だからそれぞれ計算する。計算にはヒープが使える。 import sysfrom heapq import heappop, heappushreadline = sys.stdin.readlineINF = float('inf')def main(): N = int(readline()) H = [INF] + [int(readline()) for _ in ra

          首折鯖

          CODE FESTIVAL 2014 予選B D - 登山家　【Python】

          首折鯖

          ABC 163 E - Active Infants 【Python】

          問題はこちら。 しばらくわからなかったけどグッと眉間に皺を寄せて考えたら解けた。活発度が高い順から両端に詰めていくんだろうな～と思ってたんだけどその通りだった。N <= 2000なので区間DPが使えた。 import sysreadline = sys.stdin.readlinedef main(): N = int(readline()) A = list(map(int, readline().split())) AI = [(a, i) for i, a in e

          首折鯖

          ABC 163 E - Active Infants 【Python】

          首折鯖

          ABC 142 F - Pure【Python】

          問題はこちら。 最少の長さの閉路を求めればよい。多重辺のない有向グラフなのでe = (a, b)とすればbから出発してaに戻る最小パスをBFSで求めれば、eを含むループの中で最小のものが求められる。このようなループをeについて全て求め最小の閉路の長さを見つける。最後に最小ループを再構築する。 import sysfrom collections import dequereadline = sys.stdin.readlinedef main(): N, M = map(

          首折鯖

          ABC 142 F - Pure【Python】

          首折鯖

          ABC 139 F - Engines【Python】

          問題はこちら。 想定解法とちょっと違う。例えばすべてのベクトルが y > 0 という半平面に入っている場合を考える。すべてのエンジンを使うか使わないかで場合分けすると計算量がO(2^N)になって死ぬ。だが実際は到達可能な点すべてを含む凸胞の頂点のみを調べればよいのでO(N)で済む。凸胞の求め方はベクトルを偏角ソートして小さい順(大きい順)に累積和をとればよい。ソートする部分がボトルネックになって計算量はO(N log N)。 import sysreadline = sy

          首折鯖

          ABC 139 F - Engines【Python】

          首折鯖

          ABC 139 E - League【Python】

          問題はこちら。 愚直にシミュレーション。PyPyでもだめだったのでC++で通した。想定解法はグラフの最長パスを使うらしいが賢すぎて思いつかない。 #include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < n; i++)const auto id = [](bool x) {return x;};int N;int A[1010][1010];int p[1010];b

          首折鯖

          ABC 139 E - League【Python】

          首折鯖

          ABC 140 F - Many Slimes【Python】

          問題はこちら。 大きいスライムから順に貪欲につくるのが最適のはずと決め打って愚直にシミュレーションした。高速に処理するには平衡二分木と優先度付きキューがあればよい。C++ならmultisetとpriority_queueでいいのだろうが、pythonにはheapqはあるけど平衡二分木がないのでやや性能は劣るがBITで代用。解説も読んだけど意味が分からなかった。 import sysfrom heapq import heappop, heappushreadline =

          首折鯖

          ABC 140 F - Many Slimes【Python】

          首折鯖

          ABC 140 E - Second Sum

          問題はこちら。 考察に比して実装が重め。というか最初BITで書いていたせいで0-indexedのオブジェクトと1-indexedのオブジェクトがごっちゃになってしまって大変だった。最終的なコードはすっきりしてるかなと思う。しかしこういうのを一目見て、時間はかかるかもしれないけど絶対解けるな、と思えるようになったというのはかなり成長したと思う。セグメント木を5分程度でバグも起こさずスラスラかけるようになったのも。 import sysreadline = sys.stdin

          首折鯖

          ABC 140 E - Second Sum

          首折鯖

          ABC 147 E - Balanced Path【Python】

          問題はこちら。 ループが80^4 = 4 * 10^7くらいになってpythonじゃ間に合わなかったのでC++で通した。皆の回答を見たらPythonでも結構通してる人がいて、その多くがbit演算を使った高速化を用いていた。自分も使えるようになりたくてbit演算を用いて高速化したpythonコードを書いたので載せておく。 import sysreadline = sys.stdin.readlinereadlines = sys.stdin.readlinesdef mai

          首折鯖

          ABC 147 E - Balanced Path【Python】

          首折鯖

          AtCoder Beginners Contest 159 F - Knapsack for All Segment【Python】

          問題はこちら。 公式解説と少し違った。「f(L, R, j) = 各項が L 以上 R 以下の単調増加数列 x_1, x_2, ..., x_kを用いて A[x_1] +A[x_2] + ... + A[x_k] = j とする方法の総数」と定義しておく。 dp[i][j] = f(0, i, j) + f(1, i, j) + f(2, i, j) + ... f(i, i, j) とすると答えは dp[0][S] + dp[1][S] + ... + dp[N -

          首折鯖

          AtCoder Beginners Contest 159 F - Knapsack for All Segment【Python】

          首折鯖

          Kyoto University Programming Contest 2016 E - 柵【Python】

          【問題】H 行 W 列のグリッド状のフィールドに羊が何頭かいる。羊たちは最初フィールドのいずれかのマス上におり、上下左右隣り合うマスに移動できる。あなたはフィールドのマス上に柵を建てることができる。羊がフィールドの外に脱出できないようにするには最低何個の柵を建てればよいか。 【制約】1 <= H <= 100, 1 <= W <= 100 グラフの最小点カットを最小(辺)カットに帰着する方法を体得した。 【問題】Gをグラフ、s, t をその相異なる頂点とする。G の(s

          首折鯖

          Kyoto University Programming Contest 2016 E - 柵【Python】

          首折鯖

          ABC 151 F - Enclose All 【Python】

          問題はこちら。 import sysfrom math import sqrtreadline = sys.stdin.readlinedef det(A): [a, b], [c, d] = A return a*d - b*cdef solve(A, v): [a, b], [c, d] = A z, w = v x = (d*z - b*w) / det(A) y = (-c*z + a*w) / det(A) return x, ydef

          首折鯖

          ABC 151 F - Enclose All 【Python】

          首折鯖

          ABC 157 E - Simple String Queries 【Python】

          問題はこちら。 セグメント木のノードに持たせる情報の表現方法によっていろいろな実装が考えられるが Python + numpy → TLE, PyPy + defaultdict → TLE, PyPy + numpy → RE となったので普通にリストで管理したらPyPyで通った。numpy速いとかPyPyの辞書遅いとか何となく知ってるんだけどこのへんの見極めが一目でできるようになりたい。 import sysreadline = sys.stdin.readlinec

          首折鯖

          ABC 157 E - Simple String Queries 【Python】

          首折鯖