ask.fm での質問「http://www.nintendo.co.jp/wii/sf8j/index.html」に対する返答
ドンキーコングリターンズはその名前（リターンズ）からして分かるように，ドンキーファン待望の一作となりました．
元々，スーファミ時代のスーパードンキーコングシリーズの魅力は何かというと，当時としては驚くほど美麗なグラフィック，そのグラフィックの雰囲気にぴったりと合った素晴らしい音楽，非常に手の込んだ難易度の高いステージに，（特に2以降の）ボーナスステージやDKコイン集めからのロストワールドといったやりこみ要素，等が挙げられますが，リターンズはその魅力のいずれも受け継いで更に発展させたゲームになっています．
グラフィックについてはハード面の進化もあり（そもそもスーファミ時代のドンキーシリーズの美麗なグラフィックは，異なる色を爆速で点滅させることでスーファミの限界を超えた色に見させるという，ハード面のボトルネックを何とかして超えるための技法が使われていました），よりドンキーの世界にあったものとなりました．特にジャングルが分かりやすいですが，いずれのワールドでも背景やステージのグラフィックは非常に凝っており，細かい部分まで雰囲気をよく出しています．他に特筆すべき点として，タル大砲やバナナ等のものを除き，ステージには浮いているものが一切ないという点が挙げられます．こういったアクション系のゲームでは浮いている足場とか物理法則に反している要素というものが頻繁に出てきますが，ドンキーコングリターンズでは空中の足場はちゃんと下に骨組みがあるか，背景から出っ張っている形をとっているか，天井から吊り下げられているなどの形をとっていて，その点にはかなり世界観に関するこだわりが感じられます．
音楽は基本的にスーパーファミコン時代のもののリメイクが多いです．当時も音楽はこれって本当にスーファミ？と驚くような音が多く非常に出来が良いですが，その雰囲気をしっかりと継承しつつも新しく仕上げられたリターンズの音楽は素晴らしいの一言です．こういったゲームの音楽は，単に音楽単体として在るといったものではなく，やはりゲーム自体の世界に合い，またそれを引き立てていくといった役割をもって立ち上がるわけですが，その点についてはスーファミ時代から変わらず最高の音楽であると言えるでしょう．
ステージについては当初結構心配していました．というのも，こういう風に新しいゲームだと，ぬるい難易度になってしまうのでは？という懸念があったためです．しかし，ことドンキーに限りその心配は杞憂でした．スーファミ時代のドンキーシリーズは，当時小学生であったぼくには非常に難しかった記憶が残っているのですが，リターンズはすでに大学生になったぼくがやっても当時の記憶より遥かに難しい，ある意味でかなり衝撃的な難易度でした．アクション性の高い操作はもちろんのこと，ギミックを突破するために必要な思考や，次々と崩れる足場に対応する判断力など，あまりにも満足すぎるというか，予想の何段階も上をいくかなりぶっ飛んだ難易度で逆にこんな難しくて売れるのかと心配してしまった程です．特にワールド6のクリフエリアに関しては，もうほとんどあらゆる足場が一度乗ったら崩壊するものだから，KONGパネルやパズルピースのことなんて考えずにひたすらクリアを目指すにしても何度も落ちてしまいましたね．ドンキーといえば難しい，というのは常々あったイメージですが，そのイメージ通りかあるいはその上を行くステージ達でした．ステージに存在するギミックについても，1 ステージごとにどんどん新しいものが出てきて驚きでした．
ドンキーシリーズのステージといえば，スーパードンキーコング2に出てくる「どくどくタワー」やスーパードンキーコング3の「ハラハラのこぎり」がかなり有名で，個人的にはこの二者の素晴らしい点はなんといっても強制スクロールの緊迫感の演出だと思っています．ただ単に画面が強制的にスクロールされるわけではなく，下から迫りくる毒の海や巨大のこぎりといったかなり恐怖を煽る演出は，特に小学生だった当時のぼくには衝撃でした（ちなみにこの2ステージは，ドンキーシリーズには珍しくかなり現実感のない設定ではあるのですが，いまはリターンズの話なのでこの話は置いておきましょう）．リターンズもその例に漏れず，強制スクロールステージは相変わらず衝撃的でした．というよりもむしろ，いま大学生になったぼくが衝撃を感じているほどですから，より衝撃は増したとも言えるのではないかと思います．そのステージはフォレストエリアの「だっしゅつ！虫のやかた」です．何の変哲もないジャングルステージかと思いきや，突然ぶよぶよとジャンプできるイクラのようなものが現れます．なんとこれはおびただしい数の虫の卵であり，このステージは画面端から迫り来る大量の虫に追われる強制スクロールステージとなるのです．虫は端からだけでなく，ステージ中に存在する穴などからもわらわらと湧き続け画面を覆わんとしてきます．それはもう，単純にあまりにも恐ろしいと言う他なく，特に虫がかなり苦手なぼくにとっては当時の「どくどくタワー」や「ハラハラのこぎり」を凌駕する恐怖でした．
そして何といってもやりこみ要素ですね．これはスーファミ時代に比べて最も強化された点と言ってよいでしょう．スーファミ時代には影の薄かったKONGパネルですが，今作では各ワールドに存在するKステージを解禁するための重要なアイテムとなり，パズルピースはボーナスステージで貰える他ステージの様々な箇所に（時にはとても見つけられないようなところに！）隠されており，これらを揃えるだけでも相当なやりこみ要素です．特にパズルピースは普通にプレーしていても見過ごしてしまうようなものが大半ですから，これを集めるというだけでもかなりの難易度です．いっぽうKONGパネルの方は，収集こそピースより簡単なものの，それによって解禁されるKステージが凄まじいです．特に6-Kのステージ「クライマーラビリンス」が2つの点で突出しています．ひとつはこの「クライマーラビリンス」は先ほども言及した「どくどくタワー」の正統派後継とでも言うべき強制スクロールステージであり，下から触れると即ミスの溶岩が迫ってくるという点です（さっき少し言った，ドンキーには珍しい現実感のなさという話ですが，この「クライマーラビリンス」では背景の岩石が崩れて溶岩が吹き出す描写が随所にあるなど，そういった点でも進歩しています）．もうひとつは，なんといってもその難易度です．個人的にはこの「クライマーラビリンス」がドンキーコングリターンズ全ステージの中で最も難易度が高いのではないかと思います．まず抑えておきたいのは，このKステージというのは中間地点が全く存在しない，つまりミスしたら問答無用でまた最初から始めねばならないということです．そしてこのステージには DK バレルや回復のハートも一切出現しません．これだけでも恐るべき構成ですが，中間地点やDKバレルが仮にあったとしても尚最強の難易度を誇ると言って過言ではないステージが待ち受けています．上にのぼるタイプの強制スクロールですが，足場は基本的に上から落ちてきます．上から足場の落ちてくるタイミングは固定なので，うまくプレーすればどんどん上にのぼっていけるということがありません（どくどくタワーはそうではありませんでしたので，うまくなった今プレーすればほとんど毒の姿を拝まずにクリアすることも可能です）．そうして否が応にも焦らせておきながら，上からは炎をまとった敵が壁伝いに落ちてきては床を伝ってドンキー達を狙ってきますので，上にあがることだけをひたすら考えればいいというわけにもいきません．最難所は後半のジャンプ台地帯で，これは溶岩に浮かぶ2つのジャンプ台の上をうまく飛びながら行き来する地帯なのですが，これだけでも十分に難しいギミックだというのに，なんとそこに虫のような飛ぶ敵がやってきます．その虫のような敵が驚くべき厄介さで，青い稲妻のようなものをまとっているために踏むことはできませんし，何より飛びながらドンキーたちを追尾する動きをします．不安定な足場で，しかもジャンプ台である，という状態でこの虫に追いかけられるのをかわすのは尋常でない難易度です．ここをクリアするためにいくつの風船（ドンキーでは残機は風船で表すのが伝統です）が犠牲になったか知れません．
さて，また高難度ステージに話が戻ってしまいましたが，やりこみ要素の話でしたね．これ以外に主要なやりこみ要素がまた2つあり，ひとつは「タイムアタック」ですね．このタイムアタック，各ステージを普通にプレーするのですがその時間が計測されていて，予め決められた基準タイムに従って銅・銀・金のメダルが貰えます．はじめ，ぼくはスーパードンキーコング2でRTAの練習をしていた時期があったことや，曲がりなりにもこのゲームが下手なほうではないだろうという自負があったので，ミスなくつつがなく進行できれば金メダルは達成可能だと踏んでいました．が，何ということか，普通にミスなくプレーしても銅メダルすら手に入らないステージばかりで，いざタイムを縮めようと必死に動きを最適化して頑張っても金メダルのタイムにまったく及ばないではないですか．1ステージに対して30分，1時間と時間をかけて「ここではこの敵をジャンプで超えたあと，この次の敵をちょうど踏めるようなタイミングでローリングをするのが良い」とか「このタル大砲地帯は4個目以外はノータイムで撃ってしまって構わない，4個目だけは少し待つようにする」とかそういう知見を積み重ねてようやくギリギリ金メダルがとれるとか，そういうタイムです．この基準タイムというのはスタッフが Tool Assisted でプレーして決めたのではないかとか，そういうレベルです．
もうひとつの要素が「ミラーモード」です．これはKステージをすべてクリアしたあと，ワールド9の唯一のステージ「黄金のしんでん」（このステージは唯一の例外といってよく，バナナやイチゴやブルーベリーなどの果物が空中にゆらゆら浮いているところを進む幻想的な雰囲気のあるステージで，これがまた異常に難しい）をクリアすると解禁され，全てのステージに対し「ミラーモード」で遊べるようになります．これは名前のとおり元のステージのすべてが鏡像反転されたステージを遊べるようになるわけですが，重要なのはそこではありません（だってすべてが鏡像反転されるだけなら難易度は別に変わらないですからね）．「ミラーモード」ではディディーコングは出現せず，ドンキーコングのみで進まねばなりません．これがいかに難しいかというと，今作ではディディーは樽ジェットで空中に少しの間浮けるのです（足場が不安定なことの多いこのゲームではものすごく役立ちます）が，それが全く使えなくなるというわけです．さらに，このゲームはさすがに全体的なステージの難易度を考慮してか，ドンキーとディディーそれぞれに2のライフがあり，基本的に体力満タンの状態から敵のダメージ等を3回までなら食らっても大丈夫，というシステムになっていました．が，このミラーモードではライフは1つになってしまいます．ディディーがおらず，ライフが1ということは，樽ジェットのない高度なアクション操作が求められるドンキーオンリーの状態で，しかも1回でも敵に当たってしまえばそれで終了，というかなり無茶な要求をするモードということです．
お恥ずかしながら，これらのあまりの難易度に，タイムアタックもミラーモードも途中で止まってしまっており（ほぼ挫折に近いレベル），いまだに完全クリアはできていません．いつかは完全クリアしたいところですね（ミラーモードは何とかなるだろうという気がするのですが，タイムアタックは本当に厳しすぎです）．
ICPC 2013 会津大会 チーム紹介スライド 0perasan
以下の通りです．ご確認下さい．
情報オリンピック夏季セミナー 2013 小学生並の参加記
後になるほど失速します
8月26日(月曜日)
やる気に満ち溢れている．
8月27日(火曜日)
まだちゃんとやる気がある．
8月28日(水曜日)
突然やる気がなくなって，文章とりあえず半分まで書けばいいみたいな感じになる．
8月29日(木曜日)
やる気のかけらもない．
8月30日(金曜日)
もうどうにでもなれ．
Google Code Jam 2013 Qual
長く苦しい戦いだった……．ソースを載せます．
A (LOLCODE)
一番苦労した．言語の公式サイトにつながらないし，WebArchiveからSpecificationを探してきて頑張って書いた．特に超不便な連想配列しか用意されていない点や，文字列の i 番目にアクセスすることができない点は辛かった．後者は特にどうしようもなかったので Python で input を改行区切りに変換するスクリプトを書くことで対処した．
HAI 1.3
I HAS A CSN ITZ A NUMBR
GIMMEH CSN
I HAS A CURCS ITZ 0
IM IN YR LOOP UPPIN YR CURCS WILE DIFFRINT CURCS AN BIGGR OF CURCS AN CSN
I HAS A BRD ITZ A BUKKIT
I HAS A ROW ITZ 0
I HAS A COL ITZ 0
IM IN YR RDLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
COL R 0
I HAS A LNE ITZ A BUKKIT
IM IN YR RDLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
LNE HAS A SRS COL
GIMMEH LNE'Z SRS COL
IM OUTTA YR RDLPC
BRD HAS A SRS ROW ITZ LNE
IM OUTTA YR RDLPR
VISIBLE "Case #" AN SUM OF 1 AN CURCS AN ": "!
I HAS A DTRMND ITZ FAIL
ROW R 0
IM IN YR RLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
I HAS A XC ITZ 0
I HAS A OC ITZ 0
I HAS A TC ITZ 0
COL R 0
IM IN YR RLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
I HAS A TML ITZ BRD'Z SRS ROW, TML'Z SRS COL, WTF?
OMG "X", XC R SUM OF 1 AN XC, GTFO
OMG "O", OC R SUM OF 1 AN OC, GTFO
OMG "T", TC R SUM OF 1 AN TC, GTFO
OIC
IM OUTTA YR RLPC
NOT DTRMND, O RLY?
YA RLY, BOTH OF BOTH SAEM XC AN BIGGR OF XC AN 3 AN BOTH SAEM SUM OF XC AN TC AN 4, O RLY?
YA RLY, VISIBLE "X won", DTRMND R WIN
MEBBE BOTH OF BOTH SAEM OC AN BIGGR OF OC AN 3 AN BOTH SAEM SUM OF OC AN TC AN 4
VISIBLE "O won", DTRMND R WIN
OIC
OIC
IM OUTTA YR RLPR
COL R 0
IM IN YR CLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
I HAS A XC ITZ 0
I HAS A OC ITZ 0
I HAS A TC ITZ 0
ROW R 0
IM IN YR CLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
I HAS A TML ITZ BRD'Z SRS ROW, TML'Z SRS COL, WTF?
OMG "X", XC R SUM OF 1 AN XC, GTFO
OMG "O", OC R SUM OF 1 AN OC, GTFO
OMG "T", TC R SUM OF 1 AN TC, GTFO
OIC
IM OUTTA YR CLPR
NOT DTRMND, O RLY?
YA RLY, BOTH OF BOTH SAEM XC AN BIGGR OF XC AN 3 AN BOTH SAEM SUM OF XC AN TC AN 4, O RLY?
YA RLY, VISIBLE "X won", DTRMND R WIN
MEBBE BOTH OF BOTH SAEM OC AN BIGGR OF OC AN 3 AN BOTH SAEM SUM OF OC AN TC AN 4
VISIBLE "O won", DTRMND R WIN
OIC
OIC
IM OUTTA YR CLPC
I HAS A XCDA ITZ 0
I HAS A OCDA ITZ 0
I HAS A TCDA ITZ 0
ROW R 0
IM IN YR DIAGA UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
I HAS A TML ITZ BRD'Z SRS ROW, TML'Z SRS ROW, WTF?
OMG "X", XCDA R SUM OF 1 AN XCDA, GTFO
OMG "O", OCDA R SUM OF 1 AN OCDA, GTFO
OMG "T", TCDA R SUM OF 1 AN TCDA, GTFO
OIC
IM OUTTA YR DIAGA
NOT DTRMND, O RLY?
YA RLY, BOTH OF BOTH SAEM XCDA AN BIGGR OF XCDA AN 3 AN BOTH SAEM SUM OF XCDA AN TCDA AN 4, O RLY?
YA RLY, VISIBLE "X won", DTRMND R WIN
MEBBE BOTH OF BOTH SAEM OCDA AN BIGGR OF OCDA AN 3 AN BOTH SAEM SUM OF OCDA AN TCDA AN 4
VISIBLE "O won", DTRMND R WIN
OIC
OIC
I HAS A XCDB ITZ 0
I HAS A OCDB ITZ 0
I HAS A TCDB ITZ 0
COL R 0
IM IN YR DIAGB UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
I HAS A TML ITZ BRD'Z SRS COL, TML'Z SRS DIFF OF 3 AN COL, WTF?
OMG "X", XCDB R SUM OF 1 AN XCDB, GTFO
OMG "O", OCDB R SUM OF 1 AN OCDB, GTFO
OMG "T", TCDB R SUM OF 1 AN TCDB, GTFO
OIC
IM OUTTA YR DIAGB
NOT DTRMND, O RLY?
YA RLY, BOTH OF BOTH SAEM XCDB AN BIGGR OF XCDB AN 3 AN BOTH SAEM SUM OF XCDB AN TCDB AN 4, O RLY?
YA RLY, VISIBLE "X won", DTRMND R WIN
MEBBE BOTH OF BOTH SAEM OCDB AN BIGGR OF OCDB AN 3 AN BOTH SAEM SUM OF OCDB AN TCDB AN 4
VISIBLE "O won", DTRMND R WIN
OIC
OIC
I HAS A DC ITZ 0
ROW R 0
IM IN YR DCNTLR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
COL R 0
IM IN YR DCNTLC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
I HAS A TML ITZ BRD'Z SRS ROW, BOTH SAEM TML'Z SRS COL AN ".", O RLY?
YA RLY, DC R SUM OF 1 AN DC
OIC
IM OUTTA YR DCNTLC
IM OUTTA YR DCNTLR
BOTH OF NOT DTRMND AN BOTH SAEM DC AN 0, O RLY?
YA RLY, VISIBLE "Draw", DTRMND R WIN
OIC
NOT DTRMND, O RLY?
YA RLY, VISIBLE "Game has not completed"
OIC
IM OUTTA YR LOOP
KTHXBYE
B (LOLCOCDE)
内容的にも慣れ的にも明らかに A より楽だった．
HAI 1.3
I HAS A CSN ITZ A NUMBR
GIMMEH CSN
I HAS A CURCS ITZ 0
IM IN YR LOOP UPPIN YR CURCS WILE DIFFRINT CURCS AN BIGGR OF CURCS AN CSN
I HAS A RWS
I HAS A CLS
GIMMEH RWS
GIMMEH CLS
RWS IS NOW A NUMBR
CLS IS NOW A NUMBR
I HAS A FLD ITZ A BUKKIT
I HAS A ROW ITZ A NUMBR
I HAS A COL ITZ A NUMBR
ROW R 0
IM IN YR RDLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN RWS
COL R 0
I HAS A LNE ITZ A BUKKIT
IM IN YR RDLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN CLS
LNE HAS A SRS COL
GIMMEH LNE'Z SRS COL
LNE'Z SRS COL IS NOW A NUMBR
IM OUTTA YR RDLPC
FLD HAS A SRS ROW ITZ LNE
IM OUTTA YR RDLPR
I HAS A HGHT ITZ 1
IM IN YR CTLP UPPIN YR HGHT WILE BOTH SAEM HGHT AN SMALLR OF HGHT AN 100
ROW R 0
IM IN YR CTLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN RWS
COL R 0
IM IN YR CTLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN CLS
I HAS A TML ITZ FLD'Z SRS ROW, BOTH SAEM TML'Z SRS COL AN HGHT, O RLY?
YA RLY
I HAS A RC ITZ 0
I HAS A CC ITZ 0
I HAS A TR ITZ 0
I HAS A TC ITZ 0
IM IN YR CNTLPR UPPIN YR TR WILE DIFFRINT TR AN BIGGR OF TR AN RWS
I HAS A TTML ITZ FLD'Z SRS TR
EITHER OF BOTH SAEM TTML'Z SRS COL AN HGHT AN BOTH SAEM TTML'Z SRS COL AN 0, O RLY?
YA RLY, RC R SUM OF 1 AN RC
OIC
IM OUTTA YR CNTLPR
IM IN YR CNTLPC UPPIN YR TC WILE DIFFRINT TC AN BIGGR OF TC AN CLS
I HAS A TTML ITZ FLD'Z SRS ROW
EITHER OF BOTH SAEM TTML'Z SRS TC AN HGHT AN BOTH SAEM TTML'Z SRS TC AN 0, O RLY?
YA RLY, CC R SUM OF 1 AN CC
OIC
IM OUTTA YR CNTLPC
BOTH SAEM RC AN RWS, O RLY?
YA RLY
TR R 0
IM IN YR FLDLPR UPPIN YR TR WILE DIFFRINT TR AN BIGGR OF TR AN RWS
I HAS A TTML ITZ FLD'Z SRS TR, TTML'Z SRS COL R 0
IM OUTTA YR FLDLPR
OIC
BOTH SAEM CC AN CLS, O RLY?
YA RLY
TC R 0
IM IN YR FLDLPC UPPIN YR TC WILE DIFFRINT TC AN BIGGR OF TR AN CLS
I HAS A TTML ITZ FLD'Z SRS ROW, TTML'Z SRS TC R 0
IM OUTTA YR FLDLPC
OIC
OIC
IM OUTTA YR CTLPC
IM OUTTA YR CTLPR
IM OUTTA YR CTLP
I HAS A K ITZ WIN
ROW R 0
IM IN YR CHKLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN RWS
COL R 0
IM IN YR CHKLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN CLS
I HAS A TML ITZ FLD'Z SRS ROW
K R BOTH OF K AN BOTH SAEM TML'Z SRS COL AN 0
IM OUTTA YR CHKLPC
IM OUTTA YR CHKLPR
VISIBLE "Case #" AN SUM OF 1 AN CURCS AN ": "!
K, O RLY?
YA RLY, VISIBLE "YES"
NO WAI, VISIBLE "NO"
OIC
IM OUTTA YR LOOP
KTHXBYE
C (J言語)
J言語は書きやすい言語です．これだけははっきりと真実を伝えたかった．
load'printf'
OUT =: 'C:\GCJ\qual2013\c.out'
S =. 1!:1 <'C:\GCJ\qual2013\c.in'
states =. 3 : 0
0 10 #: <. 10 * > -.&a: <@".;._2] 0 :0
)
splitWord =. 0;(states'');a.e.CRLF,LF
1.1 0
1 0.3
)
input =: splitWord ;: S
T =: ".>{.input
input =: }.input
largeSqrt =: 3 : 0
'lo hi' =. 0; y + 1
while. 1<hi-lo do.
mid =. <.-:hi+lo
if. y>:*:mid do. lo=.mid else. hi=.mid end.
end.
lo
)
comb=: 4 : 0
if. x e. 0 1 do. z=.<((x!y),x)$ i.y
else. t=. |.(<.@-:)^:(i.<. 2^.x)x
z=.({.t) ([:(,.&.><@;\.)/ >:@-~[\i.@]) ({.t)+y-x
for_j. 2[\t do.
z=.([ ;@:(<"1@[ (,"1 ({.j)+])&.> ])&.> <@;\.({&.><)~ (1+({.j)-~{:"1)&.>) z
if. 2|{:j do. z=.(i.1+y-x)(,.>:)&.> <@;\.z end.
end.
end.
;z
)
palindrome =: (=|.)@":
solveL =: 3 : 0
if. y=1 do. 4 return. end.
ks =. 1,(i.4)!<:<.-:y
+/ks*>(2|y){1 1 1 1 1;2 3 3 2 2
:
if. y=1 do. 4<.>:x return. end.
res =. 0
if. (t<:x)*.palindrome t=.2+2*10x^<:y do. res =. res+1 end.
if. (1=2|y)*.(t<:x)*.palindrome t=.t+10x^<.-:y do. res =. res+1 end.
for_p. i.4<.>:d=.<:<.-:y do.
res =. res + +/x>:s=.(>:10x^<:y)+((10x^>:d+2|y)*(+/"1)10x^cs-~<:d)+10x*(+/"1)10x^cs=.p comb d
res =. res + (2|y)*+/x>:s+10x^<.-:y
res =. res + (2|y)*(2>p)*+/x>:s+2*10x^<.-:y
end.
res
)
solve2 =: 3 : 0
N =. largeSqrt y
res =. 0
for_d. >:i.#":N do.
if. d=#":N do. res =. res + N solveL d
else. res =. res + solveL d end.
end.
res
)
solve1 =: 3 : 0
'A B' =: y
-/solve2"0 B,<:A
)
replace=: 4 : 0
'p q'=. y
j=. p nosindx x
if. ''-:j do. x return. end.
d=. p-&#q
k=. (j+(0>.-d)*i.#j)+/i.#q
select. *d
case. 1 do. (0 (j+/(#q)+i.d)}1$~#x) # q k}x
case. 0 do. q k}x
case. _1 do. q k} (0 (d{."1 k)}1$~(#x)+(#j)*|d) #^:_1 x
end.
)
nosindx=: 4 : 0
s=. x I.@E. y
i=. s I. s+#x
(i.&_1 {. ]) (s,_1) {~ (i,_1) {~^:a: 0
)
solve =: 3 : 0
'' 1!:2 <OUT
for_n. >:i.T do.
ps =. 'x',~(>(<:n){input) replace ' ';'x '
('%d\n' sprintf n) 1!:2 <2
('Case #%d: %d\n' sprintf (n,solve1".ps)) 1!:3 <OUT
end.
)
solve''
20歳になりました
2013年です．0〜20まで数えて感慨深い思いに浸りましょう．
/: 2013
# 2013
{. 2 013
{: 201 3
# 2 0 1 3
p: {. 2 013
+/ 2 01 3
p: {: 201 3
2 ^ {: 01 3
2 ^~ {: 01 3
+/ }. p: 2 01 3
2 0 1 p. 3
+: +/ 2 01 3
}. 2 013
2 * {: p: 01 3
+/ p: 2 01 3
2 ^ +/ 01 3
p: +/ 2 01 3
<. o. +/ 2 01 3
p: p: {: 201 3
{. 20 13
【「『JOI 2011年春合宿 Day1 の問題『Dragon』は強実装』はウソ」はウソ】はウソ
http://tozangezan.hatenablog.com/entry/2013/03/29/004026
upper_bound や lower_bound を使いまくったり， -1, -2 を乱発したりしない Dragon の実装が求められているそうなので書きました．
#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; typedef long long Int; int H, W, N; struct dragon { int x, y; } D[100050]; bool cmpx(const dragon& a, const dragon& b) { return a.x != b.x ? a.x < b.x : a.y < b.y; } bool cmpy(const dragon& a, const dragon& b) { return a.y != b.y ? a.y < b.y : a.x < b.x; } struct event { int x, y; bool query; event(int x, int y, bool q) : x(x), y(y), query(q) { } }; bool operator < (const event& e, const event& f) { return e.y < f.y; } int solve() { int res = 0; vector<int> xr, yd; for (int i = 0; i < N; ++i) { xr.push_back(D[i].x); yd.push_back(D[i].y); } sort(xr.begin(), xr.end()); sort(yd.begin(), yd.end()); xr.erase(unique(xr.begin(), xr.end()), xr.end()); yd.erase(unique(yd.begin(), yd.end()), yd.end()); vector<event> es; sort(D, D + N, cmpx); for (int i = 0, j; i < N; i = j) { for (j = i; j < N && D[i].x == D[j].x; ++j) ; es.push_back(event(D[j - 1].x, D[j - 1].y, false)); } sort(D, D + N, cmpy); for (int i = 0, j; i < N; i = j) { for (j = i; j < N && D[i].y == D[j].y; ++j) ; es.push_back(event(D[j - 1].x, D[j - 1].y, true)); } sort(es.begin(), es.end()); set<int> xs; for (int i = 0; i < (int)es.size(); ++i) { if (es[i].query) { int rr, dd; dd = yd.end() - upper_bound(yd.begin(), yd.end(), es[i].y); set<int>::iterator it = xs.upper_bound(es[i].x); if (it != xs.end()) { rr = xr.end() - upper_bound(xr.begin(), xr.end(), *it); res = max(res, (H - es[i].y - 1) + (W - *it - 1) - rr - dd); } rr = xr.end() - upper_bound(xr.begin(), xr.end(), es[i].x + 1); res = max(res, W - (es[i].x + 1) - 1 - rr); } else { xs.insert(es[i].x); } } return res; } int main() { cin >> H >> W >> N; for (int i = 0; i < N; ++i) { cin >> D[i].y >> D[i].x; --D[i].x; --D[i].y; } set<int> xs, ys; for (int i = 0; i < N; ++i) { xs.insert(D[i].x); ys.insert(D[i].y); } Int sol = (Int)H * W - (Int)H * xs.size() - (Int)W * ys.size() + (Int)xs.size() * ys.size(); int M = 0; for (int rot = 0; rot < 4; ++rot) { for (int flip = 0; flip < 2; ++flip) { M = max(M, solve()); for (int i = 0; i < N; ++i) { D[i].y = H - D[i].y - 1; } } swap(H, W); for (int i = 0; i < N; ++i) { int x = D[i].x, y = D[i].y; D[i].x = y; D[i].y = H - x - 1; } } cout << sol + M << endl; return 0; }
例によって main は回転などをしているだけ，solve も大半は座標圧縮などの造作も無い処理です．問題の箇所がこちら．
int rr, dd; dd = yd.end() - upper_bound(yd.begin(), yd.end(), es[i].y); set<int>::iterator it = xs.upper_bound(es[i].x); if (it != xs.end()) { rr = xr.end() - upper_bound(xr.begin(), xr.end(), *it); res = max(res, (H - es[i].y - 1) + (W - *it - 1) - rr - dd); } rr = xr.end() - upper_bound(xr.begin(), xr.end(), es[i].x + 1); res = max(res, W - (es[i].x + 1) - 1 - rr);
upper_bound のみ 4 回使用，いずれも単純な呼び出しにとどまっていると思います．また +1, -1 などについては
res = max(res, (H - es[i].y - 1) + (W - *it - 1) - rr - dd);
これは逆順に走査するときなどによく見る N - i - 1 の形です．また
rr = xr.end() - upper_bound(xr.begin(), xr.end(), es[i].x + 1);
こちらはドラゴンのいる x 座標(es[i].x) の隣に M 理事長が居る場合を考えるので +1 をつけています．そして
res = max(res, W - (es[i].x + 1) - 1 - rr);
これは上ふたつの複合です．
少なくとも「人が死ぬレベル」「複雑すぎる」といった形容は必要ない程度にはシンプルにまとまったと思います．
「強実装は多実装ではありません。『手ごわい』実装なのです。」という理解は正しいと思います．「強実装」という概念には単に記述量が多いだけでなく，正しく書きづらい，複雑な記述になってしまう，デバッグ時に動作を追いづらいなどの要素が含まれているでしょう．
さて，ぼくはこの問題を解くのは 3 度目ですが，この問題はとても良い問題だと思います．そして，決して簡単な問題ではないとも思います．しかし，「強実装である」という点に関してだけはそうではないと思います．
この問題の良い点，そして同時に難しい点というのは「解法の詰め方」と「適切な実装方法の選択」であります．この問題の解法自体がそこまで難しいかといえば，少なくともJOI春合宿で出題された問題の中ではそうでもないでしょう．では実装が難しいのかといえば，それも難しいとは限らない(少なくとも今回載せた実装はそこまで難しいわけではない)のがポイントです．
「他の人のソースコードを見ても、このような1や2といった数字が多数混在しています。」とあることからも分かるように，多くの人は(そしてぼくも初めて解いたときには)複雑怪奇，とても人間のデバッグするようなものではないソースを書いてしまうようです．これはこの問題が決して簡単ではないことを示しているでしょう．
今回載せた実装を最初から書くことができれば，この問題は難しいものではありません．しかし，その実装方法を選択すること，あるいはその実装方法へ至るまで正しく解法を詰められるかということ，これはとても難しいと思います．事実，ぼくも 2 度目に解いたときに比べ，さらによい実装方法を選択することができました．
パッとでてきた解法ですぐに勝負すると大変になってしまうことこそ多いが，じっくり解法を詰め，できるだけシンプルで書きやすくてバグを埋め込みにくくて動作を追いやすい，という実装方法へ至ることでスッと解けてしまう．そんな問題がぼくはとても好きであり，その点を見事に体現しているこの Dragon という問題は解くたびに新たな発見のある，非常に楽しくて良い問題なのだと，またひとつ確信させて頂きました．
