ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

JAG夏合宿2019参加記

番外編

1日目

1日目からポンコツをたくさんしました。


目的地に向かう途中、goodbatonさんに声をかけていただき、一緒に向かうことになりました。前方にbeetさんがいらっしゃったので、右も左もわからない自分はただついていくだけの人になりました。

このツイート、あたかもbeetさんとお話をしたかのようにツイートしていますが、同じエレベーターに乗っていただけで、beetさんと、そのときに一緒にいらっしゃった方(お名前を知らなくてごめんなさい)とは一切お話できていません...(悲しい)

コンテストは、3日とも同じ大学の後輩であるHyado君、Sen君と「Prime_turtle」というチームで出ました。僕と、後輩二人のICPC予選の際のチーム名を少しずつ取り出して合わせたものです。
1日目の予定としては、はじめに僕がA、Sen君がB、Hyado君がCを解く予定でした。
ですが、僕がAを誤読したため何もできず、Hyado君に丸投げをして、代わりにHyado君のCを横取りしました。
A問題でとてつもない時間がかかったため、そのままA~Cの3完で終わりました。
Jの考察があと一歩だったので少し悔しいです。

コンテスト後もポンコツムーブをしました。
お風呂にあるコインロッカーのお釣りの100円を取り忘れたり、着替えのズボンを前後反対に履いたりしました。


2日目


この日は、Eをまず自分が解き、その後AをHyado君が通しました。
そして、Dを僕とSen君の2人で、Iを僕とHyado君の2人で通し、何とか4完をすることができました。
Dの計算量を落とすパートをSen君がやってくれたり、Iの実装の大枠や、細かい部分の指摘をHyado君がやってくれたりしたので助かりました。
I問題は自分が書いた繰り返し二乗法がバグっていて、ACするのに時間がかかりました。TTPCでも繰り返し二乗法の実装が蟻本と違って効率が悪く、大学の先輩に笑われたのですが、リベンジができませんでした…

昼寝をした後、懇親会に参加しました。初めは早稲田の人達でかたまっていたのですが、さすがにかたまりすぎるのもよくないと思い、後半はNOSSさん、こたつがめさん、まほろばさん、もりをさんとお話をしました(途中でてぃーいけさんが挨拶をしに来ていた気もします)。
今思い返すと、隙あらば自分語りをしていたような…？
直接お会いしたことがなくても、認知をされていたりして嬉しかったです。
ちょうど、懇親会後のABCでNOSSさんが黄色になっていたのでおめでたかったです(ルームメイトのidsigmaさんと、先を越されて悲しい、みたいな話をしたのは内緒です)。自分はテザリングを当日の朝に利用可能にして出場したのですが、レートが溶けました…
テザリング費用を払ってレートを溶かしたことになったので悲しいです。

3日目


3日目は、Hyado君がA、自分がB,Cを書きました。
BはSen君が詰まっていたので途中で交代したのですが、思いついた解法を投げて、自分が後半部分の考察にまわればよかったのかなぁと思いました(Sen君の実装が3日を通して少なかったのと、おそらく3人の中では自分が一番問題を解ける可能性が高かったため)。

感想

参加している人の層がかなり上の方(なイメージ)だったので、そこにくらいついていくのに必死だったのと同時に、やっぱりすごいなぁと思いました。
名前だけしっていて勉強するのをサボっている部分がピンポイントで出てきたりしているので、精進不足を実感しました…
あのレベルの問題をぽんぽん解けるようになりたいですね(これいつも言っているような気がします！)

ABC132 F - Small Products

動的計画法(DP)

問題
提出コード

解法

dp1[i][j] = i番目にjを置くような数列の場合の数(ただし、j \leqq \sqrt{N} )
dp2[i][j] = i番目に、xj \leqq N \lt x(j+1)を満たすようなx( x \gt \sqrt{N})を置く数列の場合の数
とします。
\sqrt{N}以下で最大の整数をp、xj \leqq N \lt x(j+1)を満たすようなx( x \gt \sqrt{N})の個数をc_{j}とすると、それぞれ次のように遷移を行うことができます。
\displaystyle dp1[i + 1][j] = \sum_{s = 1}^{p} dp1[i][s] + \sum_{m = j}^{p}dp2[i][m]
\displaystyle dp2[i+1][j] = \sum_{s = 1}^{j}dp1[i][s] \times c_{j}


