Go to Qiita Advent Calendar 2024 Top
LoginSignup
4
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@orisano(Nao Yonashiro)

POH7をErlangで解いた話

Last updated at Posted at 2015-12-10

タイトルの通りPOH7をErlangで全部解いたのでコードを公開しようと思った次第です。

Erlangで競技プログラミングっぽいことをすることが初めてでいろいろ戸惑いましたが
なんとか問題をすべて解くことができました。
paizaの環境ではErlangは起動に1.4秒程度かかるようで平均実行時間が1.5秒程度になりました。

追記(12月21日 01:45)
追加されていたando16, ando17を追加

コード上ではmodule名がando*になっていますが、paizaに提出する時はmainにしなければいけません。

コード

Ando2

ando2.erl
-module(ando2).
-export([main/1]).

main([_]) ->
  N = to_i(io:get_line("")),
  io:format("~p~n", [string:copies("Ann", N)]),
  init:stop().

to_i(S) ->
  {I, _} = string:to_integer(S),
  I.

"Ann"という文字列をN回繰り返すだけなのでstring:copiesを使うだけでお終いです。

Ando4

ando4.erl
-module(ando4).
-export([main/1]).

main([_]) ->
  A = to_i(io:get_line("")), 
  B = to_i(io:get_line("")), 
  io:format("~p~n", [A + B]),
  init:stop().

to_i(S) ->
  {I, _} = string:to_integer(S),
  I.

これはA + Bするだけですね。

Ando5

ando5.erl
-module(ando5).
-export([main/1]).

main([_]) ->
  NS = [io:get_line("") || _ <- lists:seq(1, 5)],
  YC = count(NS, "yes\n"),
  if
    YC > 2 -> io:format("yes~n");
    true -> io:format("no~n")
  end,
  init:stop().

count([], _) -> 0;
count([H|T], X) when H == X -> count(T, X) + 1;
count([_|T], X) -> count(T, X).

