ABC246 E - Bishop 2 - 01でもdijkstraでもないただのBFSで突破する

atcoder.jp

問題概要: 指定したマスに置かれているナイト（角行）がポーン（障害物）のある盤面を動いて指定したマスに移動するまでに最小何回動かせばよいですか？

提出 (本番AC, 148ms):
atcoder.jp

提出 (本番後, 104ms):
atcoder.jp

まず、本筋にはあまり関係ないですが、スタートとゴールのパリティが一致している必要があります（サンプルの2とかはこれで弾かれます）。盤面を探索すれば分かることなので、する必要はないですが、こういった考察が重要な問題もあったりしますよね。

01bfsでも拡張ダイクストラでも必要なように、「どの方向から来たか？」というのは重要です。簡単な観察として、駒は常に90度曲がり続けるのが最適です。これと、一度に同じ方向のマスを順番に見ていくことで、各マスに対して「この回数で行けたんやけど最短と違う？」の質問を飛ばす回数を減らすことができます。しかし、いい感じに探索方法を構成することで、「いまどの方向から来たか」だけを記憶しておくだけで、各マスに最短回数で行けるときの方向を記憶する必要がなくなります。詳しくは後述します。

BFSとして記憶しておく（キューに突っ込む）のは、「(x,y)座標に方向dから来た」という情報です。このマスからの探索は、dと90度曲がる方向のマスを近い順に見ていきます。まず、枠外にはみ出したらアウトです。障害物にぶつかるのもアウト、その先には進めません。dは実はこの探索方向を決めるのに使うだけで済みます。

次に、そのマスが未探索であれば、操作回数を記録してキューに突っ込みます。単純な考察として、BFSをしているので操作回数が小さい順に記録されていくので、後からの操作で操作回数が更新されることはないですが、ダイクストラを意識するのであれば、操作回数を比較するのもよいでしょう。

それで、最重要ポイントなんですが、見ていったマスの操作回数が現在の操作回数「より少ない」とき、ここで探索を打ち止めてよいです。まず、考察として、「既に操作回数が記録されているマスを見たとき、そのマスは現在見ている方向と90度曲がった方向から来ている」があります。そうでないと仮定すると、現在と同じ方向か180度曲がった方向から来た、ということになりますが前者は現在と同じ探索をしているので矛盾、後者であれば現在の探索の開始地点は既にその方向から探索されていなければおかしいので矛盾します。それで、現在の操作回数より少ない回数でそのマスに到達できたということは、そこから曲がることで現在の探索の操作回数以下の回数で探索することが可能です。

落とし穴ポイントは、現在の操作回数と同じときどうするか？です。これはキューに突っ込みはしないが、探索は続ける、のが正解です。そのマスから曲がるよりも少ない回数の操作回数で探索ができるからです。これを誤ってうちやめにすると奥に探索できていないマスが取り残されてしまいます（実際にやった）。

以上の探索方法によって、各マスについて探索されるのは直交する2方向の高々2回で済み、単純な01bfsよりも定数倍速くなりそうです。本番ではきちんと論理を詰めれず当てずっぽうに高速化を図っていっぱいTLEやWAを生んで無事死亡しましたが、高速化できて嬉しいですね。雑な解説ですが、なにかの役に立てば幸いです。

ABC206E 素因数列挙とbit全探索で正面突破する脳筋解法

問題
atcoder.jp

提出
atcoder.jp

として、後から2倍します。xを固定したときのyの個数を素直に求めます。
条件より、xとyは公約数gを持ち、これはxではありません。したがって、xは合成数である必要があります。

とします。
約数のうち素因数に絞って、
となるようなyの個数をそれぞれ求めて足し上げればよさそうな感じがします。
しかしこれはダメです。 となるような場合に重複して数えているからです。

したがって約数全部を考えたほうがよさそうになります。しかしべき乗の部分は、べき乗がついていないもので完全に覆えて明らかに邪魔なので無視していい気がします。したがって素因数の積f全部2^n個を考えます。
10^6以下の数の素因数の個数はクソ少ないことが知られているので、bit全探索で間に合います。