あとは、全てΣの形になっているので、この部分を累積和で高速化することにより、dp1[k][j],dp[k][j]の総和が答えとなります。
初期値はdp1[0][1] = 1、それ以外が0です。

ABC128 F - Frog Jump

未分類

問題
提出コード

解法

A - B = Xとすると、実際の遷移は図のようになります。
f:id:emtubasa:20190821225843p:plain
ということで、距離Xおきに、前からk個、後ろからk個の蓮の得点を得ると決めた時のAは自動的に決まります。
Xをある値に固定したとき、kはだいたいN/X個の候補が存在し、Xについて全探索を行ってもO(N log N)におさまります。この全探索は、kが小さいパターンから順に、距離Xごとに前後から得点を足していくことで、十分高速に計算することができます。
あとは、A,Xが条件を満たす部分(つまりA \gt X)について全探索を行えば、その中で最も得点が高かったものを選ぶことで答えが求まります。
N-1がXで割り切れるときのみ注意が必要です。このパターンでは、前から見ている蓮と後ろから見ている蓮が被った、もしくは交差した時点で探索を終了する必要があります。

感想

今回ほぼ自力で解くことができたのですが、当時、F問題に十分時間を割けていたらどうだったのでしょうか…

ABC138 F - Coincidence

桁DP

問題
提出コード

解法

(x,y)が問題の条件を満たすには、これらを2進数に直した時に、

  • 最上位桁が一致している

  • それぞれの桁について、xのi桁目とyのi桁目が一致している、もしくはxのみ0でyのみ1になっている

という条件を満たす必要があります。
ということで、最上位桁が下からd桁目の際の(x,y)のペアを求めるために、桁DPを行います。あとはこれを全ての桁について行えばよいです。
dp[i][j][k]を用意し、

  • i:上から何桁目を見ているか(ただし最上位桁は確定しているのでないものとします)

  • j:xがmax(L, 2^{d-1})以上であることが確定しているか

  • i:yがmin(R,2^{d} - 1)以下であることが確定しているか

とします。
あとは、下の表をもとに遷移をひたすら書いていけばよいです… f:id:emtubasa:20190820173515p:plain

感想

Lの存在が邪魔で、うまい処理方法を思いつきませんでしたが、よくよく考えればR同様フラグを立てれば処理できますね…ただ桁DPの実装は丁寧にやらないといつもバグらせるので悲しいです(コンテスト中にラスト10分で書き直したものはもちろんバグだらけでした)

ABC138 E - Strings of Impurity

二分探索 全探索 貪欲法

問題
提出コード

解法

tに含まれ、sに含まれない文字が存在する場合、答えは-1になります。逆に、それ以外の場合は、必ず答えを見つけることができます。
s'の部分列でtを作る際、お互いの先頭から順番に、一致する部分を選んでいけばよいです。
作りたい文字列はtと固定されているので、tのx文字目がs'の何文字目に相当するかを調べていけば、tの最後の文字と対応するs'の番号が答えになります。
あとは、愚直にシミュレーションをしていきます。
あらかじめ、sを文字の種類ごとに分け、どの文字には何文字目が含まれるか、を調べて昇順で記録しておきます。
そして、今sの何文字目に居るか、というインデックスiを更新しながら(初期は0文字目、としておきます)シミュレートしていきます。
次に決めるのがtのx文字目t_{x}のとき、iよりも後で登場するt_{x}の場所を、先ほどの記録を二分探索して探します。iよりも後ろにt_{x}が存在しない場合は、sの中で一番最初に存在するt_{x}の場所になります。
そして、iを今探した場所に更新すればよいです。
これを繰り返すと、最終的にいる位置がわかります。
そして、肝心の答えですが、先ほどi以降にt_{x}が存在しなかった場合、sを1周することになるので、
(i以降にt_{x}が存在しなかった回数) \times |s| + i
になります。

