定数倍高速化がだるかった。 Problem - F - Codeforces 問題 k個の区間[l_i, r_i] (1 区間には色c_iがついている。色の種類はn種類である。このとき、以下のm個のクエリにオンラインで答えよ。 クエリ(a, b, x, y): a色からb色までの色すべてについて、区間[…

「理由: AGCなので」という考察を初めてやった。 D - Inversion Sum 問題 長さNの整数列Aに対して、以下の操作をi = 1, ..., Qとして順にQ回行う。 A[X_i]とA[Y_i]を入れかえる。あるいは何もしない。 最終的に2^Q通りの操作のしかたがあるが、それぞれにつ…

NTTのお手本みたいな問題だった。 Problem - G - Codeforces 問題 nを偶数とする。長さnの数字列は、先頭n/2個の和と末尾n/2個の和が等しい時luckyであると呼ばれる。 数字列に出現できる数の集合{d_1, ..., d_k}が決まっている時、luckyな数字列の総数をmod…

まあ、基本ですね。 Problem - F - Codeforces 問題 長さnの数列aが与えられる。このaを用いて、n頂点の完全グラフであって、iとjを結ぶ辺のコストがa[i]+a[j]であるものを作る。 この完全グラフにm本の辺(x_i,y_i,w_i)を加える(w_iはコスト)。加えた後のグ…

これを解けそうな人がCやDに突っ込んだからか、あまり解かれなかった。 B - XOR Spread 問題 長さNの整数列aが与えられる。以下の操作を何回でも繰り返せる: 1 このとき、最終的に得られるaとして辞書順最小のものを求めよ。 1 0 解法 おもむろにb[i] = xor_…

問題文は閲覧注意です。 F - ミックスジュース 問題 「A から B までの整数から 1 個以上を選んだ時の和として得られる整数は何通りあるかmod 10^9+7で答えよ」という問いに Q 回答えよ。 1 Q 解法 AからBまでの整数のうちi個使う場合、和はi(2A+i-1)/2からi…

もともと分割統治NTTでO(N log^2 N)想定だったのを高速化して出題した。 D - Parentheses Inversions 問題 長さNの括弧列Sがある。1からNまでの整数の上の置換pであって、Sをpで置換したものがバランスの取れた括弧列であるときのpの転倒数を合計し、mod 10^…

このコンテストの作問チームにいたが、この問題は実装しなかったので今更実装した。(は?) A - Taro vs. Jiro 問題 2人が、頂点に赤青の色が塗られた有向グラフの上にコマを置いてゲームをする。各プレイヤーは1ターンに1度、コマを置かれた頂点に隣接する頂…

線形代数をやりすぎて迷走してしまった。 https://atcoder.jp/contests/caddi2018/tasks/caddi2018_d 問題 N行N列のマス目がある。これに0または1の値を書き込む。マス目のうちいくつかにはすでに数字が書き込まれている。 完成したマス目は以下の条件を満た…

これがやりたかっただけだろシリーズ。素因数分解のためにポラードのロー法を貼った。 https://atcoder.jp/contests/caddi2018/tasks/caddi2018_a 問題 N個の正の整数a_1, ..., a_Nについて、それらの積はPである。 このとき、gcd(a_1,...,a_N)としてあり得…

ゲーム(高橋君に選択権があるとは言ってない)みたいな感じ。 https://atcoder.jp/contests/agc029/tasks/agc029_d 問題 H行W列のマス目の上に障害物がN個とコマが1個(1,1)に置かれている。x行y列の位置を(x,y)と表記する。 高橋君と青木君がマス目の上でゲー…

本番は出場せず、Twitterで「二分探索」という単語を見てから解法を考えたため、自力で思いつけたかどうかは自信がない。 https://atcoder.jp/contests/agc029/tasks/agc029_c 問題 N個の文字列S_1, ..., S_nがある。S_iの長さはA_iであり、S_1 1 1 解法 実…

まあ基本だよね。 No.753 最強王者決定戦 - yukicoder 問題 16人の人間がいる。この16人を一列に並べて順番に組を作ってトーナメントを行ったとき、並べ方に応じて優勝者がただ一人決まる。全てのペアについて、戦ったときどちらが勝つかは決まっている。16!…

思いついた解法が嘘解法で、正しい解法を思いつくためにかなり多量の実験をした。 No.770 Median Sequence - yukicoder 問題 正の整数Nが与えられる。要素が1からNまでの長さNの整数列bに対して、以下の操作で数列aを作る。 a[1] = med(1, b[1], N) a[2] = m…

想定解よりも理論的に速い解法を思いついたので記念に。 No.732 3PrimeCounting - yukicoder 問題 N以下の相異なる素数の3つ組(a,b,c)の中で、a+b+cも素数であるものの個数を数えよ。2 5 解法 相異なる素数(a,b,c)の和としてある数を表す方法の総数がわかれ…

蟻本に載っている典型問題というのはすぐにわかったが、そこから詳細を詰めるのにかなり時間がかかった。 No.767 配られたジャパリまん - yukicoder 問題 縦H, 横Wの、格子点が(H+1)(W+1)個あるグリッドの上にK個の点がある。K個の点の部分集合2^K個のそれぞ…

Q#というMS製の量子計算用言語の言語仕様 Q# statements | Microsoft Docs を読んでいたら、 というゲートが、基本的なゲートたちと観測の組み合わせで正確に実現できるという話を見たので、調べてみました。 準備 状態|0>を、状態|1>をとします。状態ベクト…

問題文: ARC024 E Sequence Growing Hard 問題概要 0要素の数列がある。この数列に、以下の条件を満たすように、1要素ずつ挿入することをN回繰り返す。 挿入後の数列は、挿入前より辞書順で大きい。 挿入の過程で同じ数列ができる操作は同じとみなす。操作の…

問題文: ARC097 F Monochrome Cat 問題概要 N頂点の木が与えられる。各頂点には0または1が書かれている。好きな頂点を選び、そこに行き、以降以下の1.または2.の操作のいずれかを何回か行う。 隣接する頂点を一つ選び、移動し、移動先の頂点の数字を1->0また…

同じ相手と白黒入れ替えて2局指した。 少しチェスをやらない期間があると、すぐにblunderの鬼になってしまう…。

kobaは黒。全体的に動きが良くないが、特に31手目から壊滅しているので、自戒のために。

chess.comでdaily chessをやった。kobaは黒を持った。12...Nxe4がひどいblunderだったが咎められず、その後も最後まで白がはっきり有利だと思ったが、後で評価してみるとそうでもないようだった。