eomole as a contestant このページをアンテナに追加 RSSフィード

2014-07-12

ICPC エア国内予選

| 01:11 |  ICPC エア国内予選 - eomole as a contestant を含むブックマーク はてなブックマーク -  ICPC エア国内予選 - eomole as a contestant  ICPC エア国内予選 - eomole as a contestant のブックマークコメント

国内予選当日に、お仕事しつつサブで4問くらい解いてみた。

A

http://ideone.com/RRFHTl

税抜き価格の組を列挙して、税率変更前の価格に合致しているかでフィルタして、税率変更後の価格の最大値を取る。

競プロとしては基本的なことをやるだけなんだけど、プログラミング初心者のゼロ完防止といえるかはちょっとよくわからない。

自然な発想としては、変更前の価格から税抜き価格を生成して、変更後価格を求めたいと思うのだけど、対応する税抜き価格というのは存在性も一意性もないところが落とし穴で、たいがい実装とデバッグが悲惨なことになり、うまく実装するにはそれなりの経験が必要になる。税抜き価格を中心にして発想を逆転させて簡潔にするのが重要になると思われるけれど、それはそんなに自明だろうか?

むむむ。

B

http://ideone.com/9eQmLC

どう転んでも問題文に書いてある通りにやるしかなさそう。

本当にやるだけ。

C

http://ideone.com/xwFWWR

真面目にやるなら座標圧縮で離散的にやるとかしないといけないんだけど、冷静になって制約よく見ると座標は 20 までの整数値しか与えられないので、幅1の長方形に切ってそれぞれについて最大値を求めて最小値を取ればいい。こうすると原点をまたぐやつとか場合分けが減って嬉しい。

見た途端に2分探索という人もいたらしい。

2分探索の基本的な考え方は、特定のパラメータ (ここでは時刻) を固定した状況を考えて更新方向を求めるものである。

状況が複雑なのでこのような考察は重要となる。

なんだけど、よく考えるとこの問題については1次不等式にしかならないので、臨界値を陽に求めることができる上に、ほとんど計算式も同じになる。(そりゃ移項しただけだからな)

自分で実装するなら慣れてるものを使えばいいと思うけど、他の人に書かせるときにそれを勧めるならどうか思わなくもない。

D

http://ideone.com/9GKukK

ルールをよく見ると1文字につき高々2通りしかできることがないので、制約に注目すると 2^20 で押さえられて普通に1個ずつ作って (順序付き) セットに突っ込んでも良い。

よく見ると最大ケースはサンプルに入っている...。

実際の列挙は、先頭から DFS とかで適当に作れば良い。

ビット列によるエンコーディングでループを回すのはどうなのだろう?ビット列へのエンコーディングは計算量の見積もりができればほぼ自明だけど、デコーディングは局所的にはできなくて、結局 DFS のときと同様に先頭からやれば良いという考えが必要で、探索における分岐だと思ったほうが自然なのでは?と思った。

SRM とかで数え上げ系とか、辞書順最小とか求める問題では、たいてい1個ずつ馬鹿正直作ると計算量で大変なことになるので、その手のコンテストを中心にしていると生理的にちょっと辛かったかもしれない。

まあ、でも C より頭使わなくて良くて簡単では?

感想

  • A はちょっとひねりすぎで、初心者には辛かったかもしれない。 (ゼロ完防止なら模擬と同じくらいの難易度にしても...)
  • 問題にかかる時間が、実装よりも考察が支配的な傾向が強いせいか、国内予選は時間が短いこともあって、ボラティリティが必要以上に高くなってしまっている気がした。
  • ゲームバランス調整むずい。やるの自分じゃないけど

2014-04-26

GCJ Round 1A

| 19:18 |  GCJ Round 1A - eomole as a contestant を含むブックマーク はてなブックマーク -  GCJ Round 1A - eomole as a contestant  GCJ Round 1A - eomole as a contestant のブックマークコメント

ダメすぎてオワってた。

A: 昔使ってた next_permutation ライブラリ引っ張ってきたら、仕様を忘れてて、最初1回分が飛んでしまって WA ではまった。どちらにしろ半分全列挙だーとかって書きだしたので、いろいろアレだった。

C: http://upload.wikimedia.org/wikipedia/commons/9/90/Probabilities7.svg を眺めてただけだった。Bias がない状態がパッと思いつかなかったわけだけど、一様になってるはず。そういえばちょっと前に Twitter でこの辺の話が話題になってた気がする。

あまりに杜撰なプレイだった。反省する。

2014-04-13

TCO 2014 Qual 1A

