JOI 2015/2016 本選(オープンコンテスト) C問題

hyoga.hatenablog.com

前回、C問題がMLE…と言っていましたが、ばとんさん(@goodbaton)さんから範囲外参照だとご指摘を頂きました。

確認してみると、こんなケースで誤作動するようです。

f:id:Hyoga:20160217232800p:plain

辺が値上がりしないと、outがINT_MAXのままになってしまうので、範囲外となります。

ということで、1行加えたら無事ACしました。REだったようです。

https://github.com/HyogaGlacier/Other-Programing-Contest/blob/master/2016-ho-t3.cpp

しかし、「発想はあっているのに、実装でつまらないバグを埋め込む」っていうのを何とかしたい…

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 C:アメージングな文字列は、きみが作る!

やはり文字列操作は苦手なようです。

問題概要

文字列sが与えられる。K回の以下の操作が可能である。

  • ある文字を削除する
  • ある文字を置換する
  • 文字を1文字任意の位置に挿入する

K回の操作後に辞書順最小となる文字列は何か。

discovery2016-qual.contest.atcoder.jp

解説

取り敢えず置換と挿入は全てaで行います。

まず、s中にaが何文字あるか確認します。K回の操作でsを全てaにすることが出来る場合、a以外の文字を全て削除し、その後余った手数で文字列の文字数を出来る限り削れば答えが得られます。

K回の操作でsをaのみの文字列に出来ない時、文字列の初めをaの羅列にすることで辞書順最小になります。ただし、この時ただ文字を置換するだけでなく、挿入する方がいい場合があります。

その例がs="abc",k=1のパターンです。

まず、元々aの部分は置換する必要がないので、それを考慮した上で何文字目まで置換でaの羅列に出来るかを求めます。

i文字目までaにすることが出来るとすると、最後のi文字目を置換ではなく、文字列の最初にaを挿入することでもaの羅列の数は同じです。同様にaの羅列の数が変わらない範囲(=iから戻って行き、最初のaにぶつかるまで)ならaを同数文字列の初めに持っていけます。

そうしたら後はそれらの中での辞書順最小が分かれば正解が分かります。

接尾辞配列を用いて範囲内でrankが最小のものを探せば上手く行きます。

Submission #637830 - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 | AtCoder

感想

接尾辞配列初めて使いました。ローリングハッシュでも通るらしいですが、これも使ったことないですね…

JOI 2015/2016 本選(オープンコンテスト)

まだ3問目までしか解いてないです。4,5問目は難しくて解けません。

しかし、修羅場になると予想された1問目〜3問目まで全てDPとは、手抜きなのか…4,5問目は修羅場か。

続きを読む

yukicoder No.202 1円玉投げ

久々に問題を解いた。JOI本選(オンライン参加ですが)も近いので、ある程度はやっておこう。

問題概要

N個の半径10の円形コインを投げる。投げた時にコインが重なるようであればそれを取り除く。

N個のコインの中心座標が与えられるので、N回投げた後いくつコインがあるか求めよ。

No.202 1円玉投げ - yukicoder

続きを読む

yukicoder no.337/338/339/340

うん。Twitterで宣言されていた通り比較的簡単だった。

続きを読む

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選(A,B)

2完+部分点10点でした。

続きを読む

SRM680 Round1 Div.2

Medまで早解き出来たからHardに挑戦…と30分程度格闘してイメージが湧きかけたところでMedの深刻なバグに気づいて修正。

残り3分で提出でした。おかげでMedが150点に…

続きを読む