ABC114 参加記録&解説
CもDも手間取ってしまい54位…
A - 753
解法
ifや3項演算子などで場合分けしましょう。
ACコード
- (Ruby)Submission #3700911 - AtCoder Beginner Contest 114
- (C++)Submission #3708253 - AtCoder Beginner Contest 114
B - 754
解法
の長さが短いので、全部試すことができます。文字列から数値への変換は、C++だと stoi
などを使うと便利です。
ACコード
- (Ruby)Submission #3702096 - AtCoder Beginner Contest 114
- (C++)Submission #3708303 - AtCoder Beginner Contest 114
C - 755
解法
こういう問題形式を見ると桁DPと思ってしまうのですが、まあ300点問題でそれはないですね…
なので、 以下の全ての整数を調べることはできません。ただ、 のみで構成される整数に絞ると候補がぐっと少なくなります。
桁数が で からなる整数は 個あります。候補となる値の桁数は が最も大きいときで3~9桁なので、 個、計算すると 個しかありません。これは全探索できますね。
実装においてはまず桁数 を1つずつ見ていって、それぞれの整数列挙には3進数を用いるとよいです。候補を全て列挙して、「 以下か?」「 が全て使われているか?」をチェックすればよいです。
ACコード
- (Ruby)Submission #3704123 - AtCoder Beginner Contest 114
- (C++)Submission #3708007 - AtCoder Beginner Contest 114
3進数の実装について少し補足します。コード中で trits
という変数で書いているのが3進数の値で、列挙される整数( からなる 桁の整数)と1対1対応しています。3進数の各桁の が にそれぞれ対応します(int arr[3] = {3, 5, 7};
で表現しています)。
例えば で のとき、 であることからこれは3進数表記すると 210
であり、この値は に対応しています。(桁数が違うと同じ3進数の値でも対応する整数が異なるので注意してください)
D - 756
解法
正整数の約数の個数は、その値の素因数分解と密接に関わっています(参考リンク)。具体的には素因数ごとに個数を数えて、その個数が 個、 個、... 個だったとすると、約数の個数は 個になります。
ということで、まずは を素因数分解してしまいましょう。 なのでそんなに多くの素因数は登場しません。2から最大で97まで、それぞれの素因数ごとに何個含まれているかが計算できます。
小さいほうから 番目の素因数 の個数を と書くことにします。例えば小さい値 で考えると、 は以下のように素因数分解できます。
1 | 2 | 3 |
2 | 3 | 1 |
3 | 5 | 1 |
の約数は、これらの素因数 それぞれについて「 0個以上 個以下の範囲で、いくつ取るか」を考え、その素因数を全て掛け合わせたものになります。各素因数についての「いくつ取るか」の取り方の組1つが、約数1つに対応します。例えば先程の の例において、「2を2個、3を0個、5を1個」取るとすれば、これは120の約数20に対応します。この20の約数の個数は 個です。
ということで、各素因数ごとに順番にいくつ取るかを考えていく数え上げDPができます。 を「 番目の素因数まで見た時に、それまでの約数の個数が であるような選び方の個数」とします。このとき は75の約数だけを考えれば十分です。
遷移は以下のようになります。 番目の素因数まででできた約数が 個で、 番目の素因数を 個選ぶ、という選び方に対応しています。
- 75の約数 について、 であれば を に加算する。
これを最後まで計算し、素因数の種類数を として が答えです。
ACコード
HACK TO THE FUTURE 2019 本選オープン 参加記録
HACK TO THE FUTURE 2019 本選オープン - AtCoder
オープンコンテスト3位!
解説というほどのものは書けないので、「こんな感じのことをしました」というのをつらつら書いていく感じになります。
最初に考えたこと
- 中盤まではスキルに投資することが重要だが、終盤は無駄なのでひたすら仕事をしたい。
- スキルは高レベルほど上げにくくなるので、特化するより均等に上げたほうが費用対効果は高そう。
- 依頼は期間終了ターンもしくはその少し前で受けることを考えたい。依頼がいっぱいあるので、極論「そのターンに終了する依頼」だけを見てもよさそう。
- 面倒なことは考えたくないので、依頼の要求スキルレベルや期間の傾向を解析したりするのはとりあえずやらない。
ということで、こんな感じのものを書きました。
- 事前準備
- 依頼を終了ターンで分類しておく。
- 目標スキルレベルを決める。
- ~900ターン目
- 901ターン目~
- そのターン~10ターン後までに終わる依頼の報酬を全部計算し、一番高いものを受ける。(これはバグって以下略)
この提出がこれ(2.96億点)。10ターン後と10ターン前を間違えて、結局そのターンに終わる依頼しか受けられないようになってました。ひどいですね。
これを書いて試してみたところ、
- 目標スキルレベルは高ければ高いだけ結果がよくなる
- スキルレベルが全て10になるのがだいたい600ターンくらいで、かなり余裕がある
ことが分かりました。そのため以降はスキルレベルを10まで上げきることを前提に考えました。
スキル上げフェーズとひたすら稼ぎフェーズ
ということで、フェーズを2つに分けてみます。
- スキルレベルがオール10になるまで
- なるべく早くスキルレベルをオール10にすることを考える。
- スキルを上げられる場合、必ず上げる。対象スキルの選択は前と同様。
- スキルを上げられない場合、そのターン~ ターン後に終了する依頼から最も良いものを受ける。
- スキルレベルがオール10になった後
- もうお金を稼ぐだけなので、後ろから順番に受ける依頼を決めていく。
は適当に試して決めます。 が大きいと候補が広がる反面、美味しい依頼を早く取ってしまい損をする可能性があります。このときは くらいになりましたが、後々の改善をした後だと が一番良くなりました。
スキルレベルがMAXになった後は、後ろから「最も報酬の高い依頼」を選んでいきます。本番中はこれが厳密に最適だと信じて疑いませんでしたが違いますね…ただ、美味しい依頼を最終日に選択できる可能性はとても高くなり、なかなか良い結果になったとは思います。
このアルゴリズムを書いてそこそこパラメータ調整したのがこれ。3.19億点まで伸びました。
所用のためここで少し離脱。
美味しい依頼はスキルよりも優先
用事を終わらせてPCの前に戻れたので、頭の中で考えていたことを試していきました。
まずスキル上げフェーズにおいて、トレーニングできるお金があるときはトレーニングをしていましたが、美味しい依頼があるときはそっちを受けてもよいのでは?という案。
「美味しい依頼」の基準は、最終的には「いままでの依頼の最大報酬× 以上の依頼であれば優先」という感じになりました。 は1.3くらい。
実装はこれ、結構伸びがよくて3.40億点。この提出ではいままでの最大報酬ではなく1つ前の依頼の報酬を使っています。
スキル上げ順番の操作
次に、今まで避けていた依頼の傾向解析。あまり複雑なことはしたくなかったので楽そうなものを選びました。それはスキル上げ順番の操作です。
スキルを上げる時、均等に上げていくのは変えません。ですが例えばスキルレベルが 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
という状態から、どのスキルを真っ先に上げるべきでしょうか?
すごく感覚的に言うと、「スキルレベルがだいたい2~3くらいになっているであろうターン」において、「要求最大スキルレベルが3である、高報酬の依頼」があるとき、そのレベル3が要求されているスキルを優先的に上げるのがよさそうです。
これを実装に落とすと、
- 各スキルレベルごとに、「だいたいスキルレベルが ~ であるようなターンの範囲」を、サンプル1の実行経過などを見て決める。
- 依頼ごとに、もし「要求最大スキルレベル」と「依頼終了ターンが上記範囲内にあるようなスキルレベル」が一致していれば、そのレベルにおいてそのスキルを早く上げることは重要とみなし、その依頼の基本報酬額を評価に加算する。
- トレーニングの時には、各スキルレベルごとに評価が高いスキルから優先的にトレーニングをしていく。
という風になります。これ もかなり伸びがよくて3.56億まで上がりました。これが実質的には最後の有意な改善でした。
その後、上記「ターンの範囲」をテストケースごとに決めるような処理を入れてみましたが、結果は微増。残り時間がなかったので場当たり的にコードを書き直して実装がぐちゃぐちゃになりました。このスコアでコンテストを終えました。
振り返り
重い実装をするとバグるので予選の反省としてあまり凝ったことをせずシンプルに考えるのがよいということを学んだので、難しそうなものはどんどん後回しにしてシンプルな解法を心がけました。
スキルレベルを最大まで上げてよい、2フェーズ化、後半は後ろから貪欲という主要な知見を早めに確立できたのはとても良かったと思います。
そこからの改善はわりと場当たり的で、結構運良く思いつきが当たっていったなという印象です。
反省点としては、実行時間がダダ余りになって有効に使えなかったこと。予選のように試行回数で稼ぐことは頭をよぎりましたが、何をパラメータとして回せばよいかのイメージが持てなくて実装に落とせませんでした。
あと後ろから貪欲が最適とは限らないことに気づけなかったのはアルゴやってきた競プロerとして普通にダメですね。実際ここで大量の報酬を稼いでいるので、改善効果は高そうです。
さいごに
まさにゲームのAI(機械学習とかそんなんじゃなくて、いわゆるコンピュータ側の行動プログラム)を組んでいるみたいでとても面白い問題でした。シミュレーションゲームの敵側の行動なんかは、こんなことを考えながら組んでるのかなと少し思ったり。
成績としてはかなり良かったですが、「なぜ良かったのか」がいまいち分からず…運が良かったんですかね。マラソンに慣れてくるとこのあたりの感覚が鍛えられて、効果的に復習できるようになるのでしょうか。もう少し場数を踏む必要がありそうです。
Rubyで競プロするときのTips
ある程度知見が溜まってきたのでまとめていきます。
各オンラインジャッジのRuby環境
2018年12月くらいの情報です。
サイト | バージョン |
---|---|
AtCoder | 2.3.3 |
Codeforces | 2.0.0 |
yukicoder | 2.5.3 |
AOJ | 2.4.0 |
この記事は基本的にAtCoderの2.3系を対象に書いていきます。
Codeforcesはちょっとバージョンが古いのと、実行時間制限がキツ目なので私はRubyを使っていません。
入出力編
基本的な入力。
N = gets.to_i # 単一整数 a = gets.split.map(&:to_i) # スペースで区切られた複数の整数 a = N.times.map{gets.to_i} # 縦に並んだ複数の整数。たまにある S = gets.chomp # 文字列。chompを付けないと改行文字がついてくる
以下のような形式の入力もよく見ますね。
N a_1 b_1 ... a_N b_N
これは次のように書くとスマートです。
N = gets.to_i a, b = N.times.map{gets.split.map(&:to_i)}.transpose # [[a_1, b_1], ..., [a_N, b_N]] を転置して # [[a_1, ..., a_N], [b_1, ..., b_N]] にする
出力は puts
を使うとよいです。数値も文字列も出力できて、改行文字が自動で付与されます。
数値編
多倍長整数
Rubyの整数は自動的に桁数が拡張されるため、算術オーバーフローはありません。
10**100 #=> 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
とはいえ、あまりに桁数の多い多倍長整数を計算し続けているとTLEやMLEになります。
負の数を含む剰余計算
b
が正のとき、a % b
は必ず0以上となります。
-1 % 3 #=> 2
言語によっては上記の結果は-1
となるかもしれません。競技プログラミングではどちらが扱いやすいでしょうか?個人的にはRubyの挙動のほうが好きです。
ちなみにほとんどやらないと思いますが、-1 % -3
は-1
になります。
浮動小数の出力
浮動小数をputs
などで出力する場合、値が大きくなると指数表記になります。
puts (10**15).to_f # 出力: 1.0e+15
内部的にはto_s
が実行されているのですが、リファレンス上は「人間が読みやすい形の文字列表現」という何ともスッキリしない書かれ方がされています。
実際にこの問題の出力例3に示されている数は、puts
を用いると1.0e+15
と出てしまいます。(ただ、この問題はそれでもジャッジが通りました。)
解決方法はsprintf
などを使うことです。
puts sprintf("%f", (10**15).to_f) # 出力: 1000000000000000.000000
1e9のようなリテラル表記
例えば C++で を代入したい時にこんな書き方をします。
const int64_t MOD = 1e9 + 7;
1e9
のようなリテラル表記はRubyでもC++でも浮動小数ですが、C++では変数を整数型で宣言していれば代入時にキャストされます。
一方、Rubyの場合は変数に型がないので浮動小数のままです。整数値を代入したい場合は**
を使いましょう。
MOD = 1e9 + 7 #=> 1000000007.0 MOD = 10**9 + 7 #=> 1000000007
ビット演算
ORやANDなどの基本的な演算は他言語と同様にありますが、個人的によく使うのが「整数の ビット目を取り出す」操作です。Rubyでは以下のように書くことができます。
5[2] #=> 1 最下ビットを0として、下から2番目のビット
ビットシフトなどを使って書くよりも簡潔ですね。見た目はキモいですが便利です。取り出すだけで、ビットへの代入(値の変更)はできません。
また、整数のビット長は bit_length
を使って取り出すことができます。これは2.0系にはないのでCodeforcesで使うとREで死にます。
5.bit_length #=> 3
最小公倍数、最大公約数
標準で使えます。
10.gcd(4) #=> 2 10.lcm(4) #=> 20
素数関連
prime
モジュールを使えば素数列挙や素因数分解ができます。
require 'prime' Prime.each(15).to_a #=> [2, 3, 5, 7, 11, 13] 15以下の素数 Prime.prime_division(24) #=> [[2, 3], [3, 1]] 2**3 * 3**1
配列編
要素の追加/削除にはなるべく破壊的操作を使う
Rubyの配列は、先頭・末尾に対する要素の削除と追加を効率的に行うことができます。この点ではC++のdeque
と似ています。
これらの操作は破壊的操作(push/pop/shift/unshift
)として提供されています。もし不都合がなければできるだけ破壊的操作を使うようにしましょう。速度が全然違います。
a = a + [1] # 非破壊的操作 a.push(1) # 破壊的操作
配列のmax/min
よりif
や三項演算子を使う
複数の値の最大値や最小値を求めるとき、わざわざ配列を作ってmin/max
で判定するよりは、if
や三項演算子を使ったほうが速くなります。競技プログラミングでは以下のような操作をよく行いますね。
ans = #<暫定最適解> while #<何かの条件> result = #<何かの計算結果> ans = [ans, result].max # これは遅い ans = result if ans < result # こっちのほうが速い end puts ans
ループの深いところでmin
やmax
を使うとかなり遅くなるので注意です。たまに300点問題とかでもこれが原因でTLEを食らったりします。
なお、この現象はRuby 2.4以降においては改善されています。
負のインデックス
Rubyの配列で負のインデックスを取ると、「末尾から数えて 番目」の意味になります。C++のvector::back
と同様、末尾の値が欲しいときによく使います。
a = [1, 2, 3] a[-1] #=> 3
他にも少しトリッキーな使い方があって、添字がマイナスになるところの処理を少し簡略化できます。例えば
- 累積和を0-indexで取ると範囲和が
S[r] - S[l-1]
のようになり、l=0
の時に負数になってしまう - グリッドで隣のマスにアクセスする時に、インデックスが減る方向を参照すると
S[i-1][j]
のようになり、i=0
の時に負数になってしまう
など。負数インデックスが例外や未定義動作になる言語では気を使わないといけないですが、Rubyでは末尾の参照になるので、末尾に「番兵」的な値を入れておくことで少しだけ実装をスマートにできます。ただ、ちょっと気持ち悪いとかバグらせそうとかあると思うので、お好みで。
配列の要素の合計
2.4だとsum
が使えるのですが、2.3系以前であればinject
を使いましょう。
a = [1, 2, 3, 4] a.inject(:+) #=> 10 a.inject(:*) #=> 24 たまに積も使う
二分探索
競技プログラミングでよくつかう二分探索。C++だとlower_bound
やupper_bound
がよく使われますが、Rubyにはもう少しだけ高機能なbsearch
メソッドがあります。これは判定条件をブロックとして与えることができます。
※C++だとpartition_point
という関数で類似のことができるようですが、あまり使われていないような気がしますね…。
これはArray
またはRange
に対して使えます。リファレンス をみる限りちょっと仕様が難しいのですが、二分探索可能な(単調な)場合において「ブロック内の条件を満たす一番左の要素」を返します。どの要素もブロック内の条件を満たさない場合はnil
が返るので注意です。
(1..(10**9)).bsearch{|n| n*n >= 500} #=>23 これはceil(sqrt(500))に相当
ブロックの中に判定ロジックが書けるので、判定ロジックが短く書けるような問題においては特に使いやすいです。こんな書き方もできます。
浮動小数の範囲オブジェクトに対しても使えますが、精度や反復回数を指定できないので競技プログラミングにおいて使うのは少し不安です。
スコープ編
定数
大文字で始まる識別子は定数となり、オブジェクトを再代入すると警告が出力されます。警告なのでまあ処理はされるのですが、気になる場合は再代入しそうなものを大文字で書き始めるのは避けましょう。競プロでは入力として与えられる整数などは定数でよいと思います。
また定数の地味なメリットですが、トップレベルで宣言した定数はトップレベルで宣言したメソッドの中で使うことができます。Rubyのグローバル変数は少し記法が面倒なので、競プロであれば入力値などのプログラム全体で使う値くらいはこのように楽に参照してもよいでしょう。
def subroutine a = N/2 # ここでNを参照できる .... end N = gets.to_i ....
おわり
何か思いついたら追記します。
Codeforces Round #522 C. Vasya and Maximum Matching
考察が重かったけど、面白い問題。
問題概要
頂点の木が与えられる。この木の辺それぞれについて辺を取り除くかどうかを考えると、その場合の数は全部で 通りある。そのうち「辺を取り除いた後のグラフにおいて、最大マッチングが一意に定まる」という条件を満たす場合の数を数え、 で割った余りを出力せよ。
制約
- 与えられるグラフは木
解法
木の最大マッチングが一意に定まる条件
辺を取り除いたあとのグラフはいくつかの部分木になる。そのため、まずは木の最大マッチングが一意に定まる条件を考える。部分木全てがその条件を満たしているとき、その辺の取り除き方は問題の条件を満たす。
- 頂点の数が1つであるとき。最大マッチングは当然0個なので条件を満たす。
- 頂点の数が3以上の奇数であるとき。どれだけマッチングを作っても必ず1つ以上頂点が余ってしまい、余った頂点と隣接する頂点でペアを作り変えることができてしまう。そのため条件を満たさない。
- 頂点の数が2以上の偶数であるとき。もし完全マッチングが存在するならばこれは一意に定まる。完全マッチングが存在しないならば、余っている頂点があるので前項と同じ理由で条件を満たさない。
ということで、頂点数が偶数のときに完全マッチングが存在するかどうかを考える。例えば、以下のようなグラフは完全マッチングを作れない。
より一般的に言うと、適当に根を決めて葉からDPをしたときに、途中で「2つ以上の子について、その子以下の部分木の頂点数が奇数である」という頂点が1つでも見つかってしまうとアウトである。
これで木の最大マッチングが一意に定まる条件を洗い出せたので、本題を考えていく。
木DPをする
本題の数え上げでも、適当に根を決めて葉からDPをしていく。
以降、辺を取り除くことによって部分木を確定させることを「完成させる」と呼び、完成された部分木全てについて完全マッチングが一意に定まることを「正当である」と呼ぶことにする。
正当性を保つためにやってはいけないことは2つあり、
- 頂点数が3以上の奇数の部分木を完成させる。
- 2つ以上の、子を含む部分木の頂点数が奇数であるような子について、その両方からの辺を残す。
である。こうならないような辺の取り除き方を数えていく。
DPの変数として、ある頂点 以下の辺の取り除き方の総数であって、 以下のグラフが正当であり、頂点 を含む部分木の頂点数が
- 1であるもの:
- 2以上の偶数であるもの:
- 3以上の奇数であるもの:
とする。先ほど見たようにこの3パターンで部分木の性質が違うため、分けて数える。
を求める
頂点 と子の辺を全て切るしかない。このとき、子が含まれる部分木の頂点数が3以上の奇数であってはいけないので、
となる。ここで は の子を示す(以下も同様)。
を求める
そのままでは数えづらいので、 と合わせて部分木の頂点の個数が奇数個になる場合を考える。
複数の子から奇数個の頂点を繋いでくることはできないため、子からは偶数個の頂点を繋ぐかまたは辺を切り、頂点 自身と合わせて奇数個になるというパターンしかない。つまり各子について、
- 子が含まれる部分木の頂点数は偶数個であり、頂点 と辺を繋ぐ。
- 子が含まれる部分木の頂点数は偶数個であり、頂点 と辺を繋がない。
- 子が含まれる部分木の頂点数は1個であり、頂点 と辺を繋がない。
の3パターンのどれかを採用することができる。数式は
となる。先ほど は求めたので、 を求めることができる。
を求める
これが少し厄介。子のうちどれか1つから奇数個の頂点を繋ぎ、残りの子は繋がないか偶数個の頂点を繋ぎ、頂点 自身と合わせて頂点数が偶数個になるパターンである。
どの子から奇数個の頂点を繋ぐかを全部考えるため、
と複雑な式になる。これを真面目に計算しようとすると子の数の2乗オーダーがかかってしまうが、 の計算について「全部掛け算したものを計算しておいて、 についてだけ逆元を掛ける」ようにすると1乗オーダーで計算できる。
仕上げ
このDPを根まで計算する。最後に根を含む部分木の頂点数が3以上の奇数になってはいけないため、根を とすると答えは のmodを取ったものである。
ACコード
ACコードとして2つリンクを貼る。
- (0除算対策あり)Submission #45964352 - Codeforces
- (0除算対策なし)Submission #45964650 - Codeforces
計算の途中で逆元を取るため、その値がmod計算後にちょうど0だった場合に危険である。十分大きい素数なので余りが0になる確率は非常に低く、意図的に0除算を誘うような入力を作るのもかなり難しいとは思われるが、ちゃんと解くなら対策をしておくほうがよい。ただ、実装がわりと面倒くさい。
リンクの通り、0除算対策をしないコードでもACは取れている。
さいごに
このように木DPで数え上げを行う問題として「Ribbons on Tree」や「Squirrel Migration」があり、これらの強烈なイメージがあったため今回の問題を自力で解くことができたと思う。
木DPは楽しい。
CODE FESTIVAL 2018 Final (Parallel) 参加記録&解説(A~F)
オープンコンテスト8位でした。
A~Fについて書きます。この記事を書いている時点で解説が公開されていないため、Twitterなどで見た他の参加者さんの解法を大いに参考にしながら書いています。
A - 2540
解法
長さが と の2本の辺で、ちょうど1つの端点を共有するペアを数えればよいです。ただし、重複しないように注意する必要があります。
私の方針は以下です。
- 頂点 と辺の長さ ごとに、「頂点 から伸びている長さ の辺の本数」をmapで管理する。
- 辺を1本ずつ見ていく。そのとき、
- その辺の端点それぞれについて、その時点でのmapを使ってこれ以前に見た辺のうちペアになるものの辺の本数を数える。
- その後、辺をmapに追加する。
このようにすると重複なく数えられます。
ACコード
- (Ruby)Submission #3609891 - CODE FESTIVAL 2018 Final (Parallel)
- (C++)Submission #3623681 - CODE FESTIVAL 2018 Final (Parallel)
B - Theme Color
解法
要求されている答え方が特殊ですが、まずは普通に確率の求め方を考えます。結論を書くと、求めたい確率は
になります。この計算は、 の場合は「反復試行の確率の公式といろいろな例題」に説明があり、これを「多項定理の例題と2通りの証明」に書かれている式のように の場合に拡張したものです。
さて、求めたいのは を満たす最小の整数 です。指数の形を除去するため、両辺底が10の対数を取ります。対数を取ると積は和になるので、
という式になります。この式から求めたい整数 は
となるので、 を の範囲で前計算しておけば を計算できます。
ACコード
- (Ruby)Submission #3610055 - CODE FESTIVAL 2018 Final (Parallel)
- (C++)Submission #3623786 - CODE FESTIVAL 2018 Final (Parallel)
Rubyのコードは多項定理ではなく二項定理の組み合わせで書いているので少し無駄な計算が入っていますが、やっていることは同じです。
C - Telephone Charge
解法
制約が特殊です。それぞれのプランで、通話時間 の時に料金が他のプランより安くなるということは、グラフで描くと以下のような関係になっているはずです。
色が各プラン、太線になっているところがその区間での最安のプランを示しています。このグラフから、例えば図中の の位置であれば、 プラン3またはプラン2が最安になることがわかります。
解法としては、プランを の値でソートしておき、各 についてどの の間に位置するかを二分探索などで特定し、その2つ(端なら1つ)の値を両方試して安い方を採用すればよいです。
ACコード
- (Ruby)Submission #3624012 - CODE FESTIVAL 2018 Final (Parallel)
- (C++)Submission #3610426 - CODE FESTIVAL 2018 Final (Parallel)
D - Three Letters
解法
本番は解けませんでしたが…
文字列の中から文字列の並びを探す時に、文字種とインデックスのどちらでループを回すかによって計算量の見積もりが変わってきます。今回の場合、「1文字目と3文字目は文字種で、2文字目はインデックスで」という少しトリッキーな考え方が必要になります。
ある文字列 について、2文字目のインデックスを左から右にずらしていきます。このとき、「左側に各文字がそれぞれ何個あるか」「右側に各文字がそれぞれ何個あるか」は、累積和のように計算することができます。
このようにすると、
- 2文字目は、文字のインデックス全てについて全探索(全文字列合わせて最大 )
- その2文字目に対して、1文字目と3文字目を文字種全てについて全探索()し、ともに1個以上あるかチェック
として、3文字の文字列の存在を判定することができます。
ただしこの数え方をそのまま行うと、ある に対して同じ文字列を重複して数えてしまう可能性があります。それを防ぐため、3文字の文字列パターン全てにおいて「その文字列が最後に発見されたのはどの か?」という値を管理しておきます。こうすると重複カウントを防ぐことができます。
※計算量について、単純計算すると となるので、これがもし想定解ならばかなり厳しい気がしています。ただコンテスト終了後のTwitterの書き込みを見た感じ、高速な言語を使ってこの解法で通した人が多そうです。
ACコード
実装においては、配列のインデックスなどに文字を使うためにアルファベット52文字を0~51の整数に変換しています。アルファベット大文字と小文字の間はASCIIコード上で連続していなかったりするので地味に注意です。
E - Tough Journey
解法
高橋くんが町 にいるとき、手持ちの水が合計何本になるように買うべきか考えます。もし距離 以下の位置に今いる町よりも水の安い町がある場合、町 ではその町に行けるだけの水を買って、安いほうの町で新しく水を買うべきです。
そのため高橋くんが町 にいて、次に訪れる町 より水の安い町が町 であるとき、
- ならば、町 では手持ち 本になるように水を買う。
- ならば、仕方がないので町 で上限の 本まで水を買う。
このように水を買うのが最適となります。
あとはこれを効率的に解く実装を考えればよいです。実装方法もいくつかあると思いますが、私の方針は
- 町を水の安い順にソートする。
- セグメント木を用いて、ソートした町に対して以下を順番に行う。今考えている町を として、
- それまで見てきた町から、 よりインデックスが大きいものの中で最もインデックスが小さいものを求める。
- 町 をセグメント木に追加する。
としました。具体的な実装はコードを参照してください。
ACコード
F - Dinner Planning
解法
まず単純に考えると、順番に食事をしていくことを仮定しながらグルメ度の変化を見ていって、
- グルメ度が を超えてしまった場合、それまでに行ったレストランの中で最も美味しさが低いものをキャンセルする。
- グルメ度が を下回ってしまった場合、それまでに行ったラーメン屋の中で最も美味しさが低いものをキャンセルする。
ということをしたくなります。
ただし、これでは困るケースが出てきます。例えば以下のグラフのように、「グルメ度が を超えたので過去のレストランをキャンセルしたら、そのせいでグルメ度が0未満になる日が出てしまった」というケースです。
こうなっては困るので、キャンセルすべきは「最後にグルメ度が0になった日以降で、美味しさが最も低いレストラン」となります。グルメ度が0を下回った場合は全く逆のことをします。
※これを毎回貪欲に選んで大丈夫なのか?後々の選択と合わせるとより良い選び方があるのでは?という疑問が浮かびますが、ちゃんとやると証明できると思います。記述がかなり長くなりそうなのでここでは省略します…
ということで、求めたいのはそれまでのグルメ度の推移を全て計算しておき
- 最後にグルメ度が0(または )になったのはいつか?
- ある区間におけるレストラン(またはラーメン屋)で一番美味しさが低いのはどれか?
を求めることです。これだけならどちらもセグメント木を用いて求めることができます。グルメ度に関してはある日から現在までの区間最小値が0かどうか(または最大値が かどうか)で二分探索です。
ただしグルメ度に関してはそれに加えて「過去に遡って、食事をキャンセルした日以降のグルメ度を1変化させる」という操作が必要です。そのため区間に対する操作を行える遅延評価セグメント木を用いれば、必要な全ての操作が可能になって解くことができます。
ただ、これまた想定解ではなさそうですね…。
ACコード
Educational Codeforces Round 54 参加記録&解説(A~F)
Dashboard - Educational Codeforces Round 54 (Rated for Div. 2) - Codeforces
今回はなんと17位!…なんですが、本番中のD問題のジャッジに致命的なミスがあって正常なコンテストではなかったため、素直に喜べない感じです…
6問振り返ります。
A. Minimizing the String
問題概要
英小文字 文字からなる文字列 が与えられる。この文字列から最大1文字を取り除いてできる文字列のうち、辞書順最小のものを求めよ。
制約
- は英小文字からなる
解法
文字列の 文字目よりも 文字目のほうが辞書順で小さいとき、 文字目を取り除くことで元の文字列よりも辞書順で小さい文字列を得ることができます。
辞書順で小さくするためにはできるだけ前のほうの文字を改善したほうがよいため、前から文字列を順番に見ていって、最初に 文字目よりも 文字目のほうが辞書順で小さくなるところで 文字目を取り除くのが最適です。ただし、s = aaa
や s = abcde
など最後までそのような がない場合は最後の文字を取り除きます。
ACコード
B. Divisor Subtraction
問題概要
正整数 が与えられる。 になるまで以下の操作を繰り返す時、その操作回数を求めよ。
- から、「その時点での」 の最小の素因数を引く。
制約
解法
もし が偶数の場合、最小の素因数は2です。偶数 から2を引いてもやっぱり偶数なのでまた2を引き…を最後まで繰り返すので、操作回数は です。
もし が奇数の場合、最小の素因数を とするとこれは必ず奇数です。そのため1回目の操作で値は となり、これは奇数同士の差なので偶数です。あとは2を引き続けるため、合計の操作回数は となります。
ACコード
Submission #45598676 - Codeforces
C. Meme Problem
問題概要
以下の問題を 回解け。
- 非負整数 が与えられる。非負の実数 であって であるものが存在するか判定し、もし存在すればその値を求めよ。
制約
解法
連立方程式を解く常套手段として、片方の変数 を消去します。 を に代入して整理すると となり、これは についての2次方程式なので解の公式を用いると となります。
のとき実際に計算すると確かに になっているため、この2つが非負の実数であれば答えになります。もちろん逆でもよいです。
まず実数である条件は で、これが満たされない場合は条件を満たす が存在しません。またこの条件が満たされる時、 が成り立つことから はともに非負となるため、それぞれ計算して出力すればよいです。
ACコード
D. Edge Deletion
問題概要
頂点 辺の重み付き単純連結無向グラフと、整数 が与えられる。辺 の重み(長さ)は である。このグラフにおける頂点1から頂点 までの最短路の長さを とする。
このグラフから 本以下の辺を残す方法の中で、「残した辺だけを使った頂点1から頂点 までの最短路を求めた際に、その長さが変わらず となるような頂点 の個数」が最大となるような残し方を1つ求めよ。
制約
- グラフは重み付き単純連結無向グラフ
解法
頂点1から各頂点への最短距離はダイクストラ法で求めることができます。このとき、一緒に「各頂点への最短路に使う辺」も調べることができます。全ての頂点に対する最短路に使う辺を集めると、これは「最短経路木」と呼ばれる木になります。
※1つの頂点への最短路として長さが同じ複数の経路がある場合は、ちゃんと木になるよう経路を適切に選ぶ必要がありますが、よくあるダイクストラ法の実装のように「新しい経路の長さが、それまでに見つかった最も短い経路より真に短い場合だけ経路を更新する」という実装をしておけば大丈夫です。
辺を全て取り除いた状態から、1本ずつ辺を足していくことを考えます。このとき頂点1からの連結性を保ったまま、先ほどの最短経路木に含まれる辺だけを足していくと、新しく連結になった頂点へは頂点1から最短路を辿って到達することができます。このようにして辺を 本まで(または、全域木となる 本まで)足していけばそれが答えとなります。
ACコード
Submission #45615172 - Codeforces
ダイクストラ法において最短路の復元を行う場合、始点以外の頂点それぞれについて「最短路における、1つ前の頂点」を記録しておくのが常套手段です。ただし今回は辺の番号のほうが後々使いやすいため、代わりに1つ前の頂点からの辺番号を記録しています。
E. Vasya and a Tree
問題概要
頂点1を根とする 頂点の根付き木が与えられる。各頂点には値が書かれていて、初期値は全て0である。
頂点 の -subtreeを、頂点 の子孫(自身を含む)であり との距離が 以下である頂点の集合と定義する。以下のクエリが 個与えられる。
- 整数 が与えられる。頂点 の -subtreeに含まれる全ての頂点の値に を加算する。
クエリを全て処理した後の、各頂点に書かれている値を求めよ。
制約
- 与えられるクラフは木
- 各クエリについて、
解法
各クエリを独立に処理し、影響を受ける全部の頂点にいちいち値を足していては間に合いません。効率的な計算方法を考えます。
頂点 の根からの深さを とします。するとクエリ で値が足されるのは、 の子孫であって深さが閉区間 に含まれる頂点であると表現することができます。範囲について値を足すクエリを大量に処理する方法として、「いもす法」のようなことができないか考えてみます。
普通のいもす法と比べるとかなり変則的ですが、以下のような方法を考えます。このようにすると、根から頂点をDFSしつつ、足される値の合計を差分更新することができます。
スライド最終ページにも書きましたが、いもす法を用いるメリットは「範囲に対する多数のクエリをまとめて処理できる」ことです。最初にクエリを全て読み込んで ごとに振り分けておけば、スライドで示したようなDFSで同時並行的にクエリを処理しながら全頂点の値を求めることができます。
ACコード
Submission #45682359 - Codeforces
F. Summer Practice Report
問題概要
ページのレポートがあり、 ページ目には 個の表と 個の数式を好きな順序で一列に並べて書く。このとき、ページをまたいで連続するものも含めて、表だけ・または数式だけが連続して 個以上続いてはいけない。そのような並べ方は可能かどうか判定せよ。
制約
解法
表だけ・または数式だけが連続して 個以上続かないような並べ方を、正当な並べ方と呼ぶことにします。
ページの境目の扱いがやっかいなので、ここを上手く扱うことができないか考えます。ページの最後には表か数式のどちらかが書かれていますが、同じものが連続することを避けるためには「ページの最後に書かれている表/数式が、そのページの最後でいくつ連続で続いているか」の値をなるべく小さくしたいです。もちろん、1個であれば最も理想的です。
そこで、各ページ について
- ページ目までの並べ方が正当であり、 ページ目の最後が表であるとき、その連続個数を最小でいくつにできるか?
- ページ目までの並べ方が正当であり、 ページ目の最後が数式であるとき、その連続個数を最小でいくつにできるか?
をそれぞれ計算します。これをそれぞれ とおくと、それらの値を使って次のページの値 が計算できます。これを最後のページまで続けて、途中で かつ となってしまうページが出てしまったら答えは「不可能」ですし、最後のページまでそうならなければ「可能」です。
ということで遷移を考えます。(注目するページを にしたいので、1つ添字をずらして から への遷移を考えることにします。)
以降、表が連続でいくつか並んでいる塊を X
、数式の塊を Y
と表記します。 ページ目の表と数式の並べ方として、以下の4パターンを考えることができます。
XYXY......XY
XYXY......XYX
YXYX......YX
YXYX......YXY
すなわち、最初が X/Y
どちらか、最後が X/Y
どちらか、の4パターンです。
ここで、例えば最初が X
である2パターンを考えます。最初の X
の中にある表は、最大でいくつまで並べられるでしょうか?ページをまたいで表が 個以上連続してはいけないので、この値は に依存しています。
- であるとき、前ページの最後が
Y
である並べ方が可能であるため、それを採用すれば最初のX
は 個並べられる。 - であるとき、前ページの最後を
Y
にはできない。そのため、- であるとき、最初の
X
は 個並べられる。 - であるとき、最初に
X
を置くことはできない。
- であるとき、最初の
このようにして、最初の X
にいくつまで表を並べられるかを求めることができます。
それでは具体的に を求めていきます。4パターンのうち XYXY....XY
を使って求め方を説明します。残りのパターンも同様に考えることができます。
連続する同じ要素を減らしたいので、要素をばらけさせる、つまり X
Y
の塊をなるべく多くしたいです。このパターンでは X
と Y
の個数が等しいため、それぞれの塊の個数は最大で 個まで増やすことができます。この値を と置きます。
塊がそれぞれ 個のときに
- 個の表を、(最初の
X
に置ける個数を考慮して)それぞれの塊に含まれる要素数が を超えないように 個のX
に分配できるか? - 個の数式を、それぞれの塊に含まれる要素数が を超えないように 個の
Y
に分配できるか?またそのとき、一番右のY
に含まれる数式は最小でいくつにできるか?
を計算します。実際に並べてみたものが以下の図です。
具体的には、先ほど求めた「最初の X
に最大でいくつまで表を並べられるか」を として
- のとき、表を
X
に正当に分配できる。 - 一番右の
Y
に含まれる数式の最小個数は であり、その値が 以下であれば数式をY
に正当に分配できる。
という結果になります。
このようにパターンを4つ試して、
XYXY......XY
とYXYX......YXY
のうち、「正当な並べ方」を実現できて、かつ一番右のY
に含まれる数式の個数が少ない方を とするXYXY......XYX
とYXYX......YX
のうち、「正当な並べ方」を実現できて、かつ一番右のX
に含まれる表の個数が少ない方を とする
ことで遷移が求められます。これをバグらせずに全パターン実装するのはなかなか神経を使いますが、結果的には で解くことができます。
ACコード
Submission #45627726 - Codeforces
私の実装の癖もあって、上の説明とは変数名がかなりずれています…すみません。適宜読み替えてください。
ABC113 参加記録&解説
AtCoder Beginner Contest 113 - AtCoder
22分台全完で21位でした。
A - Discount Fare
解法
を計算して出力すればよいです。
ACコード
(Ruby)Submission #3531033 - AtCoder Beginner Contest 113
B - Palace
解法
個の地点それぞれについて を計算し、それが最も小さい地点を探せばよいです。
ACコード
- (Ruby)Submission #3542648 - AtCoder Beginner Contest 113
- (C++)Submission #3542662 - AtCoder Beginner Contest 113
ちょっとした実装テクとして、上記のコードのようにC++の min_element
を使うと、「 vector
の中で最も小さい要素のインデックス」がスマートに取得できます。
C - ID
解法
市を県ごとに分類し、それぞれの県ごとに誕生年でソートします。そうすると、それぞれの市がその県で何番目に誕生した市かが分かります。
…というものを素直に実装すればよいです。300点問題で数学が要らないのは、最近だと珍しいですね…
ACコード
- (Ruby)Submission #3533911 - AtCoder Beginner Contest 113
- (C++)Submission #3542824 - AtCoder Beginner Contest 113
実装テクという点では、
- 誕生年でのソートをする際に、市のインデックスも巻き込むと後の実装がしやすくなる。そのため市を県ごとに分類する際、C++だと
pair
などを使って、誕生年と市のインデックスをまとめておく。 - 指定された桁数になるように左に0を埋める方法(C/C++だと、
printf
のフォーマット指定子で可能)
などを知っておくとよいですね。
D - Number of Amidakuji
解法
ある行までの横線の引き方は、その1つ上の行までの横線の引き方から計算できそうです。上からDPをしていくことを考えます。
「 行目まで考えた時に、縦線1からスタートしたものが 番目の縦線に移動しているような横線の引き方の総数」を とします。初期条件は で、答えは です。
行目から 行目への遷移に必要な情報は、「1行の横線の引き方であって、 番目の縦線から 番目の縦線に移動する引き方の総数」です。これを とすると、 行目から 行目の遷移は
と求められます。
次は、この の求め方を考えます。1行の横線の引き方は、線を引くところが 箇所しかないため、高々 通りです。 であることから は十分小さいので、全部確認してしまいましょう。
1行の線の引き方を全部列挙すれば、以下のように が求められます。
- 0から までの整数をループで回す。この整数をビット列として見た時の 個のビットがそれぞれ横線の有無を表し、 番目のビットが1であることは「 本目の縦線間に横線がある」ことを示す。
- これが「どの2つの横棒も端点を共有しない」というルールに違反する、つまりビット列として見た時に連続した1を含む場合、スキップする。
- この線の引き方のとき、 番目の縦線からどこの縦線に移動するかを各 ごとに計算する。これを とおく。
- 各 ごとに、 に1を加算する。
この を用いてDPを行えば、答えを求めることができます。