これはyesかnoという文字列が5回与えられて多い方を出力する問題です。
それと定数回処理を回したいときはどうするのがベストなのでしょうか。
(lists:seqを使って対処してる）
countなんて自作してますが何か良い方法があれば教えて下さい。
(書いてて気づいたのですが、length(lists:filter(ほげ))で終わりな気がします。。。)
(そもそもcount([X|T], X) -> count(T, X) + 1のほうが簡潔ですね)

Ando6

ando6.erl
-module(ando6).
-export([main/1]).

main([_]) ->
  N = to_i(io:get_line("")),
  S = string:join([to_s(X) || X <- lists:seq(N, 0, -1)], "\n"),
  io:format("~s!!~n", [S]),
  init:stop().

to_s(T) -> io_lib:format("~p", [T]).
to_i(S) ->
  {I, _} = string:to_integer(S),
  I.

これはカウントダウンして最後に!!をつける問題です。
to_sなんていう関数を作りましたがinteger_to_listがこれと同じ動きをしそうですね。
あまりにも無知。

Ando7

ando7.erl
-module(ando7).
-export([main/1]).

main([_]) ->
  [C1, P1] = [to_i(X) || X <- string:tokens(io:get_line(""), " ")],
  [C2, P2] = [to_i(X) || X <- string:tokens(io:get_line(""), " ")],
  if
    C1 * P2 > C2 * P1 -> io:format("1~n");
    true -> io:format("2~n")
  end,
  init:stop().

to_i(S) ->
  {I, _} = string:to_integer(S),
  I.

コストパフォーマンスが高いほうを出力する問題です。
splitはないのかと絶望していましたがErlangではstring:tokensなんですね。勉強になりました。
第3引数は複数のデリミタを指定することができるのでchars()でマッチしていて、
文字リテラル(? $から始まる一文字のatom)は使えないというところにハマりました。

Ando9

ando9.erl
-module(ando9).
-export([main/1]).

main([_]) ->
  N = to_i(io:get_line("")),
  SS = [string:strip(io:get_line(""), right, $\n) || _ <- lists:seq(1, N)],
  io:format("~p~n", [string:join(SS, "_")]),
  init:stop().

to_i(S) ->
  {I, _} = string:to_integer(S),
  I.

入力された文字列を_で結合して出力する問題です。
string:join
以上

Ando10

ando10.erl
-module(ando10).
-export([main/1]).

main([_]) ->
  io:format("~p~n", [fact(to_i(io:get_line("")))]),
  init:stop().

to_i(S) ->
  {I, _} = string:to_integer(S),
  I.

fact(0) -> 1;
fact(N) -> fact(N - 1) * N.

階乗を出力する問題です。
factを自分で定義するか、lists:foldl(fun(X,Acc) -> X * Acc end, 1, lists:seq(1, N))するかのどちらかですね。
前者の方がシンプルに書ける気がしたのでこちらで書きました。

Ando11

ando11.erl
-module(ando11).
-export([main/1]).

main([_]) ->
  N = to_i(io:get_line("")),
  NG = in_grid(N),
  M = to_i(io:get_line("")),
  MG = in_grid(M),
  {Y, X} = search(NG, MG),
  io:format("~p ~p~n", [Y, X]),
  init:stop().

in_grid(N) ->
  [[to_i(T) || T <- string:tokens(io:get_line(""), " ")] || _ <- lists:seq(1, N)].

search(NG, MG) ->
  N = length(NG),
  M = length(MG),
  [{X, Y}|_] = lists:dropwhile(fun({BX, BY}) -> not match(NG, MG, BX, BY) end, [{X + 1, Y + 1} || X <- lists:seq(0, N - M), Y <- lists:seq(0, N - M)]),
  {Y - 1, X - 1}.

match(NG, MG, X, Y) ->
  M = length(MG),
  MG == [lists:sublist(S, X, M) || S <- lists:sublist(NG, Y, M)].

to_i(S) ->
  {I, _} = string:to_integer(S),
  I.

模様付きの正方形の中から、別の模様付きの正方形を見つけて出現座標を出力する問題です。
取りうる座標をすべて列挙して、lists:dropwhileで先頭要素を取得する形です。
一致しているかはlists:sublistを用いて探す対象の正方形を切り出し、listのまま比較しました。
lists:sublistが1-indexedなところにハマりました。

Ando12

ando12.erl
-module(ando12).
-export([main/1]).

main([_]) ->
  [X, Y, Z, N] = [to_i(T) || T <- string:tokens(io:get_line(""), " ")],
  {XS, YS} = readCutting(N, [X], [Y]),
  io:format("~p~n", [lists:min([AX * AY || AX <- diffList(XS), AY <- diffList(YS)]) * Z]),
  init:stop().

diffList(L) ->
  {X, _} = lists:mapfoldl(fun(T, Acc) -> {T - Acc, T} end, 0, L),
  X.

readCutting(0, XS, YS) -> {lists:sort(XS), lists:sort(YS)};
readCutting(N, XS, YS) ->
  [D, A] = [to_i(T) || T <- string:tokens(io:get_line(""), " ")],
  if
    D == 0 -> readCutting(N - 1, [A|XS], YS);
    true -> readCutting(N - 1, XS, [A|YS])
  end.

to_i(S) ->
  {I, _} = string:to_integer(S),
  I.

X * Y * Zの直方体に対してY軸とX軸に対して並行に切断するクエリが飛んで来るので、
クエリを処理し終わったあとの直方体の最小の体積を出力する問題です。
この問題はZに関してはほとんど考えなくて構いません。X軸とY軸の切られた場所をソートして
差分をみてすべての組み合わせから最小を求めると終わりです。
（差分の最小同士を掛け合わせるだけで良さそうな気がしてきました）
ソートされたリストから差分のリストを作る上でlists:mapfoldlが非常に便利でした。

Ando13

ando13
-module(ando13).
-export([main/1]).

main([_]) ->
  N = to_i(io:get_line("")),
  MOD = pow(10, 9),
  {A, Two, Five} = lists:foldl(fun(X, {Prod, T2, T5}) ->
                                   {Y, C2} = divo(X, 2),
                                   {Z, C5} = divo(Y, 5),
                                   {(Prod * Z) rem MOD, T2 + C2, T5 + C5}
                               end, {1, 0, 0}, lists:seq(1, N)),
  io:format("~p~n", [lists:foldl(fun(X,Acc) -> (X * Acc) rem MOD end, A, lists:duplicate(Two - Five, 2))]),
  init:stop().

divo(X, N) -> divo(X, N, 0).
divo(X, N, C) when X rem N == 0 -> divo(X div N, N, C + 1);
divo(X, _, C) -> {X, C}.

pow(_, 0) -> 1;
pow(X, N) -> X * pow(X, N - 1).

to_i(S) ->
  {I, _} = string:to_integer(S),
  I.

Nの階乗の下の桁から連続する0を取り除いた下8桁を出力する問題です。
Nが大きいためまともに階乗を計算すると制限時間に間に合いません。
そこで下の桁から連続する0を取り除くという点と下8桁という点に注目します。
下の桁から連続する0を取り除くというのは10で割り切れるうちは10で割り続けると同義です。
10で割り続けながら階乗を計算していきます。計算途中でも下8桁以上は計算する必要がないので
10^9で剰余を取ることで下8桁のみを求めることができます。
10^9*10^9程度の小さい数字だとNが大きくてなり計算回数が増えても高速に解を求めることができます。

Ando16

ando16.erl
-module(ando16).
-export([main/1]).

main([_]) ->
  N = read_int(),
  _ = read_int(),
  X = [to_i(Token) || Token <- string:tokens(io:get_line(""), " ")],
  _ = read_int(),
  Y = [to_i(Token) || Token <- string:tokens(io:get_line(""), " ")],
  All = sets:from_list(lists:seq(1, N)),
  Have = sets:from_list(X),
  Sell = sets:from_list(Y),
  Need = sets:subtract(All, Have),
  Buy = sets:intersection(Sell, Need),
  BuySize = sets:size(Buy),
  if
    BuySize == 0 ->
      io:format("None~n");
    true ->
      io:format("~s~n", [string:join([integer_to_list(V) || V <- lists:sort(sets:to_list(Buy))], " ")])
  end,
  init:stop().

read_int() -> to_i(io:get_line("")).
to_i(S) -> element(1, string:to_integer(S)).

持っている本と中古で売っている本が与えられて、買うべき本を出力する問題です。
集合の演算を用いることで簡単に書くことができます。
すべての本の集合から持っている本の集合を引きます。これで持っていない本の集合を求めました。
売っている本と持っていない本の集合が買うべき本の集合であることがわかるのでそれを出力します。
ここでハマったのがsets:to_list(Set)が返すリストが昇順じゃない点です。辛い。

Ando17

ando17.erl
-module(ando17).
-import(string, [copies/2]).
-export([main/1]).

main([_]) ->
  N = to_i(io:get_line("")),
  M = to_i(io:get_line("")),
  io:format("~s~n", [string:substr(copies(string:concat(copies("R", N), copies("W", N)), 10), 1, M)]),
  init:stop().

to_i(S) -> element(1, string:to_integer(S)).

RをN個、WをN個交互に並べて合計の長さがMになった文字列を出力する問題です。
問題の制約が小さいことを利用して、RをN個、WをN個繰り返した文字列を10回繰り返し切り出すことで
この制約下では正しい答えを返すことができます。
初めて使うべきではないと言われている-importを使ったのですが、
小さい使い捨てのコードであれば使っても良いのかなと感じました。

終わりに

Erlang初心者が書いたコードなので間違っているところだったりアドバイスが有ればぜひお願いします。

4
3
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?