読者です 読者をやめる 読者になる 読者になる

情報オリンピック予選 2014

情報オリンピックの予選に参加しました.(予選は誰でも参加できます)

次のような制約で解くことにしていました.

  • 1番は Wolf RPGエディター
  • 2番は TeX
  • 3番は Scratch
  • 4番は Excel
  • 5番は APL
  • 6番は Bash

結局1と4を解きました.

1番

Wolf RPGエディターで解きました.たぶん合っていると思います.

https://drive.google.com/file/d/0B0wUgziNPuKGUlZmaG5ka0ZIYUk/edit?usp=sharing

2番

TeXでようやくできました.もしかしたら処理系依存のところなどがあるかもしれません.

手元の環境はTeX, Version 3.1415926 (TeX Live 2013)です.

%\catcode`\@=11
\immediate\write16{}
\def\fstimpl#1 #2\relax{#1}
\def\fst#1{\expandafter\fstimpl#1\relax}
\def\sndimpl#1 #2\relax{#2}
\def\snd#1{\expandafter\sndimpl#1\relax}

\read-1to\NM
\def\N{\fst{\NM}}
\def\M{\snd{\NM}}

\newcount\x
\newcount\y
\newcount\z
\newcount\w
\newcount\k

\x0
{
  \loop\ifnum\x<\N
    \read-1to\tmp
    \global\expandafter\edef\csname costs\the\x \endcsname{\tmp}
    \global\expandafter\edef\csname prefs\the\x \endcsname{0}
    %\immediate\write16{costs[x] = \csname costs\the\x \endcsname}
    \advance\x1
  \repeat
}

\y0
{
  \loop\ifnum\y<\M
    \read-1to\tmp
    \k\tmp
    {
      \x0
      \loop\ifnum\x<\N
        \w\csname costs\the\x \endcsname
        %\immediate\write16{k = \the\k, x = \the\x, w = \the\w, costs[x]=\csname costs\the\x \endcsname}
        \ifnum\k<\w
        \else
          \z\csname prefs\the\x \endcsname
          \advance\z1
          \global\expandafter\edef\csname prefs\the\x \endcsname{\the\z}
          %\immediate\write16{OK! x=\the\x, prefs=\the\z}
          \x\N
        \fi
        \advance\x1
      \repeat
    }
    \advance\y1
  \repeat
}

\x0
\w0
\loop\ifnum\x<\N
  \y\csname prefs\the\x \endcsname
  \z\csname prefs\the\w \endcsname
  \y\csname prefs\the\x \endcsname
  %\immediate\write16{prefs[\the\x] = \csname prefs\the\x \endcsname}
  \ifnum\y>\z
    \w\x
  \fi
  \advance\x1
\repeat
\advance\w1
\immediate\write16{\the\w}
\bye

3番

コンテストから1週間経ち,今更感がありますが,Scratchで書きました.ご確認ください.

http://scratch.mit.edu/projects/15970373/

入力を1列でしか受け取れないのが残念ですが仕方ないですね.

4番

Excelで解きました.一部間違ってるかもしれません.

https://drive.google.com/file/d/0B0wUgziNPuKGNVJWVWRBdXhxSG8/edit?usp=sharing

追記:間違いの理由がわかりました.n=1000のときだけ落ちるような間違いでした.