AtCoder Regular Contest 061 + AtCoder Beginner Contest 045
成績
ARC参加で354位。なかなか緑にはならない。
解法メモ
A問題
台形の面積は 。
B問題
3人の手札と捨てられたカードの文字を変数に持たせて、実際にシミュレートすればよい。3人で最大300枚しかカードを持っていないのですぐに終わる。
C問題
結局のところ、与えられた数字列をバラバラに分解して、数字と数字の間に順番に+を入れたり入れなかったりしていけばよい。
ビット演算をつかえば効率が良い。最大で10文字しかないので、使うビットも最大9個だから十分。
D問題
C++とかならばmapを使えば一発らしいが、あいにくC言語にそういうのは用意されていない。
黒マスは最大で 個しかないから、与えられた黒マスに対して、そのマスによって黒マスの数が変化するような3行3列のマスを列挙していけばよい(最大 )。3行3列のマスが識別できればよいから、どこか1つのマス(例えば左上)を代表として表すことにすればよい。
列挙したマスを上・左からの昇順でソートすると、それぞれの3行3列マスには出現した回数だけ黒マスがあることになる。
列挙したマスを順番に見ていって、1~9個あるマスの個数を数え、最後にその総和 を計算しておけば、黒マスのない3行3列マスは 個あることがわかる。
わかってしまえばあっという間なのにわからなかったのが悔しい。
E問題
二部グラフを使えばよいらしい。まだわかっていない。
F問題
捨てられたカードを順番に見ていくことにする。たとえば、abcbacaa とカードが捨てられてゲームが終わったとする。
- ゲームが終わったときにAのターンだから、Aが勝ったことになる。すなわち、Aが勝つためには最後に捨てられたカードが a でなくてはならない。
- Aのターンでゲームが始まって、Aのターンでゲームが終わったから、Aは最初カードを4枚 (abca) 持っていたことになる。これは、a が書かれた捨てられたカードの枚数と一致する。
- Bは先頭から ca 、Cは先頭から ba というカードを順に持っていたことがわかる。これも、b, c が書かれた捨てられたカードの枚数に一致する。
以上のことから捨てられるカードの順列は、最後に a が来るような、 個の a、 個以下の b、 個以下の c の並べ方の総数に帰着する。
いま、 ターン目にAが最後に a のカードを捨てて勝ったとする。
並べる b の個数を 、c の個数を とおくと、Bの持つ 枚の手札とCの持つ 枚の手札はどの文字が書いてあってもよい。すなわち、カードの組み合わせは 通り。
だから、。
ターン目までに捨てられた 枚のカードのうち、a のカードが 枚、残る 枚が b, c のカードである。この組み合わせの数は、
通り。
したがって、求める数は
を で割ったあまり。
二項係数を求めるところは、フェルマーの小定理を使って、 と ()を事前に求めておく。
部分点解法
愚直に二項係数の総和を求めると時間を食うので、部分点しかとれない。
満点解法
二項係数 () の総和は である(二項定理)。このことを利用して、二項係数の和を一気に求める。
図の破線で囲まれた部分の二項係数の和を求めてみよう。
- 1段目の和は1。
- 2段目の和は、1段目の1が2回現れるので1段目の2倍で2。
- 3段目の和は、2段目の2つの1がそれぞれ2回ずつ現れるので、2段目の2倍で4。
- 4段目の和は、3段目の3つの数がそれぞれ2回ずつ現れるので、3段目の2倍で8。
- 5段目の和は、4段目の左端を除く3つの数がそれぞれ2回ずつ現れ、左端のみ1回現れるので、4段目の2倍から4段目の左端を引いて15。
- 6段目の和は、5段目の両端を除く2つの数がそれぞれ2回ずつ現れ、両端はそれぞれ1回現れるので、5段目の2倍から5段目の両端を引いて25。
- 7段目の和は、6段目の中央の数が2回ずつ現れ、両端はそれぞれ1回現れるので、6段目の2倍から6段目の両端を引いて35。
- 8段目の和は、7段目の2つの数がそれぞれ1回ずつ現れるので、7段目の2倍から7段目の両端を引いて35。
以上のことから、
- 1段目の和は1。
- 段目の和は、 段目の和の2倍から、追加しない側の 段目の端の数を引いたもの。
というようにして高速に求めることができる。
AtCoder Regular Contest 060 + AtCoder Beginner Contest 044
解法メモ
A問題
合計の宿泊費は、 ならば 円、 ならば 円。
B問題
はたかだか100文字なので、どの文字がいくつあるか先頭から順に数えていって、奇数個の文字がひとつでもあれば"No"、ひとつもなければ"Yes"を出力する。
C問題
動的計画法で解く。
を、 から までのカードから 個とって合計を にすることができるカードの取り方の総数とする。すると、
と漸化式が立てられる。カードの平均が となるような組み合わせの数は だから、これを出力する。
上とは別に、
D問題
のときは明らかに 。0 から までの数が各桁に使われるのは基数が 以上の場合に限られるし、基数が 以下のときに各桁の和が になることはない。
について愚直に を計算すると時間がかかってしまうので、よい方法を考える。
のとき、 の 進数表記は2桁以下になる ()。つまり、 進数表記が のとき、 と表される。これより、 である。また、 だから、 より となることがわかる。すなわち、 と の値から が一意に定まる。こうして定められた が を満たすかどうかを確認すればよい。
E問題
を、 番目のホテルから 日以内に到達できる最も右側のホテルの番号 として、まず を求め、次に として順次求めることができる。こうしてできたテーブルを二分探索すればよい。
二分探索を工夫する
しかし、C言語の二分探索関数は、値が見つからないとNULLを返してくるので、いちばん近い値を求めるには工夫がいる *1。
今回は自作の二分探索関数を作ることで対応した。要素の数が奇数のときは、見ている範囲の中央にある2つの要素両方を見て判定する工夫を施した。
Submission #860171 - AtCoder Regular Contest 060 | AtCoder
また、最右端まで到達できるときは、最右端の番号ではなくてそれより大きな番号を格納しておくと、「それより少ない日数で最右端に到達できる」ことがすぐにわかる。
F問題
まだよくわかっていない。
キーワード
C問題
AtCoder Regular Contest 059
AtCoder Beginner Contest 043 と同時開催。
k-ashiya-code.hateblo.jp
コンテストページ
解法メモ
E問題
を計算する。
まず、 が定数であると仮定すると、
と分解できる。したがって、各 に対して を について前計算しておく。
次に、動的計画法で、番目までの園児にキャンディーを個配ったときの積の総和 となるように式を立てて実行する。
F問題
小文字 a,b,c,... は0、1のいずれか、B はバックスペースを表すとする。キーボード入力が abcBdBef ならば、エディタに表示されている文字列は abef となるはずである。このとき、a,b,e,f が表す文字列の組み合わせは 通りであり、a,b,e,f としてどの組み合わせが与えられても、abcBdBef の形のキーボード入力は 通りあることがわかる。
N文字の入力でK文字の出力となるような入力の数を と表すことにすると、, , である。
次に、 について、 のときは と の文字列の後ろにBを足せばよいから 。
のときは、 の文字列の後ろにa(0か1)を、 の文字列の後ろにBを足せばよいから 。
は の文字列にaを足せばよいから 。 は の文字列にaを足せばよいから 。
以上のようにして まで求めたあと、 を出力する。
フェルマーの小定理
途中の過程で で割った余りを求めているから、単純に で割ることはできない。そこで、フェルマーの小定理を用いる。
を素数とする。 を で割った余りは1である。
証明はWikipediaに譲る。これを利用すると、 で割ることは をかけて で割った余りを求めることと同値。
二分累乗法
は確実に9桁以上の10進数になるから、ふつうに累乗していこうとするととても時間がかかる。そこで、二分累乗法というテクニックを使う。
まず、求めたい累乗を格納する変数 、底を格納する変数 、指数を格納する変数 を用意する。最初は 、 とする。
が奇数ならば、 に をかけ、 の偶奇によらず を2で割った商に書き換えて、 を2乗する。 が奇数ならば、 に をかけ、…ということを繰り返していけば、かなりの時間短縮になる*1。
プログラム上では2で割るとか偶奇の判断をするとかよりも、ビット演算で1の位のビットが立っていれば掛け算する、 を1つ右シフトする、という操作の方が早いのかもしれない。
*1:線形時間らしいけど本当にそうなのかがわからない。
AtCoder Beginner Contest 043
成績
- 700点、77分29秒=125位
B問題で思わぬ落とし穴にハマって2回ペナルティ食らったのがよくなかったが、D問題の部分点解法まで解けたのでわりと満足。翌日は朝早くから予定があったので解答時間途中で終了。
解法メモ
A問題
与えられたに対して、必要なキャンディーの個数はである。
B問題
入力文字列に対して、エディタ上の文字列*1を用意する。
だから、とわかる。ヌル文字を含めて11文字確保されていれば十分。
の文字を先頭から順に見ていき、
- 次の文字が0のときは、の末尾に0をつける。
- 次の文字が1のときは、の末尾に1をつける。
- 次の文字がBのときは、が空なら何もしない。が空でない時は、末尾から1文字消す。
最初にをヌル文字で埋めておき、の現在の文字位置を示す変数を用意すればよい。の先頭がヌル文字ならばは空だから何もしない。そうでない時はの文字目をヌル文字に置き換えて、をデクリメントする。
C問題
個の整数すべてを最小コストで書き換えられる整数をとおく。コストの総和は
だから、とわかる。
実際には、は整数とは限らないので、一旦をdouble型で計算し、nearbyint関数などで最近接整数をとるとよい。
そのときのコストはをバカ正直に展開するよりは最初からを計算するほうが早い。
個の整数の範囲がだから全探索でもすぐに終わるが、こういう問題を数学的に解けるようになっておいたほうがあとで生きてくることがあると思う。