感想

それなりにスッキリとした実装ができたので個人的に満足です。

AOJ 2152 - Restrictive Filesystem

実装系

問題
提出コード

解法

手で連結リストを作成していきます。
setで現在存在しているファイルの識別子を管理しておくことで、リストの中身を毎回書き換えずとも、削除のクエリを処理できるようにします。
あとは、リストを毎回前から探索していき、空きスペース(もしくは最後)に現在書き込みたいファイルの書き込みをしたり、ファイルの読み込みを行ったりすればよいです。

AOJ 1604 - デッドロック検出

未分類 リベンジ

問題
提出コード

解法

まずは、すでにロックを獲得した資源と、次に獲得する資源を対にした頂点を作成していきます。
10個程度しか資源は存在しないので、ビットで情報を持たせることができます。
その後、2つの頂点を選んだときのパターンを見ると、今回は3パターンします。

  • 2つの頂点どちらも既にロックを獲得した資源が存在しているパターン
    f:id:emtubasa:20190814183156p:plain
    2つの頂点が同時に存在することはないので、無視してかまいません。

  • 2つの頂点どちらも既にロックを獲得した資源が存在せず、片方の頂点が所有している資源をもう片方の頂点が次に獲得するパターン
    f:id:emtubasa:20190814183324p:plain
    片方(青い方)はこれ以降資源を獲得することはできませんが、もう片方(黄色)は次の資源を獲得することができます。この2つの頂点は、和集合の資源を獲得した状態で、次に黄色のNEXTの部分の資源を獲得しにいく1つの頂点とみなすことができます。

  • 2つの頂点どちらも既にロックを獲得した資源が存在せず、お互いの頂点が、相手が所有している資源を次に獲得するパターン
    f:id:emtubasa:20190814183552p:plain
    言うまでもなくデッドロックが発生します。

  • 2つの頂点どちらも既にロックを獲得した資源が存在せず、お互いが次に獲得する資源はどちらも所有していない資源のパターン
    f:id:emtubasa:20190814184015p:plain
    お互いが影響しあうことはないので、無視できます。


全てのパターンについて、tps://onlinejudge.u-aizu.ac.jp/problems/1604)
提出コード

解法

まずは、すでにロックを獲得した資源と、次に獲得する資源を対にした頂点を作成していきます。
10個程度しか資源は存在しないので、ビットで情報を持たせることができます。
その後、2つの頂点を選んだときのパターンを見ると、今回は3パターンします。

  • 2つの頂点どちらも既にロックを獲得した資源が存在しているパターン
    f:id:emtubasa:20190814183156p:plain
    2つの頂点が同時に存在することはないので、無視してかまいません。

  • 2つの頂点どちらも既にロックを獲得した資源が存在せず、片方の頂点が所有している資源をもう片方の頂点が次に獲得するパターン
    f:id:emtubasa:20190814183324p:plain
    片方(青い方)はこれ以降資源を獲得することはできませんが、もう片方(黄色)は次の資源を獲得することができます。この2つの頂点は、和集合の資源を獲得した状態で、次に黄色のNEXTの部分の資源を獲得しにいく1つの頂点とみなすことができます。

  • 2つの頂点どちらも既にロックを獲得した資源が存在せず、お互いの頂点が、相手が所有している資源を次に獲得するパターン
    f:id:emtubasa:20190814183552p:plain
    言うまでもなくデッドロックが発生します。

  • 2つの頂点どちらも既にロックを獲得した資源が存在せず、お互いが次に獲得する資源はどちらも所有していない資源のパターン
    f:id:emtubasa:20190814184015p:plain
    お互いが影響しあうことはないので、無視できます。


全てのパターンについての判定がこれで網羅できるようになるので、あとは複数頂点が1つの頂点にまとめられる回数、つまり10回程度、任意の2頂点について操作を行うということを繰り返せば、デッドロックが起こるかどうかを判定できます。

感想

資源数が少ないので状態を頂点にするという発想まではよかったのですが、それ以降どうすればいいかわかりませんでした…