改訂後のABCの話

水色昇格からサボってた期間がいろいろあって、いまだに水色です。

どこからか忘れましたが、ABCとARCが統合されました。

A-D問題までのABCと、C-F問題のARCの統合ですが、実質的には、ARCの開催回数が、ABCに合わせて増えたという認識をしています。

順位自体は当然以前のABCより出づらくなりましたが、パフォーマンスは逆に出やすくなっていると考えています。

twitterなどでも言及がありますが、問題は少し易化しているようです。

これは、Atcoder Problemsなどを参照すると、たしかにそのように思えます。

しかし、パフォーマンス的には問題があるとは言えず、Dまで解けても1300程度のパフォーマンスしか出ないため、ランクの上がりやすさに影響しているとは考えていません。

しかし、ここ2回のF問題に関しては、本来それ以下であるはずのD問題・E問題と比べて簡単だったではないかという印象を受けます。

実装の難しさなどを考えても、ABC146のFなどはDより簡単と言えます。

同じく、実質次回のSMTB回でも、私はF→E→Dの順番で解きました。

求められる適正は実際に異なると考えられますが、現状でFのほうがDより難しいと考える人の意見が読んでみたいところではありますね。

とはいったものの不満があるというよりは、これでパフォーマンス出てしまっていいのだろうかという疑問のようなものが中心ですので、出題傾向がどうなろうと出続けることに変わりはないかなと思っています。

急に超絶難化してD以降何もかも解けないとかになったらそれはそれで考えますけど。

あとは、ProblemsなのかはわかりませんけどAC数の話を見かけたのですが、私が今795なんですよね（ARCのAやらで水増しはしました）。

ここを仕上げるには旧ARCのE・F問題に手をつけていかなければいけないかなあと思っているところと、過去に解いた問題を整理することかなというところです。

私は記憶力が悪いほうなので、これはキューイングを使った幅優先探索をするといいよ、といわれてもその実装方法が思い出せなかったりします。

その時のコードを引っ張り出してくれば、それをいじって答えを出すことはできるのですがまあなんか難しいですね。

現状1400で水～青の折返しといった状況ですので、もうひと踏ん張りがんばっていきたいです。

ABC142

寝てたのでリアタイできず。

F問題の話

https://atcoder.jp/contests/abc142/submissions/7797670

閉路が存在しない場合は、-1を出力すればACになります。

閉路が存在する場合、正規の解答ではなく、おそらく-2以下の数値を入力することでもACになってしまいます。

問題文を読む限りでは判定器のバグに思えます。

以下、実際に解いていた時の話。

解説読んだけれど実装がわからず、とりあえずいろいろ調べて閉路検出はなんとなく理解した。

DFSで再帰関数を回し、閉路が見つかったらそれを一時的な回答として保存して終了。

その後、閉路の中の接続点を見つけて小さくしていき、問題の条件を満たせばクリア、というところまできてうまくいかない。

ここで、コンテストは終わっているので、一旦解答を探ってみることにした。

閉路がなかった場合、「-1」、

閉路が存在する場合、「-222」、

を投げることで、閉路を正しく検出しているかどうか確認しようとした。

この時点では、-222はすべての問題においてWAとなることを期待していた。

ところが、予想と違ってACが多すぎる。WAが2つしかない。

いろいろ調べたところ、閉路の検出部分に誤りがあることがわかったので該当箇所を修正した。

その後、閉路がなかった場合「-1」、存在する場合「-99999」を出力する形で提出したところ、AC。

この時点で判定機のバグっぽいなあということをボソっとツイートした。

閉路を短縮する部分の効率が悪かったのでそこらへんを書き直して正規ルートでもACが出せたので終了。Python3とPyPyの速度問題で悩むのもだるいなあという感じがしたのでしばらくはGolangを練習するつもり。

Surface Pro 6で回復ドライブが動かなかった話

最初にいつもどおりフリーズし、再起動する旨のブルースクリーンが表示されるが、白いWindowsロゴから先に進まず、UEFI画面へと戻される。

右上には、HDDにXがついたようなアイコンが出ており、この時点でかなり不穏。

というわけでここらへんを参考に回復ドライブの作成を試みる。

