2018-01-14

AGC018 A Getting Difference

数学的な問題ほど解けないの、どうすればいいんでしょう…？
（解説を読んだ後、フォロワーさんたちにもいろいろ教えていただいた）

問題概要

箱に $N$ 個のボールが入っていて、 $i$ 番目のボールには整数 $A_i$ が書かれている。
「箱から2つのボールを取り出し、その2つのボールに書かれている整数の差の絶対値を書いた新しいボールとともに箱に戻す」という操作を好きな回数行うことができる。
整数 $K$ が書かれたボールが、箱の中に入っている状態にできるかどうかを判定する。

制約
$1 \le N \le 10^5$
$1 \le A_i \le 10^9$
$1 \le K \le 10^9$

解法

（自分が理解したとおりに書いているので冗長でわかりにくいかも）

$M = max \{ A_i \}$ とする。

$M < K$ のときは不可能であることは明らかなので、 $K \le M$ の場合を考える。

$G = gcd \{ A_i \}$ とする。

$M$ は $A_i$ のうちのどれかなので、 $M$ は $G$ の倍数である。

$K$ が $G$ の倍数ならば、 $M$ から $G$ を繰り返し引けば、かならず $K$ ができるので、 $G$ が書かれたボールを作れればよい。

$G$ が書かれたボールがどんなときでも作れるのは互除法の考え方からわかる*1。

また、 $K$ が $G$ の倍数でないなら、 $K$ の書かれたボールはつくることはできない( $A_i$ はすべて $G$ の倍数であり、 $G$ の倍数同士の差は必ず $G$ の倍数になる) 。

よって、この問題は

$K$ が $A_i$ の最大値以下であるか
$K$ が $A_i$ のgcdで割り切れるか

の2点を確かめさえすれば良い

Submission #1967366 - AtCoder Grand Contest 018

*1:2つの整数 $x, y$ ( $x > y$ とする) の差を繰り返し計算していくと、整数 $x \% y ( = r )( x$ を $y$ で割ったあまり ) を作ることができる。つぎに $y, r$ の差を繰り返し計算していくと、整数 $y \% r$ を作ることができる。これらの操作はユークリッドの互除法と同じで、最終的には $x, y$ のgcdを求めることができる。 $N$ 個の整数のgcdを求める操作は2個の整数のgcdを求める操作の繰り返しでできるので、この問題で与えられた操作を使って、 $A_i$ のgcdが書かれたボールを作ることができる

2018-01-13

ABC079 D Wall

競技プログラミング AtCoder

D - Wall

問題概要

1つの数字を $i$ から $j$ に変えるコストを $c_{i,j}$ とする。
$H \times W$ 行列 $A$ が与えられ、 $A_{i,j} \neq -1$ のとき上から $i$ 番目、左から $j$ 番目のマスに数字 $A_{i,j}$ が書かれていて、　 $A_{i,j} = -1$ のとき上から $i$ 番目、左から $j$ 番目のマスに数字が書かれていないことを意味する。
マスに書かれたすべての数字を1にする最小コストを答えよ。

制約
$1 \le H, W \le 200$
$i \neq j$ のとき $1 \le c_{i,j} \le 10^3$
$i = j$ のとき $c_{i,j} = 0$
$-1 \le A_{i,j} \le 9$

解法

数字を頂点番号だと思って、各頂点から頂点1への最短経路を求めます。（ワーシャルフロイドが一番書く量が少ないのでワーシャルフロイドを書いた）
あとはそれぞれの数字がマスにいくつ書かれているかを計算して、コストを掛けて出力する。

Submission #1965974 - AtCoder Beginner Contest 079

2018-01-12

ARC083(ABC074) D Restoring Road Network

競技プログラミング AtCoder

D - Restoring Road Network

問題概要

$N$ 次正方行列 $A$ が与えられる。すべての $u, v$ について、 $A$ の $u$ 行 $v$ 列成分が頂点 $u$ と頂点 $v$ の最短距離となるようなグラフが存在するかを判定する。また、存在する場合、そのようなグラフのうち辺のコストの総和が最小となるものについて、その総和を求めよ。

