足跡-sokuseki-

りかの日進月歩の記録

AOJ1368 Quality of Check Digits

競技プログラミング AOJ

Quality of Check Digits | Aizu Online Judge

問題概要

0000~9999の4桁の数の後ろにチェックディジットを1つつけて5桁の数を作る。チェックディジット e は、4桁の数の数字を上から abcd としたとき、
e =( ((0 \otimes a) \otimes b) \otimes c) \otimes d
と定義される。ここで x \otimes y は与えられた表の x 行 y 列目の数字を指す。
与えられる表の i 行 i 列目は必ず0になっているので、 ((((0 \otimes a) \otimes b) \otimes c) \otimes d) \otimes e は必ず0になる。これが0にならない場合、誤りを発見したことになる。

0000~9999の4桁の数 x にチェックディジットをつけた5桁の数 y について、以下の2つのどちらかの操作を行った後、 ((((0 \otimes a) \otimes b) \otimes c) \otimes d) \otimes e が0になるような x はいくつあるか答えよ。

  • y のある1つの桁の数字を異なる数字にする
  • y のとなりあう2つの桁の数を入れ替えて、 y とは違う数にする

解法

全探索して愚直に数え上げます。

AIZU ONLINE JUDGE: Code Review

AOJ2340 Carpenters' Language

競技プログラミング AOJ

Carpenters' Language | Aizu Online Judge

問題概要

括弧列がvalidであるとは、文脈自由文法で以下のように定義される。

