ABC131

途中で測ったら37.2あって調子良すぎだった(若干空回りを感じたので落ち着いて熱を測った意味もある)。Dまでの早解きでとりあえず人権を得たいのだが、最近のABCはそれを許してくれない。

A - Security

問題が表示されるまでに30秒かかった。「連続したほうが押しにくいのか」と思ったのに実装するころには忘れている。双子回でもないのにYes,Noじゃないとかどうなってんの。あらゆる場所を逆にしてしまい時間がかかった。

B - Bite Eating

「なお、この値は一意に定まることが証明できます」ってビビるよね。頭の中で証明を考えて、0を通過するか0を通過しないかだからOKとか(文字にすると何も言ってないな)。とにかく、全体の和から絶対値が最も小さい要素を引けばいい。絶対値と値そのもの両方を記録する必要があるのが意外だった。int b = abs(b);と書いて気づかなかったりした。これはいつものBより難しい。

C - Anti-Division

こういう包除原理ならできます。ということで区間の倍数の個数を求める問題に帰着させそこを書く。最初、ラムダ式の中でbを変化させてしまった(constキャプチャやコピーキャプチャも考えたが使い慣れず自信なかったんだよなあ時間がないから慣れた方法でやるしかない)。ちょっと、区間を1ずらしたほうがいいのかなあとか思ったけど、なんか対称性のあるコードになったのでまあいいか安全側に倒したむしろ危険な汚いコードで提出。まあ時間かかったといっても10分とかだから、こういう境界を考える問題だと仕方ないところはある。実際は、f(t)ではなくf(t, b+1)-f(t, a)でよかった(なぜ思いつかない!!!!いつもこういう書き方しかしたくなかっただろ!!!卑屈すぎるんだよなあ)。

D - Megalomania

なにやら難しそうな問題。N通りの時刻B_iについて、その時刻までに「締切がその時刻と同じかより前のものが全て完了している」必要があり、逆にそれができていればOK。O(N^2)かと思うが、これはBが小さい順に処理していけば(ソートを除いて)O(N)でできる。この計算量の落とし方は、BITを更新しながら利用する難しい問題で覚えがある。この難しい部分に時間を使わずに済んだのがよかった。

E - Friendships

とりあえずサンプル1を手でチェック。まっすぐに並べてよさそうだと思い、とりあえず最大を考える。難しい。S<X<TでSとTの最短距離が2のケースを考えたが、XがSとTに挟まれてなくていいことに気づいてなかった。とりあえず隣同士は辺でつないで、端から多くなりそうな辺の伸ばし方をしていくが、どうもわからない。Fと並列に考えることにする。Dまでは全部解く前提なのでズガガンと1問ずつやっていくが、ここからはまず両方の問題を見て基本順番にやっていくという感じ。

FをACして戻ってきた。K=0のケースを考えて、完全グラフから辺を除いていく方法を思いつく。しかし、除きすぎると最短距離が3になったり∞になったりする。これを解消できない。二部グラフも思いついた。2つに分けて、うーん、細かい調整が難しい。最初のまっすぐに立ち返ったりもしたが、結局何もわからなかった。細かい調整できそうだけど思いついた方法ではできない(つらい)。

F - Must Be Rectangular!

これは見た瞬間面白そう。y座標が同じペア(というか3つ以上でもいい)を持ってきて、x座標がそのどれかと同じ別の点があったら増える。増え始めたらもう全部埋まるんじゃないかこれは。こう、縦横に連結であることで同値類に分けると、それぞれでx座標の種類数とy座標の種類数と元の点の数がわかればいい。単にグラフにすると辺の数をO(N)にするのが面倒そう。ということでUnionFind(まあグラフと同じことなんだけど2方向で隣同士手をつなぐ)。途中でソートするのでやっぱりインデックスも持たせる。N個の点をいくつかに分けるのだが、最大N個に分かれるし、1個あたり最大でN個含むので、O(N^2)にならないようにするのが案外難しい。uf.root(p[i].i)の値でソートして、長さNをいくつかに分けることにした。rootの値でソートしてrootの値で分けるのだが、現在のrootの値とソート済みの中でのインデックスの両方を保持しておく必要があることに気づかなかった(ここは力不足)。コピペしてsy.insert(p[i].x);とかなってたりしたし、ほんと今日はダメ(2回書くほうが悪いとは思うけど)。頭はよく回ってるけど細部に目が行かない。おおらかすぎる。解けた問題に興味がなくなるのはまあいいことだけど。x,yの絶対値も小さいし、もうちょっと簡単に書きたかったけど、F全体としてはけっこういい動きだったと思う。

