Edited at

CodeIQで印象に残った問題

More than 1 year has passed since last update.


はじめに

CodeIQは初期から参加させていただきまして、手頃な問題として解いていました。青コーダーの私が手頃というくらいだから赤コーダーが満足するような刺激はないけれど、ユーザー間で形成されていたコミュニティは暖かみがあるものでした。手動採点時代は出題者からのフィードバック。自動採点時代はコードの見せあい。他のコンテストサイトと比べると交流が密で、最大の特色だったと思います。CodeIQはなくなってしまいますが、交流は形を変えて続いていくんだと思っています。

また、バッジ数1位である私は、出題はどうかと声をかけていただくことができました。他の出題者の問題を参考にしながら、見よう見まねで出題していきました。いろいろ不手際もありますが、応援を力に変えて、良い経験になりました。ありがとうございました。

さて、出題者視点は https://github.com/cielavenir/codeiq_problems/ にある解説記事や一言コメントを見ていただくとして、こちらでは解答者視点で、印象に残った問題をピックアップしていろいろ書こうと思います。

当該番号のソースを https://github.com/cielavenir/codeiq_solutions/ から探すといいんじゃないかなと思います。


鍋谷武典様


カードゲームの役を判定する (q476)

問題としては普通なんですが、主としてこのケアレスミスが原因でyhpgの採点プログラムを書くことになった。その意味ではあの採点プログラムはコンテスト駆動開発といえなくもない。


カラフルな八面体を転がそう。 (q708)

yhpgの「サイコロを転がす」を六面体から八面体に変更したバージョン。工作をしなかったため見取り図を目視して回転を表す辞書を書かないといけなかった。すごく大変だった思い出。でも工夫して書く辞書の数を減らせたのは良かったと思う。

解説:https://qiita.com/cielavenir/items/4804b76a7872e1a62263


hello, world × 3 (q766)

言語間で重複した文字を使わずにhello, worldを出力するだけなんだけど、言語の知識がものすごく要求される問題だと思う。C/C#の組み合わせはありえないですしねぇ。勉強にはなったけど疲れた。


4つの数と四則と括弧 (q820)

yieldするだけで終わった。

解説:https://qiita.com/cielavenir/items/ff58410c66684a32e634


対戦型 hello, world! (q1356)

当時はなぜかアルファベットspの列にハマっていた気がする。sphereとか。そんなわけで私のプログラム名はspiegelです。ところでhelloworldあんまり関係なくないですかこの問題。


Minority's hello, world (q1579)

1文字の重みが「その文字を使った挑戦者数の二乗」になる変則ゴルフ。結局突破口がつかめずPHPで出してしまった。

プログラム名はchevalierですが、深い意味はなく、スカイガンナーに出てくる戦闘機の名前です。


先制 hello, world (q2074)

なるべく使う文字種を少なくし、ソース中なるべく早くその文字種を全て出現させるのが基本戦略。tbpgrさんのデスマコロシアム細則に、出力中のヌルバイトは無視して正解にするっていうのがあり、これを使うか使わないかで勝率に雲泥の差が出る。

プログラム名はBaleine、これもスカイガンナーに出てくる飛行機の名前(戦闘機ではない)。

鍋谷さんの対戦問題の中では唯一のメダル獲得(銅)。

にしても、(BF生成前のRubyコードの状態では)コードよりコメントが長い。力を入れすぎた。


ボタンを押して数を作ろう (q2349)

30-__builtin_clz(N)+__builtin_popcount(N)


遠い昔、はるか彼方の銀河系の カレンダー (q2597/q2598)

与えられたカレンダー法則からツェラーの公式を生成する問題。勉強になりました。昔はプログラム無しでやったわけですから大変でしたよね…

ところで唐突にF#のコードが見つかったんですが、スキルピース用だったのかもしれません。

解説:https://qiita.com/cielavenir/items/1c27da39041b7e0a96ce


パスカルの 三角形では ありません(字余り) (q2630)

パスカルの三角形はDPで求められるけど、法則が少し違うDP。表から漸化式を読み解くまでが大変だった。


世界は歪んでいる。それでも君は歩む。 (q2751)