https://support.microsoft.com/ja-jp/help/4023512/surface-creating-and-using-a-usb-recovery-drive

結論からいうと動かなかった。

白いWindowsロゴと、たまに読み込み中の白い輪が出たり出なかったりする程度で、１時間以上暗転を繰り返して最終的にUEFIの画面に戻るの繰り返し。

Bootメディアも、内蔵ディスク・外部USBドライブ・PXEネットワークブート・Windowsブートマネージャと全種類試すが結果はかわらず。

回復メディアの上書きが間違っているのかと思い、普通に別のWindows10で作成した回復メディアを差し込んでも結果は変わらず。

で、これらの回復メディアをThinkpadに差し込むと普通に起動メディアとして認識してくれる。

この時点でSurfaceのUSB差込口に問題があると考え、状況をまとめてサポートに投げたところ、交換対応になるという返答が帰ってくる。

ただ、念の為回復ドライブの中身を確認させてほしいということでリモート接続をつなげることになり、デスクトップを片付けている間に接続が切れてやりなおし。

問い合わせ開始時に表示されるURLは必ずメモしておこう。

その後、交換になった場合のためにSSD全消去用のUSBドライブを作成したところ、こちらは正常に作成され、起動もできた。

ただし、16GBのほうでは動いたのに64GB（USB3.0）のほうでは動かないという謎の現象が発生している。

Windows10のインストールメディアを作るみたいなツール（MediaCreationTool）もあったのでそちらをつかったところ、そちらは起動した。しかし、復元やスタートアップの修復などの項目は起動しない。

ここでクリーンインストールを試みようとするが、ドライブが確認できなかったため、SSDの故障と判断。

残念、私の冒険はここで終わってしまった。

ちなみに本当にインストールが可能だった場合でも、途中でインスタンスIDを要求されるため、回復ドライブが必須になるとかなんとか。なのでインストールメディアからの復帰はできないらしいです（MSのサポート曰く）。

データ全消去も失敗したからアクセスかディスクが死んでるんだけど、取り外せるタイプのデバイスじゃないから保証の範囲内での切り分けはできないですね。

というか、SSDが死んでいると回復ドライブが起動しないのがトラップすぎた。

ちなみにUEFIの右上にXのついたHDDアイコンが表示されている場合は、ディスクの読み込みエラーらしいです。当然、しっかり表示されてました。

Pythonのlistで速度が出なかった時の話

ABCの過去問埋めをしていて、Listかそうでないかで速度が変わるケースがいくつか発生したのでメモとして残しておく。
結論から言うと、Listへの追加・削除は非常に遅いため、他の方法があるならばなるべく回避すべきである。

①heapq

値を追加して最小値を取り出す、という処理を繰り返す場合において、リストへの追加＋bisectなどによる処理を行うよりも遥かに高速である。
実際にはリストの追加・削除自体がかなり遅いらしい。

ABC 062 D問題 3N Numbers
https://atcoder.jp/contests/abc062/tasks/arc074_b

この問題は部分点アリなので非常にわかりやすい。

試しにn=100,000で、3n個のランダムデータを内蔵したテキストを入力とし、比較を行った。
なお、ソースコードはそれぞれの入力部分をテキストファイルからに変更し、実行時間計測のためのtime.time()を追加したものを使用している。

heapqで実装したもの
https://atcoder.jp/contests/abc062/submissions/4502768
0.4147450923919678秒

list+bisectで実装したもの
https://atcoder.jp/contests/abc062/submissions/4502582
7.703240633010864秒

このサンプルケースは制約の上限値に近いものだが、問題の設定は2秒であることから、heapqで実装した場合はAC、list+bisectで実装した場合はTLEとなった結果と合致する

動作的には1個消して1個挿入するという動きを繰り返しているのだが、どうやらリストの場合はこの処理が重くなるらしい。

bisectなどの部分も関係ある可能性があるため、追加削除を繰り返すスクリプトを作成してみた。

heapq_test.py

import heapq
import time

start = time.time()
f = open('test.txt', 'r')
n = f.readline()
hoge = list(map(int, f.readline().split()))
f.close()

print(time.time() - start)
start = time.time()

for _ in range(10 ** 5):
hoge.append(999999)
del hoge[0]

print(time.time() - start)

