Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。

中学入試から：単位のある計算」の解説・解題

CodeIQ に「中学入試から：単位のある計算」という問題
https://codeiq.jp/ace/nabetani_takenori/q1058
を出した。

中学入試算数問題第二弾。

挑戦の募集はすでに締めきっている。
というわけで、解説・解題。

で。
まずは問題

問題

■問題の概要
中学入試の問題に、以下の様な問題が出ることがあります。

以下の式の□にあてはまる数を求めなさい。
　3m20cm-3m10cm-□mm=5mm

この問題を

以下の式の□にあてはまる数を求めなさい。
　【　A　】

と考え、A を入力文字列として与えます。
問題の答えを計算するプログラムを書いて下さい。

■具体的な課題
下記リンクの zip 内に data.utf8.txt および data.sjis.txt というファイルがあります。
これらのファイルの各行は
　「データID、空欄Aの内容(1)、空欄Aの内容(2)」
を TAB区切りでならべたものです。
ほとんどのデータは「空欄Aの内容(1)」と「空欄Aの内容(2)」の答えが同じになっています。
「空欄Aの内容(1)」と「空欄Aの内容(2)」の答えが異なるデータが数件あります。それらのデータの ID を答えて下さい。

data.utf8.txt と data.sjis.txt は、文字コードが異なるだけで内容はまったく同じです。
お好きな方をお使い下さい。

■補足
・データIDがTで始まるデータは、すべて (1) と (2) の答えが同じになっています。
テストにお使い下さい。
・(1) と (2) で答えが異なるデータの ID は全て数字になっています。間違い数は5件より多く、20件より少なくなっています。
・不正な入力（「4cm=□□=□宇宙ノット」 など）に対処する必要はありません。
・長さ・重さ・時間 しかありません。また、加算と減算しかありません。
・□には必ず負ではない整数が入ります。
■資料

http://nabetani.sakura.ne.jp/codeiq/q1058.zip
上記リンク先の zip ファイルの中には、以下のファイル含まれています

・ data.utf8.txt
　→ 調査対象およびテストデータです。文字コードは UTF-8 になっています。

・ data.sjis.txt
　→ 調査対象およびテストデータです。文字コードは Shift_JIS になっています。

■解答形式
「【解答】」の行に続いて解答をお書き下さい。
「【感想・工夫した点など】」の行に続いて、感想、引っかかった点、工夫した点、問題が曖昧だと感じた場合はそこをどう解釈したか、などをお書き下さい。
「【言語と処理系】」の行に続いて、言語名、処理系のバージョン、コマンドラインオプションなどをお書き下さい。
「【ソースコード】」の行に続いて、ソースコードをお書き下さい。ソースコードが複数になるようでしたら、その旨がわかるようにお願いします。

こんな感じ。

続きを読む

「中学入試から：数列の和」の解答リンク集

というわけで、解答リンク集。

「中学入試から：数列の和」の解説・解題

CodeIQ に「中学入試から：数列の和」という問題
https://codeiq.jp/ace/nabetani_takenori/q1012
を出した。

挑戦の募集はすでに締めきっている。
というわけで、解説・解題。

で。
まずは問題

問題

■問題の概要
中学入試の問題に、以下の様な問題がよく出ます。

あるきまりにしたがって、下のように数をならべました。
1,2,100,1,2,101,1,2,102,1,2,103,1,2,104,1,2,105, ...
この数列の100番目から順に110番目まで加えると、その和はいくらになりますか？

100番目から110番目を足すと
1+2+133+1+2+134+1+2+135+1+2
なので
414
が答えとなります。


この問題を

あるきまりにしたがって、下のように数をならべました。
【　A　】
この数列の【　B　】番目から順に【　C　】番目まで加えると、その和はいくらになりますか？

と考え、A, B, C を入力文字列として与えます。
問題の答えを計算するプログラムを書いて下さい。

■具体的な課題
下記リンクの zip 内に data.txt というファイルがあります。
このファイルには
　「データID、空欄Aの内容、空欄Bの内容、空欄Cの内容、期待する答え」
が、空白区切りで1000件余り入っていますが「期待する答え」が間違っているデータが数件(10件前後)含まれています。
間違っているデータのIDを答えて下さい。

■補足
・データIDがTで始まるデータには、間違っているものは含まれていません。テストにお使い下さい。
・間違っているデータの ID は全て数字になっています。間違い数は5件より多く、20件より少なくなっています。
・数列は、小学生の知識でルールが推測できるような数列です。カタラン数だったりはしません。
・数列は、小学生の知識で和の計算ができるような数列です。フィボナッチ数だったりはしません。
・空欄 B, C の値については、中学入試でそんな大きな数にはしないだろ、と言いたくなるようなデータがありますが、答えは 2の63乗を超えないようになっています。
・数列が「1, 2, 3, 4, ... 」で、2番目から5番目なら ( 2+3+4+5 ) を計算して下さい。つまり、数列の先頭は1番目(0番目ではない)で、5番目まで足します(両端含む)。
・仕様が曖昧で、厳密に考えると答えが一意に定まりませんが、そのあたりも中学入試と同じです。
・不正な入力（空欄Bの値よりも空欄Cの値が小さいなど）に対処する必要はありません。


■資料
http://nabetani.sakura.ne.jp/codeiq/q1012.zip
上記リンク先の zip ファイルの中には、以下のファイル含まれています

・ data.txt
　→ このファイルに含まれるデータについて調査します。

こんな感じ。

続きを読む

本当の難易度と、パッと見の難易度

今 CodeIQ に出している
「中学入試から：数列の和」 https://codeiq.jp/ace/nabetani_takenori/q1012
と、前回の「長くなるように、増え続けるように」が対照的かもしれないと思った。

