EPOCHまつやま 2011 予選問題
あれ、一つ前の記事が去年の予選問題の記事だ。id:wand125:20101119:1290133106
日記全く続かないなー。
id:ichyo さんがEPOCHの記事を更新していたのに影響を受けて自分も記事を書くことに。
ソースは先週ハードディスクが壊れたので無し。
一問目：グループに分けて数字をさがせ！
問題概要
N 個の正の整数が与えられたときに、その整数を
A: 1 回しか登場しなかった整数のグループ
B: 2 回以上登場した整数のグループ
にわける
B の中の最大値を b とし、A の中で b 番目に大きな整数 (大きいものから数えて b 番目)を出力するプログラムを作成する。ただし A に属する整数が b 個未満の場合は,グループ A の中の最小値を代わりに出力する。
入力
N <= 500000
値はint型に収まる
解法
素朴に書いてみる。
- 配列に入れるO(n)
- N個の整数を素朴にソートしてO(nlog(n))
- 一つしか出てきていないものを配列Aに追加&Bの最大値を求めO(n)
- Aのb番目を出力O(1)
結果
O(nlog(n))
setを使って書いた銀杏さんのコードより速かったのでこっちが採用されました。ソースは銀杏さんの記事 id:ichyo:20111017:1318846796 を参照。
ほとんどが入力時間だと思うからそんなに高速化の余地はないと思うの。
二問目：文字列変換ポイントの計算
問題概要
N個の文字列が順に与えられる。
開始時のスコアを0とし、連続した文字間について
追加 S の先頭,末尾または途中に一文字だけ追加する.(例: epoch → eapoch)
削除 -1点
S から一文字だけ削除する.(例: epoch → epch)
変更 +2点
S の中の一文字だけを別の文字に変更する.(例: epoch → epach)
一つ前の文字と同じ それまでの得点を2倍にする
それ以外 それまでの得点に関わらず0点になる
文字列を順に見ていき、最終的な得点を求める。
最終的な得点はint型に収まることが保証されている
入力
N <= 100000
文字列の長さは255文字以下
解答
書きかけでやめました。提出は100%がいちょうさんのコード
一番工夫がしにくそうなイメージだったけどどうなんだろう。
三問目：三問目：足し算になっているのは?
問題概要
N個の数字が与えられる。数字の間に+,=の順で演算子を入れ
51042552 → 510+42=552のように等式を成立させることの出来る数字の数を数える。
ただし、分けた後も含め、数列の先頭に0が含まれていても構わない。
000130026039 → 00013 + 0026 + 039
N <= 10000
桁数は1000桁以下
解答作成
9/30の昼間時点で銀杏さんのコードが遅かったのでこれは締め切りまでに作らないと書かないとと思ってたら
銀杏さんが13:00頃に改善して数百倍速になったのでその時点で自分のコードは捨て、そっちの最適化をしてました。
最終日の数時間で仕上げるとかそれは違うプログラミングコンテストや...
高速化
数値の比較部分がループの最深なのでここのループ内を改善するのが良いだろうと考える。
char a,b,c;にそれぞれ'0'〜'9'までの数値が入っているとして、
その加算&比較の処理で繰り上がりを求めるのに除算はいらないんじゃない？(どうせ1か0だし)
剰余はいらないんじゃない?(どうせその数自身か10を引いたものなんだから)
みたいな感じで演算子やif文をなるべく減らしたりしてました。2割ぐらい速くなった気がしました。
アルゴリズム
この問題の計算量は
- (1) +,=を入れる組み合わせの数
- (2) +,=で分けた数値の加算&比較
のかけ算で求められそうです。が、1,2の両方で枝刈りが発生します。
(2)では等式が成立しているかどうかを調べるだけなので桁数ごとに比較を行い、一致しなかった時点で打ち切ることができます。
(1)では、(2)で成り立ったものが一つでも見つかった時点でそれ以降の組み合わせは考える必要がないので打ち切ることが出来ます。
平均的なケースの場合(2)の比較で等式が一致する確率は各桁ごとに1/10なので
比較回数の期待値は1+1/10+1/100… = 10/9 回
すなわちO(1)です。
けれども、この問題の条件である等式を満たすケースこそが最悪ケースとなり、O(n)回必要です。
(1)の比較について、+と=の入れ方をすべて挙げると桁数をnとしたときに(n-1)C2 = (n-1)(n-2)/2の組み合わせがあるので普通に試すとO(n^2)掛かってしまいます。
このオーダーを減らす方法は各チーム毎に差が出そうです。他のチームがどのような方法を取ったのかは知らないので、ここからは自分のチームの解き方になります。
まず、先頭の0がなかった場合を考えます。
正の整数二つの足し算なので
Cの桁数 は max(Aの桁数,Bの桁数) または (max(Aの桁数,Bの桁数)+1) となります。
よって、'='の位置(Cの桁数)を動かすと、各位置に対して'+'の入る位置は4通りに絞られることになります。
この4種類を考えれば十分です。
この条件では'='は桁数の後ろ1/3から1/2まで動かせば良いです。
次に、先頭位に0が入る状況を考えます。
桁の最初に0が来ることがあるのでそのままではこの方法で桁数から位置を絞ることが出来ないように見えます。
そこで以下のように変更します。
まず、00123→123のように与えられた数字の先頭位の0をすべて無視します。
'+'を入れた位置の左側の文字列の長さがそのままAの桁数と考えることが出来ます。
'='を右端から1つずつ動かしながら
Aの桁数 = Cの桁数
Aの桁数 = Cの桁数-1
Bの桁数 = Cの桁数
Bの桁数 = Cの桁数-1
となる4通りについて調べます。ただしBの長さをCの桁数の長さで区切った際、
区切った部分のすぐ左が'0'の時は'0'以外の数が現れるまで、Bの桁数が変わらないことに注意します。
Cの桁数は'='のすぐ右側が'0'でなければ'='より右の部分の長さを代入し、そうでない時はループの1つ前の値のままにしておくことで求められます。
桁数をnとした時の平均計算量は
'='の入れ方が
n - 2 - (最上位の0の数の期待値)
通りで
'+'の入れ方が
4 + (Bの最上位の0の数の期待値)
0の数の期待値はそれぞれΣ1/10^n = 1/9なので
平均計算回数は(n-2-1/9) * (4+1/9)回、すなわちO(n)です。
また、途中で等式を満たす組み合わせがあった場合、枝刈りが発生します。
よってこの問題の平均計算量はO(n)になります。
最悪ケースはBの先頭に0が続いたとき…?でもさすがにそれがオーダー変えるようなケースは考えなくて良いよね…。
すたっきゅん(@stac_task) に悪いケースとして1が666個,2が334個続くケースがあったけど、5秒ぐらい掛かってました。
プログラムを書く際に意識した点
- なるべくデータ構造に配列を使う。
setなどを使う時も使用するメモリ量が決まっていればロスを減らすため、配列で実装しようと考えていました。
メモリアクセスの観点からも配列の効率が良さそう。
- ボトルネックとなっている部分を改善する
プログラム全体の時間の1/100しか占めない部分を改善しても仕方がないので無視します。
- 枝刈りがなるべく効果的に働くようにする
問題3とか、もう少し改善点がありそうですね…。
感想
- 今回の場合、プログラム自体のボトルネックもだけど問題1,2,3の中で問題3の改善が大きそうだった。
- 問題3がチームによって解き方に差が出そうで良問っぽい。
- 今年は銀杏さん2問、自分1問、去年が自分2問、銀杏さん1問なのでバランスが良い
- 問題3の銀杏さんのソースにBの先頭の0の処理が書いてなかったような気がするのだけど、だいじょうぶなの。
- 運が良かった…?
- 本選出場のみなさま、お会いできるのを楽しみにしてます。
- 今年もスライドがんばる
