ctyl's problem solving

競技プログラミングが主な話題です。

CODE FESTIVAL 2017 Final G Mancala

AtCoder

この記事は解説 Advent Calendar 17日目の記事です。

問題概要

G - Mancala

一列に並んだ N個のマスがある。各マスには 0 \leq x \leq K個の石を置くことができる。ここで次の操作を何回か行う。

操作：ちょうど i個の石が置いてある i番目のマスどれかを選び、 i番目の石を 0個に、 i-1以下番目のマスに石を1つづつ追加する。

操作回数ができるだけ多くなるような戦略で行って、最終的にマス目に残った石の数がスコアとなる。 ありうる初期状態すべてのスコアの総和をとるといくつになるか。

解法

(公式Editorialに補足する形式となっています)

操作1回によって石の数は1つづつ減るので、(初期状態の石の個数)-(スコア)=(操作回数)となる。 操作回数を多くするための最適な戦略は操作可能なマス目の中で最もindexの小さいマス目を選ぶことである(Editorial参照)。

全ての初期状態の石の個数の和は(各マス目に入る石の数の期待値) \times N \times (初期状態の場合の数)を考えると、

(各マス目に入る石の数の期待値) \times N \times (初期状態の場合の数) \\ = \frac{K}{2} \times N \times (K + 1)^{N}

となるので、 全ての初期状態の操作回数の和を求めることができれば、引き算でスコアの総和を求めることができる。

状態 dp(i, j)を(i番目を含む)i番目以降のマス目でj回操作が可能なi番目以降のみを考えた初期状態の場合の数と定め、 iについて後ろからDPを行う。

dp(i+1, j)からdp(i,*)を更新する際に気になるのが初期状態の時の i番目のマスにある石の個数( 0 \leq x \leq K)である。

この個数がiより大きい場合は i番目のマスで操作することはできないので i+1番目の操作回数をそのまま持ち越す。

そうでない場合はi番目のマス目で \frac{x+j}{i}回操作を行うことができる。こう立式できる理由は、最適な戦略ではi+1番目で何回か操作を行ってi番目がi個になった時点でi番目のマス目で操作を即座に行うことができるからである。(実際は即座に行うとは限らず、indexの小さいマスから順に操作を行うが、i番目のマスの石の個数に影響を与えることはない)

ここまでだと O(N^{4})に見えるが、操作の理論的な回数の上限を考えるともっと高速化することができる。 この問題だと N=K=100の場合で石の数が順に 1,2,3,\dots,100となっている場合の操作が最大で、3281回となっている。(検証用のソースコードも合わせて下に貼った) この高速化をすると十分間に合う。

Code Festival 2017 Final G Mancala

DPは想定された計算量で計算可能な状態を定義するところがそもそも難しい。この問題だと前から操作を行う最適な戦略で後ろからDPするので、再帰的な考えに慣れておく必要がありそう。

DDCC2017 本戦 C グラフいじり(+参加後記)

AtCoder

問題

ddcc2017-final.contest.atcoder.jp

解法

コンテスト中の自分の思考を再現してみたので、無駄な(最終的な解法を導くのに有効でない)考察も含まれている可能性がある。考察の正当性の証明はここでは省略する。

問題文には1つの辺の長さのみ変更できると書いてあるので、まずは長さを変更する辺を固定して考える。 例えば下のグラフの場合で有向辺1→2を選んだ場合、長さを2から-1にすれば全てのサイクルの長さを0にできる(出力はYesになる)。 f:id:ctylim:20171104030914p:plain:w300

このケースでよく観察すると、

  • 2→1の長さは1であり、つまり辺1→2の長さの符号を逆にしたものである
  • 辺1→2がないものとみなした場合、残った辺で作られるサイクルは全て長さが0である

ことがわかる。

f:id:ctylim:20171104032247p:plain:w400

ここから膨らませると、全てのサイクルの長さを0にするには、2→1に至るあらゆる経路において、長さは1でなくてはならないこともわかる。なぜなら2→1への経路は一般には1つとか限らず、たくさんある場合もあり、それらが1→2の長さと足して常に0になるはずだからである。