| 19:59 |  TCO 2014 Qual 1A - eomole as a contestant を含むブックマーク はてなブックマーク -  TCO 2014 Qual 1A - eomole as a contestant  TCO 2014 Qual 1A - eomole as a contestant のブックマークコメント

1週間延期されたのがあった。

去年の TCO 予選シーズン以来 TopCoder に出ていなかったのでかなり久々。

Easy: 文字列に対して適当な prefix を切り出して suffix N 文字をソートという処理を繰り返して辞書順最小の文字列を作る問題。Prefix の選び方は1文字ずつ前進で N 文字になるまで限界まで続ける戦略が最適であるのが、考察するとわからなくもないのでそれを実装するとよい。もう少し効率よくするなら、先頭 1 文字を除いてソート、先頭 N 文字を切り出してソートが最終結果なのでそれを実装すればよい。全体ソートして先頭 N 文字を切り出すという嘘解法にたどり着きやすいけど "TOPCODER" で落ちるので、サンプル親切だった。

Mid: 文字を並び替えて辞書順最小の文字列を作る問題。ただし、元の位置から N 文字以上離れてはいけない。これは先頭から使える文字を貪欲に置いていけば OK。ただし、その場所を逃すと制約を満たさなくなるという文字が生じたらそれを置かないといけないことに注意する。

Hard: よくわからなかったけど 8N くらいの DP でいいらしい。

Challenge: 灰色さんが "TOPCODER" で落ちるはずの嘘解法を提出していたので3人くらい落とした。(実のところ1人目はTLE狙いだった。枝刈り落とそうとしてしまうのやはり辞めた方がいい。まあ結果オーライ)サンプルくらいチェックしようね?

3 年前の TCO の時期のレートを超えて highest 更新。あと部屋 1 位で div で獲得した最高のスコアだったらしいけど、div 1.5 みたいな感じなので微妙い。

GCJ 2014 Qual

| 20:46 |  GCJ 2014 Qual - eomole as a contestant を含むブックマーク はてなブックマーク -  GCJ 2014 Qual - eomole as a contestant  GCJ 2014 Qual - eomole as a contestant のブックマークコメント

Template を Java 8 にバージョンアップして出てみた。というより template 更新ばかりに時間をかけて危うく時間切れになるところだった。。とはいえ並列ストリーム以外は全然使ってないけど。

A: やるだけ。もうちょっと詳しく説明すると、 4 行 4 列の行列が 2 つあるのでそれぞれから指定された行を抜き出して一致する数字はいくつありますか?1つならその数字も教えてねという問題。まあ、登場人物は盤面を90度回転させればよかっただけのになぜそうしなかったのか、謎である。

B: クッキクリッカーで所定の枚数を最速で集めるには?ただし、施設は農場だけで(ばーさんもいない)、さらに連続時間モデル。建てる施設数をパラメータに最適化すれば良くて多分凸性もありそう。なんか制約から線形探索で良さそうな気がしたのでそれ投げてしまったけど通った。でも、あとでよく考えてみると C=1, F=1, X=100,000 とか渡されるとヤバイことに気付いた。これだからランダム入力は…

C: 盤面のサイズと地雷の数が与えられるので、1 クリックで終了できるような盤面を生成する問題。Small は全配置を生成してそれぞれ 1 クリックで終了できる位置がないか調べた。Large はそれでは無理なので、左と上に幅 3 の領域を残して角にクリックポイントを置き、残りの部分に規則的に埋め、次に幅 3 の領域に規則的に並べて、最後に残った 3x3 は全探索した。3x3 の領域に離接する外側のタイルでアドホックな場合分けを入れたので、そこで撃墜できそうな予感だったけど、落ちなかった。ランダム入力さまさま…

D: 問題文に警告が出ているように理解するまで時間のかかる問題。詐欺プレイをするときは釣りができるので、Ken の各おもりりに最大までそれに勝てる自分のおもりを割り当てることができる。一方、しないときは自分の持っているおもりの重さしか伝えられないので、避けられないとき以外は Ken によってそれより小さい重さのおもりが 1 個ずつ消費されてしまうので、残りが答えとなる。

結局全部通って満点 90 点でした。

JAG 春コン 2013

| 20:46 |  JAG 春コン 2013 - eomole as a contestant を含むブックマーク はてなブックマーク -  JAG 春コン 2013 - eomole as a contestant  JAG 春コン 2013 - eomole as a contestant のブックマークコメント

参加者の方お疲れ様でした。

コメントはスコアボードに騙されるな、ということですね。はい。

簡単な問題を嗅ぎ分けられるようにしましょう。