f = open('test.txt', 'r')
n = f.readline()
hoge = list(map(int, f.readline().split()))
f.close()

start = time.time()
fuga =
for x in hoge:
heapq.heappush(fuga, x)

print(time.time() - start)

start = time.time()
for _ in range(10 ** 5):
heapq.heappush(fuga, 999999)
heapq.heappop(fuga)

print(time.time() - start)

出力：

0.12592029571533203
12.666174411773682

0.06795763969421387
0.07295346260070801

偶数行目が実行時間だが、この内容だとheapqのほうが圧倒的に早い。
なお、空のリストに1個の要素を追加・削除することを繰り返した場合は、heapqのほうがむしろ遅かった。
bisectとは異なり、末尾に追加・先頭を削除を繰り返しただけなのに、である。
ちなみに、追加する数は適当に999999にしているが、1にした場合でもほぼ同じである。
追加場所は固定なので、listのパターンにおけるソートの有無は関係ないといえる。

なお、奇数行目は読み込みにかかった時間だが、3行目のheapqは実際には1行目のリストのものを足しただけの時間がかかっている。

さて、さらに問題になりうるソートの時間をみてみる。

import heapq
import time

f = open('test.txt', 'r')
n = f.readline()
input_list = list(map(int, f.readline().split()))
f.close()

list_test = + input_list

start = time.time()

list_test.sort()

print(time.time() - start)

start = time.time()

heap_test = []

for x in input_list:
heapq.heappush(heap_test, x)

print(time.time() - start)

結果：

0.13991212844848633
0.06795597076416016

準備段階ではそれほど差は出ていない。やはり追加・削除の部分で大きな差が出るようだ。

②set
追加・検索を繰り返す場合、setのほうがlistより早い。

これは、1つのlistをsetに変えただけだが、それだけでTLEからACになっている。

https://atcoder.jp/contests/abc116/tasks/abc116_d

https://atcoder.jp/contests/abc116/submissions/4417704
https://atcoder.jp/contests/abc116/submissions/4417808

②collections

該当するものをリストから削除する形でカウントしていく構成でTLEになったパターン。collectionsのCounterを用いてそれぞれの要素数をカウントすると、追加・削除ではなく値の変更処理になるため、高速になる。

https://atcoder.jp/contests/agc029/tasks/agc029_b

from collections import Counter

n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)
c = Counter(a)

ans = 0
for x in a:
if c[x] == 0:
continue
temp = (1 << x.bit_length()) - x
c[x] -= 1
if temp in c.keys():
if c[temp] > 0:
c[temp] -= 1
ans += 1

print(ans)

ここまであげたものはほとんどの場合制約があるため、他のパターンで利用したい場合はまた考える必要がある。

ちょっとしたCSVファイルの処理で使うなど、大した量の計算を行わないならばリストで書いてしまってもいいだろし、そちらのほうがシンプルに書けるなら多分そうする。

ABC119

A - Still TBD

5-6文字目を取りだしてintに変換して4と比較するだけ

B - Digital Gifts

数値と文字列の複合入力のためやや面倒くさい。

しかも数値がintとfloatの2パターンある。

全部floatにしてもいいけど、先に通貨で場合分けして処理した。

C - Synthetic Kadomatsu

同じ長さのものがあれば除外して・・・と簡単にする方法を考えていたが

組み合わせをどう処理するかがわからず一旦放置。

D問題を解き終わった後でパターン数を計算したところ、4^8で65536通りしかないことがわかる。

ということで全探索。カウンターの数値を4^n回まわし、modをとりながらパターンを生成する。0-2がa,b,cにそれぞれ使う、3はどれにも使わないを示す。得られた答えが最小なら更新を繰り返す。

何本継いだかを見るために、a,b,cのそれぞれに使われた竹の本数も記録しておく。0のものがある場合は、答えの計算を行わない。

この方針でサンプルを回したところ、n=8でも十分に間に合いそうだったのでそのまま提出。結果AC。

D - Lazy Faith

ぱっと見てbisectを使うやつかなと判断

神社・寺をソートしたあと、bisect_leftで、どの神社（or寺）の間に入るかを割り出す。