yhpgの「道なりの亀」と、辞書が違うだけで同じソースになってしまった。


円と線分の位置関係 (q2786)

円と直線じゃなくて円と線分になるだけでこんなにきつくなるとは。


限られた数字で作れる数の、まんなかの値 (q2907)

日本語のメソッド名を初めて使ったと思う。「当該桁数の数の個数」…「number_of_numbers_with_such_number_of_digits」…どっちもいやだ笑


共通部分は何角形? (q2944)

Spaghetti Sourceのconvex_intersectに感謝。普段RubyなのにC++なのはこの関数をコピペしたから。


ヘックス上の最長狭義単調増加列 (q2969)

ヘックスを直交座標に直そうとしているコードが見られる。きっと面倒な問題だったんでしょうorz


異世界のブラウザの判定 (q3008)

ネタが面白かったです。辞書を変えるだけで現実のブラウザの判定にも使えるのが現実味を残していて良い。


撤去作業の果てに現れる数列 (q3011)

yhpgの「多段階選抜」は私が新しい言語でyieldの勉強をする際に使わせていただいている問題ですが、その応用で解けます。しかし、素数判定が必要なので、場合によっては面倒かもしれません。Python版はミラーラビンで解いていたようです。


外周の折り目 (q3064)

yhpgの「山折り谷折り」の発展問題。考察が非常に重かった。


縦線と横線でマス目を塗る (q3098)

このころは座圧+imos法にはまっていて、yhpgの「2つの矩形に含まれるマス目の数」の系として解いた。


周期表 (q3135)

実装はそこそこあるんですが、s軌道とかp軌道とか思い出しながら楽しくやれた思い出があります。現実味のある問題は他にも使いみちがあっていいですよね。


◯はぴったり☓は無し (q3206)

yhpg「ぴったり含む長方形」の応用問題。計算量を減らすことはできそうにない。


正六角形の分割 (q3265)

yhpg「正八角形の分割」の易しいバージョン。このころからyhpgを正しい解法で解いていれば近い解法でCodeIQの問題も解ける場合が多くなった印象です。


正方形の分割 (q3283)

正六角形の分割より易しいことはなく、条件追加により考察は重くなりました。


正六角形ブロックの回転 (q3325)

yhpg「ブロックを回す」の発展問題。


カーペット (q3357)

yhpg「ギャスケット」の別バージョン。


ドット絵の丸が2つ (q3463)

yhpg「ドット直角三角形の共通部分」の別バージョン。個人的にはyhpgの方が難しく感じます。


展開図上の反対側 (q3464)

yhpg「サイコロできるかな」の別バージョン。


魔法使いの梯子(はしご) (q3476)

yhpg「マス目を歩く」の発展問題。でもまあ、DPが1段増えるだけではある。


迷路 (q3528)

yhpg「迷路」の発展問題。SciPyで瞬殺。


ぐるぐる曼荼羅 (q3544)

カーペットの発展問題なんですが、パターンが処理しづらい配置になっているため、実装もそこそこ重かったです。


tbpgr様


EmmetでHTML高速記述 (q725/q746)

普段使っていない言語でゴルフをやると、適当に勉強する以上にパラダイムを学習できそうな気がします。手続き型言語とは違った戦略が必要で楽しませて頂きました。

そういえば採点ページが消えていたので https://cdn.rawgit.com/cielavenir/codeiq_solutions/338dd8fc/tbpgr/emmet/emmet.html に復活させました。


2文字10秒で解くJava風Ruby (q768)

今のtbpgrさんからは想像もできないほどいやらしい問題だった気がします。東大英語の4Aは誤文指摘か空欄補充ですが、さくっとできればいいけどはまると永久に時間を取られる。この問題がそのパターンだった。


Hello Vagrant! (q774)


ChefでLL言語一括Hello (q790)

環境構築をコードでっていうのは当時の私からすると新しい概念で、学べてよかったです。

昔iOS Cydia向けにいろいろパッケージを作ってましたが、Chefほど大掛かりでなくともせめてHomebrew程度、コード形式で残しておけばよかったなぁと思います(まあ「iphonedevonlinux」にある古いgccをiOSにポートしていたので時代遅れを取り戻すのはほぼ不可能でしたが)。