さらに、与えられるグラフは強連結なので、辺1→2を無視した場合でも、点2を始点とすればそれ以外の全ての辺を訪れることができることがわかる。 この考察から、辺1→2を無視した場合にサイクルでなくなるものとサイクルが維持されるものを区別する必要はなく、点2から全ての辺を訪れるようにDFSを行い、点2から全ての点への長さを計算して、2→1の長さの符号を入れ替えたものが1→2の長さとなることがわかる。

f:id:ctylim:20171104033820p:plain:w300

注意として、全ての点への長さをDFSで計算する際に、点2から全ての点への長さは一意でなければいけない(*)。下のような例は2→1の長さが一意に定まらないのでだめ。

f:id:ctylim:20171104034812p:plain:w300

これを全ての辺に対してチェックし、1つでも(*)が満たされている辺があれば答えはYesとなる。ただし、この解法では O(M^{2})となり、TLEしてしまう。

ここで、TLE解だと各点を始点とするDFSを何回(点がN個に対してM回)も行なっていることに注目する。上の図だと始点2でDFSを行うのは辺1→2を選ぶ以外に辺4→2を選ぶ場合がある。

何とかして無駄を省くことができないか考えると、例えば始点2のDFSの場合、辺1→2と辺4→2両方を無視しても、その他全ての辺を訪れることが可能であることに気づく。TLE解法と同じようにDFSを行うと、2→1の長さと2→4の長さがわかる。それぞれにおいて無視していた辺1→2との和、辺4→2との和をとり、0であるかどうかチェックする。ここでは高々1つまでの点で和が0以外であれば、Yesとなる(0でない場合はそれに対応する辺の長さを変えれば良く、1箇所までしか変えられない) 。

この解法だと、DFSをする回数は高々頂点の数になるので、O(NM)となる。

ソースコード

DDCC2017 Final C

参加後記

学生でもないのに新卒採用の一貫として開催されるコンテストの本戦に参加する権利が与えられてしまい、DISCOさんの懐の厚さを感じました。

コンテストの内容としては開始16分でA, Bを解いた後、終了8分前にCを通し、何とか3完することができました。7, 800点台の問題はAtCoderのレーティングが導入されてからずっと鬼門に感じていて、レーティングが伸び悩む原因になっていますね...。ある程度の精進で何とかなるかもしれない希望もありつつ、実際には精進できていないという現実があります。

将棋AIの特別対談のセッションは将棋AIを自分が手がけることはないだろうな...と思いながら聞いていたのですが、興味深く聞かせていただきました。将棋AIを育てていくのにも、例えばインフラ整えたりするところでサーバ貸し出しの交渉など社会性が必要となることもあったのこと。社会性を身につけなければ。

オフィス見学は技術の紹介より福利厚生の紹介の方が多く、(競技プログラマーがどういう生き物か)わかってらっしゃるという印象でした。個人的にはウェーハ加工で実際に動作させるソースコードのサンプルが見たかったです。

懇親会は普段Twitterや順位表でしか見ない方とお話できたので、満足しています(近場の人とはまた会いたい)。一度会ったことがあるのに挨拶できなかった方すみませんでした。もっと積極的に話に入るべきでした。

そろそろ純粋な競プロ以外のアウトプットもしていきたいところではあります(最近競プロのアウトプットでさえ危ういですが)。

AGC012 C Tautonym Puzzle

AtCoder

問題

agc012.contest.atcoder.jp

概要

aaはaを2回、bubobuboはbuboを2回繰り返している。このように長さ1以上の文字列を2回繰り返しているものは良い文字列と定義する。入力 N\leq 10^{12}が与えられるので、良い文字列である部分列の個数が Nである長さ200以下の文字列 sの1例を答えよ。ただし、文字の種類は最大 100種類しか使えない。

解法

まず例えば1, 2, 3, 4, 5, 1, 2, 3, 4, 5という文字列に良い部分文字列がいくつあるかを数えてみる。半分に分割すると、1, 2, 3, 4, 5から1個以上選ぶ方法存在し、それは 2^{5}-1通りであることがわかる( -1は空文字列の場合)。