制約
$1 \le N \le 300$
$i \neq j$ のとき $1 \le A_{i,j} = A_{j,i} \le 10^9$
$i = j$ のとき $A_{i,j} = 0$

解法

実質ワーシャルフロイド(?)

頂点 $i$ から頂点 $j$ に行く最短距離が、頂点 $i$ から頂点 $k$ を経由して頂点 $j$ に行く最短距離よりも長いことはありえない*1、もしそうなっていたら、そのようなグラフは存在しないので-1を出力する
頂点 $i$ から頂点 $j$ に行く最短距離が、頂点 $i$ から頂点 $k$ を経由して頂点 $j$ に行く最短距離と等しいならば、頂点 $i$ と頂点 $j$ の間にある辺は取り除いて良い

を実装する

（2は未証明だけど投げたら通ったのであんまり理解してないです）

Submission #1963963 - AtCoder Regular Contest 083

*1:距離の公理

2018-01-11

ABC084 D 2017-like Number

競技プログラミング AtCoder

400点以上の問題は積極的にブログに書こうと思います。

D - 2017-like Number

問題概要

「 $N$ も $\frac{N+1}{2}$ も素数」を満たす奇数 $N$ を2017に似た数と定義する。
$Q$ 個のクエリが与えられるので、それぞれのクエリに対して、 $l_i \le x \le r_i$ かつ2017に似た数となる奇数 $x$ の個数を答えよ。

制約
$1 \le Q \le 10^5$
$1 \le l_i \le r_i \le 10^5$

解法

方針は以下の通り。

$N$ のとりうる上限( $10^5$ )まで素数判定をする(試し割りだと間に合わないのでエラトステネスの篩を使う)
$N$ のとりうる上限( $10^5$ )まで2017に似た数判定をする
累積和を使って、「N以下の2017に似た数の個数」をすべて*1の $N$ について求める
各クエリ $l_i, r_i$ に対して、 $r_i$ 以下の2017に似た数の個数から $l_i$ 以下の2017に似た数の個数を引いたものを出力する

Submission #1961699 - AtCoder Beginner Contest 084

感想

そすーそすー

*1:本当は奇数だけで良いが、場合分けが面倒なので

2017-09-29

ACPC2017参加記

参加記競技プログラミング

会津大学競技プログラミング合宿2017 : ATND に参加してきました。

day 0

今年も会津の地に前日入りした。昼過ぎの京都発の新幹線に乗って、会津若松駅に着いたのが18時ごろだったので、やっぱり会津は遠いな〜と1年ぶりに思った。

新幹線の中では主にデレステをしていた。

駅前のマルモ食堂の会津ラーメンです！ pic.twitter.com/3eEYeO2yck
— あんずどーなつうさぎ (@wk1080id) 2017年9月17日

ホテルは駅前だったので移動が楽だった。ホテルではデレステをしていた。

