ARC094 F Normalization

 はい。ARC094のF問題(F - Normalization)の解法です。解説(aを0、bを1、cを2だと思うと和のmod3が保たれるとかいうやつ)がド天才だったのですが、もう少し思いつけるかもしれない解法でACしたので投稿します。

 といっても結局mod3を見ることにはなってしまうのでそこに至るまでのステップも書いていこうかと思います。

解法

 まず、操作後の文字列はどこかに同じ文字が連続する部分があるということはすぐに分かるのですが、それだけでは条件が足りなさそうです。また、操作の順番によってできる文字列が変わる(というか操作の順番を変えるとそもそも操作ができなくなることもある)ので左から順番に操作するorしないでDPといったことも出来なさそうです。ということで別の方向で考えてみましょう。

 数列や文字列に対して何らかの操作を施すタイプの問題では、

操作の前後で変化しないものに着目する
という方法が有効なことがあります。また、今回のように操作が3種類ある場合すべての操作に対して共通してなりたつものを見つけるとよいです。具体的に今回の問題の操作での個数の変化を見てみましょう。
  1. ab→cc   a:-1、b:-1、c:+2
  2. bc→aa   a:+2、b:-1、c:-1
  3. ca→bb   a:-1、b:+2、c:-1

「2増える」「1減る」という操作を同一視したいなぁという気持ちになりますね(なって。)。この時点でmod3に気づく人もいるかもしれませんが、さらにこれもよくある手法として、「個数の差(和)はわりといい性質を持ちがち」というのがあります。ということで各操作でのaの個数とb,cの個数の差の変化を見てみましょう。

  1. ab→cc   a:-1、b:-1、c:+2  b-a:±0、c-a:+3
  2. bc→aa   a:+2、b:-1、c:-1  b-a:-3、c-a:-3
  3. ca→bb   a:-1、b:+2、c:-1  b-a:+3、c-a:±0

 「aとbの差」「aとcの差」は操作の前後で「3増える」「変わらない」「3減る」のいずれかです。もうわかりますね。操作の前後で「aとbの差」「aとcの差」を3で割った余りは変化しないということです。なるほどここで3で割った余りがでてくるのか、という感じですね。3で割った余りがカギになることに気が付いてさらに考察を進めると解説の方針になるのかなぁ。

 とはいえこれで操作後の文字列に対する重要な性質がわかりました。

  1. どこかに 連続している部分がある

  2. 「aとbの差」「aとcの差」を3でわった余りは最初の文字列と同じ。

この性質をみたす文字列は本当に全部つくれるのかという問題はあるのですが、実は|S|≠3のときはできるらしいです。(証明は帰納法でできるらしい。解説に書いてた。)ということで|S|=3のときだけ全探索することにして、他は上の条件をみたすようなものを数えるためのDPをします。

 具体的には、dp[文字数][最後の文字][(b-a)を3で割った余り][(c-a)を3で割った余り] のようなdpテーブルを2つもって、1つで「2の条件をみたすもの全部」、1つで「2の条件を満たすが連続する箇所は1つも持たないもの」を計算して差をとるのが楽な気がします。

 ということでこれでこの問題をO(27*|S|)くらいで解くことができました。最初の文字列が連続箇所を持たない場合は答えに1足すのも忘れずに。一応自分のACコードのリンクを貼っておきます。

Submission #2374335 - AtCoder Regular Contest 094

 