ぷよぷよクロニクルのBGM一覧

ぷよぷよ音楽データ2
既存の曲(またはそのアレンジ)については、曲名をこちらから引いた。それ以外は適当にそれっぽい名前を入れた(自分で付けた名前には*を付けた)。

SEGA | ぷよぷよポータルサイト | トピックス | 『ぷよぷよクロニクル アニバーサリーボックス』の詳細を公開!
一部の曲はCDに収録されており、曲名が判明している(表には反映させていない)。

新規曲はアリィの歌(みんなみんなだいすき)のアレンジが多い(代表的なのはフィーバーモードの曲)。

初代から「QUEST OF PUYOPUYO」、SUNから「ふつうにあそぼう」、フィーバー(自分はフィバ2で知った)から「いつかの時代…どこかの世界…」、15thから「気軽にとこぷよ」「よくきいてくださいね。」が収録されており、どれもいい曲で、原曲が何なのかを知りたいと思ったのがこのエントリを作ったきっかけ。

対戦 鑑賞 曲名 備考
- 01 *タイトル  
01 02 *メインメニュー  
02 03 *キャラクターセレクト  
03 04 *インターネット  
04 05 時空を超えて久しぶり! 初代
05 06 みんなで対戦!朝までぷよぷよ
06 07 ふつうにあそぼう SUN
07 08 いつかの時代…どこかの世界… ぷよぷよフィーバー*1
08 09 QUEST OF PUYOPUYO なぞぷよ等*2
09 10 気軽にとこぷよ ブロック等*3
10 11 Tokoton from Puyopuyo でかぷよ
11 12 *FEVER!  
12 13 *ビッグバン  
13 14 よくきいてくださいね。 レッスン
14 15 や・ば・い・で・す  
- 16 *ワールドマップ RPGモード
15 17 *チーム / カードいちらん  
16 18 *みどりの村 グリンプ ↓村
17 19 *あおの村 ブルーオ  
18 20 *あかの村 レッティ  
19 21 *きいろの村 イエローム  
20 22 *むらさきの村 パープルーン  
21 23 *カードショップ  
22 24 *グリンプのもり ↓ダンジョン
23 25 *ブルーオの雪道  
24 26 *ホカホ火山  
25 27 *さびれたいわば  
26 28 *パープルーン水道  
27 29 *カーラの塔 色んな曲のアレンジが
28 30 *バトル(通常)  
29 31 *バトル(たのしいぷよぷよ地獄!)  
30 32 *バトル(ボス)  
31 33 *バトル(ラスボス)  
32 34 *スタッフロール1  
33 35 *スタッフロール2(みんなみんなだいすき) ボーカル曲
34 36 *まんざいデモ1  
35 37 *まんざいデモ2  
36 38 *まんざいデモ3  
37 39 *まんざいデモ4 ラスボス前
38 40 *まんざいデモ5 ラスボス後
39 41 *まんざいデモ6  

*1:でかぷよラッシュ・ずっとフィーバーで、フィーバーが切れたときもこの音楽になる(BGMはオン/オフのみ可)

*2:なぞぷよ・ちびぷよはっくつ・はっくつ・こおりづけ・だいかいてん
/ 3DSのVCでゲームギアの初代をやったらなぞぷよで使われてた

*3:ブロック・よんてさき・アクティブ・カルテット

ABC130

開始前36.6、Fを通した後36.8。わりと体温も理想的では?いや上がるのが正常か知らんけど。昨日と違っていつもの感じで参加できたのでよかった。準備をちょっと忘れたりしたがまあ適当に過ごしてた日のほうがいいよね。Dでグダったのは仕方ないけど、流れは4完遅解き(見切り提出に成功したので遅くもないと思うが順位表で見るとけっこう遅い)だった。そうなってしまうこともある。でも調子がいいときは何か起こることが多いもので、Fに注力して通すことができた。嬉しかった。松本「生きててよかった…!」。

A - Rounding

問題文の通りに実装する。状況が一目ではわからないので、問題文を見ながらでないと実装できない。

B - Bounding

