ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

Educational Codeforces Round 48 参加記録

Dashboard - Educational Codeforces Round 48 (Rated for Div. 2) - Codeforces

初めてのこどふぉ参戦!

結果はA~Dの4完で478位でした。

f:id:betrue12:20180811155629p:plain

1問ずつ振り返っていきます。

A. Death Note

Problem - A - Codeforces

英語よりも、一番下のNoteを見ると分かりやすいです。1を  a_{1} 個、2を  a_{2} 個…というのを各ページに  m 個区切りで書いていきます。そのとき、それぞれの数字を書く際に何回ページをめくりますか、という問題。 ただし、「ちょうど書き終わった」時にもページをめくるものとします。*1

 m 個書くたびにページをめくるので、累積で  x 個目の数字を書いた後のページは  floor[\frac{x}{m}] ページ目になります。累積和を計算して、それぞれの数字を書く前と後のページ数で差を取ればよいです。

ACコード:Submission #41161044 - Codeforces

1問目から英語に手こずるという…もしサンプルが「ちょうど書き終わった」時の処理を含んでいなかったら、それに気付かずWA地獄になっていたと思います…。

B. Segment Occurrences

Problem - B - Codeforces

文字列  s, t が2つ与えられ、クエリで  s の範囲が指定されるので、その範囲から連続部分文字列として  t が取れる箇所はいくつあるか、という問題。

 s i 文字目から  i+M-1 文字目までが  t と一致するか」は前計算できます。全箇所調べるのに  O(nm) かかりますが、  10^{6} くらいなので間に合います。

この前計算の結果を使ってクエリを処理するのですが、そのままやると  O(nq) 10^{8} くらいなので速い言語だとこのまま通りそう…?ですが、累積和を取っておけば高速化できます。

クエリの範囲が狭すぎる場合はちゃんと別で処理してあげないとマイナスとかになるので気をつけましょう(2敗、ひどい)

C. Vasya And The Mushrooms

Problem - C - Codeforces

ゴリゴリ実装しましたが、どう解くのがスマートなんだろう…

まず、可能な動きのパターンを整理します。全部のマスを1回ずつ通らないといけないという制約から、動きのパターンは以下のようなものに限定されます。

f:id:betrue12:20180804110723p:plain

実際に可能な動きのパターンは全部で  n 通りあります。意外と少ないですが、各経路を毎回計算していると  O(n^{2}) かかってアウトなので高速化します。

まず、横Uターンの経路の得点をそれぞれ前計算しておきます。そして、「途中まで縦ジグザグした後に、横Uターンする」時の得点を、縦ジグザグを1手ずつ進めながら計算していきます。

縦ジグザグ部分の得点は、順次足し算をしていけばよいです。そして横Uターンの得点は、「縦ジグザグを進めることで、横Uターン部分の得点はどう変化するか?」を考え、差分だけ更新していきます。

f:id:betrue12:20180804112637p:plain

縦ジグザグを進めた際に、横Uターンの得点は

  • 既に通過した点から得られるはずだった得点が得られなくなる。
  • 通過していない点は、通るのが先延ばしになるため、倍率が増える。*2

と変化します。それぞれの差分が分かれば、横Uターン部分の得点が計算できそうです。

まず「通過していない点は、通るのが先延ばしになるため、倍率が増える」については、通過していない点の  a_{i} または  b_{i} の合計を持っておけば、それを足すことで実現できます。最初に全部足した値を持っておいて、通過した点を順次引いていきましょう。

次に「既に通過した点から得られるはずだった得点が得られなくなる」ですが、これを正しく除くには「その時点で、その点が何倍として扱われているか」を知っている必要があります。このとき、前述の「倍率が増える」操作も考慮する必要があります。最初に横Uターンの得点を計算した時点で何倍として扱われて、そこから何回倍率が増やされたか、を管理しておけばよいです。

前計算しておけば1回1回の計算は  O(1) なので全体で  O(n) のはずなんですが…Rubyだと時間ギリギリですね…

ACコード:Submission #41177718 - Codeforces

D. Vasya And The Matrix

Problem - D - Codeforces

閃き勝負の問題。Cより先にこっちを解いておけばよかった…

 n \times m の行列において、各行と各列のxorが条件として与えられるので、それを満たす行列を求めよ、という問題。

まず、解が存在する必要条件が思いつきます。行xorを全部xorすると、全部の要素のxorになるはずです。同様に、列xorを全部xorすると、やはり全部の要素のxorになるはずです。ということは、これが一致しない場合は「解無し」です。

では、「行xor全部のxor」と「列xor全部のxor」が一致するときに必ず解が存在するかというと、実は存在します。以下のように構成すると、条件を満たすことができます。

f:id:betrue12:20180804115438p:plain

これを思いついてしまえば、コードもすぐに書けます。

ACコード:Submission #41179410 - Codeforces

さいごに

今回初めてのCodeforces参戦でしたが、いきなりコンテスト開始が遅延して「こどふぉった」を体験しました。

問題については、AtCoderのような点数が出るわけではないので難易度の見極めが難しいです。あと、英語はやっぱり時間取られて、心理的にも「読み間違いがあるんじゃないか?」という不安がつきまといます。慣れるしかないですね。

順位を決めるペナルティについては、まだあまり仕組みを理解できていませんが…AtCoderのように「コンテスト全体で、最後に点数が増えた時刻」が使われるのではなく、各問題ごとの時刻が使われるようなので、解く順番がけっこう重要なのかなと思いました。

あとは開催時刻…想像以上に眠かったです。とりあえず、深夜の参加は金曜土曜だけにしておこうかなと思います…生活が壊れそう。

言語はRubyが使えるだけでもありがたいですが、バージョンが2.0なので、これ以降に新しく追加されたメソッドを使わないように注意ですね。けっこう時間制限もキツそうだし、おとなしくC++使えという話もありますが。

こどふぉを始めた理由は、AtCoderの過去問解きがそろそろ800点くらいになってきて、解いている問題に対して実力が足りないので数をこなしたいなあと思ったからです。あと、最近AtCoderでratedコンテストが少ないので手を付けてみたという理由もあります。

やっぱりコンテストは楽しいですね。こどふぉにもちょっとずつ慣れていきたいです。

脚注

*1:原文「Note that you always turn the page when it ends, it doesn't matter if it is the last day or not.」に対応。

*2:正確には、1手進めるごとに「横Uターン1」「横Uターン2」いずれかの倍率が増えます。実験して、辻褄が合うようにコードを書いていきましょう。