ちなみにこの答案を流用して新卒用課題に取り組みました。感謝します。


デスマコロシアム (第1回: q791)

駆け引きをするには多言語でゴルフをしなければならず、ある意味マラソンよりもきつい問題群。

言語別最短で強豪バッジを狙ったが結果的に豪傑に上り詰めたことも多数あった。


他人のサイトにモンキーパッチ (q826)

cTouchの作者として絶対に外せない問題でした。でも現職はフロントエンドではありません(かといってcTouchの守備範囲はフロントエンドからは少し外れますし微妙なところ、じゃあなぜ作ったのだしorz)


Ruby警官から警告を受けろ (q883/q884)

100文字にRubocopの警告を詰め込む問題。私の圧勝でした。変則ゴルフの一種としては、あちらを立てればこちらが立たずという状況が余り発生しなかったのは幸いでした。


LTSV (q1024/q1025)

仕様書を読まなくてもパーサに突っ込むだけで連想配列が取れるのって利点ですよね。


呪いの右仮面 (q1026)

今までに解答したことがない言語から選択する縛りが私には強力に響いた問題。Mozartを選択しました(こんな言語、ideoneマニアでもなければ聞いたことないですよね)。


独創的にHubotを動かす (q1113)

Ruboty Advent Calendar 2014参加、そして拙作の「RubyでHubot!?」につながった問題。

ちなみに「独創」のネタはCodeIQ2周年をIntercalでお祝いしたコードです。


GitHub素数Userは何人 (q1197)

拙作oauth2.cgiを活用できた。


コードを汚く逆リファクタリング (q1249)

iseq gemを使わずともfiddleからrb_iseq_loadを呼び出せることがわかったのは収穫だった。(でもまあRubyのiseqはPythonのpycと違ってバージョン間互換が低いので使い所が限定されるんですが)


Emoji-サザンイマジネーション (q1323)

Emoji(のシンボル)を出力するのにソース中に半角コロン禁止で、bz2.b64形式を展開するBashを送信したらしいです。


不適切な FizzBuzz の世界(q1357)

WhiteSpace/Ruby/Perl/C/Pike/C#/F#のPolyglotを提出しました。しかし初版は、オブジェクト指向的FizzBuzz(q374)をPHPからRubyに移植して、しかも命名規則等をC++のものに書き換えた(クラス名に至ってはCOMでよく使うI/Cプレフィックス)プログラムでした。今となってはどちらがより不適切だったのかわかりません。


新カテ Opal (q1604)

拙作「RubyでHubot!?」と番号が隣接している(q1605)ことを思い出したのですが、拙作のはOpal祭として作ったのかもしれません。覚えていませんが。

(ここで終わり、ということはやはりtbpgrさんは手動採点問題のほうが明らかに向いていたんだなぁ…)


kawazoe様


スロット・マシン (q1704)

前半の問題では一番考察が大変だった気がします。


ステップ・アップ・サム (q2029)

AOJに似た問題があったために火が付き、徹底的に多言語で挑んだ問題。


ルート・パワー (q1563)

本家より少しだけ計算量を減らせて嬉しかった思い出があります。

解説:https://qiita.com/cielavenir/items/c8366a0289891342ed5c


マイナー・ゲーム (q2837)

これも考察が重かった。ソース中に無限和の極限を取っている箇所があるようです。


アフター・ドット (q2831)

整数除算は結合法則が成り立たないとかコメントにあるんですが大嘘であることが先日発覚したので、実はもう少し速くできたのかもしれません。しかし定数倍が重ければlognなんてひっくり返りそうな気もするので微妙なところです。


デジタル・ルート (q2975)

途中計算を埋め込む技を使ってみた。


増井敏克様


最短経路の計算! (q608)


運命の出会いは何通り? (q711)

「20言語でnext_permutationを実装」という企画を立ててしまい本当に死にかけた問題。力はついたけど。


畳を敷きつめろ! (q609)

ICPC2009夏合宿2日目の他の人のコードを参考にした。そうでもなければ諦めていたかもしれない。


