AtCoder Beginner Contest 140

初めに

ABC140が終わりました。自分は残念ながらABCの3完でレートは下がりました。
（といっても、元が低いので、そこまで低くはなっていないですが。
コンテスト終了して8分ほどあとにDをACしました。時間内に出せていたらと思うと悔しいです。
せっかく時間オーバーとはいえ4完したので、解説記事を書きました。

注意

今回、コンテストに出るにあたって、言語はbrainf*ckを使用しています。
言語仕様などの細かい説明は今回行いません。

A - Password

1からNまでの3桁のパスワードが何通りあるかという問題です。順当にn*n*n をすればいいです。ただし、最大で9*9*9 = 729 となり、メモリの最大値(255)を超えるので、工夫が必要です。今回は、自作のマルチバイト変数を使用しました。(詳細は省きます)

以下bfのコードです。（クリックで展開）

>>
>++++++++++>
>++++++++++>
>++++++++++>
>++++++++++>
>++++++++++>
>>>
>>+
[-<,----- -----[ >++++[-<----->]<-- 
  [>++++[-<---->]<<[->>+<<]>>[-<<++++++++++>>]<[-<+>]>+<]
  +>[-<->]< [- /* */ > ]>+<
]>]<
<
[->+>+<<]
>>
[-<[-<+<+>>]<[->+<]>>]
<<<[->>>+<<<]>>>
[-<[-<+ <<<<{[[-<+>[[>>]>]]<[->+<]<]<}>>>>  >]<[->+<]>>]
<<<<<<
<+>[<<]>
>[<+>>[<<-<[<<]<]>]
>[->>]
>>>[<+>>>]
++++++++++[-<+++++>]<---
<<->>
[[+<<]>>[>>]<+<--]
<<[<<]>>[.>>]
>+[-<<<[<<]>>[->>]>]

B - Buffet

B問題はB問題にしては難しかったように感じます。
入力が3つの配列になってますが、Nが高々100で、A,B,Cも高々50なので結構楽です。
ただし、答えは255を超えうるのでここはマルチバイト変数の出番です。

具体的には、3つの配列をメモリに展開して、A配列を前から順番に見て行って、そのインデックスに該当する番目のBの配列の要素をsumに加算、直前のインデックスと比較して、1大きいならインデックスに該当C配列の要素をsumに加算します。これを、Aの配列の末端まで繰り返せば正解できます。ただし、Cは配列長が短いことを考慮しないといけません。直前のインデックスの初期値は-1相当の225にしました。また、簡単のためにCの要素の足し算を先に行っています。
配列のi番目の要素の取得方法の説明は省略します。

以下bfのコードです。（クリックで展開）

,[,----------]
>>
>++++++++++>
>++++++++++>
>++++++++++>
>++++++++++>
>++++++++++>
>>>
>>>
>>+
[-<,----- -----[ >++++[-<----->]<-- 
  [>++++[-<---->]<<[->>+<<]>>[-<<++++++++++>>]<[-<+>]>+<]
  +>[-<->]< [- /* */ > ]>+<
]>]<
>>>>
>>+
[-<,----- -----[ >++++[-<----->]<-- 
  [>++++[-<---->]<<[->>+<<]>>[-<<++++++++++>>]<[-<+>]>+<]
  +>[-<->]< [- /* */ > ]>+<
]>]<
>>>>
>>+
[-<,----- -----[ >++++[-<----->]<-- 
  [>++++[-<---->]<<[->>+<<]>>[-<<++++++++++>>]<[-<+>]>+<]
  +>[-<->]< [- /* */ > ]>+<
]>]<
<[<]<<<<[<]<<<<[<]
<<->>
>
[
  
  -[
    [>]>>>[>]>
    [-<+>]>[>]
    >>> [>]>
    [-<+>]
    <[<]<<<[<]<[<]<<<[<]
    <+<->>>-
  ]
  <<+<
  [[-]>>-<<]+>>+
  [
    >>[>]>>>>[>]>[>]>>>[>]<
    [
      [<]<<<[<]<<[<]<<<[<]<[<]<<<
      [[-<+>[[>>]>]]<[->+<]<]< 
      >>>>[>]>[>]>>>[>]>[>]>>>[>]<
      -
    ]+
    [<]<<<[<]<[<]<<<[<]<[-]
  ]
  >>
  [>]>>>[>]>
  
  [
    -
    <<[<]<<<[<]
    <<[<]<<<
    [[-<+>[[>>]>]]<[->+<]<]< 
    >>>>[>]>>[>]>>>[>]
    >
  ]
  +
  [>]>>>[>]
  <[[->+<]<]
  <<<[<]
  
  <[[->+<]<]
  <<<[<]>
  
]
<<<
[<]<<<
<+>[<<]>
>[<+>>[<<-<[<<]<]>]
>[->>]
>>>[<+>>>]
++++++++++[-<+++++>]<---
<<->>
[[+<<]>>[>>]<+<--]
<<[<<]>>[.>>]
>+[-<<<[<<]>>[->>]>]

