hotpepsiの練習帳

SRM 574

02:27

Div1 Easy (275) TheNumberGame

問題

• 2人でそれぞれ任意の数値を決めてゲームをする
• 交互にターンが来たら、数字を反転するか1/10する
• 同じ数になったら先手の勝ち
• 最善手で先手が勝つかどうかを求める

方針

• 試してみる
• BがAまたはAの反転に含まれているかどうかっぽい
• 提出
• 275なので不安になる
• 試したら探索しないとだめな気がしてくる
• 探索で書く
• 再提出
• Failed System Test
• (終了後)
• 元に戻す...
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_574/TheNumberGame.cpp

結果

x-- 0pt 602nd/815 rating 1343 -> 1294 (-49)

275点に惑わされて再提出したら死んでしまった。

探索で書くと、同じ数字が繰り返されるのでちょっと厄介。

SRM 573

01:22

Div1 Easy (250) TeamContest

問題

• 3人単位でプログラミングコンテストに参加する
• 各人のスキルが与えられる
• チームの強さは、スキルの最低値と最高値の和である
• ありうる最大の順位を求める

方針

• どういう割り当てをしても、何位以上になるかというのを答える
• 3人ずつ割り当てていく
• 最高の一人と、最低の二人の組み合わせが、自分よりランクが高い場合、答えに+1
• そうでない場合、最低の三人をグループにする
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_573/TeamContest.cpp

Div1 Medium (450) SkiResorts

問題

• スキーリゾートに場所0から場所N-1までのN個の場所がある
• 同じ高さか、より低い場所へのみ移動できる
• 任意の場所を工事して高さを変更できる
• 場所0からスタートして場所N-1に行けるようにするための最小のコストを求める

方針

• Dijkstraらしい
• 最小のコストで工事した場合、既存の高さのどれかに揃えることになる
• どこの場所をどの高さに揃えるか決めて、最小コストの場所からpriority queueで取り出して処理していく
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_573/SkiResorts.cpp

結果

o-- 144.66pt 379th/580 rating 1330 -> 1343 (+13)

どうもeasyの「maximum」というのは最高ではなく最低の意味っぽい。わかりづらい。

mediumは典型問題らしいが、高さを削ることだけ考えてしまいだいぶ時間がかかった。

SRM 572

02:21

Div1 Easy (250) NewArenaPassword

問題

• 新しいパスワードルールでは、先頭のK文字と末尾のK文字が一致する必要がある。
• 古いパスワードが与えられる。
• ルールに適合するために変更しなければならない文字数を求める。

方針

• メモ化探索で提出
• MLE
• 適当に書き直して提出
• Challenge Succeeded
• (終了後)
• 解き直し
• length - Kの周期を持つらしい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_572/NewArenaPassword.cpp

Div1 Medium (500) EllysBulls

問題

• 数当てゲーム
• 推測した数字(guess)と、当たりの総数(bulls)の配列が与えられる
• 元の数がわかるなら答える

方針

• さっぱりわからない
• (終了後)
• 半分全列挙らしい
• しめじたんのソースを読む
• mapのキーがvector...素晴らしい
• 前半と後半の桁にわける
• 前半を全部列挙して、bullsを全部試す
• 初期値を各bullとして、guessと一致したら-1していき、総数が負にならない数とbullのペアを記憶する
• ここで記憶するbullは、前半でヒットしなかった総数なので、後半でヒットすべき
• 後半を全部列挙して、bullsを全部試す
• 初期値をゼロとして、各桁について、guessと一致したら+1していき、先に記憶していたbullと一致するものがあれば、それは前半と後半両方の条件を満たす
• 複数マッチするものがあるなら"Ambiguity"
• 一つもマッチしなかったら"Liar"
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_572/EllysBulls.cpp

結果

x-- 0pt rating 1401 -> 1330 (-71)

周期性を持つパスワードって...

TCO 2013 Round 1B

23:06

Easy (250) EllysPairs

問題

• 生徒を2人ずつペアでプロジェクトに当たらせる
• 生徒のパフォーマンスが与えられる
• 生徒のパフォーマンスの合計がプロジェクトの成果となる
• 最低と最高の成果が最も小さくなるときの最小値を求める

方針

