2/26 2:30-6:30 (日本時間) に開催された Google Hash Code 2021 に参加しました。 codingcompetitions.withgoogle.com Hash Code への参加は初めてでしたが、とても楽しかったです。 結果は 4510位/9004チーム中でした。同じ点数のチームがたくさんいたので…

問題: E - ひも 問題概要 $N ( \leq 10^5)$ 個の区別できるノードがある。 $i (1 \leq i \leq N)$ 番目のノードの次数が $a_i (1 \leq a_i \leq 3) $であり、すべてのノードが直接または間接的に辺で繋がれており、かつ辺が全体で $N-1$ 本となるようなグラ…

問題: D - L 解説: 公式解説 問題概要 二次元の平面上の点 $(0, 0), (0, 1), (1, 0)$ に石が一つずつ並んでいる。このような石の置き方をくの字であると呼ぶ (詳細な条件は問題文参照) 。 3つの石の中から1つ選んで好きな位置に移動させる操作を好きだけ行う…

とりあえず今月中は随時更新してみる 1. 誤読 正の数とは限らない入力を正だと思い込んでいた $10^9+7$で割った余りを求めなければならないと思い込んでいた 2. 考察ミス 必要十分条件を考えなければならない場面で十分条件だけ挙げて満足 最小ケースを考慮…

問題: C - Fair Elevator 解説: 公式解説 問題概要 $1$ 以上 $2N$ 以下の整数からなる数列 $A = A_1, A_2, \dots A_N$ および $B = B_1, B_2, \dots B_N$ が与えられる。ただし $A$, $B$ は一部の値が欠損している場合がある。$A$, $B$ の欠損した値を適切に…

問題: F - Intervals on Tree 公式解説: 解説 pdf 問題概要 $N (\leq 2 \times 10^5)$ 頂点の無向木がある。整数 $1 \leq L \leq R \leq N$ について，関数 $f(L, R)$ を次のように定義する。 $S$ を$L$ 以上 $R$ 以下の番号のついた頂点からなる集合とする…

問題: Problem - E - Codeforces 公式解説: Editorial — Codeforces Round #651 - Codeforces 問題概要 長さ $n (1 \leq n \leq 10^6)$ の 01 文字列 $s. t$ が与えられる。この文字列 $s$ に次の操作を繰り返し， $t$ と等しくする。 操作: $s$ の部分文字…

問題: B - Joker 公式解説: 解説 pdf 問題概要 $N \times N$ の正方形の座席を持つ劇場に $N^2$ 人の客が座っている。客が席を立つ順番が与えられるので，以下を求めよ。 客が自席から外周へと出るまでに通る，人の座っている座席の数の，すべての客について…

問題: F - . (Single Dot) 公式解説: 解説 pdf 問題概要 無限に広がる平面上に $N (\leq 1000)$ 本の縦線と $M (\leq 1000)$ 本の横線がある。 縦線と横線の端点の座標の値は$-10^9$ 以上 $10^9$ 以下の範囲に収まる。 座標 $(0, 0)$ から動くことのできる範…

問題: Problem - E - Codeforces 公式解説: Codeforces Round #641 Editorial - Codeforces 問題概要 $n \times m (1 \leq n, \mathit{m} \leq 1000)$ の行列 $A$ が与えられる。$i$ 行 $j$ 列の要素は $a_{i, j}$ であり，0 なら白，1 なら黒である。 この…

問題: O - Variable Spanning Trees 問題概要 $N ( \leq 10^5)$ 頂点 $M (\leq 10^5)$ 辺の無向グラフが与えられる。$i$ 番目の辺は頂点 $a_i, b_i$ を結び，$c_i$ の重みを持つ。 各辺について，その辺を含む最小の重みの全域木を求め，その重みを出力せよ…