※追記

 少し考察すると「aとbの差」のmod3が保たれるなら「aとcの差」のmod3も自動的に保たれることがわかるため、dpテーブルは、dp[文字数][最後の文字][(b-a)を3で割った余り]と1つ項を減らして計算しても大丈夫なようです。(Submission #2374698 - AtCoder Regular Contest 094)

感想

 本番中にこの性質に気づけていながら手計算の実験部分を間違えていて解けなかったのはちょっと悔しい。|S|=3の場合だけ無理というのも罠でした。短すぎる文字列なら例外がおこりうることには思い至るべきだったなぁ。700点はさすがに嘘な気がするけどとても面白い問題だと思います。

Atcoderで青色になりました。

 こんばんは。先日のARCでレートが無事1600に到達したのでブログを更新する次第です。

f:id:tempura0224:20180412144919j:plain

水色から青になるために必要だと思った知識とかをまとめられるとよいのですが水色から青までで通した問題が5問(文字列、数学、算数(偶奇)、数学、貪欲)だけなのでただただ自分語りをするだけの記事にしようと思います。

 ということで「Atcoder 青色」とかで検索してこのブログに来ちゃった人は閉じちゃってくれて大丈夫です。僕の生い立ちが見たい人は見ていってください()

1月

 僕が競技プログラミングを始めたのは今年の1月からでした。新年特有の意識高い瞬間の思い付きでAtcoderに登録しました。で、薦められるがままに蟻本と螺旋本を買い、Atcoder Problemを開いたあたりでそもそもプログラミング経験が皆無なことに気づきました(は?)。幸いにして冬休みで時間だけは腐るほどあったので

 問題(A,Bあたり)を見る→何をすればいいかはわかる→書けない→人のコードを見る→初見の関数をググる→すげえ→自分も書いてみる→バグる→つらい→直る→嬉しい

 の繰り返しで知識を増やしていきました。間違いなく正しい学習方法ではないです。で1/7にABCデビューを果たしてなぜか全完をしてしまいました。D問題が貪欲で解ける問題で知識がいらなかったというのが理由なんですがこれで調子に乗り、そこからは蟻本を読んだりABCの過去問(C,Dあたり)をばしばし解いたりしてました。

使った知識:BFS,DFS,ワーシャルフロイド,二分探索,累積和,DP(1番基本的なタイプ),BIT

2月

 2/4のAPCで緑になりました。ABCのCまでは安定して解けるようになっていたのと過去問ではDもだいぶできるようになっていたのとでARCに移りました(が本番中はなかなかDは解けませんでした)。こどふぉやCSAにも参加するようになり生活が壊れました。

使った知識ダイクストラ,Union Find,累積和(2次元imosとか),桁DP,行列累乗

3月

 こどふぉで惜敗を繰り返したりAtcoderに虐殺されたりCSAで黄色タッチにことごとく失敗したりと絶妙に噛み合わない月でした(つらい)。競プロも競技である以上こういう期間もあるんだなぁと勉強になりました。それでも何とか3/25のARCで水色になりました。

tempura0224.hatenablog.com

使った知識最小全域木,フロー(最大流とか2部マッチングとか),区間DP,木DP,LIS

4月

 4/7のARCで青になりました。大学院生活が始まってしまったりで海外コンテストを見送ることが多くなってしまって悲しい。精進も滞りがち。

おわりに

 「使った知識」はコンテストだったり過去問埋めだったりで1回でも使ったものを書き出しただけなので必ずしも使いこなせるわけではないです(おい)。学習の順番も必要になったものから順番に、みたいな感じなのでところどころ非常識だったりしますがこれくらい身に着ければアルゴ的には十分なんだなぁくらいの参考になれば嬉しいです。

 これから黄色を目指すうえではデータ構造に弱すぎる気がするので個人的にはその辺を強化していけたらいいなぁと思っています。「黄色になりました」を書ける日が少しでも早く訪れますように。

 

 

AGC022 E Median Replace

 AGCお疲れ様でした。EのMedian Replace(E: Median Replace - AtCoder Grand Contest 022 | AtCoder)の解法です。公式の解説が天才すぎたのですけど別の方法で解けたので書きます。

 場合の数をいきなり考えるのは難しいのでとりあえず判定問題を考えます。

 まずいろいろと実験してみると最初の2文字が11だとそれ以降の並びによらず美しい文字列なことがわかります。また、左から順番に見ていったときに、1はなるべく最後まで残すべき(111→1とか110→1とかの操作は極力しない)なことや、0が2つ以上連続していたらそこはさっさと潰して0が1つだけの状態にしてしまったほうがいいということが(直感的にですが)わかります。

 以上をまとめると文字列abcde...が与えられたときにとるべき戦略は

  1. 01cde...のとき:前の01は残しておいたほうがいいのでcde…以下で1をつくれる、つまりcde...が美しい文字列ならよいです。
  2. 00cde...のとき:前の00cは潰して0にするしかないので、0de...が美しい文字列ならよいです。
  3. 11cde...のとき:cde...以下によらず美しい文字列です。
  4. 101de...のとき:前の10は残しておいたほうがいいので、1de...以下が美しい文字列ならよいです。
  5. 100de...のとき:00dの部分を潰して0にしてしまうのが最適で、残る10e...が美しい文字列ならよいです。

 これで、与えられた文字列に対して1回の操作ごとに最低でも長さが2縮まるDPを書けてO(N)で判定することができます。

 数え上げも本質的には同じで、dp[n][a][b]で「n文字の文字列でabで始まるもののうち美しい文字列の個数」とすれば上記と同じ遷移が書けます。?がでてきたときは1と見たときと0と見たときの場合の数を足せばよいです。

 2と5のパターンはそれぞれc、dが?のときは2倍しなきゃいけないみたいな罠があったりするのですがこれでO(N)で解くことができました。

 https://beta.atcoder.jp/contests/agc022/submissions/2289522

 一応コードも貼っておきましたが可読性が死んでます。

 

 ところでこれを通せたのがコンテスト終わってから15分後くらいっていう、、、。

 コンテスト中に通せなかったのは一か所1にしなきゃいけないところが?も許容しちゃってたからなんですけどコンテスト中は気づけないもんですね。Atcoder苦手すぎてつらい。

 しばらくAGCも多いのでどこかで結果が出せたらいいなぁと思います。では。

Atcoderで水色になりました。

 こんばんは。てんぷら(TwitterID:tempura_pp)です。先日(3/25)のARCでレートが1200に到達したのでとりあえず今までをざっくりまとめてみます。自分の備忘録としての用途が主なのであまり参考にならない部分も多いかと思いますが悪しからず。

 f:id:tempura0224:20180328210555j:plain

コンテストの成績

 こんな感じです(画像参照)。

 f:id:tempura0224:20180328210649j:plain

 謎の大成功回を除けばパフォーマンスは1000~1600くらいです。具体的な点数でいうと、

  • ABC,ARC…Cまで解けたのが4回、Dまで解けたのが3回。
  • AGC…2回ともAが解けただけ。
  • APC…これは無視でいいです。

 要は300点以下の問題(ABCのCまで)を安定して解けて、400~500点が半分くらいできるようになると水色になれるんだと思います(適当)。

使った知識

 ここまで参加したAtcoderのコンテストで本番中に解けた問題で使ったテクニックやアルゴリズムなんですが

 以上です。(単純な全探索やAd-hocなものは省きました。)DP書いてなかったのか、、、。ということで極端に難しい知識がなくても水色までは到達できることがわかりますね。

 

水色になるために必要そうなこと

 僕なりに必要そうだと思ったことをまとめてみようと思います。

蟻本を買う

 読む、じゃなくて買う、なところがポイントです()。蟻本初級編でも普通に難しくてなかなか読めないんですよね。(僕は一回挫折して螺旋本に逃げました。こっちは初心者でも読めると思います。)

蟻本に関してはいきなり理解しようと思って読むと大変なのであまり深く考えずとりあえず「こんなテクニックあるんだすげぇ」くらいから始めるのでいいと思います。蟻本の知識が必要になる頃には読めるようになってます、たぶん。「蟻本をちゃんと読み切る」というのをモチベーションに頑張るのも1つなんじゃないかと思います、というか僕がそうです。

とにかく問題を解く

 結局これにつきます。AtCoder Problems等で過去問を見られるのでABCの問題をばしばし解いていきましょう。

 さすがにこれだけで終わると何のためにこの項目を作ったのかわからないのでもうちょっと真面目に書くと、

  1. わからないときは解説を読む。めっちゃ大事。無理なものは無理なので解説を読みましょう。わからないまま放っておくより何億倍もいいです。
  2. 人のコードも見てみる。これも大事な気がします。自分が解けた問題でも他人のコードを読んでみると「こんな書き方もあるのか」とか「こう書くと場合分けの数を減らせたのか」とか勉強になることが多いです。
  3. ちゃんとACするところまでやる。解説を読んだ場合であっても絶対に自分でコードを書いてACするところまでやりましょう。意外とバグります()。特にプログラミング経験の浅い場合はコードを書きまくって慣れるのがめちゃくちゃ大切です。競プロって考察がちゃんとできたら後は極論するとタイピングゲームですしね()。
  4. コピペはなるべく使わない。上とほぼ同じ理由です。何度も同じようなコードを書いていると使いまわしたくなるのですが少なくとも勉強するときはなるべく全部書くようにしましょう。個人的には青色になるまではライブラリなしで頑張ろうと思っています。

こんな感じですかね。問題を考えるのにもコードを書くのにも頭を使うのはしんどいので思考停止でできることを増やしていけるとだいぶ楽になります。なにぶん自分の経験が浅すぎるので書けることが少ないのがね、、、。

とりあえずこれ(AtCoder Beginners Selection - AtCoder)は解いておきましょう。dr.kenさんがまとめてくださった初心者用問題集です。ちなみに僕を競プロに導いてくれた人でもあります。

 

最後に

 水色になった記念にブログ書こうと思い立ったのはいいものの文章書くのって難しいですね。定期的に記事書いてる人すごすぎる。

 せっかく開設したので今後は解けた問題の解法だったりコンテストの記録だったりに使うかもしれません。成長日記として色が変わるごとに記事書くのもありかもですね。