• ソートして、最小と最大を組み合わせる
• 先頭と中央のペアの差を返す
• 提出
• Challenge Succeeded
• サンプルは先頭と末尾のペアが最大だが、どのペアも最小または最大になりうる
• 例えば{1,2,4,5,6,9}で落ちる
• 全ペアの最大と最小を取る
• 書き直し
• https://github.com/firewood/topcoder/blob/master/tco_2013/EllysPairs.cpp

Medium (500) EllysFigurines

問題

• グリッド上のボードにいくつかの人形が置かれている
• 一回の操作で、連続するR行またはC列の人形を取り除くことができる
• 最小の操作回数を求める

方針

• 制約が小さい
• 全探索できるかも
• 行か列をビットマスクでループさせれば良さそう
• 列のビットマスクでやってみる
• あるビットマスクBを決めて、最初に見つかったビットから連続するCビットを1とカウントする
• 列については、ビットマスクBの反転と論理積を取って、残っていれば列消去する必要があるので、そこからR列をまとめて1カウントとする
• 提出
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/tco_2013/EllysFigurines.cpp

Hard (1000) EllysReversals

問題

• いくつかの英数字からなる単語のリストがある
• 任意の単語Sと、Sの長さを超えない偶数kを選ぶ
• Sの1番目からk番目までの文字列を反転する
• その結果ほかの単語と一致した場合は、その単語をリストから取り除く
• 最終的に残る単語の数を求める

方針

• 色々試してみる
• 文字列の長さが奇数の場合、最後の文字だけは移動できない
• そのほかの文字は、どこへでも行ける
• ただし、移動は2個がペアになっていて、ペアは解消されない
• ペアのリストをソートしたものに末尾を加えたもので比較すればよい
• 最終的に重複したものを消す
• 提出
• Failed System Test
• 同じものが奇数のときは1つ残る
• 書き直し
• https://github.com/firewood/topcoder/blob/master/tco_2013/EllysReversals.cpp

結果

xox 388.90pt 503rd/1820 rating 1383 -> 1401 (+18)

easyは、サンプルにはソートした最小と最大のペアが最大値のケースしかなかったので、逆のケースを考えてabsを足しておいたが、全く不十分だった。弱い。

mediumは、このタイプのビットマスクで全列挙は何回かやったことがあったので、迷わず書けた。

hardは勢いで書いた割にはおしいところまで行った。

3つ提出できたのでなかなか楽しめた。R2はプラス点を目指したい。

Codeforces 170

22:13

Div2 A. Circle Line

問題

• N駅からなる環状線がある
• 駅から駅への時間が与えられる
• どちらの方向へも行ける
• 最短の時間を求める
• ただし出発駅と到着駅が同じ場合もあり

方針

• 足して一つ進める、と、一つ戻して足す、の合計の少ないほう
• オーバーフローしないようにindexにNを足してmodを取る
• Passed System Test

Div2 B. New Problem

問題

• 今までにない問題を出題したい
• 過去に出題されたタイトルの部分文字列でない文字列を求める
• ユニークかつ辞書順最小の文字列を求める

方針

• 長さが短いほうが良い
• 同じ長さなら普通に比較する
• 1文字ずつ進めて総当り
• Passed System Test

Div2 C. Learning Languages

問題

• N人の従業員とM種類の言語がある
• それぞれの従業員は0以上の種類の言語を話せる
• 任意の従業員同士がコミュニケーションを取るために必要な学習回数を求める

方針

• 少なくとも誰か1人以上と話せればよいのかなと思って書き始める
• 全員とコミュニケーションを取れないとだめっぽい
• union find木でいけそう
• それぞれの人が話せる言語をunion find木に格納しておく
• 誰かが話せる任意の言語Xを一つ選ぶ
• 従業員Yがその言語を話せないなら+1
• 全ての従業員が何も話せないケースもありうる(その場合答えはN)
• Passed System Test

結果

ooo-- 2208pt 51st/1874 rating 1680 -> 1755 (+75)

wrong answerなしで、比較的早く提出できた。割と良い出来。

Aは、総和と順方向を求めておけば、逆方向は総和から順方向を引けば求まるのだった。

Cはunion findでやればBより簡単だったかもしれない。解いた人が多かったらしく最終的にBと同じ点数だった。

順位が良かったのでdiv1に上がった。div1 Bくらいまで練習したい。