C - Maximal Value

C問題は、ぱっと見難しそうですが、Nも高々100ですし、入力を前から処理していけばいいので、比較的楽です。
答え自体は、B0 + Σ_0..n-2 Min( Bi , Bi+1) + Bn-1で求まります。~~(数式が見にくくてすみません。)~~ Bはもちろん、255以上を取りうるので、マルチバイト変数を用いて計算します。また、Min( a , b )を求めるのはめんどくさいので、

a -= b;
if(a > 0) a = 0;
a += b;

という計算方法で実装しています。この実装はもちろん遅いのですが、Nが高々100なので時間は十分に間に合います。数列の末端判断は、数列が読み込めたかどうかで実現していますが、正直、Nをカウントした方が楽だったと思います。

以下bfのコードです。（クリックで展開）

>>>>
++++++++++
-[[>]+[<]>-]+[>]<
>>> ,[,----------]
>
+>+>+>+>+>+>+>+> //桁数
>+[-<
  ,+[-----------[----------------------
    [--------------<-[+<-]>[[-<+>]>]+<]
  ]]>
]
<<-[+<-]+>[->]
<
[
  [<]<<[<]<[->+<]
  >[>]>>[>]>+<<
  -[ [<]<<[<]>+[>]>>[>]>+<<- ]<
]
>>>[[-<<+>>]>]<<<[<]>
<<< 
[ 
  [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[ 
    <+>[->+<]>----------< 
  ]]]]]]]]]]]<
]
>>[[-<<+>>]>]>[>]<
>
>>>
+>+>+>+>+>+>+>+> //桁数
>+[-<
  ,+[-----------[----------------------
    [--------------<-[+<-]>[[-<+>]>]+<]
  ]]>
]
<<-[++<-[+<-]]+>[->]
<
[-[+[>]>]+<] <[[<]<]>>[>]>
[
  [-]
  <<-
  [
    [w<]<[->+<]
    >+++++++++[>]>>[>]>+<<
    -[ [<]<<[<]>-[>]>>[>]>+<<- ]<
  ]
  >>>[[-<<+>>]>]<<<[<]>
  <<< +
  [ 
    [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[ 
      <+>[->+<]>----------< 
    ]]]]]]]]]]]<
  ]
  >>[-[+<]]
  >[[-<<+>>]>] 
  <<<[<]>
  -[[-]<->]<+
  [
    [-]
    >>[[-]+>]<[<]---------<
  ]
  >++++++++++[>]>>>[>]<
  
  [
    [<]<<[<]<[->+<]
    >[>]>>[>]>+<<
    -[ [<]<<[<]>+[>]>>[>]>+<<- ]<
  ]
  >>>[[-<<+>>]>]<<<[<]>
  <<<
  [ 
    [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[ 
      <+>[->+<]>----------< 
    ]]]]]]]]]]]<
  ]
  >>[[-<<+>>]>]> 
  <<<<
  [<]
  <<[>>>[-]<<]>>>[>]<
  [
    [<]<<[<]<[->+<]
    >[>]>>[>]>+<<
    -[ [<]<<[<]>+[>]>>[>]>+<<- ]<
  ]
  >>>[[-]<<+>>>]<<<[<]>
  <<<
  [ 
    [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[ 
      <+>[->+<]>----------< 
    ]]]]]]]]]]]<
  ]
  >>[[-<<+>>]>]> 
  [>]>>>[>]<
  
  [
    [<]<<[<]<[->+<]
    >[>]>>[>]>+<<
    -[ [<]<<[<]>+[>]>>[>]>+<<- ]<
  ]
  >>>[[-]<<+>>>]<<<[[-]<]>
  <<< 
  [ 
    [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[ 
      <+>[->+<]>----------< 
    ]]]]]]]]]]]<
  ]
  >>[[-<<+>>]>]> 
  
  +>+>+>+>+>+>+>+> //桁数
  >+[-<
    ,+[-----------[----------------------
      [--------------<-[+<-]>[[-<+>]>]+<]
    ]]>
  ]
  <<-[++<-[+<-]]+>[->]
  <
  [-[+[>]>]+<] <[[<]<]>>[>]>
]
<<[<]<<<
[
  [<]<<[<]<[->+<]
  >[>]>>[>]>+<<
  -[ [<]<<[<]>+[>]>>[>]>+<<- ]<
]
>>>[[-<<+>>]>]<<<[<]>
<<<
[ 
  [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[ 
    <+>[->+<]>----------< 
  ]]]]]]]]]]]<
]
>>[[-<<+>>]>]>[>]<
[<]<<<
+[<]>[-[+[>]]<+>>] ++++++[-<-------->]<+<--> [[<]>[+>]<]<[<]>[.>]