2014-02-19

最近のコンテスト活動

| 14:29 | 最近のコンテスト活動 - eomole as a contestant を含むブックマーク はてなブックマーク - 最近のコンテスト活動 - eomole as a contestant 最近のコンテスト活動 - eomole as a contestant のブックマークコメント

最近出たコンテストというと物見遊山な感じで出てみた謎コン、その前がM杯な感じでSRMすらほとんど出ていない気がする。このブログも終わりなのだろうか。

追記

| 16:23 | 追記 - eomole as a contestant を含むブックマーク はてなブックマーク - 追記 - eomole as a contestant 追記 - eomole as a contestant のブックマークコメント

FHC とか他にも出ていたものがあったことを思い出した。

何か出たらメモるという習慣を取り戻そう。

2013-06-16

ARC 14

| 00:32 | ARC 14 - eomole as a contestant を含むブックマーク はてなブックマーク - ARC 14 - eomole as a contestant ARC 14 - eomole as a contestant のブックマークコメント

夕飯食いながら参加してみた.

  • A: パリティ見るだけ
  • B: 1個ずつ確かめつつ出力はターン数のパリティ見るだけ
  • C: 貪欲に各色のパリティを加算すればいい
  • D: x + y の小さいクエリからイベント処理の要領で

フォーム直書き縛りとかもやってみた. C で文字列が入力に与えられているとは思わなくて 1 WA, 14 位.

C

筒の中に2個までは, 何が来ても貪欲にペアを消すことが自明に可能なので略.

3個目に消せないものが来たときを考える. 4個目の色を見て, それが消せるように3個目を入れる側を調整すればよい. この操作のあとは, 必ず2個になる.

このようにすると, 貪欲にすべてのペアが消せることが示せるので, 残る個数はパリティだけで決まる.

D

説明は略してソースコード

http://arc014.contest.atcoder.jp/submissions/80867

2013-06-03

GCJ2013 R2

| 01:59 | GCJ2013 R2 - eomole as a contestant を含むブックマーク はてなブックマーク - GCJ2013 R2 - eomole as a contestant GCJ2013 R2 - eomole as a contestant のブックマークコメント

初めてTシャツはもらえたっぽい気がするけど、ここで今年の冒険は終わってしまった。。

来年こそは最強のオレオレ言語でオンサイトに行くんだ...

テンプレ (改)

前のは実行方法が煩わしかったので、カレントディレクトリを読んで適切そうなものを実行するようにした。

しかし、これ WA ったときにファイル退避しないといけなくて面倒だし失敗かも。。とサブミットデバッグして思った。

http://ideone.com/ANceid

2013-04-14

GCJ2013 Qual

| 15:08 | GCJ2013 Qual - eomole as a contestant を含むブックマーク はてなブックマーク - GCJ2013 Qual - eomole as a contestant GCJ2013 Qual - eomole as a contestant のブックマークコメント

最近は完全に引退勢でした。

A

Tic-Tac-Toe が 4x4 になって、Tomek (内輪ネタ...) なる X / O どちらとしても使えるものが最初から盤面に置かれている。盤面を見て勝敗を判定せよ。

やるだけ。

どちらも勝利条件を満たしているときの処理は invalid な盤面はないとのことなので無視して良さげ。

B

縦横1直線に同じ高さに刈れる芝刈り機があるので、与えられた芝の高さが作れるか判定せよ。

やるだけ。

縦横どちらかの方向でそのマスより高い芝がなければ良いので、各行・列の最高を求めておけば簡単。

C Small / Large1

閉区間が与えられるので、x, x^2 が回文となるような x^2 の個数を求めよ。

やるだけ。

x だけ全列挙しておけばよいので高々 10^7 個、あらかじめ求めておいてもよいのでさらに簡単。

C Large2

注: これはまともな解法ではありません。想定解法は他の人の解説を見てください。

実際に数えてみると 39 個しかないので、観察してみた。

すると x には次の規則性があるように見えた。(未証明)

1桁のとき
1, 2, 3
両端
1, 2
奇数桁のときの真ん中
0, 1, 2
それ以外
0, 1

となり、列挙すべき候補がだいぶ減ったように見える。

実際調べてみると 40,000 ちょっとだった。

あとは埋め込みして2分探索。したけれども、ソースコードが大きくなりすぎて弾かれた。そういえばそういうのもあった。覚えていたら形式をもう少し考慮したのに。反則とられるのも嫌だったのでスルー。

  • ちなみに gzip + base64 とかで十分 1 MB 以下になる
    • GZIPInputStream は JDK にある
    • Base64JDK 8 に入る予定