「白」で埋めつくせ! (q770)

当時「赤一色にせよ」とかの変則ライツアウトアプリ があったのでそれのライブラリを作っていた。そのライブラリに投げた。


最速の連絡網 (q848)

シーズン1最難問題。手計算で解くことにしたが、あちらを立てればこちらが立たずという状況が続き大変でした。方針を変えた結果1段落とすことが出来た時の喜びはひとしおでした。


最速のポスティング(q2484)

交差せずに一筆書き(q918)と完全に同じ問題を出題してしまって大丈夫だったのでしょうか。心配です。


予約で満席の指定席 (q2510)

組合せ爆発をうまく防ぐのが難しかったです。


壊れたピンチハンガー (q2608)

手動採点問題だったためOctave上級のスキルピース取得に使われたようです。


セルの結合で一筆書き (q2713)


照明を消さずに端から端まで移動 (q3308)


カエル跳びゲームを一般化して! (q3516)

この3問はawkで突破できるって今週のアルゴリズムらしからぬという印象でした。3516は考察が必要なのが救い。


まわり将棋に挑戦! (q2900)

繰り返し二乗法に持ち込むための乗算を考えるのが面白かった。

解説:https://qiita.com/cielavenir/items/c5ac9f79a3f2719286fe


一列に並べたマトリョーシカ (q2950)

どうしてもわからなくて、数列で検索したらGoogle Booksの洋書のプレビューがひっかかった思い出があります。ちなみにOEISや日本語の資料はありませんでした。


十文字に反転して色を揃えて! (q2972)

ライツアウトの0解(quiet pattern)について学ぶことができました。

解説:https://qiita.com/cielavenir/items/2fa1f1149132de579a46


魔方陣で最大値? (q3106)

全部計算するのはきついので一部埋め込み辞書最適化にリソースを費やした問題。web archiveに感謝。


現地で使いやすい両替 (q3149)

計算量O(NT 2^T) (T=10)で通した問題。#pragma GCC optimize("O3")必須なので想定解法でないと思う。

あと、ideoneの実行環境がPyramidからCubeに変更されたのが大きい。


他人と同じ商品は選ばない (q3165)

シーズン2高難易度問題の一つで、解ける問題と(実はサンプル入出力2を含め)解けない問題がある。

解けないってのは正解より少し多い値が出るって意味です。理由の一部は書籍を見ればわかります。

紙こそ使ってないけどAAでのシミュレーションは丁寧にやった。


幅優先の二分木を深さ優先探索 (q3197)

yield fromを使いたいと思ったけど、RubyはKernel.procをちゃんと引き回せばyield移譲自体必要ないことに気づいた。Pythonはブロック引き回しができないので、こういう設計の違いってあるんだなぁと。

あと、私の実装みたく、ノードを全部書き下してから当該インデックスのノードを出力するようにしたほうが(この問題に限っては)きれいな気がするんですがどうでしょうか。


上下反転した数字表示器 (q3225)

コメントに「66... 99… きみは妖精の商人のフレンズ(以下略)」とありますが、こちらの元ネタの元ネタは 遊戯王1st「ライバル激突 最大ピンチ」 のワンシーンです。窮地を脱するために妖精の商人が66を99にひっくり返すのです。細かいことはぐぐって出てきた記事でも。しかし…当時の放送から 20年近く経ってる のにこの辺のエピソードだけ焼き付いてるってどういうこと笑

「フレンズ」の方は言及不要ね。


素数の日付を含む最長期間 (q3267)

50年分の素数をリストアップするのは時間制限的に厳しそうなので、素数一覧を圧縮して埋め込んだ。


たくさん組み合わせて作る合成抵抗 (q3424)

デバッグが大変だった思い出。なんかDSLを生成してevalとかやってる。


結城先生


グループを作ろう! (q171)

連想配列なunion_findを作るきっかけになった。


チョコの量を減らせ! (q197)

MacPortsやHomebrewで入る(g)factorはGMPとリンクされているのでラッキーだった問題。最初にDebian使ってたらGMPの有効無効なんて気づかなかったと思う。あと、後ほどだけど、ミラーラビンを自作するきっかけになった。