のとき、yは2^n回重複して出現します。af=1はアホなので2^n-1回としてよいです。
ここで、だいたいこういうときは偶奇によってプラスマイナスを変えるといい感じになるという気持ちになります。
後からしっかり考えると、
(1-1)^n = -nC0 + nC1 - nC2 - ... nCn
より、
nC1 - nC2 + ... nCn = 1
みたいに証明できます。やったね。
すなわち、素因数の積fでループして、|x-y| = a*f となるようなyの個数を数え上げていくわけですが、素因数を奇数個選んだ場合は足す、偶数個選んだ場合は引くことでいい感じに重複が消え去ります。包除原理とかいうやつです。

これですべてが良さそうに見えますが、最後にg=xの場合を除く必要があります。除くだけです。
あとはとしたので2倍してください。

以上よりコードはだいたいこんな感じになります。
エラトステネスの篩を使ってRまで素数と合成数を判定して素因数を列挙
xをL~Rまでループを回して固定
xが素数ならパス
bit全探索で素因数の積f全部をループ
となるようなyの個数を数え上げ、fの素因数の個数が奇数なら足す、偶数なら引く

以上により正面突破ができました。なおコンテスト中は考察が間に合わなかったのでg=xの場合を包除原理中で処理しようとして爆発しました。みなさんは正面突破しないようにしましょう、以上です。

AtCoder青色になりました

ABC188を1時間で終わらせて過去最高順位がほぼ確定したので余裕ぶっこいて色変記事を書くマン、だいたいこういうのって1年ぐらいで達成できたレベルで書けばいいんでしょ？（よく知らない）

スペック

私立中高→東大理1（ペンシルパズル同好会）→計数工学科→数理情報学専攻→プログラマ

このスペックの中では普通（以下）の人だよ！どこいっても優秀な人間に囲まれているのに発狂してなくてえらい！（だいたい察して）

タイピングをまともに学ばずに手癖でやっているので2本指打法（2本指にしては速度がある）。

精進量

https://kenkoooo.com/atcoder/#/user/AsamiCrayon

2020年2月から始めて1300ACぐらい、ABCのAB、ARCのA、難易度は水色まで全部やった感じで今は青を潰したり色がついてない個人コンテストのとかをやってる。毎日ACはしてない。業務中の暇なとき（）に考察して家帰って＋休日で実装が多い。AtCoder Problemsは神。

茶色とか緑ぐらいのをサクッと書いて遊ぶために始めたのに茶色とか緑が枯渇して悲しい。

お作法

C++使い。お道具箱全部ぶちまけるなんか魔法のコトバがあるらしいんですが気持ち悪いので使っていません。スニペット？コンテスト開始時の状態は以下です。あ、ACLはよく使います。

#include <iostream>
using namespace std;

int main() {
}

よく使うので別に保存してるやつ（いちいち書くと長くなんないこれ？）

bool IsOneBit(long long bits, int i) {
	return (bits & (1ll << i)) > 0;
}

提出したコードは最初は難しかったやつとか保存してたんですが、見返すことがないので最近は容赦なく消してます。

使えるアルゴリズム・データ構造

競技プログラミング始めて新しく知った感じがあるのは累積和（＋いもす法）、ダブリングぐらい？いもすはなんか再発明した記憶がある。DPとかグラフアルゴリズムとか大学で習ったけどそこまで実装してなかったので競技プログラミングで身に付いた感じはある。微妙に業務にも役立ってる……？役立ってるといいな……。ACLにあるのは実装できないけど使えるようになって嬉しい（実装できるようになる気はしない）

お気持ち

茶色はAtCoderの操作方法がわかれば取れる（提出する言語を間違えないなど）ぐらいの気持ちだったんですけど最近はレベルが高くなってる気がしますね、これが緑～？みたいな問題が多い。水色ぐらいはサクッと行けてまあ緑がサクサク解けるぐらいだとそんなもんかなと思いました。青は正直目指してなかったんですが水色がそこそこ解けるようになると狙えるようになりました（当たり前感）。早解きは別にやりたくないんですが、できると顕著にレートが上がりやすいのでできるとよいですね。

色変記事を丁寧に書ける人は羨ましいですね。私は何を書けばいいかもわからん。だいたい競技プログラミングに関して書かれるべきことは既に書かれてないですか？

正直青を維持できるか微妙なのでほどほどで頑張ります。私は緑とか茶色を解きたいだけの人です。

AGC049 B

これが緑なんてたいがいにせえよ

問題
atcoder.jp

公式解説
atcoder.jp

マイ提出 (C++)
atcoder.jp

SとTの累積xorを取ると見やすくはなるがあんま本質ではなさそう。見やすいので以下累積xorで考えます。

