ゆるふわ競プロオンサイトにオンライン参加した

hackerrank

先日、Twitterでゆるふわ競プロオンサイト #2なるものが流れてきた。
オンサイトといいつつ、オンラインでも参加できそうだったのでやってみた。

（レート帯から考えて、オンラインはさすがに参加できなかった）

主催は@matsu7874さんと@prd_xxxさん

 

問題はこちら

https://twitter.com/prd_xxx/status/1172712295610236928

 

主催の@prd_xxxさんによる解説スライドはこちら

 

 

TL;TD

  • Ａ：1文字目と2文字目をif判定
  • Ｂ：アルファベットに対応した数値を計算するだけ。O(N)
  • Ｃ：!Nを計算して10^9+7で割った余り。オーバーフロー注意
  • Ｄ：文字列をreplaceして計算。O(N)
  • Ｅ：うさぎの現在地点をクエリごとに更新していく。

 

A – honda’s janken

入力は制約2文字が確定している。
1文字目と2文字目を取って同値判定すればOK


submissions:1316238163

 

B – sentouryoku

JavaだとString.codePointAt(int i)で文字固有の数値を取得できる。

A(65), B(66)…Z(90)と加算されていくので、S.codePointAt(i)-64で各charの数値を配列化。
Mapとかでも一応それっぽいことはできる。

 

最大戦闘力はZが10個の”ZZZZZZZZZZ”になる。
その場合、26^10となりintの最大値を超えてしまうのでオーバーフローに注意すればOK


submissions:1316238423

 

C – mosaic tile art

コンテスト中はいい解法が思いつかず、法則性だけ考えました。

 

1:1
2:2
3:6

これらの入力例から、以下となるかを仮定。

各インデックスの値 = 1個前のインデックスの値 * インデックス値

 

実際に計算してみると合っていそうなので、これで実装進めてみる。
例)2の場合
ans = 1 * 2
= 2

例)3の場合
ans = 2 * 3
= 6

 

前回の計算結果が必要なので、まずSまでの計算をfor文で行う。O(N)
今回は1と2の場合だけ初期値で分かっていたので、その値だけ初期配列に持たせる形で実装した。

計算途中でのオーバーフローを防ぐため、各計算の度に%1,000,000,007で値を小さくしておく。

途中で除算しても、最終的な結果に変化はないので問題なし。

100000のケースでも正しく出力されたので、そのまま提出してAC

 

解説スライド見たら、
きれいな条件とは各列で白マスが1個のみの状態。
つまり、行ごとに前回の白マス列以外から選択する
よって、すべての列に対して白マスが重複しないように選択する
＝N!

 

というすごくすっきりした解法でした。
こういうのコンテスト中に考えられると楽しいだろうなーと思う。


submissions:1316240681

 

D – n-dwich box

問題見た瞬間、以下の2つの類似っぽい問題が頭をよぎった。

 

AtCoder ABC049 C:白昼夢

Cyber-dojo:BalancedParentheses

 

まず、BalancedParenthesesと同じように再帰的に文字列判定するか悩んでみた。

パンの部分の開始->終了があれば判定できるだろうという考え方。

 

ただ、今回の問題での特徴は、サンドイッチのパン部分が必ず開始-終了というペアにならないこと。
例えば、こういう例

|#|||||#|
// 21112

|||
// 111

 

とすると、開始->終了といった具合で判定していくのはちょっと難しい。

 

 

次に、白昼夢と同じようにString.replace()で削っていく作戦。
今回のサンドイッチのパターンを場合分けすると、こんな感じになりそう。

 

  • |  :1-dwitchかもしれないし、n-dwitchかもしれない。
  • #|:2-dwitch以上が確定する。以降、#|と続くこともある

 

先に”|”でreplaceしてしまうと、”#|”のパターンを潰してしまう。
そのため、以下のような形で実装する。

String ndWitch = "|||#|#|||#|";
String ndAfter = ndWitch.replace("#|", "z").replace("|", "");
// 111zz11z

String ichi_dWitch = "|||";
String ichi_dAfter = ichi_dWitch.replace("#|", "z").replace("|", "");
// 111

String ni_dWitch = "|#|#|";
String ni_dAfter = ni_dWitch.replace("#|", "z").replace("|", "");
// 1zz

 

あとは、zの部分を判定していく。

zの出現した箇所より、1つ前の1に値を加算していく処理を記載すればOK。

 

先ほどのコード例だと、こんな形になってくれると通りそう。

111zz11z -> 11312

111 -> 111

1zz -> 3

 


submissions:1316243285

 

E – usagi vs kame

コンテスト中にACできませんでした。。。

 

以下、思ったこと。

クエリは昇順ソートされてるっぽかった。

亀は毎秒1ずつしか進まないので、クエリ値（秒）＝亀の移動先と考えられる。

 

問題はウサギのクエリをどう算出するかで、毎回計算していては到底間に合わない。

ウサギの累積和の配列を生成して、クエリ値によってそのインデックスを更新していくと間に合う。

コンテスト中は、値をTreeMapに置けばキーソートされるので有利かと考えた。

しかし、毎回map.entry()でループさせるので最悪NQ(10^5 * 10^5 = 10^10)となりTLE。

 

解説見た後、1時間くらいかけて配列にして実装を変えてみた。

配列を用いて、クエリごとに二重ループの内側の開始indexを終端にずらしていくことで計算量を落とす。

更新する場合、クエリが複数インデックス分まとめて進むことがある事に考慮するのがポイントっぽい？

 

以下は疑似コード。

for 1 ... Q          // クエリ全件
  for x ... Q        // xを更新していく
    if kame < usagi  // 更新できないところまでループする
      break
    else
      // update
      // xを加算

 

submissions:1316241568 こっちはTLE

submissions:1316263839 こっちはAC

 

 

使用するテクニック

貪欲法

n-dwitchのも貪欲と言っていいのか微妙。

 

累積和

ウサギと亀でウサギのクエリを生成するのに使う。

[1, 2, 4, 5, 10]

[1, 3, 7, 12, 22]<-累積和

 

感想

やっぱり実力不足感は否めない。（57/65位）

ただ、問題はめっちゃユニークで面白かったし、クエリの更新とかグリッドの問題とかで今後にも使えそうなテクは得られたので個人的には大満足。

特にD – n-dwich boxがタイトルと問題合っててすごく好きです。

 

オンサイトはもっと実力つけてから参加してみたいけど、オンラインでもかなり楽しいのでまたの開催が望まれる。

 

ほかの方の参加記

 

 

@ohuton_laboさんの参加記。
A-H問題までの考察があります。
オンサイトの方なので、臨場感を味わいたい方へ。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする

, Naoto