D - Face Produces Unhappiness

D問題はぱっと見難しそうに見えますが、1回行うごとに幸福な人が最大2人増えます。
ただし、幸福な人は最大でもN-1人しかそんざいできません。また、1回の試行で幸福な人が2人増やせない場合もありますが、その時は、N-1が答えになるので、 現在幸福な人 + 2*KとN-1の最小値を取ればいいです。現在幸福な人は、前後が同じ向きである組み合わせの数なので、入力を前から処理していけば問題なく行えます。

以下bfのコードです。（クリックで展開）

>>
>+> >+> >+> >+> >+> >+> >+> //桁数分移動(桁識別用の1を加算)
>+[-<,----------[----------------------[---------------[<<]>>[[-<<+>>]>>]<+<]]>]<<
[<[-<<]<]>>[-<+>>>]<<<[-[-<+>]>++++++++++<<[->+>-<<]<]>>>[>>]<<
>>-<< [>>+<<<[->+[>>]]>[-[-<+>]]<<]<  >>[>+[>>]]<<
>>>>

>>
>++++++++++>
>++++++++++>
>++++++++++>
>++++++++++>
>++++++++++>
>++++++++++>
>++++++++++>
>>>

>>
>+> >+> >+> >+> >+> >+> >+> //桁数分移動(桁識別用の1を加算)
>+[-<,----------[----------------------[---------------[<<]>>[[-<<+>>]>>]<+<]]>]<<
[<[-<<]<]>>[-<+>>>]<<<[-[-<+>]>++++++++++<<[->+>-<<]<]>>>[>>]<<
>>>>

,---------->+++++++++++[-<------>]<[[-]>+<]>[-<+>]<
>
,----------
[
  >+++++++++++[-<------>]<
  [[-]>+<]
  <[->+<]>>[-<-<+>>]+
  <[//NEqal
    -[+]
    >-<
  ]
  >
  [
    <<<<<< [<<] <<<<< [[-<+>[[>>]>]]<[->+<]<]< 
    >> >>>>>[>>]>>>
    >-
  ]
  <
  ,----------
]
<[-]
<<<<

[
  <[-><
    << << << << << << << // 桁数分表記
    <<<<<
    > 
    [[-<+>[[>>]>]]<[->+<]<]<
    >>
    >>>>>
    [>>]
    <
    
  ]
  <
]
>>[<++++++++++>[-<->>+<]>[-<+>]>]<<//Revert
[
  <[-><
    << << << << << << << // 桁数分表記
    <<<<<
    > 
    [[-<+>[[>>]>]]<[->+<]<]<
    >>
    >>>>>
    [>>]
    <
    
  ]
  <
]
>>[<++++++++++>[-<->>+<]>[-<+>]>]<<//Revert
[<<]<<<<<

[
  <[-><
    << << << << << << << // 桁数分表記
    <<<<<
    > 
    >>-<< [>>+<<<[->+[>>]]>[-[-<+>]]<<]<  >>[>+[>>]]<<
    >>
    >>>>>
    [>>]
    <
    
  ]
  <
]
>>[<++++++++++>[-<->>+<]>[-<+>]>]<<//Revert
[<<]<<<<<[<<]
>>
-[
  +[<[->+<]>>>]
]
<[>+[>>]<]<

>>>>>>>[>>]<<

[
  <[-><
    << << << << << << << // 桁数分表記
    <<<<<
    > 
    [[-<+>[[>>]>]]<[->+<]<]<  [[<<]<]>>>[>>]<<
    >>
    >>>>>
    [>>]
    <
    
  ]
  <
]
<<<<<

<+>[<<]>
>[<+>>[<<-<[<<]<]>]
>[->>]
>>>[<+>>>]
++++++++++[-<+++++>]<---
<<->>
[[+<<]>>[>>]<+<--]
<<[<<]>>[.>>]

あとがき

一応今回のコードはGithubに上げました。 github.com 質問とかあれば、ここにコメントするか、Twitterでリプもらえれば反応すると思います。今回の記事の内容じゃなくても全然大丈夫なので気軽に質問ください。 ~~ところで、こんな記事見る人いるんですかね…~~

三流プログラマの戯言

プログラミング初心者が気になったことを書き綴るだけ。主にc#

初めに

目次

注意

A - Password

B - Buffet

C - Maximal Value

D - Face Produces Unhappiness

あとがき