読者です 読者をやめる 読者になる 読者になる

ctyl's problem solving

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

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|が小さいので気にしなくてもよいと思われる。

総評:

yukicoder No.348 カゴメカゴメ

yukicoder

★4昇格.Union-find,木DP,DFSなど色々な要素が入っている問題でためになるのだけれど,実装がかなり難関.個人的には今までyukicoderの問題の中で最凶クラスの実装難の問題でした.


方針:輪の包含関係を根付き木で表現する.Union-findなどで各輪の強さを求め,あらかじめ構築しておいた木において『ある輪と,その輪のすぐ外側にある輪の両方を使用することは出来ない』という条件を満たすようにDPを行う.

Step 1:根の'.'が飛び地になることがあるので,周囲をもう一周'.'で囲む.サンプル4にこの操作をすると下の図のようになる(縦と横が2マスづつ増える).こうすることで一番外側の'.'はすべて共有されることになる.

f:id:ctylim:20160227173727p:plain:w300

Step 2:Union-findを使って'.'のつながり,'x'のつながりを一つの代表元にまとめる.上の図の丸で囲ったところが各素集合の代表元(の例)である.ここで注意すべき部分は'x'は周囲8方向に存在する'x'とマージできるが,'.'は上下左右の4方向の'.'としかマージできないことである.時間計算量: O(NM)

Step 3:根を左上の'.'を含む'.'のつながりとし,そこから一枚づつ'.', 'x', '.', 'x', ...と交互に剥がしていくようにグリッド全体を走査しながら木を作っていく(dfs).木に追加した素集合を訪れたかどうかはメモしておく(vis).ここでも'x'の内側にある'.'を探すときは周囲8方向をチェックすれば良いが,'.'の内側にある'x'は上下左右の4方向しかチェックできない.サンプル4では下のような木ができる.青が'.'で赤が'x'に対応する.時間計算量: O(NM\log (NM))

f:id:ctylim:20160227173658p:plain:w300

Step 4:赤のノード('x')のみを辿ってDPを行う(dfs_m).一例として,配列dp[i][0]には「マス目iにある輪より内側にある輪のみを使ったときの最大の強さ」,dp[i][1]には「マス目iにある輪を使い,かつ内側にある輪を使ったときの最大の強さ」を記録しておく方法がある.時間計算量: O(素集合の数)

サンプル4での計算例(更新則):

 dp[28] [0] = \max (dp[80][0], dp[80][1]) + \max (dp[89][0], dp[89][1])

 dp[28][1] = dp[80][0] + dp[89][0]

最後にノード0の子の強さをすべて足しあわせることで答えとなる.

yukicoder No.348


BFSもいいけどDFSの実装のコンパクトさが体感できたので,徐々に再帰は慣れていきたい.

yukicoder No.209 Longest Mountain Subsequence

yukicoder

DP★3.3ヶ月位前にも一度挑戦していて,その時は自分の方針のアラが探せず出来ずじまいだったが,今回は一発でACできた.

方針:{S_{i-1}-S_{i-2} \lt S_i-S_{i-1}}を満たす最長の上昇部分列の長さを今選んでいる要素のindex,直前に選んだ要素のindexの情報を持った上で求める.下はA= \left\{1,7,5,3,1,6,3,9,1 \right\} のときの例.各 iに対する最大値が A_iを最後に使ったときの最長の上昇部分列長である.自分の提出は左からの上昇列長を求めたら,Aを反転して同一の処理をしている.

f:id:ctylim:20160224181654p:plain:w500

yukicoder No.209


想定解が Q \leq 100, N \leq 100 O(QN^3) なのだけれど,意外と間に合うのね.

Codeforces AIM Tech Round Div.2 C Graph and String

Codeforces

本番はSCCに固執しすぎて実装が間に合わず.その後冷静に考えたらもっと単純な方法があった.

解法

まず気づきそうなこと:実線は辺,点線はそうでないとする.次のようなグラフの場合,bは一意に決定する.

f:id:ctylim:20160206160557p:plain:w250

そこで点線を辺とする(完全グラフから与えられるグラフを引いた)グラフに着目する.このグラフが下のように2つ(以上)に独立していると仮定する.

f:id:ctylim:20160206160600p:plain:w250

点線の両端は(a,c)で一意に決定する.

f:id:ctylim:20160206160603p:plain:w250

上と下のa,c同士は必ず結ばれる.

f:id:ctylim:20160206160604p:plain:w250

よってそのようなグラフの仮定は間違っていて,点線で構成されるグラフは連結である.それを確認した上で,(a,c)は辺で結ばれ,(a,a),(c,c)は結ばれないような判定をすればよい.幅優先探索などで深さの順番にa,c,a,c,...とメモして行って,最後に全ての頂点の組み合わせで前述の判定をすると上手くいく.

AIM Tech Round 2C

二部グラフの判定方があればそれを使えばよさそうですが,自分はあるかどうかすら知らないです.もっといい方法があれば教えて下さい). 時間内に解けたら美味しかっただけに悔しい回でした.