ここに1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 6, 5のように6を追加すると良い部分文字列がいくつ増えるかを考える。6を含む選び方の数だけ増えるが、6と5を同時に選ぶことは出来ず、1, 2, 3, 4から0個以上選ぶ方法( 2^{4})通りだけ増える。 別の場合として、1, 2, 3, 4, 5, 6, 1, 2, 3, 6, 4, 5のように6を追加すると、良い部分文字列は1, 2, 3から0個以上選ぶ方法( 2^{3}通り)だけ増える。

このように、新しい文字種のペアを挿入する場所によって、増加する文字列の数を 2^{4}, 2^{3}, 2^{2}, 2^{1}, 2^{0}個増加させることができる。しかもこの挿入は独立なので、 1から 2^{5}-1個まで増加する文字列を1刻みで調節できる。

N=60の場合を例にすると、下のように文字を追加する。 f:id:ctylim:20170403021926p:plain

10^{12} \lt 2^{40}より、生成される文字列の長さは 40\times 2+40\times 2=160文字以下、文字の種類は 40 \times 2=80以下となる。よって制約を満たす文字列を作ることができる。

ソースコード

AGC 012 C

こういう構築系は配点がそこそこ高くても思いつき次第でACを狙える時があるので、レート上昇が滞っている今は解ける問題を時間中に貪欲に探していく戦略が大事かも。

yukicoder No.441, 442, 443 コメンタリー (解説なし)

yukicoder

初めてyukicoder contestのwriterをやりました。100人ほど参加してくださって、いろいろwriterとして得られるものがあったので書き残しておきます。解説はそれぞれの問題の解説タブに書いてあるので、ここでは解説や提出コードは書きません。

コンテストのリンク： yukicoder contest 153 - yukicoder

No.441 和か積

No.441 和か積 - yukicoder

簡単な問題、でも少し考察が必要という願いのもとで作りました。結局多倍長整数が扱えたらやるだけ、という問題になってしまいました。多倍長整数が使えなくても簡単な考察で正解することができますし、大きい数の組なら積が大きいというアバウトな考察でも正解することができます。コンテスト参加者の9割以上が正解していました。

No.442 和と積

No.442 和と積 - yukicoder

和&積シリーズで簡単な問題がもう一問作れないかと思って産まれた問題。多倍長整数は使ってほしくないけど Aと Bの最大公約数なら計算しても良いよ、という願いのもとで作りましたが、予想通り提出は多倍長祭りでした(C++だと__int128という抜け道があるのでほぼすべての言語でやるだけができる)。コンテスト終了後であっても64bit以上の整数型を使わず提出してくださった方、ありがとうございます。No.441とNo.442はyukicoderだから出せるかなというお楽しみ(?)問題でした。

No.443 GCD of Permutation

No.443 GCD of Permutation - yukicoder

コンテスト中想像以上に荒れた問題でした。荒れた原因としては、入力の制約に従っていないケースがあったり、乱択解やnext_permutation解を通してしまったテストケースの質の悪さが大きかったです。 O(N!)を試す人なんていないでしょうと思っていた(怠慢)のですが、そこはrandom_shuffleを使ったりしてうまくやっている人が多くて感心していました。

そして想像以上に難しく感じている人が多くてびっくりしました(当初は問題案は10分くらいで作れたし、考察もそこそこだからと★2に設定していました)。解法のポイントを簡単にまとめると、

  • Nの並べ替え N_1と N_2(N_1 \neq N_2)を考えた時、その差は必ず求める最大公約数 Gの倍数になる。
  • 下二桁の入れ替えで起こる差の最大公約数だけ考えれば、任意の桁の入れ替えで起こる差の最大公約数を考えていることになる。

の2点です。

この記事を書く直前に乱択解を撃墜するケースを追加してリジャッジをかけましたが、結局コンテスト中に正しい提出をしている方は8人でした。コンテスト中の時のAccepted rateがとても低かったので、かなり不安でした(問題の不備やwriter嘘解法説など)。

総評