会津、神の地では(10連で念願の結城晴出ましたありがとうございます！！！！ pic.twitter.com/urqSFA1Frw
— あんずどーなつうさぎ (@wk1080id) 2017年9月17日

なんか合宿前の高揚感とガシャの引きによる高揚感で4時まで眠れず（ア

day 1 立命館大学セット

ぽきた
— あんずどーなつうさぎ (@wk1080id) 2017年9月17日

起床のプロなので7時半に起きた。

ぼく「あれ？スタミナが全回復してないぞ？ちゃんと寝たはずなのにおかしいな…」
— あんずどーなつうさぎ (@wk1080id) 2017年9月17日

ホテルの無料朝食おいしい。

pic.twitter.com/PBQKEftawt
— あんずどーなつうさぎ (@wk1080id) 2017年9月18日

ヅに島村卯月の中の人が来るらしくて羨ましい。

へごちんー！ pic.twitter.com/kkV86lJhIy
— あんずどーなつうさぎ (@wk1080id) 2017年9月18日

初日なので自己紹介があって、(何かネタに走ろうかとも考えていたけど)普通に名前だけ言った。ウクニキアさん(@ukuku09)が面白かった。

コンテストは、立命館がジャッジ側だった。コンテストが始まってから、解説スライドを作りながら自分たちが考えた問題が解かれていくのを眺めてた。

コンテスト後にC問題の解説*1をした。

原案はAとCと若干B*2。Aはもともとシャトルランを題材にしていて、2回連続で線にたどり着けなかったら終了みたいなのを考えていたけど、シャトルランの定義が難しいということで丸付けになった。CはTwitterをしていたら降ってきたもの。Twitterから作問のインスピレーションを得ることが多い。

初日の懇親会は会津の人がたくさんいるテーブルにいたので、会津の人の話を聞いていた。その場にいないのにbeetさん(@beet_aizu)とうしさん(@ei1333)が話題にされていた。ツカサさん(@tsukasa_diary)と隣だったので北海道の話も聞いた。

ホテル帰ってかららずくん(@Luzhiled)とめる先輩(@ixmel)と一緒にデレステをした（DEGwerさんもいた）。

メンバーが競プロのプロやが
— あんずどーなつうさぎ (@wk1080id) 2017年9月18日

日付変わる前くらいに解散して明日の準備をしてからデレステをした。

さて、今夜もね、デをして寝ようと思うのですが、
— あんずどーなつうさぎ (@wk1080id) 2017年9月18日

デレステ、やると目が醒めることで有名
— あんずどーなつうさぎ (@wk1080id) 2017年9月18日

眠気が完全に飛んだ
— あんずどーなつうさぎ (@wk1080id) 2017年9月18日

どうしようかなぁ……

よし！デレステしよ！w
— あんずどーなつうさぎ (@wk1080id) 2017年9月18日

結局グダグダ4時まで起きてた（ア

day 2 会津大学セット

朝起きるのが世界一下手すぎる(二度寝した
— あんずどーなつうさぎ (@wk1080id) 2017年9月18日

朝起きるのが世界一下手なので二度寝して8時半に起きた。それでも起床のプロなので(?)無料朝食と集合時間には間に合った。

コンテストに問題を解く側として参加。

@DAyamaCTF さんと @Luzhiled さんと一緒に、チームacpc_hayaokiで出ます！
— あんずどーなつうさぎ (@wk1080id) 2017年9月19日

B問題を担当して、1時間くらいかけてバグらせながらACした。そのあとはDの考察に加わったり問題を読んだりしてたが、とくに貢献はできず。

ABCEFIの6完でした(個人で言えばBの1完(ア
— あんずどーなつうさぎ (@wk1080id) 2017年9月19日

解説はDとMが頭良すぎて素晴らしくてやばかった。

解説が終わってから懇親会会場に移動するまでの間にkzyKTさん(@kzyKT_M)とK問題について少し話した。

K問題を見たぼく「Chino……Chino……(ここで脳死
— あんずどーなつうさぎ (@wk1080id) 2017年9月19日

懇親会に移動するときに近くにうしさんがいたので少しお話しした。

🐮さんに話しかけたい
— あんずどーなつうさぎ (@wk1080id) 2017年9月19日

🐮🐇
— あんずどーなつうさぎ (@wk1080id) 2017年9月19日

が、話すのが苦手なのですぐにTwitterに逃げた。

Twitterを眺める会をしています
— あんずどーなつうさぎ (@wk1080id) 2017年9月19日

ACPCday2、リスト荒らし担当です
— あんずどーなつうさぎ (@wk1080id) 2017年9月19日

2日目の懇親会は右隣にらずくん、左隣にkzyKTさん、正面にめる先輩がいて、途中でみんな揃ってデレステの宝くじとガシャをやり始めたのがハイライト。

ホテルに帰って来たためデをします
— あんずどーなつうさぎ (@wk1080id) 2017年9月19日

ホテル帰ってかららずくん(@Luzhiled)とめる先輩(@ixmel)と一緒にデレステをした。

日付変わる前くらいに解散して明日の準備をしてからデレステをした。

3日目は集合が早いので早く寝ようと思っていたら気づいたら3時回ってた（ア

day 3 北海道大学セット

早起きするのが世界一苦手
— あんずどーなつうさぎ (@wk1080id) 2017年9月19日

早起きするのが世界一苦手なので7時半に起きた。それでも起床のプロなので(?)無料朝食と集合時間には間に合った。

コンテストに問題を解く側として参加。

チーム ACPC_Anzio_High（with @__KasSA さんと@__imulan__ さん）です！
— あんずどーなつうさぎ (@wk1080id) 2017年9月20日

アンツィオ高校が何のアニメかわかりませんでした＞＜
— あんずどーなつうさぎ (@wk1080id) 2017年9月20日

チーム名は何かのアニメに出てくる高校の名前らしいです（よく知らず……

B問題担当で、問題を見た瞬間数学で内心*3ハイテンションだった。が、考えてみると難しすぎて、imulanさんと一緒に考察していた。1時間くらいかかったけど、0WAで通せた(実装したのはimulanさんなのでぼくが通したわけではない)のは良かった。

Bを通した段階でチームとしてはABCの3完でDの考察も結構進んでいて、その後特に貢献とかはできなくて、考察や実装を眺めていた。

チームとしてはABCDEGの6完、ぼくはBの考察担当でした（1問もsubmitしてない
— あんずどーなつうさぎ (@wk1080id) 2017年9月20日

おみやげを買って会津若松で電車に乗ろうとしたらうしさんとらずくんに会った。のでデレステをした。(立命館勢が乗り込んだ後に他のACPC参加者も乗ってきたので競プロer率がやばかった)

郡山で新幹線の乗り換えまで時間があったのでアニメイトに行った。広かった。

pic.twitter.com/6XQ5oTh96t
— あんずどーなつうさぎ (@wk1080id) 2017年9月20日

新幹線に乗ってる間はデレステをした。

まとめ

問題はあまり解けなかったけど、普段合わない競技プログラマーと直接会って交流できたのでよかった。とても楽しかった。

次の合宿は春のRUPCなので、それまでにもっと難しい問題を解けるようになりたい。

RCOさんのおかげでおいしい食事を食べられたので良かった。懇親会と牛丼ありがとうございました！

会津大学のみなさんもありがとうございました！

ヅに行ったのに大学に生えるセグ木と甜菜を観測してくるの忘れてた……
— あんずどーなつうさぎ (@wk1080id) 2017年9月20日

*1:会津合宿 2017 - 立命館大学情報理工学部プロジェクト団体RiPPro

*2:Bの原案はテセウスの船みたいな感じ

*3:三角形の内接円の中心ではない

2017-07-15

ICPC2017国内予選参加記

競技プログラミング参加記

ICPC国内予選に出ました。

参加記を書くまでが国内予選みたいな風習があるっぽいので書きます。

ACM-ICPC 2017 国内予選

予選前

去年のチームは同学年3人で組んでいたので今年も同学年で組むか〜となって、yebi君(@sigsigma19)としゅもん君(@shumon_84)と組むことに(去年とメンバーは違う)。

1回生たちも出るみたいだから負けたくない！って3人でずっと言ってた(これがフラグとなる)(たぶん)。

6月末に部内コンでチーム練を始めたら、1回生チームたちと互角の戦い(ほんまか？)をしていて、これはやばいとなる。

模擬国内は3人で出て、2完でした。B問題を担当してバグらせながら通した。

1回生に負けたのでお通夜だった。悲しいね。

f:id:wk1080id:20170715123629p:plain

本当に予選で1回生チームに負けることが現実的になったので、それから予選までの2週間はおびえていた。

部内コン(AOJ-ICPCの問題以外も含まれている)では1回生に負け続け精神的負担が大きかった。今年の1回生はプロが多い。っょぃ。

前日は(きっと使わないであろう)ライブラリをいくつか印刷した。あと、超健康児(?)なので日付が変わる前に寝た。

予選当日は普通に授業日だったので直前まで授業を受けていました。

予選開始

とりあえず問題文の印刷が終わるまでyebi君がA問題を解くという話だったので、A問題を任せる(といいつつ印刷に時間がかかっていたので3人で見てた)。O(N^2)の全探索が間に合うのでそれでいこうとなってyebi君が書いてA問題をAC。そのころに問題文が来たので、B問題を読んだ。yebi君がC、しゅもん君はDを考え始める。B問題は前から見ていくだけでできるでしょ！wとなったのでコーディングを開始。が、実装が終わってサンプルを試すと合わなかったので、印刷クエリを投げて、yebi君に替わってCの実装をしてもらうことに。その間紙デバッグをしていた。Dはなんか二部マッチング臭がすると言われて、誰も書けないのでDは諦めるか〜みたいな話をした。しゅもん君には他の問題に目を通してもらうことにした。

Cの実装が終わってサンプルが合わないようだったので、コーディングを替わってもらった。Bはサンプル出力が合ったのでsubmitしたらWAでつらい気持ちになった。印刷クエリを投げてyebi君に交代したら、Cが通った。プロ。

自分はというと、サンプルが合ってるのにWAでどこが間違っているかわからなかった(世界一頭が悪い)ので、しゅもん君にB問題をバトンタッチして他の問題を考察することにした。Eの構文解析は全くできる気がしなくてパスして、Fの折りたたむやつは去年の会津合宿の立命セットぽさを感じて(よく考えたらそうでもない)、無理そうな雰囲気を感じ取った。Gはdfsかbfsでできそうな感じがした。Hは幾何だから考えたくもないと思って放置。

一番できそうなGの考察をyebi君としていた。各部屋を1度しか通れないことから、対角線に移動するのは不可能だとわかるので、宝の取り方は左上->左下->右下->右上->左上の順番だけ考えればいいということがわかる。宝の場所に移動するまでに遠回りをすると通ることのできない場所が増えてしまうので、最短距離のルートで通ればいいんじゃないかとなる。しゅもん君の実装が終わり次第yebi君にGを実装してもらうことにしてHを考えてみる。

Hは移動する頂点と移動先の頂点を決めれば、2回の移動で頂点を重ねられることと、5回以上の操作が必要な場合はそこで計算をやめていいので、場合分けすればいけるか？となった(が、幾何ライブラリはあるものの使いこなせないので無理ゲー臭がしたので諦めた)(あと、幾何ライブラリを写すのに時間がかかりすぎる)。

しゅもん君がバグらせながらもB問題を通してくれたので、Gをyebi君に書いてもらう。

その間にEを少し考察したが、できそうにないので、しゅもん君とともに実装を見ていた。最後まで実装できずにコンテストが終了。

結果は3完99位でした。

f:id:wk1080id:20170715131642p:plain

戦犯すぎてつらい(1ACもできずバグを量産した
— 素数うさぎりかさん (@wk1080id) 2017年7月14日

なお1回生チームに負けた。先輩ってなんですか。後輩がプロなので先輩を名乗るのをやめたい気持ちでいっぱい。

予選後

なーう pic.twitter.com/2zbGvnEPxH
— 素数うさぎりかさん (@wk1080id) 2017年7月14日

部室で菓子パしながらゲームとかで盛り上がってた。

22時くらいに警備員さんにはよ帰れって追い出されて辛かった。

そういえば去年の国内予選でもBをバグらせてACできなかったなあとか思い出して悲しい気持ちになった。成長できてないじゃん。実質バグ担当。つらい。

次のチーム戦はおそらく会津合宿になるだろうから、それまでにもっと(主にグラフ系の)知識をつけたいなと思った(その前に簡単な問題をバグらせる癖を直したい)。

チーム名について

ICPC参加登録の直前まで名前がきまっていなくて、どうしようとなったときに、素数うさぎ関連にしないかということになって(ぼくが言い出したわけではない)、Prime Rabbitになった。が、某がごちうさ要素を入れてもいいんじゃないかとか言い始めたので、アルファベット数が575になる「prime rabbits house」を提案してみたらなぜかそれでいくことになった。なんでみんなそんなに素数うさぎが好きなんだろう……。