最高のカレーを作れ! (q210)

graphvizの出力を目視で使った。よく罠に落ちなかったなぁとか。


リンゴ列をもっと短く! (q279)

codeevalにハフマン木作成問題があったのでその答案を流用。事前にVerifyされていると安心ですね。


“ピッグデータ”に負けないで! (q303)

openmpの学習に役立ちました。まる。


星間飛行ルートを作ろう! (q411)

探索をWeb APIでやるのが新鮮でした。ダミーを目視で確認したりとか。


交差点をすばやく数えよう! (q432)

マージソート解法を普通に出せば良いものをなぜOpenMP版で頑張ろうとしたのか笑


王女様の宝石パターンを見つけよう! (q684)

next_permutationを実装したことがあるかどうかで明暗が分かれそう。


クリプタン帝国の暗号文を解読しよう! (q782)

問2はSHA1ライブラリの 実装に依存 する点でまれに見る悪問だったと思います。私が唯一落とした結城先生の問題でもあります。


チケットゴブル社の旅行プランを作れ! (q863)

出力の仕方が時刻順ではなく名前順…。フルフィードバックのコンテストであってもサンプルの量によっては死んだりするかも。


マヨイドーロ問題 (q2549)

行列の掛け算より多倍長のほうが実装めんどくないですか。

多倍長に関する解説:https://qiita.com/cielavenir/items/7d60f034765aa7c6cf8c


stakemura様


キュラゲの最小包含円を求めよう (q296)

解説にて最小包含円の近似解を知ることができたのは収穫でした。


勝率をモンテカルロ法で求めよう(2) (q514)

normal_distribution<double>をただ使えるのではなく、ボックス=ミュラー法により正規乱数の原理を知ることができました。


条件分岐を減らして最速を目指せ! (q1238)

この絶対値の求め方は新鮮でした。


賭け事はお好き? (q2796)

解析的に解いてしまいましたが、その過程で極限を取る操作が2回あり、特に1回目は公式が使えないため式をこねくり回す必要がありましたが久々に数学やってるぜーって感じで面白く感じました。


IPアドレスから国内のアクセスか否か判定しよう (q2998)

完全なリストを格納するにはlzma.b85形式で格納せねばならず、Ruby版はデコーダを書くのがそこそこ大変でした。


一流を見分けられるのは誰? (q3538)

data leagueで得た知識(DCG)が役に立ちました。


ワイルドカード文字列を推定しよう (q3554)

LCSを取るよりワイルドカードを生成するほうが大変でした。


柳井政和様


マラソンマッチ:効率的に敵を撃滅せよ (q378)

簡単な解法から進化できなかった。マラソンはきつい(?)


シフト演算子を使った掛け算と割り算 (q426)

掛け算は累乗の変形として、割り算はなかなか難しかったです。


ダンジョン問題群 (1問目: q558-561)

JavaScriptについてすごく詳しくなれた気がします。あちらを立てればこちらが立たずという状況が続いた問題もありましたが、最終的に全問全レベル正解できたことは喜びです。


Ozy様


スパゲッティコードを召し上がれ♪ (q568)

第1段階が問題文を読むのではなくコードを解きほぐすようになっていて面白かった。まあ結果自体は並でしたが。


A+B+Cはいくつ? (q626)

謎解きには示唆が必要ですが、はたしてあれは示唆といえるものだったのか厳しいところ。


大きなナップサック (q629)

バックトラックがうまく行かず、結局マシンを文字通り7日間走らせ続けて解答を出した思い出が残っています。


チョコレートバー様


6枚のカードの並べ方を求めて! (q847)

spliceとか使って順列作るやつをmain再帰でやった。文字列縛りが面白かった。


増井雄一郎様


メロスを形態素解析せよ (q506)

mecabの使い方を学習できた。

解説:https://qiita.com/cielavenir/items/3a726fcb1cf6049e92b8


マシュー様


美女の暗号を2つの素数に分解せよ。 (q1250)

まともに解答できるわけないので、 http://en.wikipedia.org/wiki/RSA_numbers をスクレイピングするコードを提出したら出題者からびっくりされた。


