Codeforces Round #427 Div. 2 E - The penguin's game
http://codeforces.com/contest/835/problem/E
問題概要
N要素の数列があり、そのうち2要素はYで残りの要素はXである。質問クエリとして数列のインデックスの部分集合を指定すると、それらの値のXORを知ることができる。19回以内の質問クエリで値Yを持つ2要素のインデックスを特定せよ。
2 <= N <= 1000
解法
求めたい2要素のインデックスをp1, p2とする。
場合分けして考えてみると、1回の質問クエリによって得られる情報は①「その部分集合内にYが1個ある」②「その部分集合内にYが0個or2個ある」のいずれかであることがわかる。
重要な観察として「数列のインデックスを2進数で表現したとき、n桁目のbitが立っているインデックスの集合を質問クエリで投げると、(p1 xor p2)のn桁目の値が得られる」という事実がある。なぜなら、この質問クエリの回答が①であればp1とp2は違うグループにいる=その桁の値が異なる=xorが1であり、②であればp1とp2は同じグループにいる=その桁の値が同じ=xorが0になるからである。N <= 1000より高々10回の質問クエリですべての桁のxor, すなわち(p1 xor p2)の値そのものを得ることができる。
ここで得られた(p1 xor p2)からbitが立っている桁をひとつ選び、これをx桁目と呼ぶことにする(p1 != p2より、少なくとも1桁は必ずbitが立っている)。あとはx桁目を除く各桁iに対して(x桁目のbitが立っている && i桁目のbitが立っている)という集合の質問クエリを投げると。p1かp2の片方が特定できる。(p1 xor p2)は既知なので、片方がわかればもう片方もわかる。以上でp1とp2が求まった。
前半のxorを求めるパートで高々10回、後半の特定パートで高々9回の合計19回ちょうどで制限内に質問クエリが収まる。
感想
本番結構考えてまったくわからなかったんですがnvipさんのツイートのおかげで理解できました。 ビットごとに絞り込むの自分では絶対思いつかないけど色々使えそうなんで覚えておきたい
コード (D言語)
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop; int ask(int[] q) { writeln("? " ~ q.length.to!string ~ " " ~ q.map!(a => a.to!string).join(" ")); stdout.flush; return readln.chomp.to!int; } void answer(int x, int y) { writeln("! ", x, " ", y); stdout.flush; } void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto X = s[1]; auto Y = s[2]; int xor = 0; foreach (mask; 0..10) { int[] q; foreach (i; 1..N+1) if (i & (1 << mask)) q ~= i; if (q.length == 0) continue; int ret = ask(q); ret = ret == X || ret == 0 ? 0 : 1; xor |= (ret << mask); } int b; foreach (mask; 0..10) if (xor & (1 << mask)) b = mask; int ans = 1 << b; foreach (mask; 0..10) { if (mask == b) continue; int[] q; foreach (i; 1..N+1) if ((i & (1 << mask)) && (i & (1 << b))) q ~= i; if (q.length == 0) continue; int ret = ask(q); ret = ret == X || ret == 0 ? 0 : 1; ans |= (ret << mask); } int ans2 = xor ^ ans; answer(min(ans, ans2), max(ans, ans2)); }
Codeforces Round #427 Div. 2 D - Palindromic characteristics
http://codeforces.com/problemset/problem/835/D
問題概要
ある文字列に対して以下のようにk-palindromesが定義される。
- 文字列が回文ならば、その文字列は 1-palindrome である
- k > 1 のとき、文字列の左半分と右半分が等しく、かつ左半分が (k-1)-palindromeならば、その文字列は k-palindromeである
文字列Sが与えられるので、Sのすべての連続部分文字列においてk-palindromeが何個存在するかを、すべてのkについて求めよ。
|S| <= 5000
解法
i, j (0 <= i <= j < N) について
dp(i, j) = 部分文字列S[i..j]の最大のk
を求める。
dpの中で毎回愚直に回文判定してるとO(|S|^3)とかになるので事前に回文テーブルを作っておく。ある文字Xを中心にしたときに作れる最長の回文を考えると、テーブルはO(|S|^2)で作れる。部分文字列S[i..j]が回文かどうかはi, jの真ん中の点を中心にしたときに作れる回文の長さがi~jの長さを超えているかどうかで判定できる。これで前処理・dpともにO(|S|^2)になって間に合う。
またある文字列が k-palindrome であれば必ず (k-1) palindrome でもあるので、dpで最大のkを求めたら最後に累積和をとって答えが出せる。
この問題ではオーダーに効いてこないので意味ないが、Manacherのアルゴリズムとかいうのを用いると上で作ったような回文テーブルの計算がO(|S|)でできるらしいです。参考:文字列の頭良い感じの線形アルゴリズムたち2 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
感想
本番ではdp部分をループで書こうとしてわけわかんなくなってたけど再帰で書き直したらだいぶすっきりしました。とはいえ「k-palindrome であれば必ず (k-1) palindrome」のところがちゃんとわかってればどっちで書こうと大差ないですね。本番ではわかってなかったので終了でした。
コード (D言語)
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop; void main() { auto S = readln.chomp; auto N = S.length.to!int; auto P_odd = new int[](N); auto P_even = new int[](N); foreach (i; 0..N) { P_odd[i] = 1; for (int j = 1; i - j >= 0 && i + j < N && S[i - j] == S[i + j]; ++j) { P_odd[i] += 2; } } foreach (i; 0..N-1) { for (int j = 0; i - j >= 0 && i + j + 1 < N && S[i - j] == S[i + j + 1]; ++j) { P_even[i] += 2; } } auto mem = new int[][](N, N); foreach (i; 0..N) fill(mem[i], -1); int dfs(int i, int j) { if (mem[i][j] >= 0) return mem[i][j]; if (i > j) return 0; if (i == j) return 1; int L = j - i + 1; int m = (i + j) / 2; int ret; if (L % 2 == 1) { if (P_odd[m] >= L) ret = dfs(i, m - 1) + 1; else ret = 0; } else { if (P_even[m] >= L) ret = dfs(i, m) + 1; else ret = 0; } return mem[i][j] = ret; } auto A = new int[](N + 2); foreach (i; 0..N) { foreach (j; i..N) { int ret = dfs(i, j); A[0] += 1; A[ret + 1] -= 1; } } foreach (i; 0..N) A[i + 1] += A[i]; A[1..$-1].map!(a => a.to!string).join(" ").writeln; }
Topcoder SRM 718 Div1 Easy - InterleavingParenthesis
これまで全然やっていなかったSRMの過去問埋めをぼちぼちやっていこうという気持ちになりまして、せっかくだから解いた問題に関しては記録をつけていこうと思います。当面はDiv1 Easyを新しいものからやっていく予定です。この1回で飽きる可能性もありますがその時は察してください。記事の形式はkmjpさんのブログの影響をめちゃめちゃ受けています(僕はkmjpさんのブログをめちゃめちゃ見過ぎているので)。
問題概要
開き括弧と閉じ括弧の2種類の文字のみからなる文字列s1, s2が与えられる。次の操作を行って得られる文字列のうち、括弧の対応が正しくなるものは何通りか。
操作: s1, s2のうち空でないものをひとつ選び、選んだ方の先頭の文字を削除して新文字列の末尾に加える。これを両方の文字列が空になるまで続ける。
|s1| <= 2500, |s2| <= 2500
解法
dp[i][j] = s1をi文字目、s2をj文字目まで見たときの文字の取り方 としてdp.
遷移を考えると(s1から何文字取ったか, s2から何文字取ったか, 開かれている括弧の数)でdpしたくなるが、それだと25003で間に合わない。よくよく考えると何文字目まで見たかがわかってるなら開かれ括弧の数は一意に定まるので状態として持つ必要はなく、結局s1, s2から何文字取ったかの2つだけ見ればよいことがわかってO(|S|^2)。
遷移はこんな感じでやった
- 開かれ括弧が0より多い → 開き括弧も閉じ括弧も取れる
- 開かれ括弧がちょうど0 → 開き括弧しか取れない
- 開かれ括弧が0より少ない → 取れない
感想
解けてみれば至って普通のdpなんですが、3乗から2乗に落とすのにちょっと困ってしまいました。
コード (C++)
const ll MOD = 1000000007; class InterleavingParenthesis { public: int countWays(string s1, string s2) { int N = s1.size(); int M = s2.size(); vector<int> A(N + 1, 0); vector<int> B(M + 1, 0); REP(i, N) A[i + 1] = A[i] + (s1[i] == '('); REP(i, M) B[i + 1] = B[i] + (s2[i] == '('); cout << A[N] << " " << B[M] << endl; if ((A[N] + B[M]) * 2 != N + M) return 0; vector<vector<ll>> dp(N + 1, vector<ll>(M + 1, 0)); dp[0][0] = 1; REP(i, N + 1) REP(j, M + 1) { int open = A[i] + B[j] - (i + j - A[i] - B[j]); if (open > 0) { if (i < N) (dp[i + 1][j] += dp[i][j]) %= MOD; if (j < M) (dp[i][j + 1] += dp[i][j]) %= MOD; } else if (open == 0) { if (i < N && s1[i] == '(') (dp[i + 1][j] += dp[i][j]) %= MOD; if (j < M && s2[j] == '(') (dp[i][j + 1] += dp[i][j]) %= MOD; } } return dp[N][M]; } };
主人が競技プログラミングを始めて一年が経ちました
はじめに
いきなりの投稿失礼します。 久光さやか、29歳の未亡人です。 お互いのニーズに合致しそうだと思い、記事を書いてみました。 自分のことを少し語ります。 昨年の5月、わけあって競技プログラミングをはじめました。 自分は…アルゴリズムのことを…死ぬまで何も理解していなかったのが とても悔やまれます。 主人はTopcoderに頻繁に参加していたのですが、 それは遊びの為のプログラミングコンテストではなかったのです。 レーティングを得るために、私に内緒であんな危険なchallengeをしていたなんて。 一年が経過して、ようやく主人の0完+チャレンジ失敗から立ち直ってきました。 ですが、お恥ずかしい話ですが、毎日の孤独な夜に、 身体の火照りが止まらなくなる時間も増えてきました。 主人の残した財産は僅少なレーティングです。 つまり、WAは幾らでも出きますので、 私の競プロ欲を満たして欲しいのです。 お返事を頂けましたら、もっと詳しい話をしたいと 考えています。連絡、待っていますね。
レーティング
AtCoder
半年前: 1728(青)→ 現在: 1930(青) / highest: 1930 (2017/06/24)
メインで参加しているプロコンサイトです。レーティングの面では残念ながら色を変えるほどには上げられませんでした。 きりよく一年で黄色になれましたと言いたいところだったんですが……。ただ最近は全然振るわない時期を抜けて少しずつhighestを更新できているので、1年半経つ前には黄色に届きたいですね。
Codeforces
半年前: 1579(緑)→ 現在: 1928(紫) / highest: 1952 (2017/04/21)
AtCoderほどではないですがこっちも結構参加しています。振り返ると半年前は4回しか参加してなかったんですね。一時期全然解けないしシステムテスト落ちるし問題文が読みづらすぎるしでマジで苦手だったんですが最近は結構解けるので好きです。あとAtCoder, Codeforces, Topcoderの中で唯一青より上に行けているので好きです。Div1残留安定が目標。
Topcoder SRM
半年前: 参加経験なし → 現在: 1215(青) / highest: 1428 (2017/02/09)
微妙なところです。最初結構順調で黄色楽勝じゃんとか調子こいてたんですが負の点数取って一気に緑に落ちたりして今は間くらいで落ち着いてます。開催自体が少ないのと平日昼間にやることが多くて参加回数増えない・フィードバックなしのチャレンジありなので点数も安定しないといった理由でレーティングが収束してるような感触が全然ありません。とはいえ分散がでかければその分上振れする余地もでかいと思うので黄色に一番近いのはここかな〜と勝手に思ってます。
その他のコンテスト
CSAcademyとかHackerRankとかCodechefとかにたまに参加しています。
過去問埋め
だいたいAtCoderかyukicoderの過去問を埋めています。yukicoderは最近レベル75になりました。しばらく考えてわからない問題は割とホイホイ解説を見てしまっています。知識面に関しては黄色目標レベルなら「知らなかったから解けなかった」はもうほぼないかなとなってきたので最近は考え方とか発想とかそういうところを吸収するようにしたいな〜〜って感じです。
今日ツイッターで流行っていたやつだとこんな感じ
The Number of Solved Problems By fluffyowl
— アルハンブラ宮殿のゆるキャラ (@nebukuro09) 2017年6月26日
TopCoder: 8
CodeForces: 122
AtCoder: 698
AOJ: 46
Sum: 874
https://t.co/U9iUufPPxU
そろそろTopcoderとかCodeforcesも埋めていきたいですね。
その他の進捗
オンサイトに出れた
前の記事の話ですが、RCOさんの日本橋ハーフマラソンの本戦に出ることができました。念願の初競プロ衣服も頂けてとても嬉しい経験でした。思い返すとこのコンテストは突出しなくていい(2問両方でそこそこの得点を取るのでも上位に行ける可能性がある)という点で自分に合っていて運が良かったな〜〜と思います。
GCJでTシャツ
Google Code JamでTシャツがもらえました。1000位以内でTシャツのところ999位に滑り込み(終了時点では1004位とかで一日経ったらなぜか順位上がっていてマジで滑り込みだった)、2つ目の競プロ衣服獲得となりました。パーカー・Tシャツときてるのでズボンとか靴下とかを配るプログラミングコンテストが待たれます。
マラソンにも手を出した
上の日本橋ハーフマラソンの件とも関連しますが長期間のコンテストにもちょいちょい手を出したりしています。Topcoder MM, Codingameなど。実力不足による徒労感があったりして最初の方ほどモチベーションは高くないですが…。
競技プログラミングの効能
おわりに
半年時点で記事書いておいて今回書かないのもあれかな〜と思いつつぐだぐだ引き伸ばしてたら1年と1ヶ月になってしまいました。他にすることないし競プロはまだまだ楽しいし、今のところ飽きる気配はなさそうです。最近はKaggleとか、あと大学の数学をちゃんとやるのとかに興味が発展してきてるのでそっちの方もやっていってよい循環を作れたらいいですね。あとこれは競プロだけじゃないんですがなにかしらを作ることに取り組んでいきたいという気持ちも出始めました。競プロの作問でもいいし競プロ関係ないプログラミングでもいいし絵でも小説でもいいのでなんか創作物を作ることも日常の活動に加えていけたらな〜という感じです。どうもありがとうございました。
RCO presents 日本橋ハーフマラソンに参加しました
3/20にRCO presents 日本橋ハーフマラソンに参加しました。競プロをやりだしたのが学生じゃなくなってからなので、予選付きコンテストでオンサイトに出ることは半ばあきらめていたんですが、予選でギリギリ引っかかって上げてもらいました。感謝です。
予選
A問題 Multiple Pieces
最初山登り的なものを実装しようとするが、実装が難しく最初の提出まで1時間かかった上に点数が泡を吹くほど低い。ただ低すぎたおかげで逆にそこまでの方針を捨てる踏ん切りがついて、ごくごく単純な貪欲で書き直したら点数が10倍くらい上がってそこそこの順位に。具体的には「全マスを大きい順のpriority queueに突っ込む→順に取り出して周りの大きいマスと貪欲にくっつけていく」という感じ。単純すぎて制限時間10sのところ6msで終わってしまう。このあたりで3時間中の1時間半くらいが経っていたので一旦よしとしてB問題へ行くことにする。
B問題 Food Collector
今度は時間をかけすぎたら終わりなのでA問題の教訓を活かしてとにかくまずは単純な方針からやっていこうと考える。ということで「初期解として完全ランダムにターン数分の移動命令を生成 → 何ターン分かの移動をランダムに変えてシミュレート → よくなるならその解に乗り換える」という山登りを10秒いっぱい回す。割とまともな点数が出て一安心し、残りの時間はこの方針をベースにして逐次改善していこうとしたが大して変わらず終了。
結果
A問題50位+B問題73位で、全体49位。だいぶ微妙でしたが上位にオンサイト不参加者も何名かいたようで、「学生の上位40名を抜いたあとの上位10名枠」の9番目につけてギリギリ本戦に通してもらえました。
本戦
開始前
開始までは後ろの方に座ってぼやぼやしながらオンサイトの雰囲気を味わった。あと参加賞ということでパーカーをもらった。競技プログラミングで衣服をもらうのがひそかな目標だったのでとても嬉しかったです。あと気がつくと真後ろの席にAtCoderの社長が座っていてヒョエ〜〜〜〜となった。あと業務の説明を聞いてたのしそ〜〜〜となった。
A問題 石油王Xの憂鬱
問題文を読んだだけで変な汗が出た。めちゃくちゃ苦手な算数パズル(天秤をn回使って偽物の金貨を特定してくださいみたいな類のやつ)っぽかったからである。ちょっと考えるけど取れる行動も多いし方針すらまったく立たないのでさっさとB問題へ。
B問題 日本橋大渋滞
こっちはA問題と比べるとだいぶ素直な印象を受けた。まず何も考えず全車を目的地に向かわせる貪欲解を書いたところ、0だけの自明解(3331点)をちょっとだけ超える(4613点)。ここでビジュアライザを見てみると、どうやら車が多すぎてほとんどの車がまともに動けてないことがわかった。要するにこれをどうにかする問題なんだな〜〜〜とやっとこの段階で気づく。とにかくどこかで回り道させないといけないので、ある車が目的地に近づけない場合はランダムな移動を行うようにするとちょっと上がる(6513点)。たしかこの時点でB問題だと2位か3位を取れていてかなりウキウキしたが、1位の人を見ると60万点とかいう異次元のスコアを出していて最初真剣にバグか?????と思った。さすがにここまでスコア差がつくということは根本的にもっといいやり方がなんかあると思ってスコアの計算式をよく読んでみると、かかったターン数で割り算が発生しており桁違いの差が付くならこの辺が鍵かなあなどと考える。自分の解を省みると制限ターンいっぱい使っていたのでこれは明らかにダメだろうと思い、解を得た段階でスコアの動きをシミュレートし一番よいターンで打ちきって出力とすることしてみる(12478点)。数十万のオーダーには全然届かないが順位的にはかなりよかったのでB問題はここで一旦やめにしてA問題へ。
A問題ふたたび
相変わらずアイデアは一切なかったが、ここで予選A問題の教訓(そんなんでいいの?という単純な方針でも割と点数取れることがある)を思い出し、めちゃくちゃ単純なやり方が何かないか考え始める。そこで「自分が持ってるどれかの容器1個とまったく同じ容量の注文を出してきた客には売る、そうでなければパス」というやり方で出してみたところ、とりあえず正の点数を得ることができた(154272点)。上位陣は700万とかで争っているので順位的にはアレだけどこれでだいぶ落ち着いた。ちょっとB問題で試したいことが浮かんでもう一回戻る。
B問題ふたたび
これまでの解答だと各ターンで車の移動を考えるとき与えられたインデックス順に動かしていたのをランダムな順番にするよう変更したらスコアが4倍くらいになった(52297点)。同じ順番で動かしているとデッドロックがとれづらいとかそういう理由だろうか?ともかく今度こそA問題にちゃんと向き合うことにする。
A問題みたび
さっきの超単純貪欲からもう一歩進んで、「自分の持ってる容器を足して作れる数字の注文が来たときは売る、そうでなれけばパス」という方針にすることを考えてみる。手持ちの数列から作れる和を求めるのはDPでよくあるやつだからこれならできる!と思い実装を始める。バグを仕込みまくって泣きそうになりながら3, 40分くらいかけてやっと書き上げて提出(5576164点)。これでA問題もオーダー的にはまともなスコアが出たので、あとはここからの改善だけを考えることにした。で思ったのが同じ和に対して組み合わせが複数通りあるときどの容器を売っぱらうかは大事だなということで、dpつくるとき保存しておく組み合わせの条件をいじったりしてたら結構よかった。いろいろあって最終的には100万点底上げできた(6657203点)
結果
A問題が11位、B問題が7位の合計18で全体6位(提出者48名)でした。まさかこんな順位を取れると思ってなかったのでマジか〜〜〜ウレシ〜〜〜〜〜と思いました。いい大人だったのでお金はもらえませんでした。(事前に学生以外賞金出ませんという連絡があってそのときは自分には関係のないことだと思って気にも留めていなかったということを思い起こすと、それが関係ある順位に入れたということでむしろもらえないことが嬉しくもあった(複雑な心の動き))
まとめ
正直今後オンサイトに出れる機会があるかと考えると自分の実力だとなかなか難しいところがあると思うので、今回は本当に良い経験になりました。このような機会を与えてくださったみなさまに感謝します。あといまぜんぜんプログラミングとか関係ない仕事してるので転職してコード書く人になりたいです。PythonとC++とD言語をよく書いています。何とは言いませんがよろしくお願いします。
競プロ始めて半年経った
いわゆる競技プログラミングというものに手を出し始めて半年ほど経ったので、マイルストーン的な意味合いで文章を残しておきます。
お前は誰だ
プログラミングとは無関係の事務職についてる新卒一年目です。ただ学生時代は半分情報系のような研究室にいて授業とか研究でコードは書いてました。
コンテスト
AtCoder, yukicoder, Codeforcesのコンテストには時間が合うならできるだけ参加するようにしています。競プロの代名詞的存在っぽいところのTopcoderもやりたいんですが開催頻度と時間帯の問題でまだ一回も参加できてません。レートは11/23現在でそれぞれ以下のような状況です。
過去問を解くこと
今はコンテストよりもむしろ過去問解くのがメインのような状況で、AtCoder, yukicoderを中心に解けそうなものから手を付けていっています。過去問埋めは時間にも拘束されないし基本的に積み上げていくだけでマイナスがないのでモチベーションが保ちやすく、RPGの素材集めみたいなのが好きな人にはおすすめです。取り組み方として、最初のうちはなるべく解説を見ないでがんばる、わからなかったら撤退して別の問題に当たる、という方針でやってましたが、最近は割とさっさと解説見てしまうことが多いです。ただしわからん問題は解説読んでもわからんことが多く、そういう場合は周辺知識を調べたり他の解説がないか探したり解説を踏まえて考え直したりして出来る限り納得してから実装に取り掛かるようにはしています。
過去問埋めはAtCoderに関しては AtCoder Problemsをとても便利に使わせてもらっています。yukicoderはそもそもサイトの仕組みとして問題一覧のソート、絞り込み機能が充実していて、最高です。
Atcoderの埋め状況
yukicoderの埋め状況
★1: 103/103
★2: 122/122
★3: 82/134
★4: 6/70
★5: 0/18
★6: 0/2
感想
別に競プロに限らずなんでもそうだろと言われてしまえばそれまでなんですが、新しいことを知れる、それによって今までできなかったことができるようになったという実感を得られるのが自分にとって競プロのいちばん楽しいところです。
たとえば自分はPythonが好きで競プロでもPythonばっかり使ってたんですが、最近はD言語を勉強し始めて本番の軽そうな問題以外はD言語で書くようにしています。昔は新しい言語を覚えようとして少しかじってすぐやめる、みたいなことが多かったんですが、明確なタスクがあると書かざるを得ないんで競プロの範囲ではだいぶ違和感なく書けるようになってきました。こういう新しいことの積み重ねが楽しさに繋がっています。(ちなみにTopcoderではD言語は使えないらしい、死)
で、初めのうちは暇つぶしで気ままにやってるだけでこういう進捗が適度に得られて十分楽しかったんですが、さすがに半年も経つと頭打ち感がでてきてしまいまして、これ以上目に見える進歩を得たいならそのための取り組みを意識的にやってく必要があるな〜と感じてます。がんばるぞい。
今後の目標
レーティングに関して、AtCoderでは黄色になること、CodeforcesではDiv1に参加できるようになること、Topcoderは参加すること。あとは蟻本を一度ちゃんと読むこと、時間に余裕があれば作問側の考え方を学ぶこと。あと転職してえ