blogskol

思わず声に出して読みたくなるブログ

Spent Fuel Disposal

解説等が一切見当たらなかったので、殴り書きをする

問題

jag 夏合宿 2019 day2 の問題で、たしか作問担当は筑波大だったと思う
論文（多分これ？）を読むと解けますと言われたことしか覚えてない

解法は、S,U を source, T,V を sink としたグラフと S,V を source, T,U を sink としたグラフでの最大流の min
これがなんとなく正しいかもと言う気持ちになるための説明を書く

二つのグラフのフローは簡略化するとそれぞれ以下のように描ける

両方のグラフに登場する S,T パスと U,V パスについては元の問題で求めたいパスに含まれる*1
一方で、左のグラフの S,V パスと U,T パス 、右のグラフの S,U パスと V,T パスについては、以下のようにして S,T パスと U,V パスに変形が出来る

色使いが気持ち悪くてごめん

従って、この解法が正しそうな気持ちになる

実際には二つのグラフで得られる最大流で S,T パスと U,V パスがそれぞれ一致しているとは限らないためもう少し議論が必要だと思います

*1:無向グラフなのでパスの向きは気にしなくて良い

PAST 丁寧な実装集

PAST は良問が多く、過去問を完全に理解するだけで AtCoder 青色程度の実力になれそうな感覚がある
考察だけで無く実装を問われる問題も多く、AC 後は他人のコードを読んで綺麗な実装を学ぶのが望ましい

綺麗な実装を探すのは大変なときもあるので、各問題の（C++での）丁寧な実装を記録する
各問題を綺麗な実装で通したくなったので、せっかくだからインターネットにまとめておきたいと言うのが本音

解説は必要だと判断すればコード中にコメントで残す

以下は共通のテンプレート

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}

ライブラリや snippet は必要に応じて使う
特にライブラリに関しては内部の実装を真似る必要は無く、各関数が何を返すかのみに注目すれば十分

注意

「綺麗な実装」は完全に主観なので肌に合わないことは当然あると思う
また、競技プログラミング以外のプログラミングのことは一切考えていない
単に競技で強くなりたい層向けなので、「業務で書くには行儀の悪いコード」のような批判は的外れ

001

A B C D E F G H I J K L M N

002

A B C D E

003

004

005

006

007

008

009

2-回文作問

競技プログラミングにおいて回文の問題はそれなりに考えられているが、 2-回文はそうでも無いだろうなと思ったので思いつくままに書く
解法が分かったら都度追記する

2-回文とは？

2 つの回文の和で表せる文のこと
同様に k-回文が定義出来る
空文字列は回文と見做すことにする（従って k 回文は k+1 回文でもある）

先行研究

2-回文かどうかの判定は Manacher を使えば線形で出来る

arxiv.org S が k-回文であるような最小の k を O(|S| \log |S|) で求めるアルゴリズムが乗ってる
前読んだけどあんまり覚えてない

www.asahi.com 同様の問題を O(|S|^2) で求めるアルゴリズムが誘導を用いて丁寧に問われている

小岩井コーヒーは 2-回文

問題集

以下文字の種類数を B とし、S,T を文字列、N,M をそれらの長さとする
部分文字列と書いたら連続のと非連続のそれぞれ考える

置換距離

S を 2-回文にするために置換する必要のある最小文字数
例 : S = "abcded" なら c を a に変更すればいいので答えは 1

畳み込みで O(BN\log N) と O(N^{1.5} \log N) は思いつくけど多項式の形が特殊なのでもっと早くなりそう
そもそも畳み込みが必須とも思えない
ワードサイズを W として O(BN^2/W) とかも出来て、高速化頑張られると区別が大変そう
この問題に限った話じゃ無いけど、bit 列の時だけ速くなるとかもありそう

書いた

i 文字目の変更コストが A_i の場合は？

部分文字列の個数

S の部分文字列のうち 2-回文であるものの個数（ multiset のつもり）*1

辞書順 K 番目

S のアナグラムのうち辞書順で K 番目の 2-回文
ちゃんと考えてないけどそもそも S のアナグラム 2-回文の個数は簡単に求められるのかな 直感的には二項係数とかで出来そうだけど
奇数個の文字が 3 個以上なら作れなくて、2 個なら回文の中心 2 つが決定するのであとは残りの文字の振り分け
0,1 個の時もほぼ同様に解けそう

連結

文字列集合 S_1,\dots,S_n を好きな順序で連結させて 2-回文にすることが出来るか
最小何個連結させる必要があるか
連結で k-回文が作れるような最小の k はいくつか

素な文字列

S が i_1 , \dots ,i_k 文字目のみが与えられている時の何かしらを求めさせる問題

  • 残りの文字が全て # の時 S は 2-回文かどうか
  • 残りの文字を自由に決めていい時 2-回文に出来るか
  • bit列だとして、残りの文字を自由に決めていい時 2-回文の最小 popcount

圧縮文字列

S が 文字 c_i が a_i 個の連結で与えられている時の何かしらを求めさせる問題
例えば c4 b2 a5 b2 c7 a5 b2 a5 c3 なら "ccccbbaaaaabbcccccccaaaaabbaaaaaccc" のこと

  • 2-回文か判定 （上の例は Yes ） これは多分解ける気がする 端と分け目以外は (c_i,a_i) で一文字と見做して良いので

