灘中入試コンテスト　解説

maguro

今回のコンテストはどうでしたか？

・このスライドでは僕が作った問題を解説したいと思います

・他の人の解説はyukicoder上にも上げられると思います

Day1 A - Calculation

解説

書かれている通りに計算しましょう

​

裏話

今年の入試で入ってくる生徒が79回生（灘では学年毎に回生が決まっている）なので答えが79になる問題を作りましたが、多分誰も気付かないですよね…。

​

Day1 C - Typical Shortest Path Sum

問題概要

N頂点M辺の重み付き有向グラフGが与えられる。Gは自己ループ、辺の重みの総和が負になるような閉路を持たない。

このとき、それぞれの頂点i(1 <= i <= M)について次の問いに答えよ。

・頂点iからいくつかの頂点を通って到達可能な頂点jについて、jに行くまでの最短距離の総和はいくらか？

​

制約

・2 <= N <= 100

・1 <= M <= 9900

・-10^12 <= 辺の重み <= 10^12

解説

・Nが小さいのと、任意の頂点i,j (i ≠ j)について最短距離を求める必要が出てくることから、ワーシャルフロイド法を使えば良いことが分かる。

・なので、ワーシャルフロイド法を使ってから、それぞれの頂点について、到達可能な頂点について答えの変数をもってそれに足していくことで答えが求まる。

本当に？

・蟻本のやつをそのままパクるとWAします（これで焦った人も多いのでは？）

・螺旋本のやつはパクってきても大丈夫です

・サンプルにはわざと全部合うケースを入れました（邪悪）

本当に？

・どうしてWAするのかというと、負の辺があるからです

・dist[i][j] = 頂点iから頂点jまでの最短距離　と定義して、最初にdist[i][j] = INFで初期化すると、到達可能ではないのにdist[i][j] < INFとなる場合があります

・これに関しては実際にケースを実行してもらった方が手っ取り早いです

・「ワーシャルフロイド　負の辺」について調べるともっといい情報が得られるかも？

​

対処法

・三重ループの内側にdist[i][j] != INFかどうかのif文を追加する

・最後に到達可能かどうかの所でif(dist[i][j] != INF)というif文をif(dist[i][j] <= INF / 2)という風にする（INFの値によっては危険かもしれません）

感想・裏話

・この問題が出来た経緯としては、僕がAOJでワーシャルフロイド法のライブラリをverifyしてるときに全然合わなかったことから、多分これ対策してる人少ないんじゃないかなと思って出しました

・案の定めっちゃWAしてて面白かったです（最悪）

・テストケースには多重辺が存在します　存在しないようにジェネレーターを作ったはずなんですが、なぜか入っていました　ごめんね…

・開始1日前には実は負閉路が入ってるケースがありました　ヤバすぎ

・あとグラフの生成についての情報がネットに全然無いのヤバない？誰か作ってください（他人任せ）

Day1 D - Beautiful BINGO

問題概要

N×Nの謎解きビンゴがあり、上からi行目、左からj列目のマスを(i,j)とおく。

マスには謎が書かれていて、(i,j)のマスを空けるためにはA_{i,j}の知力を消費してそのマスの謎を解く必要がある。

このとき、M個のビンゴを作るために消費する知力の最小値はいくらか？

​

制約

・1 <= N <= 16

・1 <= M <= 2 * N + 2

・1 <= A_{i,j} <= 100

お気持ち

・O(2^(N * 2 + 2))のbit全探索は出来る

・でもN <= 16なのでこのままだとTLEしてしまう

・どうする？

・斜めと縦でビンゴするやつをbit全探索で固定してやったら横は貪欲に取っていけばオーダーが減るのでは？

解説

・前ページのスライドに書いた通り、斜めと縦でビンゴするものをbit全探索して固定しましょう

・もう開いたマスはA_{i,j} = 0として、i行目のマスを全部開くのに必要な知力をO(N^2)で計算します

・後は小さい順に答えに足していって、その最小値を求めればいいです

裏話

・多分気付いている人も多いと思うんですが、元ネタはBeautiful BINGOという謎解きです　面白い謎解きなので是非解きましょう～～

・もともとN <= 8（縦横斜めをbit全探索）だったんですがblackyukiがN <= 16の解を思いついたので引き上げました

最後に

いかがでしたか？

結構作ってて楽しかったです

問題文、かなり定義が曖昧になったり数学的に不味かったりする部分があって結構Kodamanに指摘されて直してました　もっと良い問題文が作れるように頑張ります

あとコンテスト作業は計画的にしましょう　かなり日程ギリギリになります

来年もやろうね！（圧）