まず最初のS, T不一致点 i まで移動します。それより左は問題に関与しません。
S 0000001
T 1101001

不一致点 i を一致させるにはSのS[i]と異なる文字が存在する最小の j > i から移動させるのが最小手筋です。そのようなjが存在しないとき解なし。操作回数はj-i。操作後はこう
S 1111111
T 1101001

i ~ jはすべて同じ文字となったので、次の不一致点 i' に対応する j' は j' > j となります。したがって、尺取法的に次のi', j'を探していけば O(N) で計算可能です。

答えは O(N^2) になるので int では不足します (1WA)。

ABC177 E

問題: atcoder.jp
本番提出: https://atcoder.jp/contests/abc177/submissions/16355934

エラトステネスの篩でいい感じにsetwise coprime, pairwise coprime, not coprimeを判定したいです。

not coprimeは「ある素数ですべてのAが割り切れる」であり、pairwise coprimeとは、「任意の素数で割れるAは高々1個」であり、setwise coprimeは「not coprimeではない」かつ「ある素数で割れるAが2個以上ある」であることがわかるので、長さ1000001の配列にAとして出てきた個数を数えて、エラトステネスの篩をしながら割れたAの個数を求めれば一度に判定ができます。

このとき、A=1の個数は条件判定に影響を及ぼしません。A=1があるとき無条件でnot coprimeは成立せず、pairwiseかsetwiseかの判定ですが、上に書いた条件が保たれています。

本番でミスした点は、「ある素数で割れるAが2個以上あり全部ではない」をsetwise coprimeだと思ってしまったことで、これは6, 9, 12の場合に2で6と12が割れるからsetwise coprime！みたいなことをしてしまいました。それより大きい素数で全部割れる可能性があるのでフラグだけ立てて最後に判定すればよいです。

例
A=[3,4,5]
Nums = [0,0,0,1,1,1,0,0, ...]
Primes = [1,1,1,1,1,1,1, ...]（Primes[n]=0ならnは素数でない）

p=2
num = Nums[2]+Nums[4]+ ... = 1
Primes = [1,1,(1),1,0,1,0,...]
p=3
num = Nums[3]+Nums[6]+... = 1
Primes = [1,1,1,(1),0,1,0,...]
p=5
num = Nums[5]+Nums[10]+... = 1
Primes = [1,1,1,1,0,(1),0,...]
p=7
num = Nums[7]+Nums[14]+... = 0
...

numは一度も2以上にならなかったのでpairwise coprimeです。

計算量はO(max(N) loglog max(N)), max(N)=10^6で間に合います

算数パズルをプログラムに解かせたい

次の□に＋か－を入れて等号が成り立つようにしなさい。
0□1□2□3=4

こういうパズルを業務で作ってるわけなんですが、作為を考えつつ別解がでないようにしててもどこかで見落としをするので、プログラムに確認させたい、という気持ちがある。

入力は整数列(a1,a2, ... an)と右辺の整数値で、演算子は加減乗除と「結合」（たとえば1□2が12、12□3が123となる、左が0の場合はなしにしたいけどプログラムで除外するほどのものではない）があるとする。

実際の問題では使える演算子は上述の問題のように限っているのだが、大した出力にもならないので、そこらへんは目でやることにする。色々やれば探索の枝刈りとかできそうな気はしたが、面倒くさいしどうせn<=7程度なので、全探索しても死なないので全探索することにした。こういう問題ならCとかで書いても良さそうな気はしたんだけども環境構築がだるかったので、他の業務にも使ってるHSPでやることにした。

nが入力を受け取るまで不定な以上、各□の多重ループで全探索は無理っぽいのは何となく分かる。それで最初は再帰関数を使ってやろうとしたが、配列を変数にわたすとかうんぬん考えてたら死にそうだったのでやめた。数列と答えを受け取って、実現できるかどうかを返すみたいな。あと、結合→乗除→加減の順で計算しなければいけないあたりでも死を招きそうだ。

全探索するので、とりあえず全通りの数を出せば良い。5^(n-1)である。あとはこの数を5進数表示にして演算子列に変換する。あとは結合→乗除→加減の順で順々に計算していく。ここらへんの作業用数列/演算子列と元の数列/演算子列の扱いだとか、どの演算子を見ているかあたりの扱いを適当にやって壮大に死んだが、なんとかした。コピペまみれの糞コードで250行ぐらいかかったけど間違ったことはしてなそうだし、よしとする。