その後、神社・寺をみつけるために左右のどちらにいくかで2x2の4パターンを計算し、最小のものを探していく。左右に該当する施設が存在しない場合は十分に大きな値を設定して除外されるようにする。

この方針で間に合ってAC。

久しぶりに完解1600。

からの水色昇格！落ちないようにじゃなくて、青になれるように頑張っていこう。

ABC117

また間が（）

A - Entrance Examination

T/X

B - Polygon

max(L) < sum(L) - max(L)

問題文に答えが書いてあるような状態

C - Streamline

M<=Nの時、０

そうでない場合、座標間をM-N回移動する必要がある。

それを最小にしたいなら、Xをソートして隣り合う座標間の距離を求め、

その距離をさらにソートして小さい方からM-N個の合計を求めればよい。

D - XXOR

Cが簡単だったのでナメてたらハマった。

まずは２進数を１ビットずつ数にすることを思いつく。

そして、多数決で少ない方をXの該当桁のビットにすればよいこともすぐわかった。

ここまでは公式の解説と同じことをしているのだけれど、X<=Kがうまく処理できなくて80分試行錯誤しつづけても終わらず。

Xの各桁のビットを1にする場合、増えるXの数値と、増えるf(X)を求めて大きなナップサック問題にできないか？とか考えていたのだけれど、0にする場合の基礎点の処理（上位桁に1が存在しないとその0の桁の数値は適用できない）などの問題があり、正しい解を求める方法にたどり着けなかった。

ということで未提出。

結果は532位で+29の1193。今回も水色に上がれなかった。。。

ABC113

また間があいてしまった。

出るつもりはあるんだけど幸か不幸か週末に用事がある事が多く、平日に問題だけ解くパターンが中心になっていた。

ABCの400問題はだいたい解けそうな感じになってきたので、ARCの600+に手を付けられるようにしていきたい。

問題はABCばかり出ていてratingが上がるのかという話ですが。

A - Discount Fare

X + Y/2（ほぼ自明）

B - Palace

正解の値とAとの差の絶対値の両方を保存する必要があるのでB問題にしては面倒だなあと思いつつ普通にn回のループさせて終わり。

C - ID

ソートしてそのまま出せば良いわけではないのがやや面倒だなあという印象

年度が同じものが、県をまたいでも存在しないというのがありがたく、年度の情報をキーとした辞書型にインデックスを格納していく。それと別に、答えを格納するための初期化された配列も用意しておく。

その後、県ごとに市のリストを作ってソートし、中に格納されている年度情報からインデックスを呼び出して、答えを格納するための配列の該当するインデックスに格納していく。

ここまで書いてから走らせたら普通にサンプルが通ったのでそのまま提出してAC

D - Number of Amidakuji

全探索すると2^800なのでまあ無理。それを実装することすら面倒。

経路ごとに見ていこうかと思ったが、あまった枝の処理の数え上げが難しいのではと感じて少し悩む。

しかし、よく見るとW<=8という条件がついているため、あまった横棒の候補地は、最大でも7区画分である（1本目からそのまま直上する場合、2~8本目の間は、2個連続しなければどのように横棒を付与してもよい）。

ということでX区画分についてX-1から順に手で計算していると、3>4にするあたりで、これは3-4間に棒を置かなければX=3通り、置いたならばX=2通りとなり、フィボナッチ数列となることがわかった。（Wが小さいため手でベタ書きすることにした）

それがわかればDPを作るのは簡単。

dp[i][j] = dp[i-1][j] * X + dp[i-1][j-1] * Y + dp[i-1][j+1] * Z

X .. 左右1区間を除く領域に存在しうる横棒のパターン

Y .. 左1区間と右2区間を除く領域に存在しうる横棒のパターン

Z .. 左2区間と右1区間を除く領域に存在しうる横棒のパターン

これらX, Y, Zはさきほどのフィボナッチ数列の要素の積である。

ただし、W>=3を前提としないと左右を考えたときにつきぬけてしまう可能性があったため、W=1が自明に1であることのほか、W=2についても調べる必要があった。

無駄にDPを書いていて、これ2^(h-1)じゃない？ってなったので1~3くらいまで試したらまあそうだろうなという感じになったのでそのように書き直してサンプル問題をテスト。

そのまま提出したら一発でACでノーミス完解