跳ねる高さが関係ないんだよね。この問題文は相当読みづらい。1回目はX以下なので、2回目からのN回ぶんをカウントする。問題文が読めれば、いい問題。

C - Rectangle Cutting

こういう問題もっと出題されてほしい。紙の上で色々試すと、中心を通る直線を選ぶことで最大を達成できることに気づく。誤差が許されることにニヤニヤする。さて、(x, y)が中心なら簡単だが、そうでないときに一通りしかないことが証明できない。色々なケースを手で試し、順位表もペナルティが多発してないか一応見て提出(バッドノウハウっぽい)。(解説PDFを見て)中心を通らない場合、通るように回転させれば面積が変化するから、中心を通る一通りしかないですね。こういうのをコンテスト中にちゃんと証明できないのは本当に弱すぎる。毎週コンテストに出て何やってんだ。

D - Enough Array

ド典型しゃくとりじゃんと思ったが、しゃくとりで列挙された区間より短い(K未満のほうを数えて引き算)ものもOKでそれをカウントするというのがひねり。普通に実装したつもりが、サンプル通るものは範囲外アクセスを防げてないように見えるし、自然な感じにコードを直すと落ちたり(ローカルPCでのRE)するので何もわからなくなった。そもそも俺はしゃくとりを書けるようになっていたはずでは?いくら考えてもソースコードの正しさや誤りがわからないので、通りそうなのを提出した。AC。ACとは運の良さである。ここは復習しないとな。実装が理不尽に重い問題はイヤだが、この問題は簡単に書けるはずだと感覚でわかるので復習しがいがある。

E - Common Subsequence

あまり時間をかけていないが、それにしても全然わからなかった。Fを解いているときに間違えてこちらを見て制約の2*10^3に気づいた。O(N*M)を考えると、編集距離的なDPがありそうな形だなと思う。そう思って考えてもわからず。部分列の組のうち整数列として等しいもの。状況が想像しづらい。

F - Minimum Bounding Box

EよりFのほうが解けそうなのでずっとこちらをやっていた。実行時間制限5秒が怖いが。碁石を手で動かして考える。縦と横で片方が増えて片方が減るときを考えると、寄与が大きいのは小さいほうだ(速度は一定なので小さいほうが倍率が大きい)。つまり、小さいほうを減り続けるかぎり移動させ続けたときが答えだ。下端にあるものが全部上に動いていたら減っていて、どこで出会うか。難しそう。いやO(N)を何回も何回もやる二分探索か!なら5秒なのもわかるか?移動方向が異なる2点のx座標が一致するのは0.5の倍数時刻のみ(整数で扱えそう)。とりあえず4方向に分けて1方向だけを考える。減って平らになって増えるという遷移。上下を合わせると-2,-1,0,1,2。と思ったが、境目だけを考えればいいので単に1方向の-1,0,1の2回の変化点だけを知ればいいか。最大値の時間経過による挙動パートとそれをどう使うかのパートがあって両方を気にしながら考察を進めていったが、できそうな見通しが立った。

点をstructにして初期位置と速度を4変数で表す。入力を2倍して受け取り1/4倍して出力すればいいのでそうする(全部整数になるしオーバーフローも大丈夫)。時刻tの指定方向の最大値(-最小値)を返す関数を書く(4通りの向きによってx,-x,y,-yを使う)。あとは三分探索(1秒後までの変化量で二分探索)で切り替わり地点を4方向*2個求めて時刻0を足して9通りを全部試すだけ。ドキドキのサンプルチェックだが、サンプル3だけ負の数が出力される。つまり、おおむね合ってそう。デバッグすると、二分探索で範囲内に答えがなかったときの処理だった。チェックすべき時刻が存在しなかったということなので、そういう値はスキップすればいい(時刻0を追加してあるので9個全てがスキップされることはない)。かなりすっきりしたコードになったのが嬉しい(ていうか、だから40分でACとれたんだよな)。

diverta 2019 Programming Contest 2

開始1時間くらい前に様子が変なので測ったら36.7。なんか「黄色になるなら今回」みたいな気持ちが今回に限って強く、今日はずっと落ち着かなかった。生活の中で色々判断ミスをしていた気がする。そのせいでA問題から全く頭が回ってなかった。C問題を解き始めて少ししたら楽になってきた(汗をかいて体温が下がった)。終了後37.1。たけえなおい。爆死して悲しいというよりは、ともかく普通の生活に戻れてホッとしたという感じ。頭が回ってなかったのは最初の30分くらいだけなのでそれはよかったが、残りのほとんどの時間をCの実装に費やしてしまったのが面白くない。これはどうしようもないのかなあ。

