今日解いた競プロの問題。
ABC209-E: 解説AC。結構いいところまで自力で行けたと思ったのだが。
まずこの問題はアルファベット3文字組を頂点としたグラフとして見ることが出来る。各文字列は有向辺として考えられる。各頂点に0,1,-1の状態を割り振るとして、「どこにも行けない頂点なら0」「0に行ける頂点なら1」「1にしか行けない頂点なら0」とし、0頂点スタートなら先手必勝、1頂点スタートなら後手必勝、-1頂点スタートなら引き分けとする。ここまでは自力で考えられた。-1頂点をどう決めれば良いのかがよく分からなかった。
DFSで実装することにしたが、上手く行かなかった。ループ部の処理方法として「現在処理中の頂点がもう一度参照されたなら一時的に-1とする」という方式をとったところ、サンプルは通ったがいくつかWAが出て落ちた。解説を読んだら「キューを使ってトポロジカルソートっぽくやっていく、ループが絡んで確定できない部分は-1なので単に放置する」という方式だった。そんなやり方でいいのかと思ったがまあそうかとしか言えなかった。
このあたりの原理周りについては「後退解析」という名前が付いているらしい。そういう名前があるのはありがたい。状態遷移グラフにループがある場合の問題としてこの問題は非常に参考になった。競プロの初級問題では状態遷移グラフがDAGになるゲームを扱うことが多いが、そうでないゲームを扱ったのは初めてだった。グラフとして見れるとかこういう条件で先手必勝だとかそういうあたりは自力で分かっただけに、ゲームの特性部分で自力ACを逃したのが悔しい。学びは大きい。
新しいパン屋を開拓した。店の雰囲気が良いし、なかなか美味しく食べ応えもあるパンだった。また行こうと思う。
今日分のRiJを見た。注目して見たのはENDER LILIES、SMB3、マルフーシャ、GeoGuessr、AREA4643、Little nightmareあたり。
ENDER LILIESは自分も100%クリアしたのでどんなゲームか知っているのだが、知っているLilyの動きじゃなかった。確かに幼女のくせに回避運動能力すごくない？とは通常プレイ時から思っていたが、RTAの幼女は極まりすぎて常軌を逸していた。スペシャルがものすごい速度でゴリゴリ溜まるのも見てて気持ちがいい。騎士団長の穢レーザーは大爆笑した。
マルフーシャは雰囲気良さそうだったのでSteamのウィッシュリストに入れておいた。そのうち買う。
GeoGuessrは自分も知っていたやつだったが、プロの動きは格が違った。Google検索くらい使うのかなと思っていたが、全くそんなことはなかった。普通にゲーム画面に開かれてるマップ一本でゴリゴリ位置を特定していく。端的に言って気持ち悪い。ただ、場所を日本に限った上で町名とかをよく把握していれば不可能ではないのかみたいな納得もあった。
AREA4643は中身以上に公式のプロモーションに笑った。そういうところでふざけられる公式は良い公式。
Little nightmareは雰囲気良さそうだったのでウィッシュリストに入れた。走者の一人がVの皮をかぶっているのがやや気になったが、あれで全1,2を争う人らしいので誰も文句は言えまい。いや環境ガバをするのはどうか。
Categories: 未分類