S -> SS | (S) | )S( | ε

あなたは最初、空の括弧列Sを持っている。
q 回のクエリが与えられる。 i 番目のクエリで p_i, c_i, n_i が与えられるので、Sの p_i 文字目に c_i を n_i 回挿入し、できた括弧列がvalidであるかを判定してください。

制約

1 \le q \le 10^5
0 \le p_i \le i番目のクエリの前の S の長さ
1 \le n_i \le 2^{20}
c_i は '(' または ')'

解法

よく考えると、'('の個数と')'の個数が同じだとvalidな括弧列になることがわかるので、オーバーフローを気にしながら'('の数と')'の数が等しいかをチェックすれば良いです。
ちなみにぼくはよく考えてもわかりませんでした。
AIZU ONLINE JUDGE: Code Review

AOJ2165 Strange String Manipulation

競技プログラミング AOJ

Strange String Manipulation | Aizu Online Judge

問題概要

線形合同法を使って擬似乱数を生成します。線形合同法は
R_0 = S
R_i = ( A R_{i-1} + C ) mod M
で計算します。ここで S, A, C, M は定数で、この問題では 0 \le S, A, C \le 15 、 M=256です。

いま、文字列 I を、乱数列 R を使って別の文字列 O に変換したいです。文字列 O は
O_i = ( I_i + R_i ) mod M
で定義されます。
文字列 O のエントロピーが最小になるような S, A, C を答えてください。エントロピーが最小になるような組が複数ある場合は S, A, C が最小になるものを答えてください。
文字列のエントロピー H は
H = - \sum_x \frac{\#(x)}{N} \log \frac{\#(x)}{N}
で定義されます。ここで N は文字列の長さ、 \#(x) はアルファベット x の出現回数です。

解法

S,A,Cを全探索します。16*16*16*256なので間に合います。
AIZU ONLINE JUDGE: Code Review

AOJ1249 Make a Sequence

競技プログラミング AOJ

Make a Sequence | Aizu Online Judge

問題概要

2人のプレイヤーが白と黒の石を使って交互にゲームをプレイする。黒が先手。
n* n 本のペグ(杭)があり、それぞれ n 個までボールを重ねることができる。
ゲーム開始時にはどのペグにもボールはない。

ターンになると、プレイヤーは1つのペグを選び自分の色のボールを1つ置くことができる。そのペグにボールがない場合は自分のボールがペグの一番下になり、そうでない場合はそのペグの一番上にあるボールの上に重なる。
縦または横または斜めに自分の色のボールが m 個以上連続した列ができるとそのプレイヤーの勝ちになる。勝者が決まる前にボールを置く場所がなくなったりゲームをやめてしまったら引き分けになる。（勝者が決まっているのにプレイを続行している入力があることに注意する。）

ターン数 p とボールを置いたペグの座標 (x_i, y_i) （ 1 \le i \le p ）が与えられるので、どちらのプレイヤーが勝ったかを判定する。黒が勝った場合は"Black"、白が勝った場合は"White"、引き分けだった場合は"Draw"を出力する。また引き分けでないときは勝敗が決まったターン数も出力する。

制約

3 \le m \le n \le 7
1 \le p \le n^3
1 \le x_i, y_i \le n

解法

それぞれのターンごとに、勝者が決まるかどうかを判定します。
ある位置にボールを置いたとき、ボールが m 個連続しているかどうかを見る必要があるのは13方向（くわしくは問題文参照）で、各方向につき n 個見ればいいので、全体で p * 12 * n 回になって間に合います。

愚直に書くと行数がアになるのでもう少し綺麗に書きたいですね。
AIZU ONLINE JUDGE: Code Review

AOJ1346 Miscalculation

競技プログラミング AOJ

Miscalculation | Aizu Online Judge

問題概要

1行目に0~9の数字, +, *の文字からなる数式が与えられます。この数式は奇数文字目は数字、偶数文字目は演算子(+または*)です。数式の長さは奇数で、最大17文字です。
数式の計算方法は

  1. 乗算(*)を加算(+)より優先して計算する
  2. 演算子の優先順位を考えずに左から右に計算する

の2通りあります。

2行目に 10^9未満の非負整数が与えられます。2行目の整数が、1行目の数式をどのような方法で計算したものかが知りたいです。
(1)の方法で計算したものであるなら'M'、(2)の方法で計算したものであるなら'L'、(1)と(2)どちらで計算しても2行目の整数になるなら'U'、(1)と(2)のどちらで計算しても2行目の整数にならないなら'I'と答えてください。

解法

1行目を2通りの方法で計算します。その結果と2行目の整数を比較します。
構文解析のアレを初めて実装しました。
AIZU ONLINE JUDGE: Code Review

AOJ1285 Grey Area

競技プログラミング AOJ

Grey Area | Aizu Online Judge

問題概要

N 個のデータからヒストグラムを作ります。
それぞれのヒストグラムの棒の幅は w で、棒の高さは、ヒストグラムの棒の長さの最大値を1としたときの割合で定義されます。
ヒストグラムの棒はそれぞれ色の濃さが異なり、ヒストグラムの棒がk本あったとき、左からi本目の濃さは \frac{k-i}{k-1} です。
あなたはヒストグラムを作る際の必要なインクの量が知りたいです。
ここで必要なインクの量は、「 0.01 + \sum_{i = 1}^{k} i 本目のヒストグラムの棒の高さ* i 本目のヒストグラムの棒の色の濃さ」です。
誤差は 10^{-5} まで許容されます。

制約

1 \le n \le 100
10 \le w \le 50
0 \le v_i \le 100

解法

棒の幅は w なので、 v_i は左から \lfloor \frac{v_i}{w} \rfloor 番目の棒の要素になります。（ v_i が小さいので、何番目の棒かを \frac{v_i}{w} 回試しても間に合います）
それぞれの棒の度数（長さ）を求めてから、それぞれの棒のインクの量を足し合わせてあげると良いです。
計算量は O(N) でできます。


AIZU ONLINE JUDGE: Code Review

JAG夏合宿2018 / 会津合宿2018 参加記

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

9/15から1週間の競プロ旅行をして、JAG夏合宿2018（2018/Practice/夏合宿/案内 - ACM-ICPC Japanese Alumni Group）と会津合宿2018（会津大学競技プログラミング合宿2018 : ATND）に参加してきました。コンテストの時系列はだいぶあやしいので間違っていてもゆるしてください。

9/15 (JAG day1)

参宮橋でびーとくんと松屋に行き、うしをたべる。

集合場所に行ったらそこそこ人がいた。
とりあえずみくにゃんのとなりにすわる。まえにfour-tがいた。
コンテストは去年の台湾セット。priMe.caTで出る。

コンテストが始まる。みくにゃんがテンプレ、ぼくとtm先輩が手分けして問題を読む。
AとBを先輩、Cをぼくが読む。Aがやるだけなのでみくにゃんが書いてAC。
Cはいもすをすればできそうなのでみくにゃんに伝える、a_iが大きいから配列には持つことができないし、mapを使えば良さそうということでAC。
Bもやるだけなのでみくにゃんが書いた。ここで30分経過。
Dを先輩、Eをぼくがよむ。Dは愚直にやるだけなのでみくにゃんが書く。Eは幾何。Dを提出するとTLE。うーんってなりながらEの問題をみくにゃんに説明すると、多角形の頂点がのる円の半径を二分探索すればうまくいきそうなことがわかり、Eを書いてもらう。tm先輩はFを読んで実験していた。Eのサンプルがあったところで提出するとWA。tm先輩がFの実装を生やしてくれたのでみくにゃんが書く。WA。Eは多角形が円の中心を含まない場合がまずいのではないかと気づく。提出するとWA。おかしい。Fはmodをとる値を間違えていたことがわかったので直してAC。Eわからないなーとなって、Dを考え直す。mapを使ってシミュレーションをしていたけど、stackとqueueを使ってもできるのでそれに書き換えて提出するとAC。残り40分ほど。GのAC数がそこそこあったので、ぼくとみくにゃんがEを考えている間にtm先輩にGを読んでもらう。なんだかんだでそのままタイムアップ。
ABCDFの5完でした。
そのあと解説が始まる。解説者を公募するのおもしろかった。Dはarcsinがまずかったのかなあ。

そのあと宿舎に移動。これは迷子になりますねという感じ。
おへやでまったりしてからみくにゃんとよるごはんを食べにいった。サラダ食べ放題だった。サラダ食べ放題。やさい。

帰りにコンビニに寄ったらおみやげがいっぱいあった。アイスの種類が豊富ですごいなーってなった。
おふろに行ったら広くてびっくりした。
おへやにかえってAGC。爆死。レートくんいままでありがとう。（レートとビートって似てない？）

9/16 (JAG day2)

夏合宿の朝は早い*1。7時におきた。8時前くらいにみくにゃんとせいかちゃんのへやのひとと食堂にいく。やさいをたべる。

部屋があいてなかったのでみくにゃんとコンビニにいく。ひとがおおい。
センター棟に戻ると部屋の前で開くのを待ってる人がいたのでAGCの感想戦をしたりする。

オタクTシャツを着ている人が複数いてウケるなどする。
チームメンバーがきまっていないので運営の手を借りチームを決める。apollopiaのmtsdさんとatsさんになる。メンバーが東大生2人（橙と黄色）でこわいなあ。でもチームに貢献したいという気持ちになる。

コンテストが始まる。Aを読む。いろいろ考えるとz全探索すればいいんじゃね？となる。ただ数学力のNASAのせいでどのくらい探索すれば答えがでるのかわからない。つらいなあという気持ちになっているとBが通る。手があいたmtsdさんに尋ねると17*107程度だからすぐ終わると言われてはいとなる。数学ができませんでした…みたいな気持ちになりながら実装してAC。その後すぐatsさんがCを通す。
その後、軽く全体に目を通すと、Dはリアクティブで入出力がうくそうで、Iがデータ構造ゲーな感じがするのでやめる。それ以外を分担して読むことにする。
ぼくはHの考察を担当して、禁止文字列を数え上げして全体から引くほうが簡単な気がしてくる。禁止文字列はSuffixArrayの気持ちになると数え上げができるので、mtsdさんに方針を伝えるとライブラリ写経を含めすべて実装してもらえた。AC!!!その間にatsさんがEの考察を詰めていてくれていたみたいで、すぐにEの実装がはじまる。
えーなんかここらへんの記憶が定かじゃないんですが。
Kはできそうな雰囲気なんですが考察を詰めると意味がわからなくなります。
Gは重心のあたりをいい感じに探索すると見つかるのでは？という嘘解法が生えます。（それと同時にダメなケースも生えます）
Fは2直線の交点を求めていくんですが、サンプル2で誤差死します。
Jはよく考えるとマンハッタン距離みたいな感じになって解けるということをatsさんから聞きます。実装してもらいます。ACします。すごすぎる……。
その後進捗が特にないままコンテストが終了します。
解説のKやばくないか？

夕食まで時間があったので談話室で杏ちゃんを降臨させたりします。夕食にいきます。



ごちうさの3期が決定したりします。
お風呂に入ったあと、談話室で精進(?)をしながらボドゲ勢を眺めていた。12時くらいに解散になる。SuffixArrayをちょっと勉強して寝る。

9/17 (JAG day3)

朝起きるのがつらい。7時におきたんですが、おきてすぐ朝食にいくのつらくないですか？
キャベツを無限にたべた。シーツ回収にも無事まにあったのでよかったね。


時間があったのでらいぶぱーちーをする。

コンテストはpriMe.caTで出ることになったんですが、コンテスト開始10分前にpcが更新して再起動をはじめやばい雰囲気になる。

コンテストがはじまったので、3人でABCをよむ。pcの再起動がおわって、問題を把握した順にB,C,Aをみくにゃんに実装してもらう。3ACした段階で30分くらい経過していた。
そのあと、順位表からIが解けそうだということがわかって、みくにゃんとtm先輩がIの考察、ぼくがその他の問題の問題概要を把握する係をする。Iの解法がはやめに生えたので、みくにゃんがIの実装をはじめる。IがACしたタイミングでJが解けそうな感じがしたので3人で考察する。偶奇で場合分けすればできそうとわかる。みくにゃんに実装をまかせる。AC。みくにゃんとtm先輩がFの考察をする。解法が生えたのでみくにゃんが実装する。AC。ぼくはずっとDを考えていたんですが、順位表をみてUKUNICHIAがFAしているのがわかり、これは文字列ではなくセグ木とかのデータ構造を使うのでは？という気持ちになる。w_iをそのままソートしたもののインデックスの配列と、w_iをreverseしてからソートしたもののインデックスの配列を作って、クエリごとに「[l1,r1]と[l2,r2]に共通するインデックスの個数は？」に答えるという言い換えができることに気づく。みくにゃんにそれを伝えるとBITでできるという話になる。みくにゃんにがんばって実装してもらう。AC。tm先輩はその間Gを考察していて、実装がおわったみくにゃんも加わって考察して、DPをすればできそうという気持ちになる。ぼくは順位表をみて敬遠していたEHKの読解をする。幾何幾何数列で解くなら数列かなーという印象をうける。みくにゃんがGの実装をはじめて、Kをtm先輩と考察する。Gがサンプル合わなくてつらい感じになる。そんな感じでコンテスト終了。
ABCDFIJの7完。

解説の後、部屋で駄弁るをしていた。部屋から追い出された後もロビー(?)でずっと喋っていた。
オリセンから出た後、JOIer御用達と教えてもらったラーメン屋を見つける。お腹が空いていないため立ち寄るのはやめた。

JAG合宿は終了です。「ACPCでまた会おうな！（なお2日後）」というのをした。

9/18 (JAGとACPCのあいだ)

はむこさんと巣鴨のラーメンを食べに行って*2芥川龍之介のお墓を観光する。

会津に向かって出発する。電車の乗車時間が長すぎる。




9/19 (ACPC day1)

13時に集合ですが学食を食べたい気持ちになったのと運営なので早めに行く。9/19であることに気づき、食堂でチーズカツカレー*3を食べたい気持ちになる。が、チーズがないのでカツカレーを食べます。うしくんと宝くじをいっしょにひくをします。6等なんですが…。
会津合宿がはじまります。自己紹介フェーズでは本名を言うだけで周囲の笑いを生やす人がいてすごいなあとなる。運営なのでチーム決めを見守りますがチームを事前に決めている人がいないことに驚く（内心、これはオンサイト全完は出ないな…という気持ちになる）。
会場が2つの部屋に分かれているらしいことを聞く。風船を運んだりするの面倒だなあという気持ちになる。
コンテストが始まる。30分くらいは風船運びがめちゃくちゃ忙しかった。
最後のFGHが全然解かれなくてやばいなあという気持ちになる。GはオンラインでACが出たけどFHは解かれないままコンテストが終わる。
解説も終わって、うしうくびーとと一緒にラーメンを食べに行く。解散してホテルに戻ってぼーっとする。風呂に入って寝る。

9/20 (ACPC day2)

8時におきる。うくにきあ。朝キャベツをたべる。おいしい。
大学につくとうしくんがいたのでらいぶぱーちーをする。たのしい。こたつがめと同僚になった。同僚に対して同僚申請お願いしますを連打しがち。
チーム決めは運に任せることにする。ツカサさんとやまさんとチームを組む。
レート順にやまさんがA、ぼくがB、ツカサさんがCをやることにする。

コンテストが始まる。Bを読んでいるとAがACされる。1分半。早解きが得意すぎないか。（あとで順位表をみたらみんなはやかった、世界がこわれてる。）Bわからない、Cもわからないらしい。3人で少し考えたあと、ぼくとやまさんでAとBを一緒に考えて、ツカサさんにDを考えてもらうことにする。DはBFSをやるだけらしい、実装をたのむ。AC。BとCがわからないなあとなる。Eをツカサさんに読んでもらうと2つの長方形の中心を通る線の傾きを求める簡単な問題であることがわかるので、実装してもらうことにする。AC。Cはスワップクエリのたびに区間の数が増えていくと思っていたら、実は各クエリ後は区間の数を2にすることが可能であることがわかるので、数列の一番最初の数だけ持っておくことで解ける。実装をやまさんに任せたらACした。Bは人数が多いチームが相手のライフを2ずつ削っていき少ないチームが相手のライフを1ずつ削っていく戦略が最適であることがわかる。サンプルを見るとターン数はそこまで大きくならないでしょという気持ちになるので、シミュレーションぽいことをしたくなる。実装をやまさんに任せるとACしていた。Fをツカサさんに読んでもらっていたら、基本はダイクストラで、辺のコストは三分探索で求めるという方針が生えたらしい。それでいけそうな気持ちになったので実装を任せる。その間にぼくとやまさんでGとHを読む。サンプルをかきかきする。わからないなあという気持ちになり険しい。Xijの制約が怪しいのはそうなんだけどなあ。Fの実装が終わったところで提出するとTLE、三分探索のループ回しすぎじゃーんとなる。WAになる。WAの原因がわからないとなる。ツカサさんにもGとHを考えてもらうことにする。G計算量をO(NM)から落とす方法が思いつかなくてHを考える。グラフにして閉路をなくすために消す頂点の最小個数を求めたくなる。閉路が重なっている場合、いい感じの頂点を消したいなあとなると、閉路のインデックスの区間の重なりが多いところを消したくなる。区間スケジューリングでは？となる。ツカサさんが実装してくれるらしいので任せる。
ツカサさんがHを実装している間、ぼくとやまさんはIを読むことにする。文字列の問題だけどアルファベットを頂点とするグラフに置き換えられるよねとなる。入次数＞出次数となる頂点は必ず答えになることがわかる。入次数＜出次数となる頂点は必ず答えにならないことがわかる。入次数＝出次数のときどうするねんとなる。そうこうしているうちにHが通る。Fを考える。ソースコードを読んでも間違っているところがわからないがもしかして三分探索が原因か？となる。doubleじゃなくてlong long を使うことにする。テストケースが60まで進んだが？？？？しかしその先がわからない。あきらめてIを3人で考える。いろいろ考えてもわからねえとなる。ラスト20分くらいになって時間ないしやっぱりFを通したいなあとなる。三分探索の結果プラマイ10くらいの最小値をとるとACした。つらいね。ABCDEFHの7完でコンテスト終了です。
解説後のスポンサーセッションで寝ている人を観測するのが楽しかった。
懇親会会場まで歩く。雨がきつくなくてよかった。懇親会ではテーブルが知っている人だらけになる。ウケるなあ。
いろいろなおはなしをした。ハイテンションになってやばかった。うくにきあおもしろすぎないか？酔いつぶれている人を複数観測してやばそう(他人事)となる。22時くらいまで謎テンションを繰り返す。その後ホテルに帰った。風呂に入って寝る。

9/21 (ACPC day3)

6時半におきる。朝キャベツをたべる。ホテルとも今日でお別れ。ちょっとさびしい。
軽く雨がふってたけど大学まで歩く。


チームメンバーはすでに決めていたのでチーム決めフェーズは外に追い出される。
うくさんとうしくんと組む。うしくんにたくさんFAをとってもらいたいという作戦。コンテストが始まる直前までうくさんがアズリムの動画を見ていた。アズリムかわいいなあとなる。

コンテストが始まってうしくんにAを任せる。ぼくがB、うくさんがCをよむ。Bは昨日のCに似てるなあとなるがわからないね。うしくんがAに手こずっている。うくさんからCの概要をきく。abどちらかが閉路に含まれていない場合は1、両方含まれている場合は2とわかるね。うしくんがAを通してすぐCの実装をしてもらう。うくさんがD、ぼくがEを読む。Eは解法がわからないけどグラフの問題だからうくさんが得意そうと思う。うくさんにDをきくと区間スケジューリングか？となる。うしくんがCを通す。実装はやい。Dをうしくんと相談するとDPでいけるねとなる。うしくんに実装を任せる。Eをつめると強連結成分分解をすると木を2つに分ける問題になってDPぽくできるねとなる。うしくんがDをACしたのでEを実装してもらう。FとGをよむ。Fはむずかしそうとなる。EがWAったので印刷をしてうくさんがデバッグをする。うしくんにFとGを伝えるとFはわからないけどGはいけそうなかんじ。Eが実装の順が逆(?)だったみたいでなんでサンプル合うねんとなる。EがACする。うしくんがGをかきはじめる。ぼくはFのサンプルを書いて実験してみる。うくさんがBを考える。Gが通る。うしくんすげえ。なんかDPをやったらしい。順位表からBはだいぶ通されていたのでなんとかしてBを通したい気持ちになり、うしくんとうくさんがBを考える。クエリ平方分割とかいうのでできそうとなったらしい。Bとは…となりながらうしくんが実装。大変そう。Bが通る。ACしてよかったけどこれ本当にBか？となる。残り1時間でみんなでFを考える。とりあえず一番左から確定していくので、O(Q|S|)でできないか？となる。シミュレーションしたいなあとなるがむずかしいね。順位表をみるとオンサイトで全完がでる。ペナルティを計算すると、時間内にACすればオンサイト1位になることがわかる。うしくんとうくさんがペアプロぽいことをする。ぼくはがんばれーと念を送って応援する係をする。WA。残り10分ちょっと。場合分けをする。WA。場合分けをがんばる。ラスト1分を切り焦りながら提出するとAC！全完です！！！！！
コンテストが終了し、全体2位、オンサイト優勝がわかる。いえーーい！！
うれしさにつつまれながら解説をきく。Bはリストをもつらしい。なるほどなあ。Fは木になるのでLCAをするらしい。天才か？
ACPC2018はこれにて終了ですというアナウンス。廊下にでてお菓子を食べながらこたつがめさんとかに雑な絡みをする。うしくんといっしょに駅までかえる。駅でデレステをする。電車がきたのでのる。ねむいね。JAGとACPCの参加記を書きながら、2つの合宿で1問しか実装しなかったことがわかる。明日コドフェス予選ですが大丈夫ですか？という気持ちになる。
郡山で松屋に入り、うしくんの活躍を讃え牛めしをたべます。おいちい。食べ終わって、うしくんとおわかれをして、新幹線にのります。旅は終了です。

感想
とても濃くて楽しい1週間でした。みなさんありがとうございました！
あと途中でtwitterのリンク貼るの面倒になりました。まあごはん情報は誰も欲していないはずなので。

*1:夏合宿の朝は早い | Aizu Online Judge。特にこの問題を貼った意味はないです。

*2:ラーメンの写真をツイートするのを忘れていたみたいで悲しい

*3:2014/9/19にモバマスに桐生つかさが登場し、桐生つかさがよくチーズカツカレーを食べていることから、9/19にチーズカツカレーを食べる風習がある。なお桐生つかさはチーズカツカレーについて「最強だな」「チーズカツカレーを考えたやつは天才、なにより美味いしな」と語っている。