「お金を入れてね！」

普段使っているスーパーには、簡単なゲームコーナーがあり、ガチャガチャとかチューインガムが貰えるよくわからん機械が置いてある。その中に、プリチャンが鎮座している。悲しいかな、地方小都市のスーパーマーケットの客層はほとんどがジジババで、ついぞこのゲームが遊ばれているところを見たことがない。一度だけ、「ボタンを押すのは楽しい！」ということに気が付き始めた頃の男児が金も入れずボタンを連打していたのを見たっきりである。よしんば、対象年齢の女児がいたとしても、買い物の付き添いに来ただけの子供が、ナマ物を腐らせたくない母親を言い含めて、ジジババの前でゲームに興じるということの難易度が、ゲームそれ自体の難易度よりもはるかに高いことは想像に易い。アイドルになりたい女の子も、地方営業なんて別にしたくないのだ。しかるに筐体の中の女の子たちは、今日も周りのジイサマバアサマに向けて空虚な声を上げ続けている。

最近のああいう筐体は、おそらくカメラがついていて、目の前に人が立っているときと立っていないときで微妙に宣伝の内容が変わるらしい。目の前に立っている人は少なからず興味を持っているのだろうから、より積極的にゲームをプレイするように求めるのである。ただ、あまりに小さすぎてサッカー台（というらしい、あの荷物詰めるスペース）の真後ろに置かれているプリチャンは、荷造りを終えて通り過ぎるジイサマバアサマに反応して声をあげるのである。

「お金を入れてね！」

昨今の基本無料ゲームに慣れきった子供たちにとっては、お金を払わなければ遊べないゲームが存在することを知らないのかもしれない。あるいは、お金を入れずともある程度進んで途中からお金を入れるシステムだと思っている子供もいるのかもしれない。そういった子供に向けた言葉なのだろうか。あるいは、遊びもしねえくせにゲームの前に陣取ってんじゃねえぞという脅しであるのか、色々な気持ちが込められているのかもしれない。

「お金を入れてね！」

それにしても、なかなか「お金を入れてね」とは日常生活で使うことのない文章だ。1000円カットの券売機の使い方がわからんジイサン相手にしか使っているところを聴いたことがない気がする。それも、お金を入れる客と、入れられる機械、説明する店員の3人がいる状況で使われる言葉だ。プリチャンはお金を入れられる側であり、説明をする側なのだ。そしてまた、ゲームの中の彼女たちは決してその世界の内だけで生きていれば、発することがない言葉だ。いかに彼女たちがアイドルといえど、ファンに向かって「お金を入れてね」とは言わない。ゲームの中の世界から、わざわざこちらの世界の事情を汲んで、メタな発言をしているのである。いったい声優はどういう気持ちで「お金を入れてね」を収録しているのだろう……。

「お金を入れるのかしら？」

いや待て。
それはなんだ。「お金を入れるのかしら？」、それを、尋ねるのか？俺はプリチャンのことは全くわからんが、このセリフから、このキャラクターがおそらくはお嬢様で、ちょっと高飛車なところがあるキャラクターなのだということぐらいは、超絶リテラシーをもって理解することができる。プリチャンが好きな女児もまあ知ってるんだろう。こういうキャラクターは、お金の要求なんかしない。お嬢様だし。こういうキャラクターが「お金を入れてくださいね」とか言おうもんなら、没落からのにゃんにゃんな薄い本の展開まで読めてしまう。こういう現実に存在しなそうなお嬢様キャラクターは多分女児受けもいいんだろう、多分。だからわざわざゲームプレイの要求にまで出しゃばらされているのだ。その、落とし所が「お金を入れるのかしら？」なのか。「まあ、私はあなたがプレイしようがしまいが好きにすればいいとは思うけれど」ぐらい前置きとしてついてきそうだ。でも、こんなコンテクスト、女児には読めないだろ。「そうだよ！入れると遊べるんだよ！」って毎日どこかで答えている女児がいるんではないか……

通り過ぎ去ったジイサマを見失ったしゃべる箱は、また目の前に人を呼ぶ宣伝へと戻っていった。多分着せ替えた後、リズムゲームかなにかするんだろうけど、お金を入れていない私にはそこまでの説明なんてしてくれず、女の子たちが笑顔で歌を歌っているのが流れるのみである。