2017-06

Latest Entries

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

IPSC 2011 Practice Session

IPSC (Internet Problem Solving Contest) のプラクティス.
24 時間参加可能.
簡単ではなかった.

予約投稿を用いてみる.

P: Pancakes!


材料が与えられるので,作れるパンケーキの個数の最大値を求める問題.
パンケーキの基礎として,8/16 個の foo と 8/16 個の bar と 4/16 個の baz と 1/16 個の qux と 9/16 個の quux が要る.
さらに飾り付けとして,各パンケーキに対し,以下のいずれかが要る.
・1 個の A
・30 個の B
・25 個の C
・10 個の D
・3/4 個の A と 10 個の C
・7 個の D と 10 個の C
・1/3 個の A と 3 個の D と 5 個の B と 5 個の C
ただし P1 では最後の 3 種類は作らない.
各材料の個数は 0 以上 10^6 以下の整数.

D 言語で.
とりあえず分数を消した.
ケーキの基礎と P1 は割り算.
P2 は,最後の 3 種類の飾りを使う個数を y, z, x とでもおけば,
3 変数の「だいたい」線形計画なので,制約された領域の角をみればよい.
3 変数は面倒なので x についてループを回した.
0 <= y <= (y の制約),0 <= z <= (z の制約),y + z <= (y + z の制約),から 2 本の不等式を選んで作れる 8 個の交点に対して,まわり ±2 をみて,制約をみたいていればよりよい解かチェック,とした.

Q: Quality of Service


問題文が一部の文字しか与えられず,空白だらけ.
ときどき (1 分程度?) リロードすると表示される文字の集合が変わる.

最初は同じ文字を線で結んで図がでてくるのかと思ったら全然違った.
リロードして変わったので気づいた.
拾ってきたものを合わせるコードを C++ で書き,たまに手作業で問題文の一部を拾ってくるが重要そうな部分が全然埋まらない…
問題文の前半で wget が推奨されているっぽかったので自動化した.
徐々に埋まり,以下の問題が明らかになった:

数当てをする.相手の予想した数 (1 以上 10^9 以下の整数) はなぜかわかってしまう (入力でもらえる) が,
わざと外したい.ただし,
・1 以上 10^9 以下
・相手の数との差が 1 以上 100 以下
でなければならない.さらに Q2 では,
・奇数番目には偶数を予想し,偶数番目には奇数を予想
しなければならない (この部分が最も見えにくかった).

問題文が読めれば簡単.少し足せばよい.
少し足すと 10^9 を超えるので注意.
これに注意しすぎて,超えたときに 10^9/2 を引いてしまったが,100 より離れてしまっていて WA.

R: Rotate to divide


b 進法で書いて,最後 (小さい方) の桁をとって先頭に持ってくるとちょうど 1/k 倍になるような整数のうち,
最小のものの桁数と最初の桁を答える.存在しないならば指摘.
ただし b 進法で 2 桁以上のもののみ考える.
R1 では 2 <= b <= 8, 1 <= k <= 8.
R2 では 2 <= b <= 2,000,000,1 <= k <= 2,000,000.

k = 1 のときは "11",k = b のときは "10" が最小.k > b のときは解なし.
そうでない場合,l + 1 桁とすると,bx + y = k(x + b^(l-1) y) となる x, y を求めればよい.
b^(l-1) * y が b - k で割りきれることが必要で,これは簡単に確認できるので結構刈れる.
割りきれたら多倍長整数を使って割ってみる.x が適切な範囲なら OK.
l を 1 個ずつ進めて,解が見つかっていたら最小のものを返す.
b^(l-1) が被ったときにやめたらそれで大丈夫のようだった.

計算量やメモリはそこそこ使うが現実的サイズ.
しかし D 言語だと答が最大になっているケースで Access Violation で落ちた.
Java は遅かったが動いたのでそのケースだけ Java で解いた.

最初,k = b が解なしと勘違いして 1 WA.

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/4-72d0f037

この記事にトラックバックする(FC2ブログユーザー)

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。