horoyoisawaのゴミ箱

いろいろ書きます

KUPC2020に参加した話

KUPC(Kyoto University Programming Contest) 2020 Springに参加した。

最初の方は結構意識があったが後半になればなるほど、意識が遠のいていく。。。(寝てないですよ)。5時間は長いというのが率直な感想。体力がただただ欲しいと思った。訓練するしかなさそう。

とにかく結果は3/14問。みんなが解けてそうな問題に手を出して解いて行った感じだ。自分が解けた問題を最初にみていく。それ以外の問題については今回は触れない。(おそらく後日記事にまとめるが。)

問題はこちら。

onlinejudge.u-aizu.ac.jp

A. Team Making

チーム分けをする問題。4人を2人、2人に分ける。その時、各チームメンバーの合計をチームのレートとし、そのチームレートの差の絶対値を最小化する様にチーム分けをする。

これは簡単で入力をvectorで受け取ってそれをソート、求めるチームレートの差の絶対値の最小値はa[0] + a[3] - a[1] - a[2]で求められる。

B. Don't Rotate the Dice!

サイコロを回す問題。グリッド上には数字、もしくは#(シャープ)が書かれている。このグリッド上でサイコロを転がしていき、(1, 1)から(h, w)まで転がせるかどうか判定する問題。しかしいろんな条件・制約がある。

  • #(シャープ)の上にサイコロを転がすことができない。
  • サイコロを転がした時に、底面に書かれた数字とグリッドに書かれた数字が一致しなければならない。
  • グリッドの偶数行・偶数列には必ず#(シャープ)が書かれている。

(h, w)まで転がすことができるのならば"YES"、そうでなければ"NO"を出力する問題。

グリッドの具体例、初期のサイコロの状態は下図を参照。

f:id:horoyoisawa:20200320203550p:plain

グリッドの具体例(3×3)

f:id:horoyoisawa:20200320203916p:plain

サイコロの初期状態。2が前面、3が右側面である。


これは実際に転がしてみると規則性が見えてくる。結論を先にいってしまうが、4×4のグリッドを単位としてサイコロの底面に書かれた数字は以下の様になる。(そのほかのグリッドはこれの繰り返し)。

f:id:horoyoisawa:20200320205104p:plain

サイコロを転がした時に底面にくる数字

あとは実際に上図とグリッドに書かれた数字が一致していればOK(通れる)、そうでなければNO(通れない)として迷路が完成する。あとはBFS・DFS何でもしてやればいい。

ただここで僕はいつも通りqueueを使ってBFSしたらMLE(Memory Limit Exceeded)になった。AtCoderでは余裕で通るはずだが通らなかった。そこで再帰を使ってDFS。AC。

規則性にちゃんと気づければ解ける問題。

M. String Set

1以上N以下の長さの文字列を要素として持つ文字列集合Sを考える。以下の条件を満たす様に、文字列集合Sのサイズ(要素数)の最大化せよ。

  • 文字列の長さは1以上N以下である。
  • 文字列の長さは全て異なる。
  • あらゆる文字列は'0'と'1'で構成される。
  • 任意の二つの文字列をとってきた時に、一方が他方の部分文字列ではない。

最大のサイズの値と具体的な要素を出力する。

これも気づければ一瞬だ。僕はほとんどコンテスト終了間際になってやっと気がついた。簡単である。いろいろ具体例はあるが以下はその一例である。

  • N = 1 の場合
    最大サイズは1, 要素は{"0"}
  • N = 2 の場合
    最大サイズは2, 要素は{"0", "11"}
  • N > 2 の場合
    最大サイズはN-1個。要素は以下
    1000000000000000000000...000000000000000000000001
    1000000000000000000000...00000000000000000000001
    1000000000000000000000...0000000000000000000001
    1000000000000000000000...000000000000000000001
    ...             ...              ...             ...           ...        ...           ...       
    ...             ...              ...             ...           ...        ...          ....
    ...             ...             ....           ....         ....         ....
    100001
    10001
    1001
    101
    11
    互いが互いの部分文字列になっていないことはすぐに分かる。

感想

自分にとってとても勉強になるいいコンテストだった。

反省点は以下。

  • AtCoder以外のコンテストではMLEが発生することがあるのでその点に注意する。
  • BFSとDFSを書くのに少し手間取ってしまった(デバッグに想定以上に時間がかかった)無意識に書ける様にしたい。
  • 体力が本当にない。。。長いコンテストに集中して取り組めるように体力をつける。
  • 一緒に参加する友達がいないボッチも仲間を見つけた方が良さそう。
  • 見たことがある様な問題が数問あったが解けなかった。復習していて忘れたか、もしくはわからないままACしていないか。過去の自分が解いた問題を見返す。
  • Vimに慣れていない。もっとたくさんコードを書く、もしくはコマンドの反復練習をする。

ここで紹介しなかった自分が解けなかった問題については別のところで書く予定。

では。