問題を作る以上にテストケース作りが大変でした...ちゃんとしたテストケースを用意するにはいろいろな解法に触れている経験が必要ですね。自分の問題をいろいろな解法(嘘解法含む)で解かれているのは提出を見ていてとても勉強になりました。初writerにしてNo.443の評判がかなり良かったのはとても恵まれていたと思います(TLの感想は大体読んでいます)。また面白い数学的な性質を利用した問題を作りたいと思います。

AGC003 D Anticube

AtCoder

概ね解説と方法は同じですが、自分の方法は少しアプローチが違うので書くことにしました。

問題

agc003.contest.atcoder.jp

概要

正の整数列 {\{s_i\}_{i=1\dots N}}があたえられる。この中から出来る限り多くの整数を選んで、どの2つの要素の積も立方数にならないようにしたい。最大何個まで選べるか。

解法

考察

最初の考察として、 aと bの積が立方数になるならば、任意の整数 c, dについて {ac^{3}}と {bd^{3}}は立方数になるという性質を考えます。

この性質から、もし aと bが同時に選べないならば、 {ac^{3}}と bも同時に選べないことがわかります。

ここで、数列の各要素を3乗数で割り切れなくなるまで割ることを考えます。そのとき3乗数で割った数列の中では、ある元 a(\neq 1)と同時に選べない数字は一つしか存在しません。何故なら、 a={p_1}^{m_1}{p_2}^{m_2}\dots{p_k}^{m_k}と素因数分解した時、 m_iは必ず1か2になり、 b={p_1}^{3-m_1}{p_2}^{3-m_2}\dots{p_k}^{3-m_k}と一意に定まるからです。逆に bからも aを一意に定めることができ、この2つの整数はペアとして考えることができます。

2以上の数字はかならずそれ自身と異なるペアを持ちますが、1のペアは1なので、特別に処理する必要があります。

3乗数で割った数列のなかで同じ数字はひとまとめにして個数で管理することにすると、次の方針で答えを出すことができます。

  • a, bがペアのときは、個数が多い方を選び、答えに加算する。
  • 特例として、数列に1が存在するときは、他のどの1ともペアを作ってしまうので、答えに加算するのは1である。
アルゴリズム

まず数列の各要素を3乗数で割り切れなくなるまで割る部分ですが、 10^{10}の3乗根までの素数( 2200くらい)の3乗で割ると間に合います。(素数→整数としてしまうと、TLEします)

次に、各要素のペアを求める部分です。各要素は a={pq^{2}}と書くことができます(ただし、 p,qは相異なる素数の積)。このとき、ペア bは b=p^{2}qとなります。まず方針を述べると、 {p, p^{2}} ( q=1)のペアと pq^{2}, p^{2}q ( q>1)のペアに場合分けをして考えます。

{p, p^{2}} ( q=1)のタイプのペアを見つけたい場合は、各要素について2乗したものが数列の中に存在するかを調べれば良いです。全ての要素について調べると、long longでもオーバーフローしてしまう可能性がありますが、数列を小さい順にソートして、 10^{5}まで調べれば十分です。

pq^{2}, p^{2}q ( q>1)のタイプのペアを見つける場合は、各要素について素数の2乗でひたすら割って、残った数を2乗し、割った素数と積をとったものが数列の中に存在するかを調べれば良いです。愚直にやると 10^{5}までの素数で割らなければいけないため、少し工夫をします。

{{p}\lt{q}}として、数列の小さい順にペアを探すことを考えます。すると、 p^{2}qの方が pq^{2}よりも前に探すことになります。この時、ペア pq^{2}が数列に存在するならば pは 10^{10}の3乗根を超えることはありません。なぜなら {p}\lt{q}なので、超えてしまうと pq^{2}>10^{10}となってしまうからです。よって、数列の小さい方から 10^{10}の3乗根までの素数の2乗で割ってペアを計算すれば良いです。

時間計算量は K=2200までの素数の個数を Pとすると、素数列挙の前処理で O(KP)、数列のソートで O(N\log N)、 p, p^{2} タイプのペアの計算で O(N)、 pq^{2}, p^{2}qタイプのペアの計算は O(PN)となります。 Pは300弱なので、間に合います。

コード

AGC 003 D