問題 一見 実は
中学入試から：数列の和 難しそう 簡単
長くなるように、増え続けるように 簡単そう やや難

私がそう思ってるってだけで、本当にそうなのかどうかは大いに疑問。

それと。
「やや難」と書いたけど、結城さんの問題（すべて星ひとつ）よりずっと簡単だと思う。

というわけで、挑戦者募集中。
簡単だよ？

中学入試から：数列の和

CodeIQ に「中学入試から：数列の和」という問題
https://codeiq.jp/ace/nabetani_takenori/q1012
を出した。

問題の内容としては（出てくる数値が巨大であることを除いて）中学入試算数で出る問題ほぼそのまま。
ある意味小学生レベルだけど、プログラムを書くとなるとちょっと違ってくる部分もあったり。

挑戦お待ちしています。

「長くなるように、増え続けるように」の 実装例

CodeIQ に出した「長くなるように、増え続けるように」の 実装例を公開してくださっている方がいらっしゃるので、リンク集。

お名前(敬称略) 言語 リンク
kuuso C# https://gist.github.com/kuuso/116565fc623bfd53e326
mikecat C+perl https://gist.github.com/mikecat/381b3b74c046b2344a91
haruya12 C http://d.hatena.ne.jp/haruya12/20140716/1405502382
cielavenir C++ https://github.com/cielavenir/(略)/tyama_codeiq957_mod.cpp

意外と ruby とか python がいない。

問題は
http://nabetani.hatenablog.com/entry/codeiq_incseq_q957
から辿るといいと思う。

「長くなるように、増え続けるように」の 解説・解題

CodeIQ に「長くなるように、増え続けるように」という問題
https://codeiq.jp/ace/nabetani_takenori/q957
を出した。

挑戦の募集はすでに締めきっている。
というわけで、解説・解題。

で。
まずは問題

問題

■ 問題の概要

23342020662 のように、先頭が 1〜9 のいずれかで、 残りは 0〜9 が並んだ文字列があります。
この文字列に区切りを入れ、 値がどんどん増えていく数列 (狭義単調増加列)にすることを考えます。
上記の例の場合、たとえば
「2, 33, 420, 20662」 、 「2, 3, 3420, 20662」 、あるいは 「2334, 2020662」
のように区切ると 値がどんどん増えていく数列 にすることができます。
このように、 値がどんどん増えていく数列 になるように区切る方法はたくさんあることが多いんですが、このなかで要素数が最も多いものを探します。
この例の場合、 「2, 33, 420, 20662」 や 「2, 3, 3420, 20662」 などが、要素数 4 で最大となります。
さて。
入力文字列から、出来る限り要素数の多い 値がどんどん増えていく数列 を作ると、その要素数がいくつになるのかを計算するプログラムを書いて下さい。

■詳細な仕様

入力文字列は

  • 先頭は 1 〜 9 のいずれかの文字。
  • 先頭以外は 0 〜 9 のいずれかの文字。

という形式になっています。
つくるべき 値がどんどん増えていく数列 は、

  • どの要素も、前の要素よりも大きい値である。
  • どの要素も、先頭の文字が「0」であってはいけない。
  • 入力文字列の順序どおりに過不足なく数字が現れること。順序を変えたり余らせたりしてはいけない。

というルールを守らなくてはいけません。

■出力

出力は、最長の 値がどんどん増えていく数列 の要素数を 10進数で表記したものです。
例えば、入力が 23342020662 の場合、数列の項数を最大にするような区切り方は、例えば
「2, 33, 420, 20662」
なので、要素数の 4 を出力します。

■サンプルデータ

# 入力データ 出力の期待値 要素数が最大になる区切り方の例
0 23342020662 4 2, 3, 3420, 20662
1 23342121662 5 2, 3, 34, 212, 1662
2 2334200200662 5 2, 3, 34, 200, 200662
3 1 1 1
4 123 3 1, 2, 3
5 321 2 3, 21
6 11 1 11
7 111 2 1, 11
8 1111 2 1, 111
9 223043 3 22, 30, 43
10 33616382 4 33, 61, 63, 82
11 43727677 4 43, 72, 76, 77
12 123456789 9 1, 2, 3, 4, 5, 6, 7, 8, 9
13 987654321 3 9, 87, 654321
14 9876543210 4 9, 87, 654, 3210
15 1023456789 5 10, 23, 45, 67, 89
16 2000010000 1 2000010000
17 1000020000 2 10000, 20000
18 9080706050 2 9080, 706050
19 1222222221 4 1, 2, 222, 22221
20 1222222223 5 1, 2, 22, 222, 223
21 5463728191 5 54, 63, 72, 81, 91
22 223138576279 6 22, 31, 38, 57, 62, 79
23 9119291321331341 6 9, 119, 291, 321, 331, 341
24 123456789101112131415 15 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
25 103456789101112131415 7 10, 34, 56, 78, 910, 11121, 31415
26 100000000000000000000123456789123456789123456789 2 10000000000000000000012, 3456789123456789123456789

■ 課題
data.txt というファイルがあります。
このファイルの各行には空白区切りで

データ番号 入力データ 出力の期待値

が書かれています。
出力の期待値が間違っているデータが数件(10件以下)含まれています。
出力の期待値が間違っているデータのデータ番号を、昇順にコンマ区切りで並べたものを答えて下さい。

■補足

  • 不正な入力に対処する必要はありません。
  • 区切られた後の値が 64bit整数の最大値を超えることもあるかもしれません。オーバーフローにご注意下さい。
  • 要素数が 1 でも 値がどんどん増えていく数列 に該当します。

こんな感じ。

続きを読む