実力判定


極めよプログラミング道!【実力判定:Aランク】 (q3117)

1+2, 2+3, 3+4, ..., 999999+1000000のうち与数の倍数の個数を数える。O(M)かけるとTLEになるのでO(1)で解答しなければならない。実装量が小さいのに歯ごたえのある問題だった。一方Sランクは左上から右下までグリッドを最小コストで移動するっていうよくあるやつで拍子抜けだった。


極めよプログラミング道!【実力判定:Sランク】その2 (q3333)

AOJ DPL_3_A「Largest Square」にて既出なんだけど、N<=3000だとRubyでは厳しいのでは?ちなみにAランクはフィボナッチを行列累乗で得るやつでした。


【実力判定:Sランク】欲張り団子 (BランクのURLより推定でq3205)

全探索でいいと思うんだけど、探索範囲を減らすのに工夫が必要だった。

問題:http://ozy4dm.hateblo.jp/entry/2018/05/02/204239


その他


Rubyの基礎問題1 (q128) (答案非公開)

CodeIQ初挑戦の問題。カレンダー出力。ツェラーの公式を実践で活用した最初の問題。パンカクさん、MeetUpありがとうございました。ちなみにC言語に移植されて拙作のツールキットの1アプレットになっています。


Gopher君のかるた大会 (q181)

Goの型システムは死ぬほど理解に苦しむ、と思った。一発でGoアレルギーになった(≒以降多言語解答でしか使わない)。せめてInterfaceがオーバーロードっぽく使えれば。。


おいしい好みの順番 (q320) (答案非公開)

トポロジカルソートをできるようにする、すなわちDAGにするのに必要な辺除去を最小化する問題。

解説:https://qiita.com/cielavenir/items/96a4baf104f3311eeccb


アイテム類似度のレコメンド (q190) (答案非公開)

データ分析の基礎(コサイン類似度)と尺取法(ソート済みの配列に対しO(n)で共通部分を得るあれ)の複合。尺取法を思いつくのが大変だった。


つぶやいたURLの収集 (q344)

どこぞに転がっていたPythonのtwitterライブラリだが、使う練習ができてよかった。


UnityでEditor拡張 (q471) (答案非公開)

言語はC#だしとたかをくくって挑んだら泣きを見た問題。なお容量不足に伴いUnityはこのマシンから消えました。


FLOWer言語でフィボナッチ数列 (q796)

言語仕様がわからんかったので理解のために処理系を作った。なお公式ページのドキュメントはまだ準備中らしい。

問題の解答は https://qiita.com/cielavenir/items/7bc8992555cc9dec1e8f です。


ガールフレンドをコンプリートせよ (q801)

1日に9個バッジが得られるということで取り組んだ。内容は単に文字出力すれば良い。

しかし、各指定範囲のアルファベットで始まる 任意の 言語で1言語ずつ通せばよいのだが、私は各指定範囲のアルファベットで始まる言語から 指定の1つ を当てなければならないと勘違いし、9言語通せば良いところを50言語で通してしまった。つらいだけです。

メジャー言語が正解なわけないよねとか…なわけあるかorz


WebRTC問題 (q849) (答案非公開)

WebRTCのソースを穴埋めしながらわかりやすく学ぶことができました。


電卓を起動するだけの簡単なお仕事です (q947/q1126/q1172) (答案非公開)

リバースエンジニアリングの経験がある私でしたが、ソフトの脆弱性をどう攻撃するのかまでは具体的にはわかっていませんでした。実戦形式で学ぶことができました。

なお、今はコメントを見ても意味がわからないようですorz


Adminパスワードを破れ! (q1005) (答案非公開)

SQLインジェクションにinner joinを使う例を今まで知らなかったので勉強になりました。でも実戦では使えずじまいだろうなー


電脳体キュラゲタムを討伐せよ (q2574)

実は典型ということでしたが、高速なセールスマン問題解法を書いたことがなかったため勉強になりました。

解説:https://qiita.com/cielavenir/items/33aaf548b14bcae386a2


最後に

素晴らしいサービスを運営してくださりありがとうございました。CodeIQよ永遠に!