コメンタリー：本番は素数列挙せずに解いたため、TLEしてしまった。定数倍と素数列挙分の高速化の意識が足りず、普通に間に合うと思ってしまったが、早くできるところはした方がよさそう。

ICFPC 2016 参加レポート

kenkooooさん,roitiさん、わいんさんとICFPCにチーム"COBOL Lovers"で参加していました。

全員非学生なので金曜は問題を読む日にして、土日に集まって問題を解いていました。会場を提供してくださったkenkooooさん及び同居人の方に感謝します。

問題概要

ICFP Programming Contest 2016: Official Site

  • 正方形の折り紙を折った時のシルエット(頂点と辺の情報)が与えられる。どのように折り目がついたかの展開図と、折った時の頂点がもともとどの点と対応しているかを答えよ。ただし、最初は折り紙は(0,0), (0,1), (1,1), (1,0)を4頂点とし、入力は必ず有理数で表現される。折った後の折り紙は回転移動や平行移動を含んでいる場合がある。

入力は次の順に与えられる。

  • 折り紙を作る多角形の個数。以降の入力が多角形の個数分与えられる。
  • 多角形の頂点の個数
  • 次に頂点が列挙される。中実の場合は時計回り、中空の場合は反時計周りに列挙される。
  • 線分の本数
  • それぞれの線分の両端の頂点
1
4
0,0
1,0
1/2,1/2
0,1/2
5
0,0 1,0
1,0 1/2,1/2
1/2,1/2 0,1/2
0,1/2 0,0
0,0 1/2,1/2

ビジュアライズしたもの(kenkooooさん作) f:id:ctylim:20160809224148p:plain

次の順で出力する。

  • 展開図の頂点の数
  • 折った時の各頂点の座標
  • 展開図の折り目がついた多角形の数
  • 多角形の頂点の個数、及び上で出力した頂点のどのindexに対応するかを時計回り、または反時計周りで列挙
  • 折られる前に各頂点がもともとどこにいたか

出力例

7
0,0
1,0
1,1
0,1
0,1/2
1/2,1/2
1/2,1
4
4 0 1 5 4
4 1 2 6 5
3 4 5 3
3 5 6 3
0,0
1,0
0,0
0,0
0,1/2
1/2,1/2
0,1/2
1日目

問題を読む。yukicoderがあったので参加した。

2日目

折り紙を買う。会場にてチームメイトと合流する。すでにkenkooooさんが問題をクロールして、入力をビジュアライズするスクリプトを書いていたので、ありがたく使わせて頂く。そして全員がpythonを使う流れに。入力に有理数表現があって、fractionモジュールがあるpythonを使うのは結果的に正解だった。

2日目は有効な手法をほとんど実装できずに終わってしまった。roitiさんが何も折らない正方形の解をひたすら無差別に提出していたからか、一時期順位が50位くらいまで上がった時があった。オーバーフローさせるだけの(クソ)問題がいくつか提出されていて、インタラクティブなコンテストの難しさを感じた。(正解者は入力のサイズに比例した点数が獲得できる)

公式から折り紙シミュレーションプレイヤーの提供があった。ソースは難読化が施されたjavascriptで書かれていたらしく、それを解読したら難読化されたアルゴリズムが記述されていた。もちろん読めない。

凸包解はコンセプトは簡単に思いついたが、実装が難航し、この日は手動提出+正方形爆撃で終了。

3日目

とにかくプログラムを書いて簡単な非自明な問題に正解することを目標とした。夕方ごろまで実装が何も進まず、鶴を折れなかったり、わいんさんが筋肉で非自明な問題を提出をしているのを観察していた。ずっと頂点の対称移動の方針で考えていたが、面の対称移動をする方法を思いつき、夕方頃から1回折る問題に解答できるソルバーの実装を始める。わいんさんがあらかじめ実装していた対称移動ライブラリをお借りしたが、実装が終了する前にわいんさんの帰る時間となり見送ることに。

すまん、どうしても寿司が食べたかったんだ...

食後に折り目によって分割された面を木で管理する方法を思いつく。帰宅後は自分のソルバーの続きを実装。 夜中に1回折る問題を半自動(折り目のみ指定)で数問通した。この程度だったら2日目に実装できたレベルだが、疲れたので次のステップに進むことはできなかった。kenkooooさんから面を木で管理する方法でかなりうまくいったらしいが、無限のバグで死亡したという報告を受け、寝る。