Practice は通った。

D Small

箱の鍵がいくつか入った箱が幾つかあるので、全部開けられるような順番を求めよ。複数あるときは辞書順最小で。

Small は小さいので巡回セールスマンで解いた。直前の状態が何だったかを覚えておく必要はないので少し状態は減る。

D Large

マッチングに見えた。よく知らない。

結果

135 で 1205位。

おまけ

毎年 http://www.go-hero.net/ から去年のものを発掘してきてテンプレを作るのも賢くないので自分用にペタリ

http://ideone.com/6jTc7k

2012-03-18

SRM537

| 14:00 | SRM537 - eomole as a contestant を含むブックマーク はてなブックマーク - SRM537 - eomole as a contestant SRM537 - eomole as a contestant のブックマークコメント

賞金付きなのでたまには真面目に参加してみる。

275

AとBがXと適当なYから作れるか調べればよい。AもBもXだけで作れてしまうならYは何でもいいので-1。それ以外のときは1<=Y<=max(A,B)の範囲に収まるので全部調べて数え上げる。小さいのでユークリッドの互除法とかは不要。

200.27

http://community.topcoder.com/stat?c=problem_solution&rm=312058&rd=14730&pm=11817&cr=22695644 (要ログイン)]

500

Bit別に処理できるので、各部屋の各bitが1になる確率をDPで計算していけばよい。

352.97

http://community.topcoder.com/stat?c=problem_solution&rd=14730&rm=312058&cr=22695644&pm=11822 (要ログイン)]


925

Euler Cycle を貪欲に取り除いていくのではダメなんだろうなあ。と思いつつ放置。

Compiled.

Challenge Phase

TLE狙いで撃墜しようとしたけどミスした。あとで見たらWAだった。

-25.00

結果

528.24 で 103位。1374 -> 1534 で黄色復帰。闇雲な撃墜をやめたい。。

2011-06-24

ACM-ICPC 2011 (エア)国内予選

| 00:22 | ACM-ICPC 2011 (エア)国内予選 - eomole as a contestant を含むブックマーク はてなブックマーク - ACM-ICPC 2011 (エア)国内予選 - eomole as a contestant ACM-ICPC 2011 (エア)国内予選 - eomole as a contestant のブックマークコメント

すでに引退しているので裏方でした。低速で何問か本番やっている裏で解いてみました。大体30位相当かな。

A. チェビシェフの定理

適当。途中で2倍しないといけないことを思い出した形跡が。

source code

B. 世界の天秤

適当。Stackに積んだように見える。

source code

C. 同色パネル結合

最後の色が指定されているのを忘れて時間かかった。図が多いと縦に長くなるので、横長ディスプレイだと忘れずに読むなんて無理な気がする。マジックナンバー多くてちょっとひどいコード。

source code

D. そして,いくつになった?

適当にメモりつつ探索。最初leftがimmutableな使い方していないことを忘れてmapに突っ込んでしまった。反省します。

source code

まとめ

みなさんずいぶんハイレベルになりましたね。しみじみ。いつも1歩大学内トップチームにいくらか及ばなくて、あまり解けていないのに地区予選に進出するチームを苦々しく思っていたものですが(後継のチームはずいぶん強くなりましたが)、全体のレベルが上がると気持ちがいいものですね。

あと、ペアプロ懐かしいです。僕と契約して以下略。

おまけ

練習セッション大事です。使い方覚えて無意味なWAを出さないというのもそうですが、様々な不具合によりログインすらできないということがしょっちゅうあるので、きちんと動作確認に協力してください。お願いします。

と、模擬国内予選運営して思いました。

2011-05-21

Google Code Jam 2011 Round 1A

| 13:38 | Google Code Jam 2011 Round 1A - eomole as a contestant を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 1A - eomole as a contestant Google Code Jam 2011 Round 1A - eomole as a contestant のブックマークコメント

1問しか時間内に通らなくてほげほげ。

A. FreeCell Statistics

できないのは、PGが100または0なのにPDがそうでないとき、Dの最小値がNより大きいときだけです。Dの最小値は約分すれば求まります。

source code

28m 23s

B. The Killer Word

適当にソートして範囲を狭めつつ調べるつもりでした。90分くらい間違った方針で書いていたので時間内に終わりませんでした。で、終了後25分くらいで書けたコードはLargeが10秒くらい。

source code

1 wrong try

C. Pseudominion

読みませんでした。

まとめ

最近スタッフ側にまわってタイムリミットなしで解く方が多くなったせいか、実装が遅すぎですね。トレーニングします。