4/18 に AtCoder 社主催のアルゴリズム実技検定 (通称 PAST) に参加しました。 リアルタイム受験だったので検定終了直後から早く解法や感想を語りたくてうずうずしていたのですが，通常受験期間が終わるまでぐっとこらえました。 総得点は94点 (O 問題以外の…

問題: ESAb ATAd - Code Jam 問題概要 '0' と'1' のみからなる長さ$B$ の文字列が与えられる (制約は本節最後を参照)。この文字列に対して，次のクエリを 150 回まで投げることができる。 文字列の $i$ 文字目は '0' と'1' のどちら？ 1回目，11回目，21回目…

問題: J - ボール 問題概要 $N (\leq 16)$ 個の障害物が $x$ 軸上に置かれていて，$i$ 番目の障害物の座標は $x_i (0 \leq x_i \leq 15)$ である。 すぬけ君がボールを座標 $x$ めがけて投げると，$x-1$，$x$，$x+1$ にそれぞれ $\frac{1}{3}$ の確率で飛ん…

問題: I - イウィ 問題概要 i と w からなる文字列 $s (|s| \leq 300)$ から iwi を削除し残った文字列を連結する操作を繰り返す。 最大何回操作できるか答えよ。 解法概要 $\mathit{dp}_{i, j} := i$ 文字目 (ソースコードでは 0-indexed) から始まる j 文…

問題: H - ナップザック 問題概要 $N (\leq 100)$ 個の物があり，$i$ 番目の物の重さ，価値，色は $ w_i, v_i, c_i$ である。重さ $W$，かつ $C$ 色までナップザックに詰めることができるとき，ナップザックに詰められた物の価値の和の最大値を求めよ。 解法…

問題: D - GCD区間 公式解説: 解説 スライド 問題概要 長さ $n (\leq 10^5)$ の数列 $a_1, a_2 \dots, a_N (1 \leq a_i \leq 10^9)$ がある。この数列に対して，次のクエリが $m (\leq 10^5)$ 回与えられる。それぞれのクエリの答えを出力せよ。 最大公約数…

問題: https://atcoder.jp/contests/abc156/tasks/abc158_f 公式解説: 解説 pdf 問題概要 $N ( \leq 18)$ 枚のカードがあり，左から $i$ 枚目のカードは表に $A_i (\leq 100)$，裏に$B_i (\leq 100)$ が書いてある。次の操作のみを行い，カードが左から右に…

競プロを始めて今日でちょうど 4 年です。 4年というと中途半端ではありますが，大学編入学という環境が変わる直前に始めた趣味なので，同様に就職で環境が変わる直前である今，なんとなく感慨深いものがあります。そういうわけで，ブログに思い出を残してお…

問題: https://atcoder.jp/contests/abc156/tasks/abc158_f 公式解説: 解説 pdf 問題概要 次の同じ方法で得られた長さ $2000$ 文字以内の文字列 $ a, b, c$ が与えられる。元の文字列 $s$ の長さとしてありえる最小値を求めよ。 文字列 $s$ の空でない部分文…

問題: https://atcoder.jp/contests/abc156/tasks/abc158_f 公式解説: 解説 pdf 問題概要 数直線上に $N$ 台のロボットが置かれている。$i$ 番目のロボットの初期位置は $X_i$ で，このロボットは起動させると $X_i+D_i$ まで移動する。移動中，$i$ 番目のロ…

問題: No.1001 注文の多い順列 - yukicoder writer 解説: yukicoder 問題概要 $1$ 以上 $N$ 以下の整数の順列 $p_1, p_2, ... p_N$ であって，以下の条件を満たすものの数を $10^9+7$ で割った余りを求めよ。 すべての $i (1 \leq i \leq N)$ について以下を…

ゆるふわ競技プログラミングオンサイト at FORCIA #3 writer料は初任給に含まれます - connpass に writer として参加しました。writer をやるのは初めてでした。記憶が薄れないうちに感想など書き殴りたいと思います。 コンテストページと解説はこちらです…

問題: Problem - E - Codeforces 公式解説: Codeforces Round #620 (Div. 2) Editorial - Codeforces 問題概要 $n (3 \leq n \leq 10^5)$ 頂点の無向木が与えられる。次のクエリに $q (1 \leq n \leq 10^5)$ 回答えよ。 頂点 $x$ と頂点 $y$ の間に辺を追加…

問題: F - Modularness 公式解説: 解説 pdf 問題概要 長さ $k$ の数列 $d_0, d_1, \dots, d_{k- 1} $ について，次のクエリを $q$ 回処理せよ。 3つの整数 $ n, x, m $ が与えられる。長さ $n$ の数列 $a_0, a_1, \dots, d_{n- 1}$ を， $a_0 = x$ $a_j = a_…

問題: D - Pairs 公式解説: 解説 pdf 問題概要 $N (2 \leq N \leq 2 \times 10^5)$ 個の整数 $A_1, A_2, \cdots, A_N (-10^9 \leq A_i \leq 10^9)$ が与えられる． ここから2つの整数を選んでペアにして積をとったとき，$K$ 番目に小さい値を求めよ。 解法概…

問題: Problem - E - Codeforces 公式解説: Educational Codeforces Round 80 Editorial - Codeforces 問題概要 整数 $n, \mathit{m} (1 \leq n, \mathit{m} \leq 3 \times 10^5$ と数列 $a_1, a_2, \cdots, a_m (1 \leq a_i \leq n)$ が与えられる． 順列 $…

何が起こった？ 数日前から今日の夕方まで，このブログが重すぎて表示できませんでした． 設定をいじることでどうにかしようとしても，ブログ管理画面の「デザイン」画面も，さらにいうと記事編集画面でのプレビューも途中で表示が止まってしまっていました…

問題文: C - スペースエクスプローラー高橋君 公式解説: https://img.atcoder.jp/colopl2018-final/editorial.pdf 問題概要 長さ $N \leq 10^5$ の整数列 $a_1, a_2, \cdots, a_N (a_i \leq 10^{12}) $ が与えられる． 各 $i (1 \leq i \leq N)$ について， …

問題: https://codeforces.com/contest/660/problem/F 公式解説: https://codeforces.com/blog/entry/44259 問題概要 えびちゃんのお気に入り問題の一つなので人々に解いてみてほしいhttps://t.co/mflgdhqEVH pic.twitter.com/aVVI23MM3R — えびちゃん (@rsk…