総評

最終順位は約300チーム中80位前後でした。自分の貢献度が低すぎてチームメイトに申し訳なかったのですが、ワイワイできて楽しかったです。3日目に思いついたアイデアを2日目に思いついていたらもうちょっと生産的になったかも、という後悔もありました。またインフラの重要性も感じ、前半でインフラをどれだけ充実できるかも勝負を有利に進めるポイントとなった気がします。というのも、提出の結果は手動提出時のリザルトページかAPIレスポンス経由でしか取得できず、チーム参加の場合は提出環境を統一して、問題リストを一括管理する必要を感じました。公式のジャッジシステムやシミュレーションツールがとても出来が良く、公式ツールレベルの実装に達しただけでも相当上位に食い込めそうな印象でした。チームUnagiが潜伏しながら首位争いをしていて、格の違いを感じました。ネタが折り紙だからか、日本人のチームが上位に多かったようです。普段のコンテストと違い、こういった長時間のコンテストも楽しかったので、来年も参加したいと思います。

チームのソースコード及び自分のスパゲッティソルバーはこちら。 github.com

JAG Contest 2016 Domestic 参加記 (C, Eレビュー)

AtCoder JAG

kenkooooさん、roitiさんとチームshinsotsuで参加。会場を提供してくださったroitiさんに感謝いたします。

結果：CとEを担当して総合15位。Eはroitiさんの考えた解法を自分が実装した形になり、チーム戦っぽいことができてよかったです。幾何は基本的なライブラリがある程度ないとVerifyだけで時間を取られてしまうので、今回ACできたコードはライブラリに入れようと思います。

C問題

jag2016-domestic.contest.atcoder.jp

解法： 構文解析+DFS。ノードを作って二分木のデータ構造を構築してしまう方法もあるが、DFSをやりながら対応する頂点をマージし、stringを再構築する方法を思いつき、楽そうということもあって途中で方針転換した。

JAG 2016 C

コメント：サンプルが仰々しいせいか、考えを整理するのに時間がかかってしまった。stringそれぞれの処理を愚直に書いてしまったが、プロコンだから許してください

E問題

jag2016-domestic.contest.atcoder.jp

解法： 幾何。最も多くの有権者がX氏を見ることのできる領域の境界上を考えると、各有権者がどこかの障害物の頂点をみて、かつ視線がその障害物によって妨げられない場合のときを考えればよい( * )。各有権者が各障害物に視界を遮られない領域の境界は2本の直線で表現できる(**)。

ここで、有権者A, Bがいて、先ほどの2本の直線をすべての障害物に対して描いたとする。下の図でいうと、赤い4本の直線、青い4本の直線のことである。ここで赤い直線と青い直線の交点( 4 \times 4 = 16個)を作ることができる(平行の場合は交点がないのでさらに少ない)。極端な話をいうと、( * )の考察から、この交点にX氏がいると仮定してもよい。各交点に対し最高何人から見えるかチェックすればよい(***)。最後にそのmaxを取る。

  • (**)の計算 有権者からある多角形の障害物のすべての頂点に直線を引き、多角形を貫通しているかどうか調べればよい。計算量は O(LMN)

  • 2人の有権者の組ごとに交点を計算する 直線と直線の交点の計算。これが意外と書くのが大変。計算量は O(M^2N^2)

  • (***)の計算 各交点から各有権者に線分を引き、ある多角形を貫通しているかどうかを調べればよい。計算量は O(LM^3N^3)

f:id:ctylim:20160425025118p:plain

JAG 2016 E

コメント：すべて一から実装したのもあり、バグを各所に生んでしまってまるまる2時間かかってしまった。mainの中身は20分程度で実装できたが、結局直線の多角形貫通判定、直線同士の交点導出のデバッグで時間を取られた。直線同士の交点を計算するだけとはいえ、甘く見ては痛い目を見る。誤差死は今回は |x|,|y|が小さいので気にしなくてもよいと思われる。

総評：