感想

文字列問題 2-回文にすると全部難しくなる

*1:set では流石に難しそう？

試験作り

D - 試験作り

試験を B で昇順に並べておきます

選ぶ試験の集合を S と置くと、明らかに太郎くんは S の問題を全て解くとして良いです。
したがって、\sum_{i\in S} A_i \leq T が成り立ちます。

また、次郎くんは S を番号が小さい順に解きます。 従って、次郎くんが解いた問題のうち最も番号が大きいものを k と置くと、[tex:T-\sum{i \leq k} B_i < min{B_i \mid i>k , i\in S}] が成り立ちます。

mn[i][j] を 仕事[0,i)まで見た時、次郎くんの使用時間がjになるような仕事の選び方で太郎くんの使用時間が最小になるもの
mx[i][j] を 仕事[i,n)まで見た時、太郎くんの使用時間がj以下になるような仕事の選び方で太郎くんのこなした仕事量が最大のもの
と置きます。

mn[i][j] で選ぶ仕事は全て二人ともこなす仕事、mx[i][j] で選ぶ仕事は太郎くんのみがこなす仕事です。

この二つの配列から頑張ると解けます。

atcoder.jp

Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2) F. Sports Betting

問題リンク

最初 ans=n と置き、winner にならないケースを引いていく

人 i が winner にならない各ケースで、以下を満たす極小な人集合 S がちょうどただ一つ存在する

  • i \not \in S
  • S の各人は S に含まれない各人に勝利

従って各 S に対してS が起こる確率を P(S) と置くと、 ( n-popcount(S) ) P(S) を ans から引けば良い

win_{i,j}=\frac{a_i}{a_i+a_j} と置くと、 P(S) は以下の式で求められる
各 T \subset S に対して、極小な人集合が T になるケースを除いている

P(S) = \prod_{i \in S} \prod_{j \not\in S} win_{i,j} - \sum_{T\subset S} P(T) \prod_{i \in S-T} \prod_{j\not\in S}win_{i,j}

[tex:O(3n n2)] とかで厳しいけど適度に高速化を入れると通る
もう少しいい計算量で P(S) 求められそうな気はするんだよな

競プロのランダム入力生成方法

備忘録

はじめに

betrue12.hateblo.jp

この記事を読もう！
終わり

改善

※ここから先は Mac を仮定

oj を使い始めてからコード毎にディレクトリを作るようになったので、ランダム入力生成コードなどもその都度書く必要があり、汎用的な部分は snippet に追加することにした
愚直解に関しては C++ で毎回書いているけど、これももしかしたら愚直解書く時専用の関数とか作った方がいいのかも？

ランダム入力生成コード

python の snippet に以下を追加した
C++ の snippet があんまり増えるのが嬉しく無いので python にしたけど結構メリットが大きい

import random

def RND( l, r, n ):
  res = [ random.randint( l, r ) for _ in range(n) ]
  return res

# print( *RND( 5, 10, 3 ) ) => 9 6 5

最後のコメントにもある通り、print( *RND( l, r, n ) ) で競プロの入力っぽく出力してくれる

pythonを使うメリット
  • 数を少しだけ変えた時などに、コンパイルの手間が省ける
  • 直感的な操作が出来る関数が多い
  • パソコン出来る気分になる
shellscript

こちらも snippet

while true;do
  python rand.py>input.txt
  wrong=$(./a.out < input.txt)
  correct=$(./g.out < input.txt)
  if [ $wrong != $correct ]; then
    echo "$(<input.txt)"
    echo "Wrong:"
    echo $wrong
    echo "Correct:"
    echo $correct
    exit
  fi
done

冒頭の記事と比較すると、

  1. inputの出力
  2. どっちが正しい答えか記述

この2点は個人的にとっても大事だと思っている

あと、元の記事では make_random.out や guchoku.out みたいな長い名前を採用していたけど長いので適度に短く

drogskolバチャについて

概要

drogskol が不定期に開催するバチャ(virtual-contest)
AtCoder:drogskol
codeforces:drogskol

カレンダー

コンテスト予定は以下のリンクから確認できます
Google カレンダー
iOS

参加するにあたって

上記のカレンダーでバチャを開催したい時間帯に drogskol が書き込みます
忙しさにもよりますが、週3~5くらいの開催を目標にしており、二、三日前に書き込むことが多いです

大体の時間が決まったら「未定」と言う名前で書き込みます
「未定」のうちは走るコンテストが決まっていないので、drogskol (@cureskol) | Twitter に声をかけてもらえると走るコンテストを合わせます
codeforces だけでなく AtCoder や yukicoder など、drogskol が解いたことの無いコンテストならなんでも ok です
開始時刻、終了時刻共にある程度融通も効くと思うので、気軽に言ってくれると嬉しいです
並走者がいなければ手をつけてない Div1 などを適当に埋めます

コンテスト後は upsolve も含めて #drogskolバチャ で呟いてくれると嬉しいです*1
感想戦をする人間が欲しくてこの記事を書いているので、何卒

その他

並走者が多い方が開催モチベ、頻度も上がると思うので本当に誰か

*1:これを書くと並走者が全くいないことがバレて恥ずかしい