A - Ball Distribution

かなり難しい。全員に配れるだけのボールはあるので、まず全員に配って残りを一人に渡してその渡した人と1個だけの人の差が答え。だと思ったらサンプルが通らない。1人しかいないこともあるのか。今の自分には難しすぎる。

B - Picking Up

めちゃくちゃ難しい。まず問題の趣旨を理解するのに5分くらいかかった。p,qは最初に決めて固定なのね。「p≠0 または q≠0」という条件は最後まで意図がわからず悩んだ(両方0にしてもメリットないんだから答え変わんないよね)(結局無視して解いた)。しばらく紙の上で考えて、移動ベクトルはO(N^2)通りしかないことに気づいた。つまりp,qを全部試せる。180度違うやつが面倒だが、absでいいかと思って実装を始めて、少ししてabsは向きが変わっちゃうからダメと気づいて、pが正になるように(pが0ならqが正になるように)正規化した。思いついたときは全体でO(N^3)かと思っていたが、順番がわからないのでO(N^4)だ。なんかよくわからないので待っても仕方ないってことで提出したがWA。なんも考えてなかったけど全部の辺を検索したらまずかったんじゃ?しかしよく考えると三角形みたいにつながることはない(同じ向きだから)のでこれでよさそうだ。正しそう。正しそうなコードのデバッグが最も難しい。原因はabsの消し忘れだった。同じこと2回書いたからね。まあ頭が回ってなくても解けてるのはよい(さすがにコーディングはきつかったけど)。(tokuminiさんの提出を見て)map使うの頭良すぎか!逆向きのやつも両方mapに入れてしまえばいい。ミスしにくいコードがすごい。

C - Successive Subtraction

3-(1-2)とかカッコを使って紙の上で考える。1つを除き望みの符号にできそうだと気づく。1小さい問題でできていればできるからできるな。引き算なので全部同じ符号にするのは無理。解けた。しかし、実装に5億年かかった。最後のほうになって「なんだ簡単かよ今更すぎる」というのもありがちだが、そういうこともなかった。3通りに場合分けすれば解けるのはわかっているが、それぞれが重い3つを一つもバグらせずに書くのは無理だ。といってまとめる方法も全くわからない。いうて少しは簡単なの思いついて、正の数が2個以上と1個以下に分けた。N=2のケースを常に気に掛ける必要があってしんどかった。出力が独特なのもきつい(意識をそっちに持っていかれる)。0と負の数は扱いが楽で、引いていくだけでいい。正の数が、1個だけならそこから他の数を引いていくだけでいいのだが、2個以上だと面倒になる(だからあの場合分けを思いついた)。これを一発ACした俺の実装力は神懸かってると思った。最初に戻って、符号を決めてやってそれを実現する手順を求めるという方向性はなかったかな。

これを1000人以上が解いてるのは意味がわからない。短時間で解いてるのは魔法かなんかか?ともかく、早々に「解けた」と思ってしまって実装ではまるのは自分にありがちなパターンだ。他の問題に行ければそれもいいが、今回のようなセットだと無理。じゃあ無理か。こういうのは、いい方法を時間をかけて考えたいので、時間に制約がある状況だと単純につまらないんだよね。

D - Squirrel Merchant

22分くらいしかなかったので、いつもとは違う解き方。解法をどんどん決め打ちしていった。1回だけ訪れるBを2回に分解する。Aで金属に換えてBでドングリにする、Bで金属に換えてAでドングリにする。交換の仕方は、有利なものから貪欲に。ドングリは整数個ずつしか使えないので、1種類の金属で済むわけではない。とりあえず提出したがWA。不利な交換はしなくていいのではと気づく。なんにもわかってなくて考えてるのでなんにもわかってない。提出するがこれもWA。そういえば、交換レートが同じでも交換する個数は違っててドングリを捌ききるには順番が大事になることがありそうだと気づく。さすがに2分では無理。今思うと、6通りしかないし全通り試せばよかったか。そして、順番を決めても貪欲に取っていいわけではなさそう。さすがに短時間では無理だった。(解説放送を見て)全部ドングリにするという本質っぽいものを乗り越えたあとに待っているのがDPwwこれは無理ですわw